4 ms·

I did not read the paper yet, but COW btrees are interesting for practical reasons since it is possible to update the tree just writing in append-only mode, tha

by antirez 16y ago

I did not read the paper yet, but COW btrees are interesting for practical reasons since it is possible to update the tree just writing in append-only mode, that is nearly the only way to avoid fsync (or alike) but still avoiding trivial corruptions (the new root node is always written at the end of the update). Otherwise you either use fsync as a write barrier or live with the problem that from the OS to the disk itself writes reordering can corrupt very easily your data structure in the event of a crash. However I think that the real problem here is not at the algorithmic level, but at OS API level: just a provocation, don't you think that in the era of SSD drives where seeks are cheap is strange we resort to append only data structures?

tjarratt 16y ago
You raise a good point w.r.t. SSD drives, but the reality is that even if most computers being manufactured today included a solid state drive, the vast majority of consumers are using drives with moving parts. It will be at least a few more generations of hardware before OS-level developers will be able to focus specifically on the features of solid state drives when designing the filesystem and main OS APIs. That said, there is room for someone to develop a filesystem API designed with solid state in mind, or even an entire OS, but I don't know if there would be enough of a market to make that development worthwhile. Is there Anything about SSDs that interests you, from the perspective of the future of Redis?
- sigil 16y ago
  > That said, there is room for someone to develop a filesystem API designed with solid state in mind... What about the Journalling Flash Filesystem? It's been around for quite some time. http://en.wikipedia.org/wiki/JFFS2 http://en.wikipedia.org/wiki/JFFS2
  - tjarratt 16y ago
    Someone more knowledgable might want to correct me here, but I think JFFS2 arrived a little too early; the performance gains are not enormous and it suffers from too many disadvantages (namely performance with small blocks and apparently determining free space??). LogFS is yet another file system designed for larger solid state drives (on the order of gigabytes instead of megabytes), and seems to be a step in the right direction. http://en.wikipedia.org/wiki/LogFS http://en.wikipedia.org/wiki/LogFS
    - sigil 16y ago
      > LogFS stores the inode tree on the drive; JFFS2 does not, which requires it to scan the entire drive at mount and cache the entire tree in RAM. For larger drives, the scan can take tens of seconds and the tree can take a significant amount of main memory. Interesting. I've only used JFFS2 on embedded systems like OpenWRT routers, where you wouldn't see the large drive penalty.
    - dfox 16y ago
      JFFS2 is intended to be used on raw controller-less flash an thus have to solve many problems that are more efficiently done in hardware. So it's probably only useful in embedded systems. Running normal filesystem on raw flash is good way to make it unusable in few days of light use. In fact, JFFS2 works by scanning all the storage on mount and having it all in RAM, that causes it's problems with large volumes (slow mounts and also large memory use). In embedded systems, for which it is intended, mounting the volume is rare operation and volumes are generally small, also typical embedded systems running linux has more RAM than Flash.
  - wladimir 16y ago
    JFFS(2) is aimed at embedded devices that directly access flash chips. With a controller in between, such as with SSD, which performs wear leveling and other tricks to emulate a real harddrive, it might even be hurtful to performance. I'm not sure about LogFS.
  - nitrogen 16y ago
    I don't know much about the technical details of JFFS2, only that it takes forever to mount after an unclean shutdown and runs painfully, painfully slow on larger flash volumes (i.e. >512MB) as they approach capacity. I wrote a tutorial (mostly so I could remember how to do it myself) for converting a SheevaPlug from JFFS2 to UBIFS because of the performance difference: http://nitrogen.posterous.com/converting-a-sheevaplug-from-jffs2-to-ubiubif http://nitrogen.posterous.com/converting-a-sheevaplug-from-j...
  - wazoox 16y ago
    NILFS2 probably is a much better candidate : http://www.nilfs.org/en http://www.nilfs.org/en
- wladimir 16y ago
  I think you underestimate how serious OS vendors are taking the quickly growing popularity of SSD drives. A lot of work has already been done on OS/filesystem level just for SSD drives, for example to support TRIM. Sure, it will be a long time (if ever! likely, mechanical drives will remain important for bulk storage) before filesystem developers focus solely on SSD drives, but SSD performance is already very important.
crux_ 16y ago
I don't think append-only has much to do with seek time [1]; as you said, it has to do with corruption & consistency. Second, they actually tout that their data structure is better on SSDs than btrees (due to block-size obliviousness): > One major advantage is that they are naturally good candidates for SSDs, where a large asym- metry in read/write block sizes makes life very hard for B-trees. In contrast, the arrays making up the SDA can be written with extremely large effective block sizes. Footnote in edit: [1] in the case of search trees; for large objects that will be read front-to-back it does become a seek-time issue.
- andytwigg 16y ago
  SSDs are typically great at random reads, but not so good at random writes, particularly when you start rewriting the device (see http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-for-each-other/ http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-...). The attraction of append-only structures is in alleviating the random writes; but you still need to be careful. For example, CoW trees and log file systems often have a big space blowup, which translates into a slowdown in insert rate, and potentially random IO in the log cleaner/GC. That's a scenario in which the Stratified B-tree does a lot better.
soamv 16y ago
I have also not yet read the paper, but to your point about SSDs -- SSDs are definitely good for random reads, but for random writes, it seems like having an append-only structure would help avoid write amplification. If you do a lot of small random writes to an SSD that will be slow and reduce the disk's life drastically. (That said, I'm no SSD expert, so I might be way off)
hristov 16y ago
Actually using append only writing is very helpful for SSD drives. Overwriting a particular piece of data is very tricky for flash drives. In fact, underneath the hood, flash drives use append only even when you are trying to overwrite something. For example, if you want to overwrite a byte at location X, the flash drive actually writes the new data at a different location Y and uses logical mapping to have the byte at location Y pretend it is the byte at location X. The initial byte at location X will eventually be "recycled" and initialized. Since Flash does append only writing under the hood anyways, it is a better idea to do append only explicitly so that you get the advantages of append only (e.g., the ability to revert to older versions).
speleding 16y ago
The paper actually explains why their new algorithm also works better on SSDs.

