Synchronized rebuilds slow inserts in learned indexes under concurrency
Synchronized Rebuilds:The Hidden Cost of Concurrent Inserts in Learned Indexes
Databases
Summary
In systems that organize data for fast reading, adding new items at the same time can cause big delays. The authors found that many learned index designs pause and rebuild big data blocks simultaneously, causing slowdowns and sometimes losing data. They tested common fixes and discovered that rebuilding data in the background or using short-term buffers reduces delays and improves performance, even with millions of entries and multiple processor cores.
What this means in practice
- •For database engineers: Optimize high-concurrency write systems by applying background rebuilds and temporary buffers to reduce insert latency spikes in learned indexes.
- •For distributed storage developers: Implement improved node rebuild techniques to maintain data integrity and reduce blocking during concurrent inserts at scale.
Authors
Emmilly Immaculate Namuganga, Laurent Bindschaedler
Abstract
Nine years after learned indexes were proposed, their advantage on read-mostly data is well established, and a standard benchmark rates their best concurrent version as almost ready for use. Across more than 4000 runs of 13 indexes, we find that each design pays for concurrent inserts in a different way. Gapped-array indexes rebuild their nodes in synchronized bursts, at positions that follow from three constants in the source. Model-placement indexes use three to four times the memory, buffered indexes take two to three times as long. Three of five concurrent learned indexes lost keys or stopped making progress. Standard benchmarks miss both the bursts and the lost keys. The bursts cost far more than in B-trees because each rebuild copies a node a thousand times larger than a page and, under concurrency, blocks every operation that reaches the node. The typical B-tree fix of randomizing node density only spreads the bursts out,while smaller nodes trade them for longer run times at scale. Two standard systems techniques remove them: a buffer that exists only while a node is rebuilt, and background rebuilds.We show that on 400M real keys, these techniques reduce the number of inserts whose latency exceeds 100$μ$s by two orders of magnitude at one thread, and by one at sixteen when spare cores run the background threads, at a third to half the run time of the buffered designs.