0

I am building a database, and have implemented a transaction log system to ensure that writes are atomic, idempotent & consistent.

When a transaction is 'committed' it is appended to a log file before it is considered 'committed'. The log file is eventually persisted to the disk file, once it is marked as "full" during running operation by a boolean flag stored in memory.

The log contents are stored in memory so in case an updated record is requested, but hasn't been persisted, the in-memory layer is checked prior to the disk layer being checked.

Each log-file stores up to 250 transactions, and a new log file is created, and the name is incremented by 1.

I also want to keep logs for backup/auditing, so each log file name is numbered from 0 to infinity - like 0.log, 1.log etc

I want a good way to keep track of which log files have been marked as "persisted" and which are yet to be persisted, so then when the database is restarting, it can load those committed, but not yet persisted changes into memory, but also avoid loading all logs into memory because that would be O(n) time complexity.

There may be a number of log files at any given time that have not been persisted to disk.

Essentially, what I'm asking is

  • Whats the best way to find out which log files have not been persisted, so that they can be loaded into the temporary memory on restart, and eventually persisted?

These are the only ideas I currently have:

  • Having a separate log file for the database in which the most recently persisted transaction log file number is stored.
    • problems: This operation will need to happen each time a new log file is generated, which could slow down writes
  • Reading the log files backwards, and checking a flag to see if they were persisted
    • problems: very large folder sizes with hundreds of thousands or millions of log files could slow things down (I am not sure if this will be significant)
  • moving persisted files to a separate folder
    • I am not sure if this will work, and whether this is an operation that will result in a consistent database state
6
  • 1
    Keeping complete transaction logs for eternity is probably a bad idea. You'll likely run out of resources long before you get database restart performance problems if you use a sensible storage strategy (i.e. keeping logs in a folder hierarchy so that no folder contains excessive amounts of subfolder/files).. Sep 12 '21 at 6:00
  • @Hans-MartinMosner Agreed. This is essentially a variation of "There are only two hard problems in computer science, cache invalidation and naming things"–Phil Karlton. Log-structured filesystems have the same problem. They typically have a garbage collection process, which in the realm of log-structured filesystems is also sometimes called vacuuming. Sep 12 '21 at 7:29
  • "I am not sure if this will work, and whether this is an operation that will result in a consistent database state" – rename is actually pretty much the only thing on a POSIX filesystem that is guaranteed to be atomic. Sep 12 '21 at 7:31
  • @Hans-MartinMosner agreed, but we need it in our business case.
    – Albert
    Sep 12 '21 at 8:55
  • 1
    Have you considered investing in an off-the-shelf tool such as Splunk for managing, monitoring and analysing your logs? This feels like a potential re-invent-the-wheel scenario. Sep 12 '21 at 13:36
1

Before digging in some technical details I'd like to share some higher level considerations:

The amount of times you need to build your database for a database requirement is low, and it's better double check whether or not an on the shelf solution would be better suited; or a solution built on top of an on the shelf solution. Too many times, rewriting a database is reinventing the wheel for NIH reasons. I speak from experience; I am, for instance, working in a team of engineers that missed this step several times and implemented file databases, home-made orchestrators...

Additionally, to make sure you effectively addressed, it's important to challenge the requirements of the database, in either the persistence span, the response times, write throughput, cluster efficiency, transaction support etc. It's to be understood there is no silver bullet design, as highlighted for example by the cap theorem. If you aim for all features, you will at best correctly have a subset of them, and be lucky if that were the most important one for business reasons.

With that being said:

You essentially need to associate a boolean data to a bunch of object you are persisting. Here, their transactional state, but you could imagine future features allowing you to produce index on the persisted files, or any other content summary that could be handy to have for searching or similar.

That's why I believe the most long-term solution would be an eventually-persisted "index" file, in the simplest form a list of boolean values where the i-th entry is the status of the i-th log. The implementation only have to care that:

  • The index is being updated in memory after the persisting of the logs is done and complete
  • The index is being stored at regular intervals. The cleanest would be to have at least two files so if a write is interrupted the backup can be used
  • The index is loaded at startup and rebuilt if missing or corrupt.

In this implementation, you would be sure the files flagged truly are persisted and can be skipped. The reverse is not guaranteed, but you could live with files being re-writewritten (if this is idempotent) or being checked with a more expensive way when the database is live, as false negatives will be low frequency.

1
  • Yes, the writes are idempotent so this solution should work. It's a bit similar to the first idea I listed.
    – Albert
    Sep 13 '21 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.