France Lasfargues
email: france.lasfargues@bnf.fr

Clément Oury
email: clement.oury@bnf.fr

Bert Wendland
email: bert.wendland@bnf.fr

Legal deposit of the French Web: harvesting strategies for a national domain

Keywords: H.3.3 [Information storage and retrieval]: Information search and retrieval -Information filtering, Query formulation, Relevance feedback, Retrieval models, Search process, Selection process Measurement, Documentation, Experimentation Web archiving-Internet legal deposit -French national

According to French Copyright Law voted on August 1 st , 2006, the Bibliothèque nationale de France ("BnF", or "the Library") is in charge of collecting and preserving the French Internet. The Library has established a "mixed model" of Web archiving, which combines broad crawls of the .fr domain, focused crawls and edeposits.

Thanks to its research partnership with the Internet Archive, BnF has performed four annual broad crawls since 2004. The last one has been made with noticeably different features: one of the most important was the use of the all-comprehensive list of the .fr domain names, given to BnF by the AFNIC ("Association française pour le nommage Internet en cooperation", the registry for the .fr) after an agreement was signed between both institutions in September 2007.

The technical choices made before and during a crawl have a decisive impact on the future shape of the collection. These decisions must therefore be taken according to the legal and intellectual frame within which the crawl is performed: for BnF, it is the five-centuries-old tradition of the legal deposit. To assess the consequences and the outcomes of the different technical solutions available, we propose to analyze the results of the BnF"s last crawl and to compare them to those of previous harvests. These studies also prove to be useful in our attempt to characterize the 2007 French Web.

THE FRENCH CONTEXT 1.1 Defining the scope of the legal deposit

On August 1 st , 2006, a new Copyright law was voted by the French Parliament. One of the titles of this law, long-expected by BnF, extended the legal deposit to the Internet. The legal deposit is the obligation for every publisher to send copies of his production to the Library. First established in 1537 for printed materials, the legal deposit has been extended through centuries to every new published form of intellectual creation, from engravings to software and video games. As the World Wide Web was becoming the favorite place to create and spread out knowledge and information, it was necessary to give French heritage institutions a legal frame to organize its preservation.

The law is not explicit on what the French domain of the Internet is, but a decree is expected to clarify this issue in a near future. In the meantime, the Library has forged its own doctrine of the online national domain, which is likely to be consistent with the decree whenever it will be enforced. In order to refine the scope of its Web archiving policy, BnF combined its five-centuries-old practice of legal deposit together with its more recent experience of Web harvesting technical challenges. Our approach therefore needed to be both pragmatic (that is, compliant with bulk harvesting exploratory tools) and consistent (with the French legal deposit tradition). This tradition is based on three criteria:

-Publication: documents to be collected are aimed at an audience and serve a public purpose, they should not fall in the fields of private or corporate internal communications;

-Media: all previous legal deposit dispositions were based on the physical existence of a media: prints, scores, photographs, tapes, disks, etc.;

-Territory: documents are to be published or distributed within the borders of the national territory.

In short, traditional legal deposit is applicable to any publication embedded in a media produced or distributed on French territory.

Unfortunately, none of these criteria is easily applicable to Web harvesting because websites:

-Tend to merge and mix public and private communications rather creatively; -Are not a media as such, but rather a platform where all existing media tend to migrate (we can find books, photographs, films, scores, etc. on the Web); -Cannot easily be localized on a specific territory, at least not on a very large scale.

Moreover, we cannot use the French language as selection criteria either, since our legal deposit applies regardless of the language of publication: BnF legal deposit collections include many items in foreign languages provided they are published, printed, or distributed in France. Likewise, we cannot expect our legal deposit strategy to focus on specific themes, authors or levels of publications. An important aspect of our legal deposit tradition is that collections should mirror the French society and culture in all its diversity regardless of the scientific value of the publications or their popularity. If we are to select, this is rather to sample than to choose. It is the next generations to decide what will be valuable one day, not the Library. In BnF stacks, unknown writers and dirty magazines stand side by side together with the Great thinkers and we expect the same philosophy to apply to our Web collections. Bulk harvesting represents a great opportunity to extend this approach at the scale of the Web. Last, our legal deposit tradition is both about content and formor media -, which means that BnF pays attention to build collections which reflect trends in publishing models: we try to grasp a great diversity of objects and formats representative of the practical conditions met by the people who use information.

As a result, we needed to find a definition for our national domain which would reflect the "spirit" of this tradition, yet remain flexible and easily applicable. Defining a French "focus" while allowing for flexibility was indeed the only way to facilitate exploratory harvesting methods on a large scale. Language, geography, names or topics having proved to be either irrelevant or too challenging to be used for scoping discrimination on a large scale, what was left as a possible starting point for our exploration of the national domain was therefore the use of our national Top Level domain, the .fr, as a core starting list for our exploration, to be combined with other strategies.Our online legal deposit doctrine, as we expect it to be clarified in the decree, was therefore defined as follows. We consider to be "French":

-As a core, any website registered within the .fr TLD or any other similar TLD referring to the French administrative territory (for instance, the .re for the French island of La Réunion); -Any website (possibly outside of .fr) whose producer is based on the French territory (this can usually be checked on the website or using DNS); -Any website (possibly outside of .fr) which can be proved to display contents produced on French territory (this last criterium is more challenging to check but leaves room for interpretation and negotiation to the Library and the Web producers).

Of course, none of these criteria is expected to be strictly met before we build our seed lists (this would forbid exploration, and would involve checking every website before crawl, which is simply not scalable). However they are aimed at serving as legal and intellectual framework in order to:

-Define and explain the general policy of our national Web archiving policy to the public, stakeholders and librarians involved in the project; -Clarify for ourselves the missions and directions we need to keep in mind when monitoring our crawls; -Provide explicit elements of decision when we need to find out whether a website is definitely in scope or out of scope. This should prove especially useful whenever the Library is being asked by a webmaster to stop crawling a particular website or even face a law suit: if the website does not meet any of the above criteria, then it shall be excluded from future crawls and from the collections. This approach of our national domain therefore reflects a compromise between our legal deposit tradition and the challenging characteristics of the Web. It is also a compromise between a totally open and absurd approach which could possibly lead us to consider the whole World Wide Web as potentially French and, on the contrary, a restrictive approach reduced to the sole .fr TLD while it is known to contain only a limited portion of the French websites. In short, it is aimed at providing both focus and flexibility.

Where we are for now

The Library is allowed to use various ways to collect the French Internet: "Mandated institutions may collect material from the Internet by using automatic techniques or by setting specific agreements and deposit procedures together with the producers" (Clause 41 II). In line with these dispositions, BnF defined a "mixed" model, which combines three strategies.

-Bulk harvesting of the French Internet. The goal is to collect at least the .fr domain on a yearly basis. These broad crawls allow the Library to archive snapshots of the French Web. It is the less expensive approach if we compare the costs of the harvest (machines and humans) and the retrieved amount of data. However, due to resources and tools limitations, it is not possible with such crawls to harvest the deep Web (very big websites, databases…). -Focused crawls of a restricted number of websites. These sites are discovered by a collaborative network of librarians and researchers, inside or outside the Library. Focused crawls are dedicated to big websites and to frequently modified websites. -E-deposits for a limited number of electronic publications.

The Library did not wait for the law to experiment crawling techniques. The Web archiving project began in 1999. A first event-based focused crawl was tested in 2002, when the Library harvested nearly 2 000 websites related to the national elections (presidential as well as parliamentary elections). This work was renewed two years later, for European and for local elections: BnF then collected 1 162 websites1 .

However, the technical means (hardware and software), the skills and the experience necessary to realize large-scale crawls of the French Internet were still lacking within the Library. This is the reason why BnF agreed on a partnership with the Internet Archive, a not for-profit foundation involved in world-wide Web archiving since 1996. On November 2004, both institutions signed a research agreement named « Research project: Selection of a National Domain for Web archiving ». Its goal was to assess several methods and tools to be applied to a national domain Web crawl. The agreement specified that the broad crawls necessary to test these tools and methods would be performed by Internet Archive, and that the data collected during these crawls would be delivered on storage racks to BnF.

The first broad crawl done in the frame of this agreement occurred at the end of 2004. Three other .fr broad crawls followed in 2005, 2006 and 2007 (this last crawl will last until 2009 thanks to an extension of the research agreement).

Smaller-scale crawls were also performeddirectly or notby BnF. Two focused crawls, on a limited number of websites (about 4 000), were completed by IA for the research project [START_REF] Illien | Web archiving at BnF[END_REF]. As of 2007, these websites have been harvested by BnF by its own means. Other thematic or event-based focused crawls were performed the same year, such as the websites related to the French national elections of 2007.

Up to now, BnF has thus performeddirectly or thanks to its partnership with IAfour broad crawls besides a large number of focused crawls. The Web archiving is not a project within the Library anymore instead it has become a daily activity and a permanent unit within the Library"s Legal Deposit Department.

As it is the best approach to face the challenge of collecting a growing number of digital objects on the Web, bulk harvesting is still considered to be the top priority.

However, bulk harvesting does not mean blind harvesting. Even when they try to discover a maximum of files on the Web, robots conform themselves to a set of rules and settings [START_REF] Masanès | Selection for Web Archives[END_REF]. The technical decisions made before, during and after the crawl have a decisive impact on the outcome of the harvest.

