A New Radix-Tree Based Memory Storage Engine
Talkat FoundationDB Summit 2019 · on Monday, 2019-11-18· at 11:20· Grand Ballroom 8, Marriott Marquis San Diego Marina·
summary
A radix-trie based in-memory engine for FoundationDB replaces the BST and cuts per-process memory by about 25% less memory on Wavefront workloads and ~20% on Wikipedia titles, while reducing node-to-KV ratio from 2.2 to 1.3. Implemented on a 6-node test cluster with murmur-hash sharding, optimizations include separating leaf/internal layouts, replacing std::map with vectors, bitfields for metadata, inline string storage and a small-node adaptive layout (capacity 3); node sizes drop to 56/64 bytes but read latency rises due to key reconstruction.
AI-written summary · about
chapters (28)
- 0:00Introduction
- 0:14Agenda
- 0:55Key Container
- 2:25Motivation
- 2:53Prefix Compression
- 4:02Demo
- 5:33Advantages
- 6:46Optimization
- 6:57Test Environment
- 7:13Test Cluster Configuration
- 7:46Memory Usage Gap
- 8:07Key Format
- 8:20Registry
- 8:53Bottom Line
- 9:15Node Structure
- 9:32Optimizations
- 10:29Data part
- 11:19Inline data
- 12:04Adaptive registry
- 12:18Internodes
- 13:10Value
- 14:27Key Smile
- 14:46Summary
- 15:18Performance results
- 15:45Total Memory Usage
- 16:01Histogram
- 16:22Wikipedia Title Benchmark
- 17:00Thank you
related talks
26mFuture of FoundationDB Storage Engines
15mImproving Performance of Flash Based Key-Value Stores Using Storage Class Memory...
22mSolving Everyday Data Problems with FoundationDB
17mArctic: A Practical Lock-Free Adaptive Radix Tree
26mRunning FDB at scale at Wavefront
01h 07mEmerging Embdedded Memories and Storage
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
50mPostgreSQL meets ART - Using Adaptive Radix Tree to speed up vacuuming