Bio

Ankita Kejriwal is a PhD candidate in the Computer Science department at Stanford University working with Prof. John Ousterhout. She enjoys working on problems in distributed systems. She is building RAMCloud, a low-latency datacenter storage system, along with the rest of her lab. Her recent project, called SLIK, extends a key-value store to enable scalable, low-latency indexes. She interned at MSR-SVC in 2013 with Marcos Aguilera and designed an algorithm for low-latency distributed transactions. Prior to graduate school, she completed her Bachelor in Computer Science at Birla Institute of Technology and Science – Pilani, Goa Campus.

Scalable Low-Latency Indexes for a Key-Value Store

Scalable Low-Latency Indexes for a Key-Value Store

Many large-scale key-value storage systems sacrifice features like secondary indexing and/or consistency in favor of scalability or performance. This limits the ease and efficiency of application development on these systems.

My work shows how a large-scale key-value storage system can be extended to provide secondary indexes in a fashion that is highly scalable and offers ultra low latency access. The architecture, called SLIK, enables multiple keys for each object, and allows indexes to be partitioned and distributed independently of their objects. SLIK represents index B+ trees using objects in the underlying key-value store. It uses an ordered write approach for object updates, which allows temporary inconsistencies between indexes and their objects but masks those inconsistencies from applications. When implemented using RAMCloud as the underlying key-value store, SLIK performs indexed reads in 11 μs and writes in 30 μs; it supports indexes spanning thousands of nodes, and provides linear scalability for throughput. SLIK is also an order of magnitude faster than other state-of-the-art systems.