zywang0/kv-storage

This is a k/v storage database project based on Bitcask model.

KV Storage

This project is based on the key/value storage engine designed by basho's bitcask paper.

• Database Startup Process
• Design
  • Bitcask Model Design
  • Memory Design: How data is stored
    • Index(Data structure)
  • Disk Design: How data is organized
    • Record
  • I/O Types

Database Startup Process

• Step 1: Load the files in the data directory and open their file descriptors.
• Step 2: Traverse the contents of the data file to construct an in-memory index.

Design

Bitcask Model Design

• All keys are stored in memory; all values are stored on disk.
• Bitcask model contains only one read/write(active) file and multiple read-only(inactive) files.
• Merge operation

Memory Design: How data is stored

Key: key | Value: ValuePos {Fid, Offset, Size}

Index(Data structure)

We used B Tree and Adaptive Radix Tree as our memory index in this project because these two data structures support efficient insertion, reading, and deletion of data.

Disk Design: How data is organized

Record

One datafile contains multiple records. We separate our single encoded record into two parts: Header and Real Data.

crc	type	keySize	valueSize	key	value
uint32	RecordType	uint32	uint32	[]byte	[]byte
4 bytes	1 bytes	variable-length field (max 5 bytes)	variable-length field (max 5 bytes)	variable-length field	variable-length field

I/O Types

Standard File I/O, MMAP I/O