4 ms·

Atomic Commit in SQLite (2007)

62 points by jeffreyrogers 9y ago

jeffreyrogers 9y ago
I was interested in this topic because people were telling me that SQLite (and other databases) have more sophisticated methods of preventing corruption to database files than just calling fsync (or the platform equivalent) on the DB and hoping that the OS and disk controllers behave appropriately. What this document shows is that while SQLite has a somewhat sophisticated mechanism for allowing rollback of transactions in the case that they are not completed, it does not have a better means of ensuring data actually gets to disk than relying on fsync. In fact, this document explicitly calls out that the DB can be corrupted if the OS and disks do not implement flushing properly. Further, when I was looking at how SQLite does testing I noticed that there are no power failure or actual disk crash tests (these are obviously hard to test in an automated way). Instead SQLite simulates faults by using an OS abstraction layer that injects fake disk faults, reorders writes, etc. This means that the actual behavior of SQLite (and probably other DBs) under actual power failure situations is probably worse than commonly acknowledged. Edit: I should add that this issue is obviously an OS/filesystem/hardware bug, and it's not really a criticism of SQLite to say it can't address it.
- jasonwatkinspdx 9y ago
  The original post is a bit stale/out of date. https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-pillai.pdf https://www.usenix.org/system/files/conference/osdi14/osdi14... has a detailed analysis of potential consistency / recovery issues of various data stores, including SQLite. SQLite in WAL mode is about as trustworthy as it gets.
  - jeffreyrogers 9y ago
    WAL mode also relies on fsync to persist data to disk, so it has the same failure mode if fsync is not working as advertised. I briefly looked at the link you posted and it appears they also do fault injection/simulation rather than directly unplugging power or crashing the OS, so their tests won't catch disk controller problems.
    - infogulch 9y ago
      Testing OS/controller/hardware failure will quickly devolve into extremely specific configuration issues and even fully verifying one particular configuration may be meaningless for the next configuration. Fault injection is probably as close as you can get to reliably exercising any fault tolerance properties while still being generic enough to apply to more than 1 real system in the wild.
    - jasonwatkinspdx 9y ago
      Well, if you read the original SQL post you'd see they do make very conservative assumptions, including that fsync may lie on some systems. Alice is considerably more sophisticated than yanking a power cord and hoping it catches bad behavior.
- arielweisberg 9y ago
  Testing via software fault injection is quite reasonable if you introduce all the necessary cases. What SQLite tests for is more than most databases do! There aren't really build any special mechanisms besides fsync/msync if the database is built on top of a filesystem. You have to tell the filesystem to make it's metadata consistent as well. Writing to a raw disk you might do something different. I don't have much experience with that as there isn't a huge amount to be gained. It's still going to look and work fairly similarly as you are writing your data to the disk and then emitting a write barrier to make all prior writes durable. If a disk lies about what data is durable there is no way to work around it from inside the database. If you can't durably store data you can't acknowledge to clients the data is durably stored. You can YOLO and build structures that probably won't get corrupted in practice, but that's no way to live life.
  - jeffreyrogers 9y ago
    I agree! SQLite is very high quality and goes to greater lengths than any other software I'm aware of to ensure correctness and reliablity... but several people told me that SQLite has ways of improving on fsync and I was interested to find that isn't the case. Edit: And I don't think testing actual power failures is realistic even for something like SQLite. Maybe if you are using SQLite and have a critically important application you'd do something like that, but it's too labor intensive in almost all cases.
    - jasonwatkinspdx 9y ago
      > several people told me that SQLite has ways of improving on fsync and I was interested to find that isn't the case. The way you're talking about this is simplistic. To have a reliable datastore you need to know not just fsync exists, but a lot of specific details in exactly how you use it, and what you can and cannot count on. There's a lot for you to learn here if you care to look a bit deeper than "oh, just uses fsync, boring".
      - jeffreyrogers 9y ago
        > There's a lot for you to learn here if you care to look a bit deeper than "oh, just uses fsync, boring". That wasn't my conclusion at all. That's why I took the time to read the docs and the source code. Because I was interested in how SQLite provided the guarantees that it does and what the limitations of those guarantees are.
- zzzcpan 9y ago
  I'm guessing you want more specific guarantees than databases attempt to provide. Like losing only last couple of commits in case HDD or an OS lies about writes, but not corrupting the rest of the database. If this is right, than sure it is possible to do better with something purely log structured with checkpoints. But this is not what SQLite and such databases aim for, they assume you achieve those things with backups.
