Line Server, a simple TCP-based server that supplies lines in a file
Given a command-line specified path to a file, the server first takes that file and stores its content (lines of ASCII text) in a file of slotted pages (N-ary storage model), the typical file structure employed by a relational database management system (RDBMS). A single page is taken to be 2 * 4096 (the typical block size of linux file system) = 8192 bytes, with each record (a line of text) corresponding to a slot on the page. The records are filled from the beginning of the page, with its offset and length being stored in its corresponding slot index, written backwards from the end of the page. If only a partial record can be stored, the remaining space is left free and the process begins again on the next page. Each page ends with an integer representing the total number of slots stored on that page. In addition to the records themselves, a directory file of (page, slot) pairs is kept so that a given record can be located in the data file. Since the record id is identical to the line number, the directory information is simply stored sequentially in a file, because the location of that information can be calculated directly given the line number. The slotted page model allows for more efficient data retrieval, because upon reading a given page into memory (with the page size selected to ensure that there are no wasted/partial disk reads), one can cache all of the records on that page because each record corresponds to an offset, length pair in the slot index.
With any system that involves disk reads, it is essential that the system also employ caching in order to minimize the expense of disk I/O operations. For my server, I have chosen to use a fixed-size Redis instance as a cache, with a least-recently-used (LRU) eviction policy when the maximum size is reached. The cache associates a given key (line number) with a hash whose with fields either for the page and slot numbers or the line content itself. On a cache miss, the entire directory page for a given line is loaded into the cache (after being resolved into (line number, (page, slot)) tuples) and then the data page corresponding to the line is also loaded. The two levels of caching improves the efficiency of subsequent reads.
I chose to implement the server as a multi-threaded, synchronous server, mostly because the disk reads are the primary performance bottleneck even for an asynchronous server. The extra logic involved in creating an asynchronous server thus outweighed the potential performance boost. If there were more processing involved with any given request (e.g. something that could be offloaded to another server), an asynchronous server would likely see a performance gain.
For files smaller than available memory (around up to 4GB), the performance will be relatively stable (and fast) as the request rate increases, because after the initial cost of loading all of the file content into the Redis cache, each of the four server threads will be able to run entirely in parallel (no locking/blocking on I/O).
As files get significantly large, however,(i.e. greater than 10GB), the performance of the server will depend largely on the pattern to line requests. If there is good locality to the requests (i.e. line numbers are within a small range of each other), the caching will signficantly boost performance. However, if the requests have low locality, the disk I/O can cause a reasonable amount of blocking and degrade performance. Thus, if the server load is sufficiently low (i.e. there is more time between requests than the time for a disk read), the client will not see a performance hit, but when load is high, it will depend on the actual content of the requests.
Limitations / Potential Improvements:
- Cannot handle files of larger than a single disk (obviously)
- Asynchronous implementation would improve performance, as explained above
- The size of the Redis instance can be tuned / dynamically determined to better utilize available memory
- Chokes on lines longer than BLOCK_SIZE = 8192 bytes
- Mount a second disk and duplicate the data/directory files across the two disks. Allow threads to obtain a lock on either file to do reads
Third Party Libraries and Tools
- StackOverflow (so much!)
- Lots of random Java tutorials and articles on networking
- Papers / Presentations
- Anastassia Ailamaki. "Weaving Relations for Cache Performance"
- Anastassia Ailamaki, David J. DeWitt, & Mark D. Hill. "Data Page Layouts for Relational Databases on Deep Memory Hierarchies"
- Lecture Notes