6 ms·

I suppose the follow up question is, what will replace this once enterprise SSDs start replacing spinning disks?

simcop2387 9y ago
My 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 ago
SSDs 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 ago
    This 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 ago
      My 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 ago
        There 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
- mattb314 9y ago
  Do you think you could point me towards a source for "mixing reads & writes with a SSD lowers performance"? This seems reasonable, but I've never actually heard it before, and a cursory googling didn't turn much up. I have heard before that small, random writes on SSDs are much more expensive than sequential writes because random writes can produce write amplification and increase fragmentation. It was my impression that SSDs stand to benefit significantly from log structured filesystems despite the mixed read/write load, but I don't follow it that closely and could be wrong.
  - noahdesu 9y ago
    https://www.usenix.org/conference/atc14/technical-sessions/presentation/skourtis https://www.usenix.org/conference/atc14/technical-sessions/p...
    - mattb314 9y ago
      Thanks! This talk is pretty cool. In case anyone else is interested, in addition to the above video, this [1] paper goes into some of the details, including this explanation: "Reads and writes on SSDs can interfere with each other for many reasons. (1) Both operations share many critical resources, such as the ECC engines and the lock-protected mapping table, etc. Parallel jobs accessing such resources need to be serialized. (2) Both writes and reads can generate background operations internally, such as readahead and asynchronous write-back [6]. (3) Mingled reads and writes can foil certain internal optimizations. For example, flash memory chips often provide a cache mode [2] to pipeline a sequence of reads or writes. A flash memory plane has two registers, data register and cache register. When handling a sequence of reads or writes, data can be transferred between the cache register and the controller, while concurrently moving another page between the flash medium and the data register. However, such pipelined operations must be performed in one direction, so mingling reads and writes would interrupt the pipelining." Also relevant to the "seek" conversation below: it turns out many SSDs have read-ahead caches built in, so sequential reads are much faster than random reads after an initial warm-up, just like hard disks (the difference, however is closer to ~5x than to 100x difference you see in HDDs). [1] http://bit.csc.lsu.edu/~fchen/publications/papers/hpca11.pdf http://bit.csc.lsu.edu/~fchen/publications/papers/hpca11.pdf
- dom0 9y ago
  > there's no particular penalty for random-access vs. sequential usage This is not really accurate; random access has a penalty compared to sequential access (that's just the physics of it folks™) — the unique characteristic would be that SSDs have more channels*banks than e.g. RAM, which has similar characteristics regarding access patterns. Thus, SSDs achieve close to sequential throughput with large numbers of independent random reads (i.e. high queue depth).
  - cat199 9y ago
    SSDs achieve close to sequential throughput ^ potato =~ potato
hefeweizen 9y ago
I 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 ago
  I came across this a while ago. The discussions I found online seemed to criticize it a bit.
makmanalp 9y ago
Well, 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 ago
Log 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.

My 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 ago

SSDs 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 ago
  This 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 ago
    My 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 ago
      There 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
mattb314 9y ago
Do you think you could point me towards a source for "mixing reads & writes with a SSD lowers performance"? This seems reasonable, but I've never actually heard it before, and a cursory googling didn't turn much up. I have heard before that small, random writes on SSDs are much more expensive than sequential writes because random writes can produce write amplification and increase fragmentation. It was my impression that SSDs stand to benefit significantly from log structured filesystems despite the mixed read/write load, but I don't follow it that closely and could be wrong.
- noahdesu 9y ago
  https://www.usenix.org/conference/atc14/technical-sessions/presentation/skourtis https://www.usenix.org/conference/atc14/technical-sessions/p...
  - mattb314 9y ago
    Thanks! This talk is pretty cool. In case anyone else is interested, in addition to the above video, this [1] paper goes into some of the details, including this explanation: "Reads and writes on SSDs can interfere with each other for many reasons. (1) Both operations share many critical resources, such as the ECC engines and the lock-protected mapping table, etc. Parallel jobs accessing such resources need to be serialized. (2) Both writes and reads can generate background operations internally, such as readahead and asynchronous write-back [6]. (3) Mingled reads and writes can foil certain internal optimizations. For example, flash memory chips often provide a cache mode [2] to pipeline a sequence of reads or writes. A flash memory plane has two registers, data register and cache register. When handling a sequence of reads or writes, data can be transferred between the cache register and the controller, while concurrently moving another page between the flash medium and the data register. However, such pipelined operations must be performed in one direction, so mingling reads and writes would interrupt the pipelining." Also relevant to the "seek" conversation below: it turns out many SSDs have read-ahead caches built in, so sequential reads are much faster than random reads after an initial warm-up, just like hard disks (the difference, however is closer to ~5x than to 100x difference you see in HDDs). [1] http://bit.csc.lsu.edu/~fchen/publications/papers/hpca11.pdf http://bit.csc.lsu.edu/~fchen/publications/papers/hpca11.pdf
dom0 9y ago
> there's no particular penalty for random-access vs. sequential usage This is not really accurate; random access has a penalty compared to sequential access (that's just the physics of it folks™) — the unique characteristic would be that SSDs have more channels*banks than e.g. RAM, which has similar characteristics regarding access patterns. Thus, SSDs achieve close to sequential throughput with large numbers of independent random reads (i.e. high queue depth).
- cat199 9y ago
  SSDs achieve close to sequential throughput ^ potato =~ potato

hefeweizen 9y ago

I 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 ago
I came across this a while ago. The discussions I found online seemed to criticize it a bit.

makmanalp 9y ago

Well, 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 ago

Log 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.