This paper describes the strategies that BnF has developed together with the Internet Archive in order to run large-scale crawls that could match this vision of the French national domain.

CRAWL DESIGN

What is the goal?

It seems unavoidable, when performing a broad crawl over hundreds of millions of files, to face a lot of technical issues. However, the first question one should answer before starting a crawl is not a technical one: what is the goal of this crawl? Answers will be different if they come from a corporate, a research or a heritage institution. A broad crawl will not be done the same way if the data is to be indexed (by a search engine), analyzed (for Web domains characterization, for example) or archived and displayed for the long-term.

On the other hand, it is necessary to take the technical limits into account when defining the goals of a broad crawl. That is the reason why a constant dialogue should be established between the librarians (in charge of defining the collection policy) and the engineers (in charge of performing the crawls). The methodology described in this section describes the meeting point of their respective concerns.

Broad crawls are done at BnF within the frame of legal deposit. This frame is not only a convenient one to address intellectual property protection issues. It also introduces Web archiving as the continuation of a long-lasting mission. Web archives collection policies should comply with those of previous publishing forms.

The automatic discovering of websites by robots is a way to match the "non-discriminatory" feature of the French legal deposit, to harvest the "best" (literature, scientific publishing) as well as the "worst" (from advertisings to pornography) of French publications. However, even robots are subject to bias. The hyperlink structure of the Web leads to discover and to harvest the most "cited" websitesfirst. Less popular websites should however not be forgotten by our archiving robot. To avoid such a bias, BnF signed on September 2007 an agreement with the AFNIC, a body responsible for the management of .fr and .re domains. According to the terms of the agreement, AFNIC shall give the complete list of domain names registered on the .fr and .re domains (currently more than one million domain names)twice a year. On the other hand, BnF shall guarantee the confidentiality of this very valuable data.

The goal of a large domain crawl is therefore to collect a representative sample of the national domain and to illustrate the French production at the time of the harvest. This sample is often designated as a snapshota way to record and to freeze a moving space. As it is not possible to harvest everything, we prefer harvesting few documents on every website rather than collecting entirely few websites, at the expense of the others. This is why we did not experiment ways to crawl deeper into the "most important" websites, as the National Library of Australia did by putting a high priority on government and academic sites (a list of these sites had been established by the librarians [START_REF] Koerbin | Report on the crawl and Harvest of the Whole Australian Web Domain Undertaken during June and July 2005[END_REF]). It was also not necessary, as our broad crawls are complemented by focused crawls.

On the other hand, the Web is likely to be quickly affected by technological evolutions. New publication forms appear and spread within months. The broad crawl should reflect those evolutions. One of our goals, as a legal deposit institution, is to illustrate the new forms of publishing and therefore to make sure that the robot is able to harvest these documents. This is why we paid more attention to blogs and personal websites in 2006 while we focused on videos in 2007 (see below).

According to the pre-defined goals, it is possible to shape the future collection before, and during the crawl. Two important elements decided before the beginning of the harvest play a major part in the constitution of future collections: the design of the seed list, and the crawl settings.

The seed list

The crawler begins its tasks with a list of URLs called the seed list. The seeds are the doors giving access to the websites; that is why the quality of the harvest depends for a large part on the quality of the seed list.

As our partner for performing our broad crawl remained the same for four years, it was possible to enrich the seed list progressively. Different sources of seeds were added year after year. A list of valid URLs was created from those results, so that "domainname.fr" became either "http://www.domainname.fr" or "http://domainname.fr" if the www version did not answer.

Seeds with no DNS were included and randomized in the seed list.

2 Alexa Internet is a for-profit company that crawls the Web to provide data for a browser toolbar (plug-in) offering data about sites being viewed, and based on data gathered from other users, suggestions of related pages that might also be of interest. It provides its crawl archives to Internet Archives since 1996 [START_REF] Kimpton | Year by Year: From an Archive of the Internet to an Archive on the Internet[END_REF].

We checked how many domain names listed in the AFNIC registry were also available in our web archives (and especially in our 2006 broad crawl collection). It was quite a surprise for us to discover that only 30% of the AFNIC domains were available within our collection. This is probably related to the significant increase of the .fr domain size. The .fr has been steadily increasing since 2004, thanks to the successive easing off of the .fr attribution rules.The major one was the opening of the TLD to individuals in June 2006 (only administrations and private societies were allowed to own a .fr domain name before this date):the .fr grew up to63% in one year. This must be related to the positive image of a ccTLD on Internet users. Individuals represent for now 30% of the registered .fr domains, and 50% of new registrations [START_REF]French Domain Name Industry report[END_REF]. This phenomenon might also be partly due to the presence, in the AFNIC list, of domain names that were not or were poorly-linked to other websites, and had not been discovered by robots the previous years.

Crawler settings

The That is why they have a great impact on the collection, and why the robot should be configured according to the purposes of the crawl.

Scope

The scope given to the crawler defines which discovered URLs should be included in the harvest and which should be discarded. However, by following the redirected links our purpose was to to harvest domains other than .fr and .re. It was a way of adopting a flexible scope. A more exploratory approach would probably have led us to collectmore foreign websites: it would cause legal (BnF would have been out of the frame of the legal deposit) and economic problems: collecting non-relevant (according to our mission) websites takes up resources that would be better used harvesting surely French sites. Focusing on .fr was therefore a pragmatic choice. Moreover, as the .fr is dramatically growing, we can hope it will represent a larger part of the French Web year after year. On the other hand, we may experiment in the future new ways to discover French sites out of the .fr domain, for example by using automatic DNS (Geo-location) lookup.

Crawling priorities

Every URL that is considered to be in the scope of the crawl is placed in the "queue" of the crawler, that is in the list of files waiting to be crawled. As the robot will probably not be able, to harvest all the URLs it finds on its way when performing a broad crawl, the management of such a queue, and the crawling priorities given to the crawler, are key issues.

A first major decision was to choose between a "per-domain" and a "per-host" approach. With the per-host approach, used for the previous broad crawls, the URLs in the queue waiting to be crawled are grouped per hosts, and each host is treated separately. This setting leads to crawl more websites with several hosts. Commercial platforms hosting blogs or personal pages as different hosts take a lot of space within the collection. With a per-domain approach, however, these websites are treated as a single entity.

For the 2007 crawl we decided to adopt a per-domain approach.

The main reason was to comply with the use of the AFNIC list, which handles only domains. As a legal deposit institution, we also wanted to give every domain the same "chance" to be harvested. Moreover, as the 2007 seed list was much bigger than the previous one, and as the amount of data to be retrieved by IA was not increasing accordingly (see below, 2.5), we feared we would obtain globally a lesser depth from the crawl. Therefore we did not want to give too big an importance to commercial or institutional websites, that often have several hosts, and could be better harvested with focused crawls.

Big domain names like free.fr, skyblog.fr, orange.fr had to be managed as all other domains at the beginning of the crawl. The decision of a special treatment for these websites was postponed: it seemed easier to make the relevant choices during the crawl, when analyzing the reports which were to be sent by IA engineers.

It is also to avoid the over-representation of big websites that we fixed a maximum "budget" for each site: The robot was forbidden to harvest more than 10 000 URLs from the same domain. This did not mean that the crawler would be definitively stopped when this limit would be reached. The robot could be allowed to run over it if the total budget of the crawl would have not been spent.

At last, to ensure that the robot would have enough resources to harvest the entire seed list, we chose to lower the "replenishamount": each "thread" of the robot received the order to harvest, when connecting to a seed, the 100 first URLs it discovered within the corresponding domain, and then to go further to another seed. It would come back to this seed after having finished harvesting the 100 first URLs of each seed.

This approach is a mid-term one between the breadth-first approach described in [START_REF] Najork | Breadth-First Search Crawling Yields High-Quality Pages[END_REF] and [START_REF] Baeza-Yates | Crawling a country: Better Strategies than BreadthFirst for Web Page Ordering[END_REF] which is intended to collect as many different websites as possible, and a pure archiving approach that would lead to crawl deeply into one site before harvesting the next one.

Making those decisions represented a risk for the Library. In fact, the collection could be very different from the one obtained the previous years. However, it was very important for us to experiment this way of collecting, in order to explore new ways to match the needs of our legal deposit mission.

Other settings

The per-domain approach we adopted had a shortcoming: it was not possible for the robot to detect automatically the second level domains (SLD). In our case, the second level domains are specialized sub-parts of the .fr. They are either "second level sector names" designed to identify an industry or a regulated sector (such as .aeroport.fr for airports, or .gouv.fr for governmental websites) or "second level descriptive domains" designed to identify an activity or title of some kind (for example, .asso.fr for federations or .tm.fr for holders of brands). Without any specific setting, different websites hosted on the same second-level domains would have been considered by the robot as the same entity and wouldn"t hav received the same budget. To avoid this problem, we gave the robot the entire list of domains hosted on SLDs (also provided to BnF by the AFNIC) with the instruction to treat them as individual websites.

Special attention was paid to content which was embedded in a page but hosted on a different domain than the one of the page itself. The robot was allowed to follow up to three "max-transhops", that is links embedded in Web pages. This setting was necessary to harvest a great number of video files, which was a important goal for this crawl.

