BUbiNG: Massive Crawling for the Masses

1. INTRODUCTION

• Crawling differs from textbook traversal because the graph is unknown and huge, while downloads face network limits, politeness requirements, and operational errors.Source: §1 · p. 1
• BUbiNG is a pure-Java, open-source crawler released under the GNU GPLv3.Source: §1 · p. 1
• Multiple agents coordinate without central control, and crawling speed grows linearly with agent count given enough bandwidth.Source: §1 · p. 2
• The system processes more than 10 000 pages per second while respecting politeness by host and IP, and analyzes, compresses, and stores more than 160 MB/s of data.Source: §1 · p. 2
• BUbiNG supports the robot exclusion protocol, hostwise breadth-first visits, and independently configurable minimum intervals between requests to each host and IP.The host and IP intervals can in principle be customized per host or IP.Source: §1 · p. 2
• The intended out-of-the-box use is archival crawling without page refresh, while visit behavior can be modified for other tasks.Customization of BUbiNG is outside the paper's scope.Source: §1 · p. 2
• The authors plan to use BUbiNG to gather datasets orders of magnitude larger than those collected with UbiCrawler.Source: §1 · p. 2

2. MOTIVATION

• Breadth-first snapshots, altered by politeness constraints, are intended to support more reproducible web studies, though breadth-first sampling can itself introduce artifacts.The authors argue that focused crawling can be detrimental when studying the web “as it is.”Source: §2 · p. 2
• Large snapshots gathered over long periods may introduce biases that are difficult to detect and undo, making speed important for a coherent time frame.Source: §2 · p. 3
• BUbiNG aims to remove bottlenecks and contention so large-scale crawling is possible even with limited hardware resources.Source: §2 · p. 3
• Using the same parser online and during graph construction is intended to avoid inconsistencies that can introduce artifacts such as spurious components.The authors hope this shared-code framework will improve reliability and reproducibility of web-snapshot analysis.Source: §2 · p. 3

3. RELATED WORKS

• Earlier crawler generations progressed from early web spiders to large-scale systems and then to distributed crawlers capable of snapshots of hundreds of millions of pages.Source: §3 · p. 3
• The newer generation aimed at billions of pages, but the authors describe BUbiNG as the first open-source crawler designed to be fast, scalable, and runnable on commodity hardware.The passage gives Lee et al. as an example of the newer generation.Source: §3 · p. 3

3.1. Open-source crawlers

• GNU wget and mngoGoSearch are described as stable open-source projects not designed to exceed a few thousand or tens of thousands of pages, limiting their suitability for web-scale experiments.Source: §3.1 · pp. 3–4
• Heritrix supports large datasets but is a single-machine crawler, while also offering checkpointing, URL filtering and processing, and WARC storage.Its default crawl order is breadth-first.Source: §3.1 · p. 4
• Nutch's ClueWeb09 crawl downloaded 1 040 809 705 pages at 755.31 pages/s using 100 Hadoop machines, or about 7.55 pages/s per machine.The authors attribute low throughput to Hadoop's batch-style job distribution and say modern distribution frameworks such as BUbiNG can increase throughput by orders of magnitude.Source: §3.1 · p. 4

4. ARCHITECTURE OVERVIEW

• Thousands of fetching threads use synchronous blocking I/O, which the authors say outperforms asynchronous I/O in their experience; lock-free structures keep fetching threads away from lock-based structures.The design also simplifies implementation and supports HTTP/1.1 keepalive downloads.Source: §4 · p. 4
• URL storage uses byte arrays rather than Java strings to reduce memory and object overhead, and identical autonomous agents use customizable URL assignment with consistent hashing by default.Source: §4 · p. 5
• Fetching threads download pages while parsing threads extract information; a lock-free result list passes fetched buffers between them, and discovered URLs enter a deduplicating sieve.An approximate LRU cache of 128-bit fingerprints discards more than 90% of discovered URLs before they reach the sieve.Source: §4 · pp. 5–6
• The workbench tracks visit states for hosts and checks in constant time whether a host can be accessed without violating politeness constraints.The paper says hundreds of thousands of host states are needed to reach several thousand downloads per second politely.Source: §4 · p. 6
• The distributor assigns URLs to host visit states, while the workbench's in-memory capacity is supplemented by a disk virtualizer because breadth-first queues grow exponentially.The workbench holds ready host states; virtualized URLs can later be moved back into it.Source: §4 · p. 6
• The native store writes compressed resources in WARC format, with parsing threads compressing pages in parallel before a flushing thread writes them.Source: §4 · p. 6

