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:

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

Proposed Tracks

  • Modern Operating Systems

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

  • Optimizing You: Human Skills for Individuals

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

  • Modern CS in the Real World

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

  • Human Systems: Hacking the Org

    Power of leadership, Engineering Metrics and strategies for shaping the org for velocity.

  • Building High-Performing Teams

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

  • Software Defined Infrastructure: Kubernetes, Service Meshes & Beyond

    Deploying, scaling and managing your services is undifferentiated heavy lifting. Hear stories, learn techniques and dive deep into what it means to code your infrastructure.

  • 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.

  • Developer Experience: Level up your Engineering Effectiveness

    Improving the end to end developer experience - design, dev, test, deploy and operate/understand.

  • 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 without a PhD

    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.

  • Building Predictive Data Pipelines

    From personalized news feeds to engaging experiences that forecast demand: learn how innovators are building predictive systems in modern application development.

  • Modern Languages: The Right Language for the Job

    We're polyglot developers. Learn languages that excel at very specific tasks and remove undifferentiated heavy lifting at the language level.

  • Delivering on the Promise of Containers

    Runtime containers, libraries and services that power microservices.

  • Evolving Java & the JVM

    6 month cadence, cloud-native deployments, scale, Graal, Kotlin, and beyond. Learn how the role of Java and the JVM is evolving.

  • Trust, Safety & Security

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

  • Beyond the Web: What’s Next for JavaScript

    JavaScript is the language of the web. Latest practices for JavaScript development in and out of the browser topics: react, serverless, npm, performance, & less traditional interfaces.