- tyingq 9y ago
  Any Windows experts about? I'm curious if it offers something better than fsync for this type of thing. Or perhaps nothing in the OS can really deal with the variety of behavior in disk controllers? It's kind of funny to me that we're this many years into databases and hardware and no solution has ever emerged. I suspect mainframes, for example, don't have this issue. Easy to solve when you get to spec every piece of hardware.
  - zaarn 9y ago
    The OS can't do anything. The Controller says "Fsync? Sure thing." and that's basically end of the story. Unless the cache is visible to the OS, the OS simply has to accept what the controller says as truth. The issue of a controller lying is to my experience very rare and only really exists for very cheap harddrives, SSDs or SD cards (interesting for RPi). I'm not aware of an enterprise hardware that does this, I suspect if anyone tried they'd be out of business quick.
- zaarn 9y ago
  I've somewhat researched the topic of "durability + harddisks/SSDs" for a while since I was interested in writing a simple Key-Value store. The simple answer is that "fsync" is basically the best option you have. The hardware controller tells the OS "sure, I've written all this" and the OS has no real mechanism to verify this. Worse even, some cheaper SSDs an HDDs do reorder writes around fsync's, in one case a bad HDD was able to corrupt ZFS(!) (reproducible) when loosing power during a write. The fun thing is also that filesystems themselves aren't much better either. Ext4&co. sometimes don't propagate write errors at all, so in the remote event that the HDD controllers lowers itself down the plebian OS to tell it that it may have lost a byte or gigabyte, the filesystem is probably going to ignore it since the write was already buffered and fsync'd. The only real reason why computers aren't spontaneously combusting is that most HDDs and SSDs don't do this, even in consumer space and an unexpected loss of power is rare to also meet some critical write. (ext4's physical journaling also helps a lot to make it resistant) If you want a full taste of how it works out, get a Raspberry Pi, load in a super cheap microSD and unplug the power a couple times while running a browser or other disk-heavy load.
  - jeffreyrogers 9y ago
    Interesting. I'm surprised that even cheap SSDs and HDDS will reorder the writes. I've heard that most enterprise and higher end hard drives don't lie about fsync (actually it's a bit more subtle, I've heard some do, but they have enough energy stored in capacitors to finish writing if power fails).
    - zaarn 9y ago
      They're cheap and the vendors like to pretty up the speed charts by ensuring any speed test will mostly hit the cache, even if it comes at the cost of loosing data during a power loss. Some enterprise SSD/HDD do have large enough capacitors to quickly commit the cache to a flash version or write it out, though usually you have a battery backed RAID controller for that.

62 points by jeffreyrogers 9y ago

I was interested in this topic because people were telling me that SQLite (and other databases) have more sophisticated methods of preventing corruption to database files than just calling fsync (or the platform equivalent) on the DB and hoping that the OS and disk controllers behave appropriately. What this document shows is that while SQLite has a somewhat sophisticated mechanism for allowing rollback of transactions in the case that they are not completed, it does not have a better means of ensuring data actually gets to disk than relying on fsync. In fact, this document explicitly calls out that the DB can be corrupted if the OS and disks do not implement flushing properly. Further, when I was looking at how SQLite does testing I noticed that there are no power failure or actual disk crash tests (these are obviously hard to test in an automated way). Instead SQLite simulates faults by using an OS abstraction layer that injects fake disk faults, reorders writes, etc. This means that the actual behavior of SQLite (and probably other DBs) under actual power failure situations is probably worse than commonly acknowledged. Edit: I should add that this issue is obviously an OS/filesystem/hardware bug, and it's not really a criticism of SQLite to say it can't address it.

jasonwatkinspdx 9y ago
The original post is a bit stale/out of date. https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-pillai.pdf https://www.usenix.org/system/files/conference/osdi14/osdi14... has a detailed analysis of potential consistency / recovery issues of various data stores, including SQLite. SQLite in WAL mode is about as trustworthy as it gets.
- jeffreyrogers 9y ago
  WAL mode also relies on fsync to persist data to disk, so it has the same failure mode if fsync is not working as advertised. I briefly looked at the link you posted and it appears they also do fault injection/simulation rather than directly unplugging power or crashing the OS, so their tests won't catch disk controller problems.
  - infogulch 9y ago
    Testing OS/controller/hardware failure will quickly devolve into extremely specific configuration issues and even fully verifying one particular configuration may be meaningless for the next configuration. Fault injection is probably as close as you can get to reliably exercising any fault tolerance properties while still being generic enough to apply to more than 1 real system in the wild.
  - jasonwatkinspdx 9y ago
    Well, if you read the original SQL post you'd see they do make very conservative assumptions, including that fsync may lie on some systems. Alice is considerably more sophisticated than yanking a power cord and hoping it catches bad behavior.
