4 ms·
Unfortunately this post skips over the "atomicity" part of a write-ahead log. Assume you start with data on disk AAAAAAAA, read it into memory, and update it t
by pjdesno 2y ago
Unfortunately this post skips over the "atomicity" part of a write-ahead log.
Assume you start with data on disk AAAAAAAA, read it into memory, and update it to BBBBBBBB, then write it back. If you crash in the middle, you might end up with BBBAAAAA, BBBBBBAA, or even some crazy interleaving. (at least for reasonable file sizes - note that the largest atomic write to many NVMe drives is 128K)
If you ditch the in-memory BTree and write a direct-to-disk one, with a lot of care (and maybe a bit of copy-on-write) you can make sure that each disk write leaves the database in a crash-consistent state, but that will cost multiple writes and fsyncs for any database modifications that split or merge BTree nodes - you have to ensure that each write leaves the database in a consistent state.
(for those of you old enough to remember ext2, it had the same problem. If you mounted it async and had a bad crash, the data on disk would be inconsistent - you'd lose data, so you'd vow to always mount your filesystem with synchronous writes so you'd never lose data again, then a few weeks later you'd get tired of the crappy performance and go back to async writes, until the next crash happened, etc. etc.)
The advantage of a log is that it allows you to combine multiple writes to different parts of the database file into a single record, guaranteeing (after crash recovery if necessary) that either all changes happen or none of them do. It serves the same purpose as a mutex in multi-threaded code - if your invariants hold when you get the mutex, and you reestablish them before you drop it, everything will be fine. We'd all love to have a mutex that keeps the system from crashing, but failing that we can use a WAL record to ensure that we move atomically from one valid state to another, without worrying about the order of intermediate changes to the data structure.
- bjornsing 2y agoFor some data structures you get the atomicity for “free” though. For example, a log structured merge tree where writes are done in large transactions could well do without a WAL and still achieve atomicity.
- nyrikki 2y agoEver have an LSMT quit writing a run half way through? Ever need to try and restore Cassandra where mutation storage order isn't guaranteed, with the last mutation always winning? It is absolutely not "atomic" if you have ever had to do a recovery from SSTable snapshots.
- bjornsing 2y ago> Ever have an LSMT quit writing a run half way through? That should be very easy to “solve” by just writing the length of the SSTable in a header. > Ever need to try and restore Cassandra where mutation storage order isn't guaranteed, with the last mutation always winning? This is more of a distributed systems challenge as I understand it: Cassandra is “multi-master” so can end up in a situation where transaction order is hard to sort out.
- valyala 2y agoA good example of database, which relies on LSM tree properties for protecting against data corruption on unclean shutdown is VictoriaMetrics [1]. [1] https://valyala.medium.com/wal-usage-looks-broken-in-modern-time-series-databases-b62a627ab704 https://valyala.medium.com/wal-usage-looks-broken-in-modern-...
- amluto 2y agoOne might argue that an LSM tree has a WAL — LSM’s log contains logical records instead of physical changes, but it seems like the essentials are there.
- bjornsing 2y agoYes, I guess that’s another way of phrasing it. But LSM tree implementations often have a separate WAL as well, to ensure durability for small transactions.
- neal 2y agoGood point! I'm not sure if there are any databases that do your 'with a lot of care' option, but for anyone curious about what that might look like in practice there are file systems that forgo write-ahead logging and maintain metadata consistency using techniques like soft updates[0] or copy-on-write up to a root[1]. [0]: https://www.usenix.org/conference/1999-usenix-annual-technical-conference/soft-updates-technique-eliminating-most https://www.usenix.org/conference/1999-usenix-annual-technic... [1]: https://www.cs.hmc.edu/~rhodes/courses/cs134/fa20/readings/The%20Zettabyte%20File%20System.pdf https://www.cs.hmc.edu/~rhodes/courses/cs134/fa20/readings/T... (yes, ZFS can be configured to use a WAL too for durability)
- refset 2y ago> I'm not sure if there are any databases that do your 'with a lot of care' option LMDB springs to mind. > LMDB was designed to resist data loss in the face of system and application crashes. Its copy-on-write approach never overwrites currently-in-use data. Avoiding overwrites means the structure on disk/storage is always valid, so application or system crashes can never leave the database in a corrupted state. https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Databa...
- philkrylov 2y ago> yes, ZFS can be configured to use a WAL too for durability ZFS always uses ZIL for sync writes. You can optionally set `sync=disabled` for a dataset to switch it off. I would not describe it as "can be configured to use WAL".
- makz 2y agoI imagine “a lot of care” like this: Ok, let’s write this veeery slowly, good, let’s check now it got written as intended. Right, let’s check again just in case, but this time slowly and paying a lot of attention… ok looks, good, moving on