7 ms·
How RocksDB Works
- schwartzie 3y agoCongratulations to the author for a remarkably clear, easy-to-follow, and informative post. Excellent technical writing!
- tmulcahy 3y agoAgreed. This is the best explanation of Log-Structured Merge Trees I've seen. I finally feel confident that I understand the concept.
- benjaminwootton 3y agoI was about to post the same. One of the best technical articles I've ever read.
- attrutt 3y agoDamn, there's some astonishing writing skills going on here
- kilotaras 3y ago> To find a specific key, we could use binary search on the SST file blocks. I don't think it's possible except when both key and value are fixed size (which is not the case in the example shown).
- KAdot 3y agoBinary searching SST file blocks is a stretch, I agree. The key-value pairs would need to have a specific shape. Enabling compression makes it completely impossible. I'll remove this from the article, thanks for the feedback!
- dikei 3y agoRocksDB is awesome, though don't use it with regular glibc malloc because it can cause extreme memory fragmentation. Use jemalloc, tcmalloc, or mimalloc: basically any other advance malloc libraries that can effectively reuse memory.
- jeffbee 3y agoThis goes for pretty much every C++ program. I doubt there are any useful programs for which the GNU allocator is optimal.
- dikei 3y agoFor databases maybe. However, most programs do not need to allocate so much memory, so frequently that an allocator become an issue.
- citrin_ru 3y agoglobc malloc works reasonably well if threads are not used (nginx and postgres are examples of apps which don’t rely on threads), but if an app uses many threads on multi core CPU shortcomings of glibc malloc (or advantages of jemalloc) become more obvious, especially if you use some LTS Linux distro with an old glibc.
- nitinreddy88 3y agoI am looking for optimal storage engine(KV) which can store operational telemetry (temporarily) at source node. As we know, operational telemetry is generated frequently and need to merge similar operations frequently (little compaction). Once it reaches good amount of size (100mb), we can transfer it to dedicated time series database engines through various mechanisms. I am struggling to find a fast, write heavy, memory optimal storage for this. RocksDB seems to fit few boxes but there could be much better solution as we don't need deletes/range scans sort of operations. Any suggestions?
- howerj 3y agoYou could store it in a hash and flush it to disk using something like https://en.wikipedia.org/wiki/Cdb_(software) https://en.wikipedia.org/wiki/Cdb_(software), there are a few variants and implementations that might do what you want.
- RhodesianHunter 3y agoAny reason you can't shove it into Kafka?
- deleted 3y ago[deleted]
- dboreham 3y agoParent wants storage at the source node.
- nitinreddy88 3y agoToo many network calls. Technically it's feasible, operationally it's expensive for Telemetry usecase. Ex: Imagine we are capturing API telemetry. If there are 1000 API calls per minute per node, then we will end up somewhere 1000*10 calls per minute to Kafka. It's not efficient.
- chrisjc 3y agoI didn't catch the part where "Parent wants storage at the source node.". So if the goal is to eventually have the timeseries data merged back to a timeseries DB, and latency isn't too much of a concern then wouldn't batch writing to Kafka (Kinesis, etc) be tolerable?
- zip1234 3y agoWell written article--clarification on how Meta uses it though. It is not Tao it is ZippyDb: https://engineering.fb.com/2021/08/06/core-data/zippydb/ https://engineering.fb.com/2021/08/06/core-data/zippydb/
- ckwalsh 3y agoZippy does use it, but I think the author was specifically referring to MyRocks https://myrocks.io/ https://myrocks.io/
- KAdot 3y agoAuthor here. > Well written article Thanks! > It is not Tao it is ZippyDb I don't work for Meta, so might have made a mistake. There is an old blog post[1] about Tao and there is a recent paper[2] mentioning that the graph database is powered by MyRocks, which runs on RocksDB. [1]: https://engineering.fb.com/2013/06/25/core-data/tao-the-power-of-the-graph/ https://engineering.fb.com/2013/06/25/core-data/tao-the-powe... [2]: https://www.vldb.org/pvldb/vol13/p3217-matsunobu.pdf https://www.vldb.org/pvldb/vol13/p3217-matsunobu.pdf
- zip1234 3y agoTIL, didn't realize that it was used as the storage engine for MySQL.
- ipozgaj 3y agoI am lucky enough to have worked on all three of these systems (TAO, ZippyDB, and currently MySQL) so can shed some light here. Both MySQL and ZippyDB are datastores that use RocksDB under the hood, in a slightly different way and with different querying capabilities exposed to the end user. ZippyDB uses it exclusively, but MySQL uses both the traditional InnoDB and RocksDB (MyRocks). TAO is in memory graph database, layer above both of these, and doesn't persist anything by itself - it talks to the database layer (MyRocks).
- eclark 3y ago/wave
- adev_ 3y agoRocksDB is an amazing piece of engineering that deserve to be more known. It is battle tested. It does one job and does it well. I have used it in the past as a middleware database taking an average of 2-3k req/sec with over 400 GB of data stored. It works like a charm. If I had a single reproach to do to it, it would be around the instrumentation. It is not that straightforward to get proper metrics and reporting of the internals.
- jlokier 3y agoOne thing about LSM trees that are implemented with large numbers of large files in a filesystem, such as RocksDB, is that they defer to the filesystem to deal with fragmentation and block lookup isues. That's not actually free. LSM tree descriptions typically imply or say outright that each layer is laid out linearly, written sequentially, and read sequentally for merging. And that looking up a block within a layer is an O(1) operation, doing random access I/O to that location. But really, the underlying filesystem is doing a lot of heavy lifting. It's maintaining the illusion of linear allocation by hiding how the large files are fragmented. That sequential writing is mostly sequential, but typically becomes more fragmented in the filesystem layer as the disk gets closer to full, and over time as various uses of the filesystem mean there are fewer large contiguous regions. More fragmented free space makes the allocation algorithms have to do more work, sometimes more I/O, just to allocate space for the LSM tree's "linear" writes. Lookup of a block inside a layer requires the filesystem to lookup in its extent tree or, with older filesystems, through indirect block lookups. Those are hidden from the LSM tree database, but are not without overhead. Writing sequentially to a layer generally requires the filesystem to update its free space structures as well as its extent tree or indirect blocks. Even a simple operation like the LSM tree database deleting a layer file it has finished with, is not necessarily simple and quick at the filesystem layer. In other words, when analysing performance, filesystems are the unsung heroes underlying some LSM tree databases. Their algorithmic overhead is often not included in the big-O analysis of LSM tree algorithms running over them, but should be, and their behaviour changes as disk space shrinks and over time due to fragmentation.
- vlovich123 3y agoI agree that DB papers will typically overlook the impact the filesystem has on the database (not just rocksdb - what you wrote is true for everything except something like BlueStore). It’s particularly depressing when you look at how they measure write amplification which tends to ignore things they’re just offloading to the filesystem. However, I think you’re making a mistake on a core part of your argument: > More fragmented free space makes the allocation algorithms have to do more work, sometimes more I/O, just to allocate space for the LSM tree's "linear" writes. The file system in no way needs to guarantee on-disk contiguity for read or write performance, nor does any online defrag need to happen. Indeed, the whole premise behind LSM trees is to try to optimize around solid state storage. AFAIK if the filesystem can only find 1 MiB blocks it will allocate them at the cost of a larger set of extents (there’s also defrag happening). Typically the filesystems do a fantastic job of defrag too. That’s certainly an important part but I’d say those parts of the filesystem are likely the first things implemented and never/rarely changed (just a hunch - I haven’t actually bothered looking at the Linux changelog). Also no one is really going to care about performance on an almost full filesystem (kind full like 75% but old so lots of fragments is valid but I doubt it’s actually a problem because of how good filesystems are).
- polishdude20 3y agoHow does flushing in a background process work if it says that it's an embeddable database that's in your application? It says there is no external process so how is there a background process that performs compaction and flushing?
- remram 3y agoIt's a thread: https://artem.krylysov.com/blog/2023/04/19/how-rocksdb-works/#flush https://artem.krylysov.com/blog/2023/04/19/how-rocksdb-works... > RocksDB runs a dedicated background thread that persists immutable memtables to disk. They are using "process" to mean "mechanism", something that happens, not a literal OS process. I agree that it's a bit confusing to use the word both ways.
- jamesatmeetapro 3y agoGreat writing. Looks like it is used extensively in Meta. I heard they even wanted to use it in Cassandra.
- midom 3y agohttps://developers.facebook.com/videos/f8-2018/cassandra-on-rocksdb-at-instagram/ https://developers.facebook.com/videos/f8-2018/cassandra-on-... (there's not much Cassandra now, though)
- willvarfar 3y agoA bit of a tangent, but HNers often have the kind of hands-on experience that's hard to find in internet searches, so I'll ask away :) A long time ago we had a big MySQL tokudb db and were keen to migrate to myrocks. But myrocks put every table into a single big file, rather than a file per partition. The partition-per-file is a big deal if you are retaining N days of data in a DB and every night will be dropping some old day. If your DB stores each partition in separate files, the DB can simply delete them. But if your DB stores all the partitions in a single file, then it will end up having to compact your absolutely massive big dataset. It was completely unworkable for us. Has this changed?
- jorangreef 3y agoHey Will! Joran from TigerBeetle here. Partitioning data across files (or LSM trees) can be a remarkable win. For data retention policies, as well as for exploiting immutability in different workloads to reduce write amplification. For example, in TigerBeetle, a DB that provides double-entry financial accounting primitives, our secondary indexes mutate, but half of our ingest volume, all the transactions themselves are immutable, and inserted in chronological order. We therefore designed our local storage engine as an LSM-forest, putting different key/value types in their own tree, so that mutable data wouldn't compact immutable data. This turns our object tree for primary keys into essentially an append-only log. I did a lightning talk on this, and a few of our other LSM optimizations, at Jamie Brandon's HYTRADBOI conference last year: https://www.youtube.com/watch?v=yBBpUMR8dHw https://www.youtube.com/watch?v=yBBpUMR8dHw RocksDB also allows you to do this, with its concept of column families, if I am not mistaken. However, we wanted more memory efficiency with static memory allocation, deterministic execution and deterministic on disk storage for faster testing (think FoundationDB's simulator but with storage fault injection) and faster recovery (thanks to smaller diffs, with less randomness in the data files being recovered), and also an engine that could solve our storage fault model. All details in the talk. Or ping me if you have questions.
- midom 3y agosomething doesn't make sense here - MySQL/InnoDB does put tables into files, but partitions get separate file. MyRocks has a collection of files per each column family, and when you drop data it can quickly expunge files that don't contain data for other tables/partitions - and trigger compaction on neighbors, if needed.
- almog 3y agoYou might want to also listen to the SE Daily episode with Dhruba and Igor of RockDB, they cover similar aspects of RocksDB in details: https://softwareengineeringdaily.com/2019/02/05/rocksdb-with-dhruba-borthakur-and-igor-canadi/ https://softwareengineeringdaily.com/2019/02/05/rocksdb-with...
- Tim25659 3y agoGreat post on rocksdb