arielweisberg 9y ago
Testing via software fault injection is quite reasonable if you introduce all the necessary cases. What SQLite tests for is more than most databases do! There aren't really build any special mechanisms besides fsync/msync if the database is built on top of a filesystem. You have to tell the filesystem to make it's metadata consistent as well. Writing to a raw disk you might do something different. I don't have much experience with that as there isn't a huge amount to be gained. It's still going to look and work fairly similarly as you are writing your data to the disk and then emitting a write barrier to make all prior writes durable. If a disk lies about what data is durable there is no way to work around it from inside the database. If you can't durably store data you can't acknowledge to clients the data is durably stored. You can YOLO and build structures that probably won't get corrupted in practice, but that's no way to live life.
- jeffreyrogers 9y ago
  I agree! SQLite is very high quality and goes to greater lengths than any other software I'm aware of to ensure correctness and reliablity... but several people told me that SQLite has ways of improving on fsync and I was interested to find that isn't the case. Edit: And I don't think testing actual power failures is realistic even for something like SQLite. Maybe if you are using SQLite and have a critically important application you'd do something like that, but it's too labor intensive in almost all cases.
  - jasonwatkinspdx 9y ago
    > several people told me that SQLite has ways of improving on fsync and I was interested to find that isn't the case. The way you're talking about this is simplistic. To have a reliable datastore you need to know not just fsync exists, but a lot of specific details in exactly how you use it, and what you can and cannot count on. There's a lot for you to learn here if you care to look a bit deeper than "oh, just uses fsync, boring".
    - jeffreyrogers 9y ago
      > There's a lot for you to learn here if you care to look a bit deeper than "oh, just uses fsync, boring". That wasn't my conclusion at all. That's why I took the time to read the docs and the source code. Because I was interested in how SQLite provided the guarantees that it does and what the limitations of those guarantees are.
zzzcpan 9y ago
I'm guessing you want more specific guarantees than databases attempt to provide. Like losing only last couple of commits in case HDD or an OS lies about writes, but not corrupting the rest of the database. If this is right, than sure it is possible to do better with something purely log structured with checkpoints. But this is not what SQLite and such databases aim for, they assume you achieve those things with backups.
tyingq 9y ago
Any Windows experts about? I'm curious if it offers something better than fsync for this type of thing. Or perhaps nothing in the OS can really deal with the variety of behavior in disk controllers? It's kind of funny to me that we're this many years into databases and hardware and no solution has ever emerged. I suspect mainframes, for example, don't have this issue. Easy to solve when you get to spec every piece of hardware.
- zaarn 9y ago
  The OS can't do anything. The Controller says "Fsync? Sure thing." and that's basically end of the story. Unless the cache is visible to the OS, the OS simply has to accept what the controller says as truth. The issue of a controller lying is to my experience very rare and only really exists for very cheap harddrives, SSDs or SD cards (interesting for RPi). I'm not aware of an enterprise hardware that does this, I suspect if anyone tried they'd be out of business quick.
zaarn 9y ago
I've somewhat researched the topic of "durability + harddisks/SSDs" for a while since I was interested in writing a simple Key-Value store. The simple answer is that "fsync" is basically the best option you have. The hardware controller tells the OS "sure, I've written all this" and the OS has no real mechanism to verify this. Worse even, some cheaper SSDs an HDDs do reorder writes around fsync's, in one case a bad HDD was able to corrupt ZFS(!) (reproducible) when loosing power during a write. The fun thing is also that filesystems themselves aren't much better either. Ext4&co. sometimes don't propagate write errors at all, so in the remote event that the HDD controllers lowers itself down the plebian OS to tell it that it may have lost a byte or gigabyte, the filesystem is probably going to ignore it since the write was already buffered and fsync'd. The only real reason why computers aren't spontaneously combusting is that most HDDs and SSDs don't do this, even in consumer space and an unexpected loss of power is rare to also meet some critical write. (ext4's physical journaling also helps a lot to make it resistant) If you want a full taste of how it works out, get a Raspberry Pi, load in a super cheap microSD and unplug the power a couple times while running a browser or other disk-heavy load.
- jeffreyrogers 9y ago
  Interesting. I'm surprised that even cheap SSDs and HDDS will reorder the writes. I've heard that most enterprise and higher end hard drives don't lie about fsync (actually it's a bit more subtle, I've heard some do, but they have enough energy stored in capacitors to finish writing if power fails).
  - zaarn 9y ago
    They're cheap and the vendors like to pretty up the speed charts by ensuring any speed test will mostly hit the cache, even if it comes at the cost of loosing data during a power loss. Some enterprise SSD/HDD do have large enough capacitors to quickly commit the cache to a flash version or write it out, though usually you have a battery backed RAID controller for that.