Indeed we tried to find additional solutions for harvesting video files. The number of video is steadily increasing on the Web, but it is challenging for robots to collect them. The problems of harvesting video files is related to their size, and to their broadcasting mode (see [START_REF] Ashenfelder | Web Harvesting and Streaming Media[END_REF] and [START_REF] Baly | Archiving Streaming Media on the Web, Proof of concept and Firsts Results[END_REF] for an analysis of the difficulties to collect streaming media). The lack of video files, because of crawler technical limitations, would have been contradictory with our goal of archiving a "representative" image of the Web. We decided to concentrate our efforts on the two major video-broadcasting platforms used by French netsurfers: YouTube [START_REF] Youtube | YouTube -Broadcast Yourself[END_REF] and its French equivalent, Dailymotion [9]. We asked IA engineers to study Dailymotion technical architecture (they had already studied the one of YouTube very well) and to modify Heritrix scripts in order to allow the crawler to collect video files on these websites.

Robots exclusion protocol

The 2006 Copyright law allows the Library to disobey the robots exclusion protocol (REP): "[Producers or publishers] shall not use codes or access restriction to prevent mandated institutions from harvesting their websites" 6 . That is the reason why BnF usually does not respect the robots.txt when performing in-house focused crawls. Robots exclusions are indeed frequently used by webmasters to prevent crawler from collecting pages that are not supposed to be indexed: images directories or CSS pages. Yet these documents can be critical for archiving crawlers, as they are necessary to display the archived Web pages in their original formin the future.

