Information Technology
SliceHash: High-Performance Indexing for Data-Intensive Systems
WARF: P130069US01
Inventors: Srinivasa Akella, Ashok Anand, Aaron Gember-Jacobson
The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing a method that improves access of index data from flash memory by grouping related entries.
Overview
Many data-intensive networked systems rely on high-performance indexes that link pairs of ‘keys’ with storage addresses. These indexes help locate and process large volumes (i.e., terabytes) of data at high speeds. As the volume of data increases, finding content becomes more difficult.
To improve performance, indexes based on solid state drives (SSDs), commonly known as flash memories, have been proposed. However, inflexible designs and performance issues have limited their success.
To improve performance, indexes based on solid state drives (SSDs), commonly known as flash memories, have been proposed. However, inflexible designs and performance issues have limited their success.
The Invention
UW–Madison researchers have developed a high-performance ‘slicing’ method for organizing index data on an SSD such that related entries are located together.
Buffer indexes are used to accumulate hash-type index data for writing to the flash memory. The grouped data is arranged on the flash memory so that entries related to the same hash are clustered for more efficient lookup. Specifically, data is clustered onto flash ‘pages,’ which are read and written in an order than takes advantages of the underlying parallel structure of the flash memory. Small in-memory indexes – such as hash tables, bloom filters or LSH tables – may be used as buffers to resolve slow random writes. When full, they get written to the SSD.
Buffer indexes are used to accumulate hash-type index data for writing to the flash memory. The grouped data is arranged on the flash memory so that entries related to the same hash are clustered for more efficient lookup. Specifically, data is clustered onto flash ‘pages,’ which are read and written in an order than takes advantages of the underlying parallel structure of the flash memory. Small in-memory indexes – such as hash tables, bloom filters or LSH tables – may be used as buffers to resolve slow random writes. When full, they get written to the SSD.
Applications
- Indexing software
- Content management
Key Benefits
- Supports high-performance
- Three-fold improvement in I/O performance for same cost
- Frees memory and compute resources for higher layer applications
- Indexes can be extended to use multiple SSDs in the same system.
- Scales out a sub-linear CPU and memory costs
- Works well under variety of workloads
Additional Information
For More Information About the Inventors
Related Technologies
Tech Fields
For current licensing status, please contact Emily Bauer at [javascript protected email address] or 608-960-9842