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
Best Answer
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:
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.