However, BnF decided to obey robots.txt rules for its 2007 .fr crawl, as it did for its previous broad crawls. The focused crawl experiences had shown that webmasters might not like it when they discover that a robot is crawling through their site, violating their own robots.txt rules. For example a French blogger, crawled by BnF sent furious e-mails to the Library and generated a crawler-trap to slow down BnF robot, and posted a message on his blog to encourage other webmasters to create their own crawler traps 7 ! In fact, Web pages forbidden by robots.txt files frequently hold crawler traps. Moreover, exclusion rules are sometimes intended to prevent crawlers from searching URLs that could overload websites (e.g. submissions to a forum). Technical problems as well as relationship difficulties with website producers can be easily managed during a focused crawl, when it is possible to monitor the harvest of each individual website. But BnF did not want to manage them on a large scale, and above all did not want the IA engineers to be overwhelmed by protests of angry French webmasters (IA"s policy is to respect robots.txt exclusions anyway).

Most of the institutions performing broad crawls through the Web, especially national domain harvest, chose to respect the robots exclusion [START_REF] Koerbin | Report on the crawl and Harvest of the Whole Australian Web Domain Undertaken during June and July 2005[END_REF][START_REF] Gomes | Characterizing a National Community Web[END_REF]. Netarchive.dk, the virtual center (from the Royal Library and the State and University Library) in charge of archiving the Danish domain, prefers to overlook robots.txt, as it is mostly used for the "truly important net sites" [3]8 . In fact, websites hosting very valuable content, such as newspapers or political parties websites, are those using robots.txt exclusions most commonly [START_REF] Sun | A large-scale study of robots[END_REF].

Working schedule with Internet Archive

For the 2007 broad crawl, IA and BnF agreed on the targeted size of the collection. An amount of 300 000 000 URLs seemed reasonable to match the requirements of the crawl. If needed, IA could decide an up to 10-15% extension.

Both institutions agreed also on the day-to-day organization of the crawl. The scope and the major settings of the harvest should be discussed between IA and BnF, and decided by the Library. IA engineers should monitor the crawling machines, and reports should be sent twice a week to BnF (see below). The harvest should be terminated before the end of the year, and the data should be indexed (for Wayback Machine access and NutchWAX access) in the first months of 2008. The archives should then be sent on their storage rack to the Library 9 . Two IA engineers should also come to Paris to help the Library install the racks, advise BnF team and insure the quality of the collection.

CRAWLER AT WORK

Testcrawls

Before running a crawl, test crawls must be done in order to experiment robot and machine reactions and to anticipate problems. Thesetasks are actually the most important part of the quality assurance process for a crawl, along with monitoring the robots during the crawl (see 3.2) and collection characterization after the harvest (see section 4). This methodology was used for our four broad crawls.

The main task before the beginning of the crawl was to merge the different seed lists and to test them, as previously explained. Another critical step was to performthe "test crawl": the robot was launched on the seed list, to parse it and to discover a large number of URLs. The idea is not to run the crawl from the beginning to the end, but to perform it during enough time to identify non-relevant domain names, or URLs likely to be dangerous for the crawl.

For example, URLs sending a "404 error" code were discarded. Moreover, a lot of domain names that redirected to a small number of common hosts (in most cases registrars or domain squatters 10 ), were removed from the crawl. Domain names used for domain farming ( i.e. use of multiple domain names corresponding to one single IP address, in order to increase the PageRank of a website) were also identified.

IA / BnF relationship during the crawl

The broad crawl was launched on October 11, 2007 and was definitively terminated on November 29 (that is after the "patchcrawl"). During the crawl, IA/ BnF relationship was based on the analysis of the "frontier report". This report lists all domains in the queue, showing the number of URLs already harvested for each of them, the amount of budget expended and the URLs to be crawled. The purpose of this work was to complete the traditional expertise of IA engineers in this area with the BnF team knowledge of French seeds. This work was conducted at BnF by a librarian and an engineer.

Special attention was paid to domains reaching the maximum "budget" of 10 000 URLs. We took this number as a threshold over which we should check if the collected data was relevant or not. Non-relevant data is not, in our definition, documents of poor scientific value, but redundant files generated by pathological websites features. For example, robot traps (due to calendars or javascripts) created an infinite number of URLs for the same Web pages. Mirror websites are also a problem, as several domains host the same content under different names. In most cases, these domains were discarded.

We identified the main websites using domain farming and we excluded them. Online tests were also processed to identify which character strings corresponded to calendars, to filter them and to prevent them from generating robot traps.

The goal of this weekly control was not to ensure a 100% quality crawlit was a broad crawl anyway. It was to manage the biggest queues as best as possible and to prevent the crawler from wasting too much time and resources.

"Patch-crawl"

After 3 weeks of non-stop 24 hour crawling, IA engineers decided to stop the crawl. They launched a QA analysis on the retrieved data, to identify the domains for which the robot had not reached the fourth level of depth (that is, three hops from the seed page). These domains were crawled again (as a "patch-crawl"), when possible.

Another patch crawl was launched to retrieve video files identified during the harvest but not downloaded for some technical reasons (problems of files hosted on different domains…).

CRAWL OUTCOMES

Several analyses of the harvested collection were conducted after the crawl. The IA engineers who came to Paris to assist us when we installed our racks were very helpful. The first goal of this range of analyses was to make a quality control of the delivered data. We also wanted to characterize, our collections on a large scale,: what different kinds of documents were actually in the racks, what were the shape and the depth of the harvested websites… The goal was thus to quantify and to qualify our 2007 collection. At last, analyzing the outcomes of the 2007 broad crawl, and comparing them to those of previous crawls (especially the 2006 crawl), was necessary to assess the impacts of the new crawl settings and to decide if they were compliant with our legal deposit mission. The growth of the number of harvested domains was predictable, due to the dramatic increase of the seed list. Collaboration with AFNIC allowed the Library to discover and harvest six times the number of .fr domains collected in 2006.

Key-figures

On the other hand, fewer hosts were crawled in 2007 than in 2006, in spite of the growing number of URLs harvested by IA. This is very likely due to the per-domain approach of our last broad crawl.

The number of URLs per domain or per host is a convenient way to evaluate the "mean depth" of a crawl. However, this figure hides too many differences between websites to be significant: more detailed figures are examined in 4.6.

Distribution per MIME-type

The But if we cannot fully trust the MIME type of an individual file, the broad repartition given for hundreds of millions of documents is most likely to be reliable. MIME types evolution may be viewed as a way to analyze the changes and trends of the Web, on a large scale. We can observe for example, from 2004 to 2007, adecreasing use of the GIF format (the percentage of GIF images is almost divided in two in four years), in favor of JPEG and of the PNG open format 12 . The rate of XML documents is multiplied by five in the same time. The augmentation of XML files on the Web is even more obvious when we look at the number of harvested documents: from 88 000 in 2004 to one million in 2007. This is probably partly due to the growing use of RSS feeds (the correct MIME type for a RSS file is "application/rss", but "application/xml" or even "text/xml" are often used instead).

Another file format whose rating within the broad crawls collections is increasing is application/x-shockwave-flash. Two reasons could explain this augmentation: the increasing popularity of the flash format on the Web, or the better ability of Heritrix to harvest such files.

MIME

Video files

Adding the four most used video formats (Windows media video, Quicktime, Flash video and MPEG video) makes a total of 40 000 harvested video files in 2004, against 120 000 four years later (that is 0,04% of the collection). We notice the decline of the MPEG video format, in favor of flash. In 2006 Heritrix harvested only one hundred flash video files. One year later, the script allowing our crawler to harvest content hosted on video broadcasting platforms was implemented: Heritrix collected thirty thousand documents. Our decision to focus on the video files harvesting had reached its goals: even through most of our archives contains video "holes", we did get a bigger sample of videos in 2007. It is not possible, when analyzing what was not crawled, to use the MIME types of the files, as they were not sent by the server. However, we may use the file extension of the requested URLs. Nearly 40% of these files are images 14 . Many webmasters probably wanted to prevent robots from crawling these files because they were not to be indexed by search engines. This supposition is confirmed by the way our robot discovered these files: half of them (7 378 578)were found when following an embedded link.

MIME

Thus obeying robots.txt kept us from harvesting very relevant data, unnecessary for search engines robots but very useful for our archiving robot. In many cases, REP even prevented us from accessing a whole site: more than 150 000 URL used as seeds were protected by robots.txt.

Crawling depth

To assess the depth of the crawl, we may calculate the number of URLs per .fr domains. This can be caused by persistent server unavailability during the crawl. However, we made several "hand-made" tests, i.e. we clicked on a dozen of domain names under the threshold of 10 URLs, to discover what was available online. These tests showed us that these websites were empty (their owner bought them to ensure that they will not be used, but do not use them) or that they were used for link-farming.

Number of URLs

These figures were very different from those from the previous broad crawl. -The number of domains where more than 10 000 URLs were archived is divided by 10 between the two crawls. This is the consequence of the "budget" restriction to 10 000 URLs; it is also probably due to the "per-domain" approach: domains containing several hosts are under-represented.

Number of URLs

-On the other hand, this approach allowed deeper crawling of many more "small" or "medium" domains, between 100 and 10000 URLs.

These figures are probably biased by robots traps, but we currently do not know to which extent. Other quality controls, mainly visual control of individual websites, should be necessary to assess it. However it may be, these figures seem satisfying in light with our legal deposit tradition and with initial goals for this crawl: ensuring that every .fr website is included in the collection, having a strong commitment to the harvest of small and mediumsize sites, possibly at the expense of bigger websites.

Big websites

We may focus on the biggest websites to refine our analysis of websites depth. The objective is to assess the reason why these sites have been more crawled than othersis it only because they are actually bigger online?

Different information were extracted from he crawl index (CDX): the list of the 50 biggest domains (from 2005 to 2007); and the list of the 1000 biggest domains in 2006 and 2007.

Domains

There are again huge discrepancies between the different collections. The first one is the size of big domains: only three domains have more than 1 000 000 URLs in the 2007 collection, to [START_REF] Youtube | YouTube -Broadcast Yourself[END_REF] In the 2007 collection, the most ranked domains are mostly second level domains, for which special settings were applied. On the other hand, we discover two kinds of websites in the 2005 and 2006 crawls: platforms hosting blogs and personal websites (free.fr, sportblog.fr) favoured by the per-host approach, and commercial websites advertising on numerous pages (e.g. promovacances.fr, an online travel agency). The 2005 broad crawl shows also several academic websites (16 on the 50 biggest domains), such as jussieu.fr or cnrs.fr. These websites almost disappeared in the 50-biggest list the following years. This large representation of commercial websites explains the number of general top level domains within the 50 biggest domains: even for the 2007 collection, only 32% are in .fr. As it is, this collection reflects the French Web of 2007: mainly a space for business, services and social relationships. The special attention paid to second level domains during the 2007 harvest allowed the Library to crawl amounts of data slightly inferiors yet similar to those of the 2006 harvest. The most significant exception is the .gouv.fr second level domain, falling from 2.3 millions to 500 000 URLs. A way to explain this feature is the common use of third and even fourth level domains by governmental websites (for example www.rhone.pref.gouv.fr, or www.auvergne.culture.gouv.fr).

Second Level Domains

Focusing on video files brought a better harvest of videobroadcasting websites. Dailymotion entered the 10 highest-ranked domains (only 30 000 URLs were harvested on this domain in 2006). The number of files collected on YouTube doubled.

CONCLUSION

There is no single way to harvest a national domain. A range of technical choices (done before and during the crawl, and even after if URLs are to be discarded) shapes the collection. Even at a very large scale, collection policy applies. It is necessary to identify these choices, and to assess their consequences, in order to perform a domain crawl complying with its legal frame and its goals.

The French legal deposit mission traditionally uses three criteria to decide if a document is in or out of the scope of the collection: it should be made available to a public, on a specific form, within the borders of the French territory. All those should be adapted to the new features of the Web, and should be taken into account when performing a broad crawl. The goal of harvesting the "French" Web explains the focus on the .fr. This is not really satisfying if we think that 50 to 60% of French websites are outside the .fr, but it is for now a pragmatic and economic choice: not all the French content is on .fr but anything on .fr is French. Moreover, this focus was flexible as the robot was allowed to follow redirects from .fr to other TLDs. At last, the .fr domain is rapidly growing with the easing offof the .fr domain attribution rules, and it will hopefully soon represent a larger part of the French domain. She should hope that this trend will not be stopped by ICANN"s new ccTLD creation rules.

Focusing on .fr is also very convenient, as we are sure to be able to harvest all-comprehensively this top-level domain, thanks to the agreement with the AFNIC. This is a way to match the second major principle of our legal deposit tradition: collecting the whole intellectual production of the country, whatever its "quality" or "value", as soon as it is made available to the public. Starting from a very large number of seeds is the guarantee not to neglect poor-linked or unpopular websites. These "non-discriminatory" principles do not mismatch with another feature of the legal deposit: the will to encompass every emerging form of publication. The Library got used to handle different supports: texts, images, sounds or videos. With Web archiving, it is not conceivable anymore to treat them separately, as they are linked elements on the same network. However, it may be necessary to find appropriate solutions for the different types of media: collecting, indexing, preserving and giving access to textual, audiovisual or interactive files do not always raise the same issues. Some questions still remain : it is for example hard to say, up to now, if an approach focusing only on domains is better than handling each host separately, to get a representative "snapshot" of the French Web. Further analyses should be made to answer such a question and BnF would be most interested to hear about international reports on this topic. The problem, at last, is how to define a website, as this intellectual entity often does not match with the technical hosting. If we define a website as a domain name, a per-domain approach is to be adopted, as it leads to a better crawl of small or medium websites. But if we define a website as the intellectual entity created by the same author or the same editor (one or several persons, a public or private institution), sites and domains do not match anymore. Several, or even a huge number of websites can indeed be hosted under the same domain name, such as blogs hosted on a commercial platform. These sitesalthough relevantbecame underrepresented with the strategy we used in 2007: for example, the numerous personal pages of free.fr harvested in 2006 all but disappeared a year latter. To avoid this problem, it might be possible, for future broad crawls, to adopt specific approaches for some very popular platforms hosting many personal websites or blogs, as we took care of video broadcasting platforms in 2007.

These decisions indicate some improvements we could target for the Heritrix crawler. Better abilities to parse and harvest complex file formats are one of the most necessary -Heritrix already showed itself very configurable in this perspective. Three other features are already developed in the frame of the "Smart Crawler" project, supported by IIPC, IA, the Library of Congress, the British Library and BnF, whose goal is to enhance Heritrix robot. The first one is to avoid harvesting content that has not changed since the last crawl: this deduplication feature would lead to save computing resources and storage and thus to crawl deeper the websites. The second one is to allow the robot to give priorities to some URLs within the queue. It would be very useful to mix an all-selecting approach (at the beginning of the crawl) with better automatic crawl monitoring capacities. The third enhancement, automatic recognition of the websites change frequency, would also allow the robot to identify which sites should receive special attention. This would lead us, for example, to choose broad crawl dates and frequency accordingly, or to perform focused crawls on the most frequently changing sites.

In fact, if broad crawls are supposed to harvest every website once or twice a year, with a medium depth, we should define the goal of our focused crawls accordingly: focused crawls should be primarily intended to archive big and deep websites; non .fr French websites, or/and frequently changing websitesto archive them as best as possible, as even focused crawls are often insufficient to completely harvest huge websites, and to collect documents on the hidden Web. However it may be, we should remember that snapshots are only oneif the most economic one way to collect French digital memory, and that every decision on this matter should take into account the other archiving methods of a mixed strategy.

- 2004 :Figure 1 :

 20041 Figure 1: DNS responses of AFNIC domain names

Figure 2 :

 2 Figure 2: .fr domain size evolution 3

Figure 3 :

 3 Figure 3: seed list size evolution from 2006 to 2007.

Figure 5 :

 5 Figure 5: crawler settings, from 2004 to 2007

Figure 12 :

 12 Figure 12: number of URLs per .fr domains, 2007 broad crawl

Figure 13 :

 13 Figure 13: number of URLs per .fr domains, 2006 broad crawl

Figure 15 :

 15 Figure 15: evolution of some second level domains, from 2006 to 2007.

  harvest was made by Heritrix, the open-source archival quality Web crawler developed by Internet Archive with contributions from the members of the IIPC Consortium (especially Nordic national libraries) [11 and 21] 5 . It is used for the BnF broad crawls since 2004 and for its focused crawls since 2006.

	As it is highly configurable, Heritrix allows modifying a large
	number of settings, including scope, crawling priorities, filters,
	robot politeness…
	These settings tell the crawler what it should harvest, and how.

  Even if we outline that the political websites are not fully representatives of the whole French Web (the wide use of the .org by parties and trade unions websites, for example, leads to an over-representation of this TLD), we should recognize that the .fr is not used by the majority of French websites.

		TLD	URLs	%
		.fr	22938947	36.11%
		.com	18373574	28.93%
		.org	15955225	25.12%
		.net	3690655	5.81%
		.de	882656	1.39%
		.info	733634	1.16%
		.eu	257769	0.41%
		.tv	110944	0.17%
		.us	106753	0.17%
		.re	99012	0.16%
		other TLDs 368148	0.58%
		Figure 4: Number of URLs per TLD, 2007 elections focused
		crawl
	BnF crawl scope hence includes every website in every domain
	name belonging to:
	-	The .fr TLD
	-	The .re TLD

-

Any other domain the crawler comes across because it has been redirected from a .fr or a .re domain (398 548 redirections from AFNIC domain names were noticed during the test crawl). The crawler should take everything that is part of http://fr.yahoo.com because http://yahoo.fr redirects to http://fr.yahoo.com. However, in such a case, the crawler should remain on the same host. So, the crawler should take everything that is part of http://fr.yahoo.com but not of http://de.yahoo.com or even http://fr.news.yahoo.com.

This scope seems very large on the one handit includes more than one million domainsand restrictive on the other hand, as the French Web is not only hosted on .fr domains. A report published by the AFNIC quotes that less than 30% of French websites are hosted on .fr

[START_REF]French Domain Name Industry report[END_REF]

. This figure is confirmed by our analysis of the 2007 election sites collection. Only 36 % of the URLs from this collection proved to behosted on the .fr domain.

  MIME type report of the 2007 broad crawl shows a total of 1604 different types. It was not a surprise to notice that one MIME typeonly, text/html, represents two thirds of the harvested files. Moreover, 97% of the downloaded URLs have one of the five most used MIME types: HTML, JPEG, GIF, PNG and PDF.If one looks at the MIME types of the documents harvested during the 2007 broad crawl, one could think that the French Web of 2007 mostly consisted of text and images! We should however be very cautious with these figures. We must take into account the technical limitations of therobot. The crawler is not able to parse and to harvest every file format it discovers on the Web, even if its performances are continuously improved. Complex file formats are under-represented or simply absent from the collection.Another good reason for being cautious is that the MIME type information used for our calculation is the one that is sent by the server. It is not really reliable. Sometimes, the server even sends a MIME type that does not exist (we discovered a surprising "application/x-something" in our collection). Out of these 1604 different MIME types, 1400 are associated with less than 500 files we can deduce that these types are badly specified.This problem seems to be more critical year after year. The 2004 broad crawl URLs had a total of 554 different MIME types; this figure turned to 1024 in 2006 and to 1604 in 2007.

	MIME Type	URLs	%
	text/html	229 257 942	67.96
	image/jpeg	64 222 287	19.04
	image/gif	25 376 262	7.52
	image/png	3 955 885	1.17
	application/pdf	3 955 463	1.17
	text/plain	2 256 759	0.67
	application/x-shockwave-flash 1 594 342	0.47
	text/css	1 432 809	0.42
	application/x-javascript	1 415 230	0.42
	application/xml	1 083 991	0.32
	other	2 771 213	0.82
	Figure 7: the ten most-ranked 2007 broad crawl MIME types 11

  It was not a surprise either to discover that three-quarters of the crawled documents belonged to the .fr Top Level Domain (we can add to this figure the .re domain, which is also managed by AFNIC). Figure10proves however that it is possible, with the settings we chose, to start from a .fr seed list and to exceed its borders. The two types of TLDs also present in the collection are general and country codes top level domains. Most of the sites hosted under general Top Level Domains (.com, .net, .org, .info) are probably produced by French webmasters. The country code TLDs ranked in the figure10belongs to French-speaking countries (Belgium and Switzerland) or to France"s neighbours with whom France has its main business relationships (Germany, United Kingdom): the same phenomena was noticed for Spain in[START_REF] Baeza-Yates | Characteristics of the Web of Spain[END_REF]. The .eu domain stands for Europe.The 2005 and 2006 collections, shaped with similar settings (seed list as well as crawl settings) show a predominance of general TLDs over the .fr. This feature may be explained by the large number of domains, not-included in the seed list, which had been "touched" by the robot (that is where only one URL, linked to an in-scope URL, has been crawled). A lot of links to .com or .net domains were available on .fr pages, and slightly collected for this reason. They represent a large percentage of domains available within the 2005 and 2006 collection, but not in the 2007 broad crawl, because of the significant increase of the seed list size13 .In 2007, robots Exclusion Protocol prevented us from archiving 15 million files, i.e. 4.5% of the discovered filesand obviously prevented us from archiving all the documents the robot could have discovered starting from these files. These figures are quite inferior to those of the 2006 broad crawl, when robots.txt files blocked the downloading of 6% of the discovered documents. It is difficult to interpret these rates, as they are in contradiction with the latest studies on this protocol, which identify a growing use of the robots.txt [for example 23].

	TLD	% of domains,	% of domains,	% of domains,	Type		2004	2005	2006	2007
		2005	2006	2007	video/x-ms-wmv 4 408 7 705 33 936 39 218
	com	44,59%	42,78%	17,10%	video/quicktime	22 020 26 687 39 073 36 294
	fr	26,86%	34,28%	74,55%	application/x-flv 0	0	104	31 556
	net	5,37%	5,95%	2,06%	video/mpeg		11 408 17 304 28 413 14 992
	org	4,39%	4,69%	1,46%	Total		39 840 53 701 103 532 124 067
	Figure 11: percentage of domains per TLD (restricted to .com, .fr, .net and .org), from 2005 to 2007.	Figure 9: evolution of video files MIME types from 2004 to 2007
					4.4 Distribution per TLD
	4.5 Robots.txt
					TLD	Number of URLs %
					fr	259 869 452	77.12
					com	59 843 624	17.76
					net	4 951 932	1.47
					org	3 171 196	0.94
					de	2 808 359	0.83
					eu	993 546	0.29
					info	900 544	0.27
					be	660 834	0.20
					ch	461 021	0.14
					uk	434 315	0.13
					re	381 746	0.11
					other TLDs 2 471 064	0.73
					Figure 10: Number of URLs per TLD, 2007 broad crawl
					These figures are quite similar to those obtained for the previous
					collections, from 2004 to 2006. Note however the progressive fall
					of the .biz (which was in the 10 higher-ranked TLDs the years
					before), and the sudden appearance of the .eu.
					We notice however very different repartitions if we look at the
					number of domains hosted in a specific TLD.

  in the 2006 collectionwe recognize the features identified in the previous section, and the same reasons may explain them. The content of the 50 biggest site list is also very different: only 20% of the 50 biggest domains of the 2007 broad crawls are present in its equivalent for 2006.

	The 2006 biggest website (free.fr), which was holding more than
	seven millions URLs, "weighs" only 40 000 URLs in 2007!
	Domain name,	Number of	Domain name,	Number
	2007	URLs	2006	of URLs
	asso.fr	3 984 821	free.fr	7 405 987
	com.fr	1 760 957	amiz.fr	5 194 030
	tm.fr	1 270 244	asso.fr	4 036 224
	gouv.fr	534 599	1rencontre.fr	3 482 657
	cci.fr	495 753	sportblog.fr	2 547 231
	co.uk	408 881	gouv.fr	2 360 960
	nom.fr	179 256	promovacances.fr 2 113 314
	presse.fr	144 207	football.fr	1 895 302
	dailymotion.com 108 222	mbpro.fr	1 885 549
	notaires.fr	102 018	com.fr	1 856 720
	Figure 14: the 10 biggest domains, from 2005 to 2007.

The crawler used for the

and 2004 elections was HTTrack[START_REF] Httrack | HTTrack Website Copier[END_REF]. See[START_REF] Masanès | Towards continuous Web Archiving: First results and an agenda for the future[END_REF] for more information on these two crawls.

The International Internet Preservation Consortium was founded in 2003 by 12 institutions (Internet Archive and several national libraries) to find common solutions in order to archive and ensure a long-term access to electronic publications on the Web. Since 2007, the membership is open to new institutions. See[START_REF]IIPC. International internet preservation consortium[END_REF] for more information on the Consortium goals and activities.

This sentence also means that BnF has legally the right to ask a website owner for the passwords and the codes necessary to crawl his site, for example when access to the data held by the website is not free.

The Library answered quickly to the blogger protests. After having exchanged a few e-mails with BnF, the blogger recognized the utility of the web legal deposit, and decided to suppress his trap.

Note that this decision leads the Danish web archivist to choose restrictive politeness rules for their robot, to avoid overloading requested servers and potential lawsuits.

The racks are the Petaboxes, high density, low cost, low power storage hardware designed by Capricorn Technologies. See: http://www.capricorn-tech.com/ [Accessed:[START_REF] Httrack | HTTrack Website Copier[END_REF]].

More than 100 000 domain names redirected to only three websitestwo registrars and one domain squatter.

Note that these figures sometimes group several MIME type: for example, the number of JPEG document is given by adding the number of documents having as a MIME type "image/jpeg", "Image/jpeg" or "image/JPEG".

Note that similar rates are observed for the .au domain (Australia, from 2004 to 2007): the percentage of GIF images is divided by two (from 10 to 5%). However, png images are less used in Australia (0,56%) than in France (1,17%)[START_REF] Koerbin | The Australian Web domain harvests: a preliminary quantitative analysis of the archive data[END_REF].

Note that the number of .com or .net domains harvested do not vary so much between 2006 and 2007. 163 632 .com domains were harvested in 2006 to 181 626 in 2007; 22 746 .net domains in 2006 to 21 853 in 2007.

.jpg (26%), .gif (8%), .JGP (2%), .png (2%). Note additionally that 104 109 files (1%) were CSS files.

ACKNOWLEDGMENTS

We wish to acknowledge Kris Carpenter and the Internet Archive team, our partner these last four years (already!), especially Igor Ranitovic who monitored all BnF crawls from 2004 to 2007, along with John Lee, Brad Tofel and Michael Magin who helped us install the racks and analyze these new forms of collection in Paris and in San Francisco.

We are also very grateful to Mireille Chauveinc for her careful proofreading. We wish at last to express our thanks to Gildas Illien, Head of Digital Legal Deposit, for his advice and support.


Jonathan Passerat-Palmbach

Claude Mazel

David R C Hill

ThreadLocalMRG32k3a: A Statistically Sound Substitute to Pseudorandom Number Generation in Parallel Java Applications

Keywords: Java, Threads, Pseudorandom Number Generation, Parallelization of Simulation, Software Development Tools and Support, Object Oriented Programming & Design

Abstract:

Parallel And Distributed Simulations (PADS) become more and more spread since scientists always want more accurate results in the shortest time. PADS are often sensitive to several parameters, and when they own a stochastic component, one has to ensure he knows how to correctly deal with randomness in a parallel application. This point can appear to be very tricky for non-experts, who might be tempted to move this part of the simulation aside. Several software efforts have been produced in various programming languages to help developers handle pseudorandom streams partitioning in PADS. However, these tools remain third-party libraries that need to be integrated in already existing applications, and that might be hardly swappable. The latest release of the Java Development Kit (JDK 7) tries to tackle this problem with a new class called ThreadLocalRandom. The latter is in charge of safe pseudorandom number generation across Java threads. The present work studies the pros and cons of this approach, and introduces ThreadLocalMRG32k3a, an alternative to ThreadLocalRandom that shows better results in terms of generation speed and statistical quality. ThreadLocalMRG32k3a respects the same Application Programming Interface (API) as ThreadLocalRandom, thus enabling clients to use it in place of its JDK counterpart at no cost.

Introduction

At the manycore era, simulation practitioners need to take advantage of these new architectures. However, designing Parallel And Distributed Simulations (PADS) is not straightforward, and is often seen as a potential long-term perspective rather than a real implementation consideration. Indeed, simulation developers are not offered many tools to harness manycore architectures.

The new release of the Java Development Kit 7 (JDK 7) comes to grips with this lack by focusing on Java's concurrency features. Java 7 offers a couple of new tools to enhance the already existing concurrent package. Mainly, a new framework called Fork/Join appears [Lea, 2000]. It provides an easy-to-use MapReduce implementation running in parallel thanks to a pool of worker threads. Such inputs, added to the already present tools allowing the distribution of the computing load across several threads, should attract more and more simulation practitioners to Java development. These users will also bring their own concerns bound to parallelization in their domain of expertise. Thus, simulationists working on stochastic simulations will ask for a tool to help them to partition a random source in a parallel Java environment.

As a matter of fact, correct partitioning of random streams is the main concern of several studies [Hellekalek, 1998a, Hill, 2010], and neglecting this part of a simulation could lead to biased results [START_REF] Reuillon | Parallel stochastic simulations with rigorous distribution of pseudo-random numbers with distme: Application to life science simulations[END_REF]. To avoid such issues, one needs to ensure of four main points that are exposed in [Coddington, 1996]:

1. Each thread should dispose of its own random sequence; 2. The parallelization technique must be usable for any number of threads; 3. The parallel random streams produced should be uncorrelated; 4. When the status of the PRNG is not modified, the sequence of random numbers generated for a given thread must be the same no matter the number of threads and no matter of threads scheduling.

Java 7 introduces the ThreadLocalRandom class, a tool that intends to enable developers to deal with pseudorandom numbers in parallel on a single shared memory computer, without having to figure out how to distribute numbers among the available processing elements. The question we have for scientific applications is the following: can ThreadLocalRandom serve as a random source with the statistical quality required by stochastic simulations? Although this development is a good initiative that is worth being integrated in Java, we will see that the current implementation still has some major drawbacks for scientific purposes.

The present work will:

• Study ThreadLocalRandom's intrinsics to figure out whether its output is satisfying regarding stochastic simulations needs;

• Present already existing libraries that could serve as alternatives to ThreadLocalRandom;

• Introduce ThreadLocalMRG32k3a, our proposal based upon the MRG32k3a Pseudorandom Number Generator (PRNG) algorithm from Pierre L'Ecuyer [L 'Ecuyer, 1999];