4.1. The sieve

• A sieve queues discovered elements for eventual output while ensuring that repeated enqueues produce only one dequeue.Its main implementation challenge is handling the potentially unbounded growth of discovered URLs without keeping standard dictionaries in core memory.Source: §4.1 · p. 7
• MercatorSieve stores 64-bit hashes on disk and processes sorted in-memory batches to identify unseen elements using sequential file access.Its array size is based on available in-core memory, and output preserves first-appearance order.Source: §4.1 · p. 7
• DRUM adds associated-value retrieval and updates, and its bucketed design can sort sets an order of magnitude larger than MercatorSieve with the same in-core memory.DRUM sacrifices breadth-first order, even per host; with a URL cache, the authors report that MercatorSieve becomes more competitive.Source: §4.1 · p. 7
• Bloom-filter queues can lose pages through false positives when discovered URLs exceed expectations, while fixed-size fingerprint dictionaries no longer use constant memory.The number of discovered URLs is difficult to bound in advance, making Bloom-filter sizing difficult.Source: §4.1 · p. 7

4.2. The workbench

• The workbench is BUbiNG’s in-memory next-URL structure and improves on IRLBot’s two-queues approach by checking download readiness in constant time without violating politeness limits.The workbench is identified as one of the design’s main reasons for high throughput.Source: §4.2 · pp. 7–8
• Visit states group each host’s URLs in FIFO order, while workbench entries group states by IP and prioritize them using host- and IP-specific next-fetch times.The workbench is a priority queue of priority queues of FIFO queues.Source: §4.2 · p. 8
• The top visit state is ready exactly when its first URL can be fetched without breaking host or IP politeness; otherwise, its priority gives the wait until a host is ready.The workbench acts as a delay queue, and dequeuing removes the top entry and visit state in logarithmic time.Source: §4.2 · p. 8

4.3. Fetching threads

• Fetching threads take visit states from the todo queue and fetch their first URLs, with optional repeated fetching for a fixed time to use HTTP 1.1 keepalive.They return completed states through a done queue; fetch data buffers a fixed amount in memory and spills excess data to disk.Source: §4.3 · p. 9
• Thousands of fetching threads can run in parallel because they spend most of their time blocked on I/O.Their number sets network-fetch parallelism and should be as large as bandwidth and fetch-data memory allow.Source: §4.3 · p. 9

• Parsing threads extract fetched responses from the results queue and check parsed HTML links against the URL cache before routing unseen URLs to another agent or the local sieve.Source: §4.4 · p. 9
• Response digests are stored in a Bloom filter to avoid saving pages with matching signatures, including near-duplicates, before content is saved to the store.Source: §4.4 · p. 9
• For HTML, BUbiNG fingerprints summarized content after stripping attributes and discarding digits and dates, which can collapse pages differing only in visitor counters or calendars.The paper calls pages classified as duplicates under this rule duplicates, and the remaining pages archetypes.Source: §4.4 · p. 9

4.5. DNS threads

• DNS threads resolve newly discovered hosts and add them to a workbench entry, creating one if the IP address is new; the authors found a local recursive DNS server essential to avoid an external-server bottleneck.Source: §4.5 · pp. 9–10

4.6. The workbench virtualizer