by antirez 16y ago

tjarratt 16y ago

You raise a good point w.r.t. SSD drives, but the reality is that even if most computers being manufactured today included a solid state drive, the vast majority of consumers are using drives with moving parts. It will be at least a few more generations of hardware before OS-level developers will be able to focus specifically on the features of solid state drives when designing the filesystem and main OS APIs. That said, there is room for someone to develop a filesystem API designed with solid state in mind, or even an entire OS, but I don't know if there would be enough of a market to make that development worthwhile. Is there Anything about SSDs that interests you, from the perspective of the future of Redis?

sigil 16y ago
> That said, there is room for someone to develop a filesystem API designed with solid state in mind... What about the Journalling Flash Filesystem? It's been around for quite some time. http://en.wikipedia.org/wiki/JFFS2 http://en.wikipedia.org/wiki/JFFS2
- tjarratt 16y ago
  Someone more knowledgable might want to correct me here, but I think JFFS2 arrived a little too early; the performance gains are not enormous and it suffers from too many disadvantages (namely performance with small blocks and apparently determining free space??). LogFS is yet another file system designed for larger solid state drives (on the order of gigabytes instead of megabytes), and seems to be a step in the right direction. http://en.wikipedia.org/wiki/LogFS http://en.wikipedia.org/wiki/LogFS
  - sigil 16y ago
    > LogFS stores the inode tree on the drive; JFFS2 does not, which requires it to scan the entire drive at mount and cache the entire tree in RAM. For larger drives, the scan can take tens of seconds and the tree can take a significant amount of main memory. Interesting. I've only used JFFS2 on embedded systems like OpenWRT routers, where you wouldn't see the large drive penalty.
  - dfox 16y ago
    JFFS2 is intended to be used on raw controller-less flash an thus have to solve many problems that are more efficiently done in hardware. So it's probably only useful in embedded systems. Running normal filesystem on raw flash is good way to make it unusable in few days of light use. In fact, JFFS2 works by scanning all the storage on mount and having it all in RAM, that causes it's problems with large volumes (slow mounts and also large memory use). In embedded systems, for which it is intended, mounting the volume is rare operation and volumes are generally small, also typical embedded systems running linux has more RAM than Flash.
- wladimir 16y ago
  JFFS(2) is aimed at embedded devices that directly access flash chips. With a controller in between, such as with SSD, which performs wear leveling and other tricks to emulate a real harddrive, it might even be hurtful to performance. I'm not sure about LogFS.
- nitrogen 16y ago
  I don't know much about the technical details of JFFS2, only that it takes forever to mount after an unclean shutdown and runs painfully, painfully slow on larger flash volumes (i.e. >512MB) as they approach capacity. I wrote a tutorial (mostly so I could remember how to do it myself) for converting a SheevaPlug from JFFS2 to UBIFS because of the performance difference: http://nitrogen.posterous.com/converting-a-sheevaplug-from-jffs2-to-ubiubif http://nitrogen.posterous.com/converting-a-sheevaplug-from-j...
- wazoox 16y ago
  NILFS2 probably is a much better candidate : http://www.nilfs.org/en http://www.nilfs.org/en
wladimir 16y ago
I think you underestimate how serious OS vendors are taking the quickly growing popularity of SSD drives. A lot of work has already been done on OS/filesystem level just for SSD drives, for example to support TRIM. Sure, it will be a long time (if ever! likely, mechanical drives will remain important for bulk storage) before filesystem developers focus solely on SSD drives, but SSD performance is already very important.

crux_ 16y ago

I don't think append-only has much to do with seek time [1]; as you said, it has to do with corruption & consistency. Second, they actually tout that their data structure is better on SSDs than btrees (due to block-size obliviousness): > One major advantage is that they are naturally good candidates for SSDs, where a large asym- metry in read/write block sizes makes life very hard for B-trees. In contrast, the arrays making up the SDA can be written with extremely large effective block sizes. Footnote in edit: [1] in the case of search trees; for large objects that will be read front-to-back it does become a seek-time issue.

andytwigg 16y ago
SSDs are typically great at random reads, but not so good at random writes, particularly when you start rewriting the device (see http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-for-each-other/ http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-...). The attraction of append-only structures is in alleviating the random writes; but you still need to be careful. For example, CoW trees and log file systems often have a big space blowup, which translates into a slowdown in insert rate, and potentially random IO in the log cleaner/GC. That's a scenario in which the Stratified B-tree does a lot better.

soamv 16y ago

I have also not yet read the paper, but to your point about SSDs -- SSDs are definitely good for random reads, but for random writes, it seems like having an append-only structure would help avoid write amplification. If you do a lot of small random writes to an SSD that will be slow and reduce the disk's life drastically. (That said, I'm no SSD expert, so I might be way off)

hristov 16y ago

Actually using append only writing is very helpful for SSD drives. Overwriting a particular piece of data is very tricky for flash drives. In fact, underneath the hood, flash drives use append only even when you are trying to overwrite something. For example, if you want to overwrite a byte at location X, the flash drive actually writes the new data at a different location Y and uses logical mapping to have the byte at location Y pretend it is the byte at location X. The initial byte at location X will eventually be "recycled" and initialized. Since Flash does append only writing under the hood anyways, it is a better idea to do append only explicitly so that you get the advantages of append only (e.g., the ability to revert to older versions).

speleding 16y ago

The paper actually explains why their new algorithm also works better on SSDs.