• Compare ThreadLocalMRG32k3a to ThreadLocalRandom, and consider its potential evolutions.

ThreadLocalRandom

Implementation concerns

Officially released with JDK 7, the ThreadLocalRandom facility was developed within the jsr166y initiative by Doug Lea. ThreadLocalRandom tries to solve the complexity to use random sources correctly in parallel applications. Each thread owns a ThreadLocalRandom instance, allowing each to be independent from the others to pick up random numbers. Still, the most important point behind this technique is that it is supposed to distribute pseudorandom streams safely among threads. ThreadLocalRandom inherits from java.util.Random, thus sharing its interface. Every thread must call a method named current before calling the classical nextXXX methods to pick up a random number which type is indicated by the XXX suffix.

ThreadLocalRandom makes use of the Random Spacing technique [Hill, 2010] to distribute pseudorandom streams across threads. This technique consists in initializing an identical PRNG instance in each thread with a different seed-status [START_REF] Passerat-Palmbach | Shoverand: a model-driven framework to easily generate random numbers on gpgpu[END_REF], the latter being randomly chosen by another algorithm. By doing so, each thread owns an independent pseudorandom sequence, provided the PRNG algorithm has a long enough period, and is not subject to long-range correlations [De Matteis and Pagnutti, 1988].

Random Spacing is implemented in ThreadLocalRandom through its constructor. Indeed, this method calls the Random constructor before setting a Boolean to true, thus depicting that initialization has been done and cannot be performed again. ThreadLocalRandom must then rely on the constructor of the Random class to set its initial seed. Until JDK6, the Random constructor used to automatically perform a call to setSeed, the method in charge of the Random Spacing initialization of the seed. However, this is not true anymore with JDK7, where the constructor of Random does not summon setSeed anymore. Consequently, any PRNG class that extends Random and relies on it to call setSeed, will see its seed-status remain uninitialized. According to [START_REF] Gosling | The Java language specification[END_REF], the seed of each thread is thus set to zero as any class member of the long type would be. Hence, every thread will pick up the same pseudorandom sequence in such a case!

