Database Design

• Fixed key and value size
  • This allows for an offset based indexing strategy
• Flat file
  • Sync markers at every N entries
• On DB open, build an index by doing a sequential scan
  • Build an index of key to latest position (keep updating when the same key is encountered)
• Writes are append only
  • On write, update the location of the key with the new index
• For sequential scan, reverse iterate through the WAL, forward iterate over the data file
  • Since the latest is kept at the tail of the WAL, iterate backwards
    • This will allow us to provide a consistent view of the data without even touching the index (lesser CPU)
  • Maintain a bitset to ensure that we do not run over the same key twice
• For random read, just seek to the offset position and read
• Consolidation strategy
  • Reverse iterate through the existing file, and write to a new file
  • This will cluster all the recently updated keys to the head of the new file
  • Any updates during the consolidation are to be blindly appended to the new file
  • Immediately after consolidation, all the recently updated keys are at the head of the file