• The workbench virtualizer stores host-to-FIFO-queue mappings on disk, preserving each host’s original breadth-first URL order while limiting memory use as discovered URLs grow.As workbench space opens, queued visit states are refilled from disk.Source: §4.6 · p. 10
• An earlier static on-disk queue design could not guarantee breadth-first visits under network faults, while Berkeley DB became a bottleneck; BUbiNG therefore developed an ad-hoc virtualizer for breadth-first visits.It borrows Berkeley DB’s periodically collected log files and uses memory mapping to lessen I/O burden.Source: §4.6 · p. 10
• The virtualizer memory-maps log files and tracks per-host queue links; when used space falls below a threshold, it collects queued URLs toward the start of the mapped region.The authors say appends and garbage collections are localized, making good use of operating-system caching.Source: §4.6 · pp. 10–11

4.7. The distributor

• Because the workbench is size-limited, blindly loading sieve URLs can crowd it with URLs from few hosts; the distributor also loads URLs from virtual queues as needed.The memory design limits growth with discovered URLs, while allowing memory to scale with discovered hosts.Source: §4.7 · p. 11
• The distributor grows the required front when fetching threads wait, but this competes with breadth-first order, which favors URLs already in visit states.The front is the number of visit states ready for download under politeness constraints; it affects throughput because the number of hosts visited in parallel matters.Source: §4.7 · p. 11
• To balance front size and breadth-first order, the distributor favors refilling the workbench from virtual queues, then reads from the sieve when the front is too small.URLs from the sieve may go to the workbench or to a host’s virtual queue, depending on existing disk URLs and per-IP workbench targets.Source: §4.7 · p. 11

4.8. Configurability

• Filters control resource acceptance across fetching, parsing, URL following, scheduling, and storage, and can be changed at startup or runtime.Prefetch filters evaluate URLs; postfetch filters evaluate fetched responses, for example when deciding whether to parse or store them.Source: §4.8 · pp. 11–12

4.9. Heuristics

• BURL parses and normalizes discovered URLs, handling details such as unnecessary escaping and percent-escape case normalization.The paper notes that unsuitable URL normalization contributed to problems building a web graph from ClueWeb09.Source: §4.9 · p. 12

4.10. Distributed crawling

• BUbiNG distributes crawling across identical agents without explicit leadership, with each agent maintaining the described data structures.URL assignment is configurable; by default, host-based assignment prevents two agents from crawling the same host simultaneously, and consistent hashing assigns hosts to agents.Source: §4.10 · p. 12
• Table I compares BUbiNG with open-source crawlers and includes IRLbot as a reference; its resource counts cover different types of content across crawls.ClueWeb09 and IRLbot figures count HTML pages, while ClueWeb12 also includes other resource types such as images.Source: Table I · p. 13
• Agents send URLs using JGroups messaging, defaulting to UDP; TCP-based JMX provides remote control and exposes most configuration parameters and statistics.Almost all crawler structures can be modified at runtime.Source: §4.10 · p. 13

5. EXPERIMENTS

• The evaluation combined proxy-based in vitro tests with live experiments because hardware and bandwidth affect real-world results and repeated crawls can disturb sites or sample different web regions.The in vitro parameter tests used four machines, fixed parsing and DNS threads, configured workbench and sieve sizes, and 90-minute runs.Source: §5 · p. 13, §5.1 · p. 13

5.1. In vitro experiments: BUbiNG

• In the simulated slow-connection test, speed increased linearly with fetching threads until bandwidth saturation, then plateaued without a throughput decrease.The proxy’s 300-thread limit caused the plateau.Source: §5.1 · p. 13, Figure 3 · p. 14
• As IP and host politeness delays increased, the front grew to maintain throughput, while throughput and CPU load remained independent of politeness in the tested range.The host delay was set to eight times the IP delay in Figure 4; these patterns held until network bandwidth saturation.Source: §5.1 · p. 14, Figure 4 · p. 15
• 40,600 pages per second was the average for four BUbiNG agents crawling one billion pages, with essentially the same per-machine speed as a single machine.The authors interpret this as linear scaling with the number of agents.Source: §5.1 · p. 14
• 16,000 pages per second was the average no-I/O speed through 6,000 threads; at 8,000 threads, speed first dipped slightly to 15,300 pages per second.The test processed 100 million pages on a 40-core workstation; the authors attributed the small decrease they observed to context switching and Java garbage collection.Source: §5.1 · p. 14