We have already spotted a similar problem in a Java Mersenne Twister implementation and proposed a corrective patch that solves it. Calling setSeed in every thread could easily solve this problem. Unfortunately, the setSeed public method, which would normally allow setting a thread's PRNG seed to a new value is locked by the previously mentioned boolean. Such a feature is important to prevent any user to harm pseudorandom streams independence between threads by setting several seeds to the same value. However, this also prevents us to adapt the class behaviour, and force a call to setSeed directly in the subclass's constructor. Moreover, this solution relies on user-awareness of the problem, which goes against the initial purpose of ThreadLocalRandom to hide random streams distribution to the user.

The problem was finally solved in the second update of the JDK7 by changing the Random constructor in order to take into account a potential use of setSeed by subclasses. This change is quite confusing in two ways. Not only does it break encapsulation, one of the elementary concepts of the object-oriented paradigm, but it also appears as a lack of good software engineering that discourages to adapt an implementation according to an already existing source code. Instead, it is safer to rely on the specification only. In our case, the Random class documentation issued by Oracle makes no mention of a potential call to the setSeed method by the Random constructor. As a consequence, we cannot blame Oracle for this bug, but rather advise developers to focus on the official documentation only, especially when they are working on such sensitive aspects of the implementation.

Statistical quality discussion

Nowadays, several renowned tools exist to check the statistical quality of pseudorandom streams. When Knuth's tests [Knuth, 1969] cannot be considered as a proof of quality on their own, they have been integrated in wider test batteries. A testing suite, named DieHard, highly regarded for many years, was proposed by Marsaglia [Marsaglia, 1996], and was improved by Brown [START_REF] Brown | Dieharder: A random number test suite[END_REF] who proposed the DieHarder testing suite. The SPRNG [START_REF] Mascagni | Sprng: A scalable library for pseudorandom number generation[END_REF] parallel random number library is also providing a thorough set of statistical tests. For five years now, the scientific community has widely agreed that the current reference test battery is TestU01 from [L' Ecuyer and Simard, 2007]. TestU01 currently offers the most complete collection of utilities for the empirical statistical testing of uniform random number generators. Please note that this enumeration does not take into account testing suites targeting cryptographic applications, which leading tool is rather the NIST STS proposal [START_REF] Rukhin | A statistical test suite for random and pseudorandom number generators for cryptographic applications[END_REF].

