10 ms·
In the 8 years since this was written, Log-Structured Merge Trees (the concrete realization of this idea) have basically "won". BigTable, AppEngine, LevelDB, C
by nostrademons 9y ago
In the 8 years since this was written, Log-Structured Merge Trees (the concrete realization of this idea) have basically "won". BigTable, AppEngine, LevelDB, Cassandra, HBase, MongoDB, and several others are all built around them.
There's a powerful hardware trend driving this, namely that disk capacities and write bandwidth are still increasing rapidly, but seek times have basically plateaued. That means that data structures that rely on append-only operations can continue to scale to take advantage of bigger disks, but data structures that rely on disk seeks (eg. B-trees) have hit a bottleneck. Also, as number of cores continues to increase, playback & processing from a sequential log can often be parallelized, but updating your on-disk indexes blocks on I/O.
- gregw134 9y agoI suppose the follow up question is, what will replace this once enterprise SSDs start replacing spinning disks?
- simcop2387 9y agoMy layman's guess is something that combines the two. larger immutable storage using B-Tree's (or similar), and more live data using log structured stuff. With semi-regular promotion of data from log to b-tree and eventual clean-up of data no longer referencable in the b-tree.
- nostrademons 9y agoSSDs have even more unique access patterns - they give you (relatively) fast seek times, there's no particular penalty for random-access vs. sequential usage, but you really want to avoid writes, both to preserve the lifetime of the drive and because mixing reads & writes with a SSD lowers performance. In practice (and I haven't worked in a big corp for a couple years now), I don't see SSDs replacing mechanical disks. Rather, they're being used for different functions. Disks are becoming a data warehouse; they're the new tape, but one that systems can write directly to, without needing scheduled backups. Operational serving is moving toward SSDs and RAM, with a periodic processing step that pulls data off disks and builds a pre-made shard that gets written all at once to the SSD. LSM trees are well-adapted to the data-warehousing part of this, which is why you continue to see big uptake of BigTable/Cassandra/Mongo. On the SSD end...most people are using custom algorithms & data structures, AFAIK, but you're seeing a resurgence of data structures like perfect hashes, bloom filters, and plain old sorted arrays, all of which have great read performance but can't be incrementally updated without rebuilding the whole data structure.
- bogomipz 9y ago>"SSDs have even more unique access patterns - they give you (relatively) fast seek times, SSDs don't have seek times at all as there is no actuator arm and read/write head to "seek" into place in order to read/write data.
- bogomipz 9y agoThis is not a nitpick - the fact that SSDs do not have seek times is an important distinction when discussing storage engines. You might want to read the following by Jay Kreps one of the authors of Kafka, Voldermort and Samza: "SSDs and Distributed Data Systems" >"On traditional hard drives the trade-off between in-place and log-structured storage is a bit of a wash. Write performance for log-structured storage is vastly better, but most applications have more reads than writes. Read performance may be better or worse depending on the details of the implementation (a traditional log-structured merge tree is definitely worse for reads since it does multiple seeks for each uncached read, but hashing variants or SSTables that use bloom filters to avoid unnecessary lookups need not be). However the move to SSDs completely changes this dynamic. Since SSDs have fast seek performance grouping data by key is much less important. ... Here are the facts you need to know about SSDs: They eliminate “seek time” and consequentially make random reads very, very fast"[1] Source: [1] http://blog.empathybox.com/post/24415262152/ssds-and-distributed-data-systems http://blog.empathybox.com/post/24415262152/ssds-and-distrib... Instead of downvoting maybe you could engage in a discussion?
- fizwhiz 9y agoMy guess is that nostrademons was just being somewhat fast and loose with the "seek" terminology. FWIW, your linked snippet by Jay Kreps ends with: > ... Since SSDs have fast seek performance grouping data... Clearly, Jay is aware that there is no "seek time" in SSDs :)
- jorangreef 9y agoThere is "seek time" in SSDs, just as there is "seek time" in RAM. It's just orders of magnitude faster. Some of the principles remain the same across disk, SSD and RAM. Sequential access is usually faster than random ("seek") access. Seek time from a storage point of view just means the lookup latency - the cost of jumping to a random source of data (an area on disk or in memory or in another datacenter). You could think of a hash table lookup as "seek time". It could be attributed to an L1/L2 cache reference, main memory reference, physical disk seek or network roundtrip etc. Just because the concept of "seek time" originated with spinning rust does not mean it must remain there. See: https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832
- hefeweizen 9y agoI found the following link to be an interesting read on the topic: http://codecapsule.com/2014/10/18/implementing-a-key-value-store-part-7-optimizing-data-structures-for-ssds/ http://codecapsule.com/2014/10/18/implementing-a-key-value-s... The author also has a 6-part series on programming for SSDs: here's a more descriptive blog post for general SSD access patterns and optimizations: http://codecapsule.com/2014/02/12/coding-for-ssds-part-5-access-patterns-and-system-optimizations/ http://codecapsule.com/2014/02/12/coding-for-ssds-part-5-acc...
- tayo42 9y agoI came across this a while ago. The discussions I found online seemed to criticize it a bit.
- makmanalp 9y agoWell, there is already a lot of thought that goes into LSM trees on flash storage - check out RocksDB [0] for example, which goes to great lengths to allow the user to deal with Read / Write amplification, a problem specific to flash storage. So I don't think that more SSD adoption will fundamentally change anything. The tradeoff from LSM tree to B-tree, very generally speaking, is more about access patterns: LSM trees lend themselves to insert-heavy workloads because the structure is conceptually just a big array that you very quickly append stuff to the end of without checking the rest of the array. That's the magic of why it's so fast for insertions - there's no overhead. You just ignore the older key/values. When doing a read, you read backwards from the end, reading only the newest values. When you fill your memory budget, you flush your array to a lower layer, removing the duplicate old values. I encourage everyone to read the paper - it's not that arcane, just skip the difficult bits [1]. (nb: the original uses trees at each layer, but people have moved away from that for various reasons of changing hardware, scale, use cases) Another point is that oftentimes these data structures span storage layers (or the "cache hierarchy" as database systems people like calling it) - e.g. you could have an LSM tree that has a top layer fitting in L3, then a bunch more in memory, then the majority of it spilling over to disk. Another example is the Bw-Tree [2], which introduces a mapping table that is a storage-agnostic lookup table that tells you wherever a record is, disk or memory or otherwise, and is smart about paging stuff in and out of memory based on hotness. So is this really one "data structure"? Is it a combo of many? Could we change each layer based on the storage type? It gets confusing. When you squint, a lot of data structures start looking like each other, except for certain details that form the fundamental characteristics. Figure 4 in the Monkey paper [3] is one of my favourite figures ever - their observation is that there is a tradeoff continuum of read and lookup costs, and on one end of that continuum is logs (very easy to append to, hard to find things without searching the whole thing), the other end is a sorted array (very easy to find things with binary search, very hard to append to). This is already pretty cool, but then in the middle are tiered and layered LSM trees. And you can actually tweak the level of tiering and layering to reap the benefits of that tradeoff. Then when you start thinking about how big you want your layers to be, how you want to connect them, etc, you eventually arrive to binary trees, btrees, etc. It's sort of magical how related all the storage structures are. [0] https://github.com/facebook/rocksdb/wiki/rocksdb-basics https://github.com/facebook/rocksdb/wiki/rocksdb-basics [1] https://blog.acolyer.org/2014/11/26/the-log-structured-merge-tree-lsm-tree/ https://blog.acolyer.org/2014/11/26/the-log-structured-merge... [2] https://pdfs.semanticscholar.org/7655/9c6cc259c6ab5baf7bd19dd54bb6c773736a.pdf https://pdfs.semanticscholar.org/7655/9c6cc259c6ab5baf7bd19d... [3] https://stratos.seas.harvard.edu/files/stratos/files/monkeykeyvaluestore.pdf https://stratos.seas.harvard.edu/files/stratos/files/monkeyk...
- wtallis 9y agoLog structured storage only becomes more ubiquitous with SSDs, since this is what they're all doing under the hood of their flash translation layer. The eventual long-term strategy might be open channel SSDs that allow the host system to provide the flash translation layer so that there aren't two log-structured filesystems on top of each other.
- diziet 9y agoMongoDB does not support LSM on any of the production releases of WiredTiger yet (or MMAPv1, to my best knowledge. There is support via MongoRocks (which uses RocksDB via Mongo's swappable engines), but that is Facebook's version of LevelDB
- jorangreef 9y agoRocksDB is an LSM-tree (aka log structured storage).
- w_t_payne 9y agoIt is the easy parallelism that is the key feature here.