One 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.<p>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.<p>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.<p>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.<p>Writing sequentially to a layer generally requires the filesystem to update its free space structures as well as its extent tree or indirect blocks.<p>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.<p>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.
A 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 :)<p>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.<p>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.<p>Has this changed?
I 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.<p>RocksDB seems to fit few boxes but there could be much better solution as we don't need deletes/range scans sort of operations.<p>Any suggestions?
RocksDB 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.
RocksDB is an amazing piece of engineering that deserve to be more known.<p>It is battle tested. It does one job and does it well.<p>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.<p>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.
You might want to also listen to the SE Daily episode with Dhruba and Igor of RockDB, they cover similar aspects of RocksDB in details:
<a href="https://softwareengineeringdaily.com/2019/02/05/rocksdb-with-dhruba-borthakur-and-igor-canadi/" rel="nofollow">https://softwareengineeringdaily.com/2019/02/05/rocksdb-with...</a>
Well written article--clarification on how Meta uses it though. It is not Tao it is ZippyDb:
<a href="https://engineering.fb.com/2021/08/06/core-data/zippydb/" rel="nofollow">https://engineering.fb.com/2021/08/06/core-data/zippydb/</a>
How 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?
> To find a specific key, we could use binary search on the SST file blocks.<p>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).