Devising a New Method to Transfer Large Amounts of Data
|
October 21, 2004 -- The availability of high-bandwidth optical networks along with the need to quickly and reliably transfer very large amounts of data with predictable quality of service have given rise to the novel RobuSTore file system within the OptIPuter project at UCSD. The idea behind RobuSTore is to break files into smaller blocks, produce several redundant encoded blocks using erasure coding, and distribute these blocks among many storage sites. The information is retrieved by requesting the encoded blocks from the distributed storage sites in parallel, then decoding them once a sufficient number have been received.
To realize the gains in speed and quality of service for this distributed file system, I needed to implement an erasure coding algorithm with suitable properties. The focus of my research during the Calit² summer undergraduate research program, has been selection, implementation, and improvement of an erasure coding algorithm, called LT Codes, for use with the RobuSTore distributed file system.
LT Codes have many properties that are desirable for RobuSTore. They boast efficient encoding and decoding times, can produce practically limitless encoded blocks, and are relatively simple to implement.
However, there were also problems with LT Codes. Initial implementations ran slower than expected, and the algorithm could not give an absolute guarantee that every encoding would be decodable. Modifying the LT Code implementation to overcome these obstacles became a primary goal of the project.
To address the slow encoding and decoding speeds, I examined program execution traces to find the bottleneck in the system. The traces revealed that repeatedly reading large blocks of data from memory caused severe slowdowns. Once I identified the problem, I rewrote the code to use as few memory operations as possible. In addition, I implemented other small optimizations to take full advantage of the features that our system architecture offered. The result was that the new LT Code implementation ran nearly three times faster, double our initial speed expectations.
The second obstacle was to ensure that every encoding stored by the system could be recovered. Since the LT coding algorithm is a random process, an absolute guarantee is difficult to obtain. I pursued several ideas and implementations, but, while they further reduced the chance of a bad encoding, they did not eliminate it completely.
The solution to the problem was to run a fast, lightweight version of the decoding algorithm during the encoding process. If an encoding was not viable, a new one was created to replace it. Because the memory operations are still a major time cost, the process of checking each encoding and possibly generating a new one is a relatively inexpensive solution.
The final implementation of LT Codes satisfies the key requirements of an erasure code for the RobuSTore model. They are fast, efficient, and guaranteed to be decodable.
In addition, I have done some work to understand the expected performance of RobuSTore using this coding system for different network and computing configurations. It is expected that LT Codes will allow RobuSTore to provide excellent speed and quality of service.
As I conclude my work with erasure coding for this project, other researchers are continuing to develop the necessary interfaces and components to make RobuSTore a fully functional, high-performance file system.