Replace full-file rewrite persistence with a reliable write-ahead log

[rayvn-42]

What problem would this address?

Cache (as of this moment) holds the whole database in memory and rewrites the entire .sdb file on every write via flush(). That's the main cause for persistency and data loss issues (as stated in #160 and #90). Both of these issues are because of write-time corruption risk and non-atomic full-file rewrites. And in #97 attemepted a WAL-based fix but got halted because of missing tests for WAL, compaction and crash recovery.

What outcome would help?

This issue proposes (and FYI, already has a working, fully tested implementation of the same general direction that #97 was going for). An append only write-ahead log <file>.wal that every write durably appends and fsyncs to immediately and with periodic compaction, appending the WAL file into the JSON file and clearing the WAL. Cache's public methods (like insert, select, delete, load) keep their existing signatures, so that nothing that calls into Cache, needs to change.

A few scope decisions:

• Compaction trigger is a fixed write counter (defaults to 50), and it is not a size nor a time based trigger, open to suggestions if another approach is preffered.
• No cross-process locking, as for now the existing cache.lock only ever protects multiple threads withing a single process, multiple processes writing the same file concurrently is a seperate and much more difficult problem, which I don't attempt to solve within this issue. I have also updated docs/persistence.md to state this issue.
• .sdb's on-disk format remains unchanged as a plain JSON snapshot, only addition is the WAL file.
• flush() becomes a no-op, and will be kept only because main.py (currently) still schedules it as a background task after each write. And durability now happens synchronously inso insert/delete instead, which is a strictly stronger guarantee than before when using flush(), since no background task is needed.

Additional context

Using #222 as a guide to check in before any major changes take place, since this approach is already built and tested, I'm opening this issue for visibility and to discuss different approaches and methods. I'll be happy to modify and change my code if anything doesn't line up.

[rayvn-42]

Not opening a PR until I'm told the approach is reasonable.

[rayvn-42]

Also @AnnoDomine in #161 you said that persistence logic is changing, just wanted to know if this is the right approach.

[izaaksarnecki1]

Hey! nice work, good call checkin in before creating a PR
Just wanna point out #220 in case you havent seen it. @AnnoDomine sketched an idea there for a new read/write system with some neat charts as well. Even though only an idea, but also that the current Cache will probably change quite a lot, so it might be worth checking out how WAL would fit with that direction before putting more work into the current class.
Also agree it makes sense to keep cross-process locking out of scope for now. I ran into that on #220, so if it becomes relevaqnt later Im happy to contribute

[rayvn-42]

Thanks for pointing it out. Since I hadn't seen #220.
I read through it and I think there's a real question that needs to be asked before working more on Cache, Does the cache layer's write queue in #220's design imply that writes are only durable once a queued block gets transmitted to the database layer, or is durability meant to happen under that, like for example with something like a WAL implementation as database layer's write method? if it is the latter, then my implementation might slot in directly as that piece, or if it the former, then that's a different durability guarantee than what #90 and #160 talked about. And to be honest since its @AnnoDomine's design I think we should hold off until he clarifies this.

[danieldeer]

File writes are now atomic. I have implemented this. I am reviewing the remaining proposed changes.

[rayvn-42]

Great. That does solve the crash safety half of this issue nicely. Although the other half of this issue was that even with atomic writes, every write means serializing and writing the whole database back. Which doesn't scale. The WAL approach I took handles that specifically, writes are appended instead of fully rewritten with periodic compaction. Given the atomic fix already covers write safety, I think additionally adding appending instead of full rewrite with periodic compaction is a nice thing to have. But seeing that #220 is still active, I think I'll hold until that's fully resolved.

[danieldeer]

Yes @rayvn-42, I have understood that 👍

I have raised a discussion with some tracked benchmarks here #254, because I expect that the WAL will be a MAJOR performance improvement.

Thanks a lot. Please implement the WAL approach as you proposed it. Don't consider #220 for now. I want to see how seriousdb evolves by adding plain, obvious improvements, like a WAL. No need to introduce big architecture (for now).

I have assigned this to you. Keep it stupid, and simple! Good luck. Looking forward to your PR.

[danieldeer]

@rayvn-42 please confirm you are implementing the WAL, otherwise I will do it

[rayvn-42]

Yes, I am working on it. Currently resolving some merge conflicts with your last commit. Once thats done I'll open a PR.

[rayvn-42]

@danieldeer I have ran benchmarks for both the non-WAL and WAL approaches, and the results are greatly different. And at the highest dataset the result of the WAL approach is about 185x better than the non-WAL approach.