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

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


  • Modern Operating Systems

    Applied, practical & real-world deep-dive into industry adoption of OS, containers and virtualization, including Linux on.

  • Software Supply Chain

    Securing the container image supply chain (containers + orchestration + security + DevOps).

  • Modern CS in the Real World

    Thoughts pushing software forward, including consensus, CRDT's, formal methods & probabilistic programming.

  • Tech Ethics: The Intersection of Human Welfare & STEM

    What does it mean to be ethical in software? Hear how the discussion is evolving and what is being said in ethics.

  • Optimizing Yourself: Human Skills for Individuals

    Better teams start with a better self. Learn practical skills for IC.

  • Modern Data Architectures

    Today’s systems move huge volumes of data. Hear how places like LinkedIn, Facebook, Uber and more built their systems and learn from their mistakes.

  • Practices of DevOps & Lean Thinking

    Practical approaches using DevOps and a lean approach to delivering software.

  • Operationalizing Microservices: Design, Deliver, Operate

    What's the last mile for deploying your service? Learn techniques from the world's most innovative shops on managing and operating Microservices at scale.

  • Bare Knuckle Performance

    Killing latency and getting the most out of your hardware

  • Architectures You've Always Wondered About

    Next-gen architectures from the most admired companies in software, such as Netflix, Google, Facebook, Twitter, & more

  • Machine Learning for Developers

    AI/ML is more approachable than ever. Discover how deep learning and ML is being used in practice. Topics include: TensorFlow, TPUs, Keras, PyTorch & more. No PhD required.

  • Production Readiness: Building Resilient Systems

    Making systems resilient involves people and tech. Learn about strategies being used from chaos testing to distributed systems clustering.

  • Surviving Uncertainty: Regulation, Risk, and Compliance

    With so much uncertainty, how do you bulkhead your organization and technology choices? Learn strategies for dealing with uncertainty.

  • Languages of Infra

    This track explores languages being used to code the infrastructure. Expect practices on toolkits and languages like Cloudformation, Terraform, Python, Go, Rust, Erlang.

  • Building & Scaling High-Performing Teams

    Building, maintaining, and growing a team balanced for skills and aptitudes. Constraint theory, systems thinking, lean, hiring/firing and performance improvement

  • Evolving the JVM

    The JVM continues to evolve. We’ll look at how languages like Kotlin, Graal, Clojure, and Java are evolving the JDK. Expect polyglot, multi-VM, performance, and more in this track.

  • Trust, Safety & Security

    Privacy, confidentiality, safety and security: learning from the frontlines.

  • JavaScript & Transpiler/WebAssembly Track

    JavaScript is the language of the web. Latest practices for JavaScript development in and how transpilers are affecting the way we work. We’ll also look at the work being done with WebAssembly.