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

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

  • Monday, 16 November

  • Operating Microservices

    Building and operating distributed systems is hard, and microservices are no different. Learn strategies for not just building a service but operating them at scale.

  • Distributed Systems for Developers

    Computer science in practice. An applied track that fuses together the human side of computer science with the technical choices that are made along the way

  • The Future of APIs

    Web-based API continue to evolve. The track provides the what, how, and why of future APIs, including GraphQL, Backend for Frontend, gRPC, & ReST

  • Resurgence of Functional Programming

    What was once a paradigm shift in how we thought of programming languages is now main stream in nearly all modern languages. Hear how software shops are infusing concepts like pure functions and immutablity into their architectures and design choices.

  • Social Responsibility: Implications of Building Modern Software

    Software has an ever increasing impact on individuals and society. Understanding these implications helps build software that works for all users

  • Non-Technical Skills for Technical Folks

    To be an effective engineer, requires more than great coding skills. Learn the subtle arts of the tech lead, including empathy, communication, and organization.

  • Tuesday, 17 November

  • Clientside: From WASM to Browser Applications

    Dive into some of the technologies that can be leveraged to ultimately deliver a more impactful interaction between the user and client.

  • Languages of Infra

    More than just Infrastructure as a Service, today we have libraries, languages, and platforms that help us define our infra. Languages of Infra explore languages and libraries being used today to build modern cloud native architectures.

  • Mechanical Sympathy: The Software/Hardware Divide

    Understanding the Hardware Makes You a Better Developer

  • Paths to Production: Deployment Pipelines as a Competitive Advantage

    Deployment pipelines allow us to push to production at ever increasing volume. Paths to production looks at how some of software's most well known shops continuous deliver code.

  • Java, The Platform

    Mobile, Micro, Modular: The platform continues to evolve and change. Discover how the platform continues to drive us forward.

  • Security for Engineers

    How to build secure, yet usable, systems from the engineer's perspective.

  • Wednesday, 18 November

  • Modern Data Engineering

    The innovations necessary to build towards a fully automated decentralized data warehouse.

  • Machine Learning for the Software Engineer

    AI and machine learning are more approachable than ever. Discover how ML, deep learning, and other modern approaches are being used in practice by Software Engineers.

  • Inclusion & Diversity in Tech

    The road map to an inclusive and diverse tech organization. *Diversity & Inclusion defined as the inclusion of all individuals in an within tech, regardless of gender, religion, ethnicity, race, age, sexual orientation, and physical or mental fitness.

  • Architectures You've Always Wondered About

    How do they do it? In QCon's marquee Architectures track, we learn what it takes to operate at large scale from well-known names in our industry. You will take away hard-earned architectural lessons on scalability, reliability, throughput, and performance.

  • Architecting for Confidence: Building Resilient Systems

    Your system will fail. Build systems with the confidence to know when they do and you won’t.

  • Remotely Productive: Remote Teams & Software

    More and more companies are moving to remote work. How do you build, work on, and lead teams remotely?