Trie memtables in Cassandra

Download PDF

Abstract

This paper discusses a new memtable implementation for Apache Cassandra which is based on tries (also called prefix trees) and byte-comparable representations of database keys. The implementation, which is already in production use in DataStax Enterprise 6.8 and is currently in the process of being integrated into mainstream Apache Cassandra as CEP-19, improves on the legacy solution in the performance of modification and lookup as well as the size of the structure for a given amount of data. Crucially for Cassandra (a database running under the Java Virtual Machine), it also reduces garbage collection and general memory management complexity by operating on blocks of fixed size in large pre-allocated buffers. We detail the architecture of the solution and demonstrate some of the performance improvements that we have been able to achieve with it.