6 ms·

Way back in my final year undergrad project, I put together a LSM-based filesystem that was write-optimised. I even thought that I had invented the notion of an

Way back in my final year undergrad project, I put together a LSM-based filesystem that was write-optimised. I even thought that I had invented the notion of an LSM tree, but the original LSM tree paper pre-dated my invention by 3 years. I applied to take the idea and run with it for a PhD afterwards, but no joy. The criticism of LSM on the FAQ that it can't have as good read performance is perhaps a little over-egged. A fair proportion of the work I did on my project was on how to optimise the read performance. The biggest problem with a LSM tree was working out which level of the hierarchy your entry was in, which involves looking in one, then the next, until you find it. When your data is larger than your RAM, then this becomes a disc access for each level. I was working on structures that could be very small and answer that, so they were more likely to fit in RAM. The other difference between an LSM and a B-epsilon tree is that with an LSM, the merging is done in bulk as a single operation, whereas with a B-epsilon tree it is done on a node-by-node basis as the node buffers fill up. Therefore an LSM could potentially perform more of its housekeeping in long sequential disc operations than a B-epsilon tree, which is likely to have a more random-access pattern.

vlovich123 5y ago
Random access patterns don’t matter so much for SSDs which is where LSMs make the most amount of sense if I recall correctly.
- skyde 5y ago
  This is not completely true. LSM does not just convert random write into sequential write. It also reduce the number of write IO when the dataset is larger than memory. With B-tree inserting a random entry require reading all b-tree page from disk until the right page is found then writing the updated page (4KB) back to disk. While in LSM if you are trying to add a new entry that is 300byte you only need to append 300 bytes to the top level file on disk.
  - vlovich123 5y ago
    Right. So it's more a problem of data dependency than it is with the access being random/sequential. Eg. if LSM needed to do 1 large sequential read & then jump around in RAM the same way, it would still largely have the same basic problem, no?
    - skyde 5y ago
      With LSM (leveldb, rocksdb) its just a different tradeoff. LSM Write are faster than b-tree (half write amplification) while B-tree read are faster than LSM. Reason is because with a warm cache B-tree requires at most one disk read per query since internal nodes will be in cache but for LSM you need one Read per Level. This advantage disappear if you don't have enough memory to cache all internal nodes. Another advantage with LSM is it only does half the space amplification as a B-tree. This is because all level except the top level contain long run of sorted data that compress very well. In a b-tree page are small and most page are not full and you need to store metadata in each page.

vlovich123 5y ago

Random access patterns don’t matter so much for SSDs which is where LSMs make the most amount of sense if I recall correctly.

skyde 5y ago
This is not completely true. LSM does not just convert random write into sequential write. It also reduce the number of write IO when the dataset is larger than memory. With B-tree inserting a random entry require reading all b-tree page from disk until the right page is found then writing the updated page (4KB) back to disk. While in LSM if you are trying to add a new entry that is 300byte you only need to append 300 bytes to the top level file on disk.
- vlovich123 5y ago
  Right. So it's more a problem of data dependency than it is with the access being random/sequential. Eg. if LSM needed to do 1 large sequential read & then jump around in RAM the same way, it would still largely have the same basic problem, no?
  - skyde 5y ago
    With LSM (leveldb, rocksdb) its just a different tradeoff. LSM Write are faster than b-tree (half write amplification) while B-tree read are faster than LSM. Reason is because with a warm cache B-tree requires at most one disk read per query since internal nodes will be in cache but for LSM you need one Read per Level. This advantage disappear if you don't have enough memory to cache all internal nodes. Another advantage with LSM is it only does half the space amplification as a B-tree. This is because all level except the top level contain long run of sorted data that compress very well. In a b-tree page are small and most page are not full and you need to store metadata in each page.