In addition to the classical statistical tests for PRNGs, and the other tests previously cited and proposed in the literature, TestU01 proposes new original tests as well as predefined tests suites (SmallCrush, Crush and BigCrush with more than a hundred tests). Many of the most spread PRNGs fail quite significantly when faced to this software. ThreadLocalRandom's underlying PRNG, which is a well-known and widely studied LCG from Knuth [Knuth, 1969], also ruling the output of the POSIX drand48 C function for example, is among the algorithms at fault. LCG generators should be banned from scientific applications since their structure is not adapted to many modern applications, and the problem is even bigger when parallel and distributed computing is considered. In addition, the period proposed by ThreadLocalRandom is relatively small for modern scientific applications: it is 2 48 numbers long, when Pierre L'Ecuyer suggests that for modern applications periods should be at least 2 100 numbers long [L 'Ecuyer, 2010]. Now thinking of a parallel utilization of ThreadLocalRandom, we can barely imagine that such a bad generator [START_REF] Ferrenberg | Monte carlo simulations: Hidden errors from "good" random number generators[END_REF][START_REF] Hellekalek ; Hellekalek | Good random number generators are (not so) easy to find[END_REF], Hellekalek, 1998a] when considered in sequential environments could behave better in a parallel environment. Thanks to TestU01 parallel filters [L' Ecuyer and Simard, 2007], we can easily create a random sequence formed by the combination of any number of input sequences from different ThreadLocalRandom initializations. However, as stated in [START_REF] Salmon | Parallel random numbers: as easy as 1, 2, 3[END_REF], it is impossible to perform a complete coverage of all possible logical sequences because many strategies can be set up to distribute both tasks and random streams across parallel computational units. Nonetheless, some samples are particularly representative of how most users will use random sequences, and we will study them in section 5.3.

Related Works

Several attempts to provide a user-friendly interface to generate random numbers in parallel environments can be found in the literature. Here we recall the major proposals that can compete and replace ThreadLocalRandom in scientific applications. We only consider frameworks providing ways to automatically distribute pseudorandom streams through threads without the user's help.

As we have seen previously, the standard Java library only ensures thread safety through synchronized methods when accessing to the random number generation features of the java.util.Random class. This approach is not satisfying at all in the world of High Performance Computing: in addition to not ensuring reproducibility of simulations because of thread scheduling, it impacts performance of parallel stochastic applications because of the sequential bottleneck implied by the synchronization guarding random facilities. This method to partition pseudorandom sequences is known as Central Server in the literature [Hill, 2010].

JAPARA [START_REF] Coddington | Japara-a java parallel random number generator library for high-performance computing[END_REF] has been proposed by [START_REF] Coddington | Japara-a java parallel random number generator library for high-performance computing[END_REF] to tackle this lack in Java libraries. They bring up a Java API to support parallel generation of random streams. On the other hand, JAPARA proposes that every processing element (be it Java threads in our case) handles its own pseudorandom stream. By doing so, only the initialization phase is synchronized, and a referenced partitioning technique is then used to distribute the underlying pseudorandom streams. As a matter of fact, JAPARA comes with three PRNGs implemented, each coupled to a distribution technique that matches its intrinsic characteristics. The point is that the user only has to select the PRNG he wants to employ, and then rely on the framework to ensure independence between the different streams assigned to the threads. Furthermore, JAPARA allows the user to save and restore the current state of a PRNG, thus permitting to checkpoint a simulation.

L'Ecuyer's team first minded on an object oriented pseudorandom generation package in 2002 with [L' Ecuyer et al., 2002]. This has been concretized in the rStream library [L' Ecuyer and Leydold, 2005] that implements a single MRG32k3a PRNG, whose independent streams are partitioned from an original stream thanks to the Sequence Splitting technique [Hill, 2010]. A declination of rStream comes with the SSJ (Stochastic Simulation in Java) [L' Ecuyer et al., 2002] framework as the pseudorandom streams parallelization utility of the library. It provides a greater set of PRNGs, with the famous Mersenne Twister [START_REF] Matsumoto | Mersenne twister: A 623-dimensionnally equidistributed uniform pseudorandom number generator[END_REF]] for instance, and also a compliant set of distribution techniques.

The latest Java random number generation framework that has retained our attention is Dis-tRNG [Reuillon, 2008, Reuillon et al., 2011]. While its API does not diverge from the two other proposals described in this section, DistRNG focuses on correct partition of random streams. To do so, this framework handles XML generic statuses that model any PRNG state. Every computational element is initialized with a different XML status that needs to be built upstream. DistRNG displays a fine choice of statistically sound PRNGs according to the TestU01 reference testing library.

As a conclusion, this section has shown that several satisfying proposals of APIs for parallel pseudorandom number generation can be found in the literature. Consequently, users have many reliable solutions at their disposal if they want to take advantage of statistically sound pseudorandom sequences in their Java applications. Moreover, most of these solutions can replace ThreadLocalRandom's features, but require modifications on the application source code to meet their functioning requirements.

MRG32k3a Implementation

In this section, we present the Java implementation we made of MRG32k3a PRNG, described by Pierre L'Ecuyer in [L 'Ecuyer, 1999]. Several features of this algorithm retained our attention, from its internal data structure to the results it displays when faced to today's most stringent testing batteries.

The choice of MRG32k3a

Talking about its internal properties, MRG32k3a is really suited to parallelization among small computational elements such as threads, because its lightweight data structure only stores 6 integers to handle its state. It means that introducing this PRNG in already existing Java applications will have roughly no impact on their memory footprint. The algorithm itself is quite short, relying on simple operations only to issue new random numbers. The parameters chosen for MRG32k3a are such that it has a full period of 2 191 numbers. This period is fairly enough since L'Ecuyer suggests periods between 2 100 and 2 200 are highly sufficient even for large-scale simulations. MRG32k3a has been designed to produce independent streams and substreams from its original random sequence thanks to its parameters that enable safe Sequence Splitting. Thus, the internal parameters split the initial sequence into 2 64 adjacent streams of 2 127 random numbers, themselves divided into sub-streams containing 2 76 elements.

The ability to issue independent streams is very important when tackling the safe distribution of random numbers across parallel computational elements. MRG32k3a's Sequence Splitting approach suggests an obvious partition of the original sequence by assigning each computational element a stream or a sub-stream, depending on the application eagerness for random numbers. As long as we are focusing on parallel applications that are Java threads based, the parallel grain is limited to how many threads a single manycore machine can handle. This figure depends on the underlying architecture hosting the Java platform, but we do not expect having to deal with more than 2 64 parallel threads, which is the total number of independent streams bearing 2 127 random numbers each that MRG32k3a can provide.

