Applications of Tries in Apache Cassandra
summary
Apache Cassandra replaces comparison-based memtables and SSTable indexes with tries and reports concrete wins: about 2x faster random SSTable reads and over 2x sustained memtable write throughput after switching formats (DataStax first, upstream in Apache Cassandra 5). Implementation uses byte-comparable serialization for all column types, chain nodes, variable pointer sizes, page-packed immutable tries with unique-prefix indexes plus small hash bits to avoid disk lookups, 32-byte block nodes with pointer tagging, and removes the special key cache while reducing GC pauses and heap footprint.
AI-written summary · about
chapters (16)
- 0:00Introduction and background
- 1:45Problem of key-based data organization
- 7:03Why tries outperform comparison-based structures
- 10:55Academic research enabling tries in databases
- 12:00Making keys byte-ordered for tries
- 14:52Adapting tries for Cassandra's storage model
- 17:21Optimizing tries for disk efficiency
- 21:15Page packing in immutable tries
- 24:49Performance gains in SS table indexing
- 25:55Optimizing memory tables with fixed blocks
- 29:05Memory efficiency with pointer tagging
- 30:56Comparison of B-trees and improved tries
- 31:17Benchmarking memory table improvements
- 32:40Future plans for merge components
- 33:43Regex and advanced query support
- 34:27Q&A on Bloom filters and tradeoffs
related talks
53mApache Cassandra. Inception - all you need to know
30mApache Cassandra: What’s New and What’s Next
37mPopular Apache Cassandra Problems & How to Fix 'Em
29mCassandra - an introduction
37mMemtable Pluggability and Alternate Memtables (CEP-11 & CEP-19)
35mReplacing Cassandra: A Digital Transformation for the World’s Largest Digital Identity Network
54mEvolving Transactions in Apache Cassandra
40mSpark Analytics on Cassandra Data