Name
Abstract | ||
|---|---|---|
ABSTRACTLow memory footprint and tail latency are important in indexing for data management systems. Learned indexes have been gaining popularity in recent years due to their low memory overhead, and adaptability to fluctuations in workloads. However, state-of-the-art learned indexes are optimized for read-heavy workloads where the key access distribution is relatively stable, and thus exhibit high tail latency for insertions. Our main observation is that high insertion tail latency stems from structural modification operations in the index, such as node expansions and splits. Based on this insight, we propose a new tail-latency optimized learned index we call TONE. TONE has a novel node layout for leaves and adaptable policies for triggering structural modification operations. Moreover, TONE provides a shard-based mechanism to boost parallelism, while minimizing contention. We evaluate the insertion tail-latency and overall throughput of TONE and provide a comprehensive comparison to state-of-the-art indexes such as skiplists (used in RocksDB) and existing learned indexes. We show that TONE reduces the 99p write tail-latency up to one order of magnitude and has a low memory use. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1145/3503646.3524295 | European Conference on Computer Systems |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yong Zhang | 1 | 0 | 0.34 |
| Xinran Xiong | 2 | 0 | 0.34 |
| Oana Balmau | 3 | 0 | 0.34 |