Relational DBs on Key-Value Stores
Over the last several years, we’ve seen the rise of fast, ordered, transactional key-value stores such as leveldb
, rocksdb
, and lmdb
. These are all very cool projects in their own rights, but perhaps even more notable are the projects built on top of them, such as MyRocks, SQLite4, CockroachDB, and Google’s F1.
To better understand how these work, I’ve been hacking together a basic relational database on a key-value store named voodoo. Interestingly, many of the concepts are applicable to everyday usage of a normal SQL database, especially in understanding query plans and indexes.
Starting from the Beginning
A relational database is centered around the concept of a table
, which is comprised of rows
and columns
. Notably, all tables have a column labeled as a primary key
, which is used to uniquely identify each row. In the example users
table below, id
is the primary key
.