LimeWire Download Code

Christopher Rohrs

November 13, 2002

This document describes the LimeWire download code, including the algorithms for multisource downloads and automatic requeries. It presumes you are already familiar with LimeWire’s design and its approximate result grouping algorithm. In particular, this document will not describe how TCP connections are accepted or how downloads are presented to the GUI.

1. Groups and Buckets

It is important to make a distinction between groups and buckets. A group is set of search results that are approximately the same. Each search result is represented as an instance of RemoteFileDesc (RFD), which is basically a host/file pair. RFD’s are grouped by TableLineGrouper when they are passed to the GUI.

A bucket, on the other hand, is a set of identical RFD’s. Two RFDs are considered identical if they have the same hash. Furthermore, two RFDs are considered identical if they have the same name and size and don’t have conflicting hashes (i.e., both hashes are null or at least one is null). As we will see, this second rule allows risky swarming from sources without hashes. Bucketing is implemented in the backend by RemoteFileDescGrouper, which ultimately delegates to IncompleteFileManager. This is admittedly confusing, but there is a good reason for it; to ensure that swarming and resuming work properly, we want to ensure that identical RFDs will always get the same incomplete file.

The download method of DownloadManager takes an array of RFDs as an argument and returns a single ManagedDownloader that will attempt to get one of those files. These RFDs need not be similar or same, though this will generally be the case. This means that a ManagedDownloader must manage multiple buckets interally. ManagedDownloader will try one bucket at a time until it completes a download.

When the user selects a number of search results and presses the download button, the GUI constructs a new downloader for each RFD using DownloadManager.download(..). However, any two RFDs in the same group will be passed to a single downloader. Hence a single ManagedDownloader will be created for each selected group, with multiple buckets within each group.

To summarize, grouping and bucketing are independent processes. Grouping happens in the GUI and bucketing happens in the backend. Two files in the same bucket will always be in the same group, though the converse does not hold. This is admittedly confusing. Other vendors do not have approximate matching and hence do not make the similar/same distinction.

2. Swarming

The basic idea behind swarmed (multisource) downloads is to download one file in parallel from multiple servers. For example, one might simultaneously download the first half of book from server A and the second half from server B. This increases throughput if the downstream capacity of the downloader is greater than the upstream capacity of the fastest uploader.

Swarming is encapsulated in ManagedDownloader, which delegates to multiple HTTPDownloader’s, one for each server. To understand this swarming algorithm, it's useful to divide bytes of a file into three categories: black, grey, and white:

• Black regions have already been downloaded to disk.
• Grey regions have been assigned to a download thread but not yet completed.
• White regions have not been assigned to a download thread.

A single IncompleteFileManager instance keeps track of the black regions of all incomplete files. This information is critical to resuming partial incomplete files and is serialized to disk downloads.dat file. (More on that later.) Note that multiple swarmers can write to the same incomplete file; this avoids having to reassemble fragments at the end of the download. IncompleteFileManager also keeps track of the hash associated with the temporary file.

LimeWire uses a “split/steal” swarming algorithm. ManagedDownloader maintains two pieces of information for the current bucket: the list of available white and grey regions and the available locations (RFDs). The controller thread of ManagedDownloader spawns a number of worker threads, each of which does the following in parallel:

1. Remove an RFD from the pool of potential locations for the bucket and establish a TCP connection to the server, using a PUSH message if needed. Abort if connection failed.
2. Atomically do the following:
1. Find a region of the file to download. If there is a white region, claim that. Otherwise steal part of a grey region from another downloader. (More below.) Or if there is no region, give up, first re-adding RFD to the pool of locations.
2. Send an HTTP request for the given region. If the request fails, return the region to the needed list and abort.
3. Download the file by delegating to an HTTPDownloader. Update the needed list if the download terminates prematurely. If it succeeds, re-add the RFD the pool of potential locations.

An important detail is how to pick a grey or white region. For HTTP/1.0 uploaders, a worker steals an entire white region if available, or half a grey region otherwise. The goal here is to minimize the number of requests needed, since each request requires a new HTTP connection. Consider, for example, the simple case of swarming from two hosts. Both threads operate in parallel, but only one thread at a time can execute step (2) above. When the first worker thread connects, it will steal the entire file (a white region) and request it from the uploader. When the second worker thread connects, it will steal half of the first thread’s region (grey) and request it from the second uploader. The first thread will close the connection when it gets halfway through the file, to the surprise of the uploader. The steal/split process may continue if one thread completes before the other.

As of this writing (11/14), the unreleased code on the mainlined treats HTTP/1.1 uploaders differently. For HTTP/1.1, things are somewhat simplified; the worker steals the first N bytes of a white region if possible, or the last N bytes of a grey region otherwise. The chunk size N should be as small as possible without causing undue overhead. (See the discussion on pipelining below.) Note that if two threads A and B are swarming from uploaders of the same speed, the incomplete file will be downloaded in the order ABABAB.... This makes file previews work better, as the file is more or less downloaded from beginning to end. Chunking also lessens—but doesn’t eliminate--problems from a stalled downloader.

