You are viewing content from a past/completed QCon

Presentation: Algorithms Behind Modern Storage Systems

Track: Modern CS in the Real World

Location: Pacific LMNO

Duration: 2:55pm - 3:45pm

Day of week: Monday

Slides: Download Slides

Level: Advanced

Persona: Backend Developer

Share this on:

This presentation is now available to view on

Watch video with transcript

What You’ll Learn

1. Hear about storage solutions, which are optimized for read or for write, which fits better various databases.

2. Learn about B-trees and LSM-trees, what they are and what are the benefits of using one over the other

3. Find out how to evaluate various storage systems to see which one fits better for the problem at hand.


In the world of Big Data, it’s important to know how the Storage Systems work in order to be able to pick a right tool right job. The talk covers modern storage system approaches, discussing storage internals, and evaluation techniques to choose a database with with the optimal read, write or memory overhead, best suitable for your data.


What's the focus of the work that you're doing today?


I can tell you about Apache Cassandra and the patches I was working on recently. In Apache Cassandra, I've been recently working on transaction replication. Before that, I was working on SASI, an implementation of secondary indexes, on the commit log and on various storage and consistency related things. I had a chance to work on most of the Apache Cassandra subsystems. In Cassandra (or in Apache projects in general) people often don’t specialize (meaning that you work not only on one small subsection of it but you work on the project as a whole). There are few people who specialize on complex subsystems like compaction or other things but it's not very often. Usually, you get to work on the database as a whole. And this was pretty much what I was lucky enough to do.


What are you going to focus on in your talk?


I'm going to focus on the distinction between the two storage types that I think are most prevailing at the moment: immutable and mutable storage. It seems to be that over the years, as the storage systems evolved, database community concentrated more on the mutable storage (the storage which was more suitable for spinning disks, like B-trees). Right now, people tend to move to something that is working slightly better for SSDs (meaning LSM-trees).

The main subject of the talk is going to be to describe what the B-trees (or B+-trees) are, what LSM-trees are, and then to give a rule of thumb to evaluate any paper that you can read. There are algorithms which are trying to optimize for the read, others for the write, and there are ones which are trying to optimize for storage overhead. I'm going to include several metrics to use in order to find a good balance between these three things: read optimization, write optimization, and storage overhead.

I’ll evaluate the two storage systems that I've been describing over the whole talk and summarize of what we've been discussing.


So is this talk really all about LSM trees?


Even though Cassandra is using LSM-trees it doesn't mean that I'm going to bash on B-tree storage. First of all this is not the point of the talk and second you can't really say that LSM-trees are superior to B-trees or vice versa. They are used for different purposes, in different databases, maybe even at different times. So it's just going to be a summary for people's understanding rather than make them all fans of whatever was picked for the Apache Cassandra.


It this an academic talk or a practical talk?


I will try to be more practical. I’ll include details on why people are picking a certain block size, why compaction is important in LSM-trees, what sort of maintenance you should be aware of in B-trees, things like that. I will try my best to include as many practical details as it is possible without sacrificing precision. The main part of the talk is describing what these data structures are, because knowing the tradeoffs without knowing how it actually works might be even less useful than the other way around. I will try to keep the balance but will do my best to include as many practical details as possible.


To better understand this discussion, is there anything that you would recommend to jumpstart the audience?


There are three papers that I would recommend to anyone regardless of their job description, seniority, years of work in the industry, and the databases they are currently using. One of them is Ubiquitous B-trees by Douglas Comer, which summarizes the B-trees techniques, and the second paper is the "LSM paper" which is the Log-Structured Merge Trees. As a summary, I’ll also talk about the RUM Conjecture. These three papers would be ideal, maybe not read all the details but at least get the general idea. As a general overview, you can check out my ACM article on the subject that covers some things I’ll be talking about:

Speaker: Oleksandr Petrov

Apache Cassandra Committer, Distributed Systems Engineer

Alex Petrov is an infrastructure engineer and Apache Cassandra committer. He is interested in storage, distributed systems, and algorithms.

Find Oleksandr Petrov at

Last Year's Tracks