Abstract Filesystems for Streaming Databases

Workloads for high-performance streaming databases often contain many writes of small data blocks (for example, of metadata) followed by large subrange queries. Most of today’s file systems and databases either cannot provide adequate performance for the write phase, the read phase, or both. The supercomputing technologies group at MIT CSAIL has been investigating cache-aware and cache-oblivious data structures for disk-resident streaming data. We investigated the cache-aware buffered repository tree (BRT). A BRT with a block size of B can theoretically perform a write in time O((log B n) / √ B), as compared to B-tree’s O(log B N), and can perform reads only a constant factor slower than the B-tree. We implemented a prototype of a cache-aware streaming B-tree. For 1megabyte blocks the streaming B-tree achieves a 230-fold speedup for random insertions, at a cost of slowing down serial insertions by factor of 6. Preliminary measurements on the SSCA#3 IO benchmark show a 1.4-fold speedup using stream B-trees instead of standard B-trees. We have also designed a cache-oblivious data structure called the cache-oblivious lookahead tree, which should be able to achieve similar bounds without requiring us to tune for the block size. 1