SBIR Phase I: A Multithreaded Storage Engine using Highly-Concurrent Fractal Trees

点击翻译按钮获取中文摘要

This Small Business Innovation Research Phase I project will investigate techniques for implementing high-performance databases on multi-core computers by focusing on how to support concurrent activity with provably good thread scheduling in "Fractal Tree" databases. Today's databases suffer from resource imbalances between storage bandwidth, disk-seek rate, and CPU core capacity, leading to underperformance, cumbersome workarounds, and energy inefficiency. The company has developed a high-performance storage engine for MySQL that maintains indexes on live data 100 times faster than traditional engines. The approach employs cache-oblivious Fractal-Tree indexes, which scale with storage bandwidth rather than seek rate, thus addressing the imbalance between bandwidth and disk-seek rate. If successful, this research will produce a database implementation that for each query that either saturates the CPU cores, saturates disk bandwidth, or consumes all of the inherent parallelism in the query.The target market comprises organizations that have very large databases and a workload dominated by insertions and queries. There are many application areas that do not employ databases because their performance is too slow. Orders-of-magnitude speedup for databases can help grow the market. Applications in finance, retail, homeland security, telecommunications, and scientific computing will benefit from high-performance databases. Furthermore the researchers hope to lead all database implementers into the multi-core realm. The proposed research will further the understanding of how to schedule database queries when data is well laid out on disk. As users' appetite for data continues to outstrip the availability of fast memory, organizing multithreaded queries on disk-based data for performance will only grow in importance.