News for hackers. Stuff that matters.
Re:Algorithms Behind Modern Storage Systems by JelteF on Wednesday May 16, 2018 @03:26AM (#17080611)
There's is one important detail that is never fully articulated in this article. It says B-trees are read optimized. This is true, but there's only a big difference for random reads and not sequential reads. Because seeking a key in LSM is relatively expensive, because it has to read multiple indexes. But after this is done, reading the a lot of keys an values from this point on is not expensive (or at least not much more so than in a B-tree). The reason for this is mentioned in the article, which are the SSTables. These allow for quick through the keys, because they are stored on disk in sorted order.
Re:Algorithms Behind Modern Storage Systems by dhd415 on Wednesday May 16, 2018 @07:14AM (#17081477)
LSMs do not guarantee that sequential key/value pairs are stored in the same SSTable so reading "n" k/v pairs, in the worst case, could require seeking through "n" different SSTables. There are datastores that use LSMs such as HBase that provide guarantees on top of LSMs to facilitate efficient range reads and, of course, many LSM compaction algorithms improve range reads, but the basic LSM is optimized only for single k/v reads. That's the reason, for example, why Cassandra doesn't even offer range reads such as "SELECT * FROM mytable WHERE KEY > x AND key < (x + k)".
Re:Algorithms Behind Modern Storage Systems by misframer on Wednesday May 16, 2018 @03:44PM (#17085788)
> That's the reason, for example, why Cassandra doesn't even offer range reads

This is not true. The reason why Cassandra doesn't support that is because of hashing of keys across the cluster -- you'd have to query all shards and merge the results. That has nothing to do with the LSM storage.