You won’t believe how we efficiently exported a billion rows!

Sudarshan Muralidhar
Oct 30 · 7 min read

Shipping metadata to the cloud with log-structured merge trees

This article is part of a series about building Igneous Data Discover, a searchable file index. Click Here for the overview.

Image for post
Image for post
Go to the first post in this series for an overview of this diagram

Transferring Metadata to the Cloud

As you may imagine, it’s nontrivial to move metadata about a billion files from our VM to a compute node. To do so efficiently, we’ll need to carefully choose a strategy that allows for fast transfer, in order to keep up with the speed of our scan. At the same time, we need the metadata to end up in sorted order on the cloud, because it must be sorted to build a search index.

Log-Structured Merge Trees

We decided to use a variant of the log-structured merge (LSM) tree, a data structure that, thanks to its internal layout, provides the performance characteristics we need. While LSM trees are not the only tool for the job (and may not even be the best, depending on exact needs), they meet our requirements. We’d already invested the time into implementing a highly optimized LSM Tree for our backup and Data Flow applications, so we were able to adapt our existing libraries for this new purpose.

Inserts

An LSM tree works because it’s a hybrid of the two approaches we explored above. It consists of two components — a small sorted list held in memory, and a pyramid-like structure stored on disk. Conceptually, the pyramid structure consists of a series of sorted layers, stacked on top of each other.

Image for post
Image for post
https://tenor.com/view/reverse-funnel-gif-9554341 — “It’s Always Sunny in Philadelphia”
Image for post
Image for post
An in-memory list reaches its maximum size k, and then is sent to the cloud where it becomes Layer 0
Image for post
Image for post
A second in-memory list reaches its maximum size, and becomes Layer 1 in the cloud structure

Compaction

Like a plate in a buffet, an LSM tree can only have so many layers piled onto it before it causes serious problems for you later. If we kept adding layers, we’d end up with N/k total layers at the end — which would again require a long post-processing phase to process and merge. So, we merge layers as we go in a process called compaction.

Image for post
Image for post
When we get too many layers, adjacent layers are merge-sorted together to form a new, larger layer
Image for post
Image for post
L0 is much larger and much less frequently touched then L3
Image for post
Image for post
The larger numbers in 2048 are like the bottom layers of an LSM tree

Reading

Because we have multiple layers, looking up specific values in an LSM tree is a little more expensive than if we had a single sorted list. To find the value for a particular key, we need to check each layer until we find what we’re looking for.

Nerd For Tech

From Confusion to Clarification

Sudarshan Muralidhar

Written by

Software engineer at Igneous. Cofounder of Upbeat Music App. I do cloud things.

Nerd For Tech

We are tech nerds because we believe in reinventing the world with the power of Technology. Our articles talk about some of the most disruptive ideas, technology, and innovation.

Sudarshan Muralidhar

Written by

Software engineer at Igneous. Cofounder of Upbeat Music App. I do cloud things.

Nerd For Tech

We are tech nerds because we believe in reinventing the world with the power of Technology. Our articles talk about some of the most disruptive ideas, technology, and innovation.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store