5.3. In vivo experiments

• 1.2 Gb/s was sustained by one BUbiNG agent crawling the .it domain in the iStella live experiment, with about 85% overall CPU load.The agent ran on a 48-core, 512 GB RAM machine with a 2 Gb/s link.Source: §5.3 · p. 16

5.4. Comparison

• Crawler comparisons depend on the task and measures chosen; ideally they use the same seed, page count, and breadth-first policy, but some crawlers are unavailable.Reported comparisons include literature data and experiments; the paper notes that some collection figures are contradictory and that ClueWeb09 used retired search-engine hardware.Source: §5.4 · p. 16
• BUbiNG’s throughput is reported as several times IRLbot’s and one to two orders of magnitude above Heritrix or Nutch; the authors call it the highest-throughput system in their comparison.They also report that throughput scales linearly by adding agents, making BUbiNG, in their assessment, the fastest publicly available crawling system.Source: §5.4 · p. 17

6. THREE DATASETS

• The three snapshots contain about one billion unique pages each: a .uk crawl capped at 10,000 pages per host, a deep EU crawl capped at 10,000,000, and a worldwide shallow crawl capped at 100.The .uk crawl starts at the BBC site; the EU and worldwide crawls start at europa.eu.Source: §6 · p. 17
• The snapshots support comparisons of crawl depth and site-size limits: the EU crawl’s large host cap was never reached, while the shallow crawl aimed to maximize the number of hosts.The authors use the latter two snapshots to investigate how indegree relates to site size and inter-site connections.Source: §6 · p. 17

6.1. Degreee distribution

• Across the reported datasets, low-depth pages tend to have fewer outlinks but more external links than inner pages, and pages in the shallow snapshot are closer together.The paper reports graph statistics including average outdegree, external outdegree, average distance, harmonic diameter, and reachable-pair percentage.Source: §6 · p. 17, §6.1 · p. 18
• Root pages’ intrahost inlinks largely shape the indegree-distribution tail; the EU snapshot’s curvature indicates a non-power-law distribution, with a fitted p-value below 10^-5.The paper reports sharp degree-rank steps at the 10,000-page .uk and 100-page worldwide host limits.Source: §6.1 · p. 18

6.2. Centrality

• The paper reports top-ten indegree, PageRank, and harmonic-centrality nodes on host and top-level-domain graphs; harmonic centrality identifies sites of interest more often than the other measures in host graphs.The authors report that harmonic centrality is more precise and less prone to spam than indegree or PageRank on these graphs; noise decreases at the TLD level.Source: §6.2 · p. 18

7. CONCLUSIONS

• BUbiNG is orders of magnitude faster than existing open-source crawlers, scales linearly with agents, and is intended as a reliable tool for gathering large datasets.Source: §7 · p. 18
• Its main novel ideas include lock-free data structures for I/O-bound fetching threads, a workbench that selects the next URL in constant time while respecting host- and IP-level politeness, and an on-disk virtualizer for excess URLs.Source: §7 · p. 19
• BUbiNG’s high parallelism also led to enhancements in related software libraries and helped diagnose a regression in the Apache HTTP client.Source: §7 · p. 19
• Planned work includes spam detection, spider-trap handling, politeness throttling based on download times and site branching speed, and integration with distributed storage systems.Source: §7 · p. 19
• URL-level prioritization requires deeper changes to visit states and is left for future investigation; the described priority can be per host and agent, or extended across agents at moderate communication cost.Source: §7 · p. 23
• Integrating user-space fibers is a future direction that might further increase parallelism with the synchronous-I/O design.Source: §7 · p. 23