Still, the most important point in our opinion is that this generator displays a great statistical quality, according to its TestU01 results related in [L' Ecuyer and Simard, 2007]. MRG32k3a passes all the tests of BigCrush, the most stringent and complete testing battery coming with TestU01, and is so referred to as a "Crush-resistant" PRNG in [START_REF] Salmon | Parallel random numbers: as easy as 1, 2, 3[END_REF]. While being Crush-resistant cannot ensure a perfect randomness of the considered pseudorandom stream, it is a satisfying property that few PRNGs can be proud of. Furthermore, PRNGs stated as bad according to TestU01 criteria have led to incorrect simulation results in the past [De [START_REF] Matteis | [END_REF], Ferrenberg et al., 1992, Maigne et al., 2004], and even good PRNGs can miss some tests [Reuillon, 2008, Salmon et al., 2011]. Thus, as we did not want to take any risks with our PRNG choice as a replacement of ThreadLocalRandom's LCG, we focused on Crush-resistant PRNGs such as MRG32k3a.

Implementation Details

We have designed ThreadLocalMRG32k3a so that it can be used as an alternative to ThreadLo-calRandom. Thus it displays the very same interface as its counterpart. The methods contained in our class are all dedicated to produce various kinds of random outputs: from integers to double precision floating point values, so as ThreadLocalRandom performs. In the same way, we also reused the current() method introduced in ThreadLocalRandom: it actually aims to provide its independent instance of ThreadLocalMRG32k3a to each thread calling it. The current() method is the core of ThreadLocalMRG32k3a in a sense that the call hierarchy it implies highly differs from the original behaviour of ThreadLocalRandom.

Current() is a static method that every thread must call in order to retrieve its own Thread-LocalMRG32k3a instance. The method basically acts like a singleton that builds a ThreadLocal instance parameterized with the PRNG class, ThreadLocalMRG32k3a in our case. ThreadLocal is a generic Java class appeared in JDK 2 that provides easy copy-on-access facilities to concurrent threads. When a thread first accesses a ThreadLocal object, the latter gets an instance especially built for it that does not require synchronized accesses with other threads. Typical applications of this mechanism are thread-based counters such as thread identifiers for example.

Our implementation first takes advantage of this technique to ensure reproducibility between executions. Indeed, stochastic simulations need to be reproduced for debug purposes or their results to be checked. When ThreadLocalRandom is used by default, it does not satisfy this need because it relies on the Random constructor to set its internal seed, which behavior is to use the current system time as seed. We fix this problem by basing the seed initialization on the thread unique identifier, so that for a given identifier, a thread will always be assigned the same stochastic stream. Although Java enables us to figure out a thread identifier at runtime through the Thread.currentThread().getId() call, we cannot rely on this identifier since it is global for the whole JVM and thus depends on how many threads were created before ours are. Therefore, we have stored a handcrafted unique identifier within ThreadLocalMRG32k3a, thanks to a synchronized atomic counter handled through the ThreadLocal mechanism.

Please note that the ThreadLocal mechanism only operates at thread level and is not aware of any task concept introduced by top-level frameworks such as Fork/Join. Thus, reproducibility cannot be expected when either ThreadLocalRandom or ThreadLocalMRG32k3a is used by tasks from these frameworks. Now that we are able to assign a stream to each thread, we need to determine how these streams are actually handled within our MRG32k3a implementation. We have seen previously that this PRNG had been designed to partition its original sequence into streams and streams. We have chosen to give an independent stream to each thread, so that they can all benefit of their own independent 2 127 numbers long pseudorandom sequence. As long as streams are contiguous in the original sequence, the beginning state of each independent stream is located every 2 127 elements in the original sequence. Hopefully, a Jump Ahead algorithm is detailed in [L' Ecuyer, 1999] that enables us to advance the state of the original sequence at almost no extra cost, no matter how much elements we skip. Thus, if a thread has been assigned an identifier k, the seed-status of its ThreadLocalMRG32k3a instance is initialized by the constructor to X n with n = 2 127 * k. The latter situation is summed up in Figure 1:

Original Pseudorandom Sequence Thread 0 [2 2 * 0] X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 X 11 Thread 1 [2 2 * 1] Thread 2 [2 2 * 2]

Example of use

From a Java developer point of view, picking up random numbers from ThreadLocalMRG32k3a is as simple as using the original Java Random API as exposed in Listing 1:

Listing 1: Example of use of ThreadLocalMRG32k3a

ThreadLocalMRG32k3a myRNG = ThreadLocalMRG32k3a . c u r r e n t ( ) ;

Thread t i d = new Runnable { p u b l i c v o i d run ( ) { f o r ( i n t i = 0 ; i < numbersCount_ ; ++i ) { myRNG. next ( ) ; } } }
The implementation detailed in this section makes ThreadLocalMRG32k3a the equivalent of ThreadLocalRandom concerning API and features. However, our proposal is more suited to parallelize scientific applications where statistically sound random sources are necessary. That being said, let us see how ThreadLocalMRG32k3a outcomes its counterpart with detailed analysis of both PRNGs' performances.

Results

In this part, we compare three aspects of the original ThreadLocalRandom and of our proposal ThreadLocalMRG32k3a: their memory footprint, their numbers throughput and their statistical quality.

Memory footprint

Here we want to evaluate the memory footprint added to each thread by both PRNGs. ThreadLo-calRandom wraps a LCG that uses one integer to store its internal state, whereas MRG32k3a needs at least 6 integers. Our ThreadLocalMRG32k3a also relies on an extra thread identifier to provide reproducibility as required by stochastic simulations. As a conclusion, ThreadLocal-Random is taking the lead on the memory footprint criterion, consuming only one integer when our proposal implies 6 more.

Speed

It is quite hard to isolate accurately the methods involved in random number generation across several threads when trying to evaluate the speed of two PRNGs. That is why we based our comparison on the Netbeans' profiler data to figure out which algorithm was the most efficient. Figure 2 presents the average profiling results of the two PRNGs obtained by probing an 8-thread application, which each thread issues the same amount of random numbers:

Figure 2 shows that ThreadLocalMRG32k3a is about 10 times faster than ThreadLocal-Random. Therefore, our Java wrapper has no impact on MRG32k3a's performance since its genuine version was announced 10 times faster than the LCG used by ThreadLocalRandom [L 'Ecuyer, 1999].

Statistical quality

We have already discussed LCGs statistical quality, but in our case, the LCG at the heart of ThreadLocalRandom is used in parallel thanks to the Random Spacing distribution technique. When parallelizing an application, data processing is spread among the available computational elements following a particular pattern, so as random numbers. As a result, knowing the parallelization techniques used for both random numbers and input data, we could recreate the computation scenario that would have taken place in a sequential environment. This allows us to check the corresponding random sequence resulting from the concatenation of the subsequences. We know that it is nearly impossible to examine every possible combination, thus we decided to focus on the most obvious technique to process input data: assign an equally sized subset from the original data to each thread.

To simulate this situation, we have faced the two PRNGs to TestU01. The random stream studied by the testing battery was provided by combining the sub-streams of a given number of threads. In the following chart, each PRNG is tested using combined streams resulting from what would be the concatenated random sequence of 16 to 64 threads: Figure 3 shows that using MRG32k3a instead of the LCG implemented in ThreadLocalRandom is particularly relevant when considering the statistical output of both generators. Here, we see that none of the 180 configurations of ThreadLocalRandom tested can pass the TestU01 Bigcrush testing battery, when ThreadLocalMRG32k3a only misses 30. This figure backs our PRNG choice for the underlying algorithm ruling our ThreadLocalRandom alternative.

Discussion

In this paper, we propose a Java implementation of L'Ecuyer's MRG32k3a that can be used in the very same conditions as ThreadLocalRandom. However, simulation practitioners often expect to challenge their stochastic models with different random sources. In this way, providing a full framework offering implementations of other PRNGs, wrapped in an API identical to ThreadLocalRandom, could help simulationists who champion Java threads based developments for their parallel simulations to harness parallel architectures. In this section, we review the algorithms that we plan to include in future versions of this work.

Having already considered a Sequence Splitting partitioning technique with MRG32k3a, we chose to focus our further investigations on what seems the most reliable parallelization technique: parameterization [Hill, 2010]. While Sequence Splitting intends to slice an original random sequence in several independent random streams, parameterization tackles the problem differently. Indeed, PRNGs employing parameterization own a parameter that can distinguish one instance of a given PRNG from one another. This unique parameter then contributes to issue highly independent random streams that can be assigned to different processing elements, such as threads.

TinyMT

TinyMT is the latest offspring from the Mersenne Twister family. TinyMT is not described in any scientific article yet, but information about it can be found on its dedicated webpage [Saito, 2011]. This PRNG matches the requirements we have formulated for a PRNG to be integrated in our ThreadLocalRandom alternative: it is stated as producing a good quality output, according to TestU01 statistical tests, and displays a long-enough period of 2 127 numbers. As explained in the introduction of this section, this PRNG champions parameterization to provide highly independent streams. It is consequently shipped with a software tool that can create over than 2 32 × 2 16 independent statuses.

We are now considering the implementation of this PRNG as another alternative to ThreadLo-calRandom. Part of this development work will be close to what has already been achieved with the implementation of MRG32k3a. However, because of parameterization, we might be faced to technical difficulties to provide a user-friendly implementation. Actually, TinyMT parameterized statuses need to be precomputed by a third-party application called Dynamic Creator, which is delivered with the PRNG. Thus, to provide a full Java concurrent implementation, not only we need to implement the algorithm, but also to ship a large amount of precomputed statuses with it, provided that Dynamic Creator relies on several C++ libraries, and would thus be difficult to reimplement in Java in a portable way. Each thread will then receive an instance of ThreadLocalTinyMT initialized by a different status. Since the data structure representing a status weights no more than a hundred of bytes, delivering lots of ready to be used parameterized statuses should be possible.

Threefry/Philox

Threefry and Philox are counter-based PRNGs [START_REF] Salmon | Parallel random numbers: as easy as 1, 2, 3[END_REF]] also relying on parameterization to solve random streams partition concerns. Like any other PRNGs considered in this study, they are Crush-resistant and display good performance in regards to their low memory footprint and high numbers throughput. They appear to be better suited than TinyMT (or any other member of the Mersenne Twister family) to target a smooth integration in the Java threads API since their parameters are formed by a single key that can be set at runtime according to each thread's unique identifier. Indeed, Mersenne Twister-like PRNGs might not fit some applications that cannot afford wasting any memory space to store the state and the initialization parameters of each thread's PRNG.

Conclusion

This work has studied the recent ThreadLocalRandom proposal shipped with JDK 7 that intends to provide independent random streams for parallel Java applications. Having stressed the importance of using statistically sound PRNGs and partitioning techniques, we have asserted that Crush-resistant generators were in our opinion the only category of generators that should be trusted for scientific applications development. Considering this criterion, we have evaluated ThreadLocalRandom, as having a satisfying design but a poor implementation. On the other hand, this study surveys the most spread libraries aiming the same goal as ThreadLocalRandom, but displaying improved quality. We strongly recommend some of them, like SSJ or DistRNG, to replace ThreadLocalRandom as much as possible.

In addition, we propose in this work ThreadLocalMRG32k3a as another alternative to Thread-LocalRandom. Our proposal respects the same API as ThreadLocalRandom, but it relies on MRG32k3a, a well-known Crush-resistant PRNG. Not only does ThreadLocalMRG32k3a display a far better statistical quality than its JDK counterpart, it is also much more suited for stochastic simulations, given that it issues a reproducible output by default. ThreadLocalMRG32k3a is a bit greedier in memory but it completely outperforms its counterpart in both speed and statistical quality. Indeed, ThreadLocalMRG32k3a is more than 10 times faster than ThreadLocalRandom and passes TestU01's most stringent testing battery: BigCrush.

We now plan to implement other Crush-resistant PRNG algorithms such as TinyMT, Threefry or Philox that display statistical properties equivalent to MRG32k3a. This effort would allow simulation practitioners to compare the results of their simulations when fed with different random sources that would integrate smoothly in their developments, in the same way as ThreadLocalRandom. We want to enable them to switch the PRNG they use with the slightest impact on the source code of their simulations.

Figure 1 : 3

 13 Figure 1: 3 Threads performing respective Jump Ahead on an original pseudorandom sequence, according to their unique identifier. Streams are here limited to 2 2 elements each

Figure 2 :

 2 Figure 2: Computation time of the two PRNGs according to the profiler's output

Figure 3 :

 3 Figure 3: BigCrush results for ThreadLocalRandom and ThreadLocalMRG32k3a used by 16, 32 and 64 threads. Each test configuration was initialized with 60 different seed-statuses

Acknowledgements

The authors would like to thank Florian Guillochon for his careful reading and useful suggestions on the draft. This work received financial support from the Auvergne Regional Council.

is partially funded by the Auvergne Regional Council and the FEDER