LimeWire uses two techniques to detect corruption when downloading. The first is to simply check the hash when the download is complete. This only works if the initial search result had a hash. As a second technique, LimeWire checks overlapping regions of each download chunk. This requires verifying that the bytes being written match the area already on disk. This check is encapsulated in VerifyingFile, which keeps track of the bytes already written to disk. In many ways, VerifyingFile and IncompleteFileManager do the same thing.

3. Pipelined Downloads

One problem with the code described above is that it does not support pipelining for persistent HTTP/1.1 connections. With small chunk sizes, this can reduce throughput on high-latency high-capacity connections. Pipelining is the obvious way of solving this. The idea is to send the request for chunk i+1 before reading the data for chunk i. Assuming that the round-trip time of the connection is less than the time to download a chunk, this maximizes throughput. Here is a simple algorithm for pipelining:

//The interval requested but not yet downloaded. Live across loop.

//Steal interval (if any) and send request.

requested=sendRequest(); //may be null

while (requested!=null) {

read headers UNLESS //chunk i

404 or 503 ==> add requested to needed, close connection, return

queued ==> wait; rerequest; continue

content-range!=requested ==> add part of requested range back to needed

downloading=requested;

requested=sendRequest(); //chunk i+1, may be null

do download(downloading) UNLESS //chunk i

IOException ==> re-add downloading and requested to needed

}

A few things are worth noting:

• The download code must separate the writing of a request from the reading of response headers.
• The downloader has two chunks at any given time. If a download terminates prematurely, it must return both chunks to the needed list.
• The request for chunk i+1 is not written until reading the headers for request i--but not the data for chunk i. This is necessary to make remote queuing work. Otherwise the server might disconnect you for sending requests too quickly.
• The actual download logic must be passed the start offset of the temporary file, since that information has already been consumed from the connection. Alternatively this could be stored in fields of an HTTPDownloader. (See below.)
• LimeWire currently has a provision where a fast downloader can steal an entire region from a stalled downloader. This becomes much more complicated with the above code, as a downloader now has two active regions.

There are several ways of expressing this in the LimeWire code. The above loop needs to be expressed in the connectAndDownload method of ManagedDownloader. The type of the “requested” variable above could either be an Interval or an HTTPDownloader, depending on whether you want to instantiate one HTTPDownloader per request. I recommend a bottom-up approach; first decide on the new interface to HTTPDownloader. At the least, you will need to split the connectHTTP method of HTTPDownloader into sendRequest and readResponse. A key decision is how much state is maintained in HTTPDownloader and how much is passed as parameters. Then you can change the assignAndRequest method of ManagedDownloader to call sendRequest but not readResponse.

4. Requeries and Subclasses

If ManagedDownloader runs out of download locations, it may issue a requery to find more sources. Requeries are dangerous and should be used with extreme care. For this reason, all requeries go through DownloadManager, which limits the global rate that requeries are issued across all downloaders. A ManagedDownloader may requery as often as it likes; DownloadManager will only broadcast one query per T seconds.

ManagedDownloader uses three template methods to control requeries: nextRequeryTime, newRequery, and allowAddition. Three subclasses of ManagedDownloader exist primarily to control this requery behavior. These classes all provide slightly different constructors:

• RequeryDownloader (a.k.a. “wishlist downloader”) is constructed when there are no search results and the user presses the “add to wishlist” button. A RequeryDownloader will continue to issue requeries using the original search keywords. The first results matching the search keywords are downloaded.
• ResumeDownloader (a.k.a “incomplete file downloader”) is constructed when the user presses the “resume” button from the incomplete directory of the library. ResumeDownloader will issue requeries with the name and hash of the selected incomplete file. It will only accept search results that match this incomplete file.
• MagnetDownloader is constructed from MAGNET URIs. MagnetDownloader’s can requery by hash or keyword, and can also provide default locations by faking up RFDs from URLs. In many ways, this downloader is the most powerful.

All requeries have marked GUIDs for data gathering purposes. There is one exception; the very first requery of a ResumeDownloader or MagnetDownloader does not have a marked GUID. Futhermore, DownloadManager does not apply the global throttling rules to these special queries. The rationale is that the user has no search results and needs immediate action.

LimeWire remembers the state of all downloads between sessions in the downloads.dat file of your current directory. This file contains serialized versions of all downloaders plus the IncompleteFileManager. ManagedDownloader has custom writeObject and readObject methods, since things like sockets are inherently unserializable. Be very careful when changing an serializable objects. For example, you may not rename any of the above classes without losing backwards compatibility.