Cinderstore

Cinderstore is an embeddable key and value store. It is built on a log structured merge tree (LSM tree). It is written in Crystal and uses only the Crystal standard library.

The store keeps a write ahead log for durability. It flushes memory to sorted files. It merges those files during compaction. It recovers all data after a restart. It serves get, put, and delete over a local socket.

Snapshots give you a consistent view of the store at one instant. A snapshot never blocks new writes. Release it when you are done.

This is release 0.4.0. It adds level-based compaction. Tables cascade from level 0 to deeper levels, and each level stays within its size target.

Features

• Memory table with ordered writes
• Durable write ahead log with CRC32 framing
• Sorted tables with a block index and a bloom filter
• Block cache for fast repeated reads
• Level-based compaction with size targets per level
• Background flush and compaction
• Point-in-time snapshots with consistent reads
• Snapshot iterators that stay valid during writes
• Range scans with an iterator API
• Crash recovery from the write ahead log
• Local TCP server with a line protocol
• Zero runtime dependencies

Quick start

You need Crystal 1.10 or newer.

crystal spec
crystal run examples/demo.cr

Cinderstore has no dependencies. It does not need shards install.

Build the command line tool.

shards build --production

Run the demo.

bin/cinderstore demo

Demo output

The demo loads a product catalog from fixtures/catalog.csv. It writes, scans, flushes, compacts, deletes, snapshots, and reopens a database. The output is deterministic.

== Cinderstore 0.4.0 demo ==

Loaded 24 products from ...\fixtures\catalog.csv
Database directory: ...\cinderstore-demo

1. Writes buffered in the memtable
   entries: 24, memtable bytes: 2990, tables: 0

2. Range scan SKU-0010 to SKU-0020
   SKU-0010  {"name":"Ash Rake Forged","price":14.00,"stock":31}
   SKU-0011  {"name":"Coal Shovel Small","price":19.40,"stock":22}
   SKU-0012  {"name":"Ember Tray Brass","price":52.80,"stock":15}
   SKU-0013  {"name":"Ember Poker Curved","price":17.60,"stock":40}
   SKU-0014  {"name":"Fire Tongs Dining","price":15.90,"stock":35}
   ... (24 rows in the store)

3. Flush memtable to a sorted table
   tables: 1 (l0: 1, l1: 0), entries: 24
   disk bytes: 1649, memtable bytes: 0

4. Delete 4 products, update 2 products, then flush again
   tables: 2 (l0: 2, l1: 0), entries: 30
   disk bytes: 1902, memtable bytes: 0
   The deleted keys still occupy space in the level-0 tables.

5. Compact merges the tables and drops the deleted keys
   tables: 1 (l0: 0, l1: 1), entries: 20
   disk bytes: 1384, memtable bytes: 0
   The store keeps the newest value for each key.

6. Verify deletes and updates after compaction
   get SKU-0003 => nil
   get SKU-0001 => "{\"name\":\"Forge Anvil 45kg\",\"price\":175.00,\"stock\":14}"
   scan count   => 20

7. Snapshot the store for a consistent read
   snapshot rows at creation: 20
   after 2 new writes and 1 delete, then a flush
   live rows: 21, snapshot rows: 20
   live SKU-0001    => nil
   snapshot SKU-0001 => "{\"name\":\"Forge Anvil 45kg\",\"price\":175.00,\"stock\":14}"
   snapshot iterator SKU-0010 to SKU-0016
   SKU-0010, SKU-0011, SKU-0013, SKU-0014, SKU-0015

8. Reopen the database and verify recovery
   rows after restart: 21

9. Leveled compaction keeps each level within its target
   after 5 flushes, level counts: [5]
   after compact_levels:          [0, 0, 1]
   all 100 rows still readable

Demo complete.

Step 7 shows the value of a snapshot. The live store drops SKU-0001 and adds two products. The snapshot still sees the state before those writes.

Step 9 shows the value of leveled compaction. Five flushes create five level-0 tables. compact_levels merges them into a fresh level-2 table, so the store stays tidy as it grows.

Use the library

Require the library.

require "cinderstore"

Open a database and use it.

db = Cinderstore::DB.new("data/my-store")
db.put("forge-hammer", "steel")
db.get("forge-hammer") # => "steel"
db.delete("forge-hammer")
db.scan("a", "z").each do |key, value|
  puts "#{key} => #{value}"
end
db.close

Read a snapshot

A snapshot is a consistent view at one instant. Take a snapshot, read it, then release it.

snap = db.snapshot
snap.get("forge-hammer") # => "steel"
snap.scan("a", "z").each do |key, value|
  puts "#{key} => #{value}"
end
snap.release

The block form releases the snapshot automatically.

db.snapshot do |snap|
  count = snap.count
end

Iterate a snapshot with a snapshot iterator. The iterator stays valid while the database keeps writing. Close the iterator before you release the snapshot.

snap = db.snapshot
iter = snap.iter("SKU-0100")
while entry = iter.next?
  process(entry.key, entry.value)
end
iter.close
snap.release

Iterate a range with a block.

db.each("SKU-0100", "SKU-0200") do |key, value|
  process(key, value)
end

Flush and compact explicitly.

db.flush    # Move the memtable into a table.
db.compact  # Merge all tables into level 1.

compact merges every table in one pass. It drops stale data. For a growing store, run compact_levels instead. It merges one level at a time, so each pass touches only two levels. It returns true when any table moved.

moved = db.compact_levels

Command line tool

The tool uses a database directory. The default directory is cinderstore-data.

Write a value.

bin/cinderstore put --key forge-hammer --value steel

Read a value.

bin/cinderstore get --key forge-hammer

Delete a key.

bin/cinderstore del --key forge-hammer

Scan a range.

bin/cinderstore scan --start a --finish z --limit 100

Show counters.

bin/cinderstore stats

Start the local server.

bin/cinderstore server --db data --port 7654

Run bin/cinderstore help for the full list of commands.

Wire protocol

The server listens on 127.0.0.1:7654 by default. Commands are lines of text. A command ends with a newline. Keys must not contain spaces or newlines. Values must not contain newlines.

Command	Meaning
PUT key value	Write a value
GET key	Read a value
DEL key	Delete a key
SCAN start finish limit	List a range
STATS	Show counters
PING	Check the server
FLUSH	Flush the memtable
COMPACT	Compact the tables
SHUTDOWN	Stop the server

The server answers with one line per command.

• OK for a successful write
• VALUE value for a read
• NOT_FOUND for a missing key
• ROW key value for each scan result, then END
• STATS {...} for the counters
• ERR message for an error

Use a tool such as nc or the included example client.

printf "PUT forge-hammer steel\nGET forge-hammer\n" | nc 127.0.0.1 7654

Architecture

The database stores data in a single directory. The directory contains a manifest, one write ahead log, and sorted tables.

Write path

A write goes to two places at once.

1. Append the entry to the write ahead log.
2. Insert the entry into the memory table.

The default mode fsyncs after every write. Set sync_writes to false for faster, less durable writes.

Flush

When the memory table grows past its limit, the database freezes it. A new memory table starts. A background task writes the frozen table to a sorted file. The old log is deleted only after the file is durable.

Compaction

Tables live in levels. Level 0 holds new flushes. Its tables may overlap. Deeper levels hold merged tables. Tables in one level never overlap each other.

Each level has a size target. The target grows by level_ratio for every deeper level. Level 0 has no size target. It compacts by table count instead.

Compaction works one level at a time. Level 0 compacts when it holds enough tables. A deeper level compacts when it holds more bytes than its target. The merge reads that level and the overlapping tables in the next level. It writes fresh tables into the next level.

A tombstone stays in the merged output until the deepest level. It must stay, because a deeper table may hold an older copy that the tombstone hides. At the deepest level, all older copies are gone, so the tombstone can drop.

The compact call merges every level in one pass. The compact_levels call merges one level at a time. The background task uses compact_levels.

Compaction keeps a table file on disk while a snapshot references it. The file is deleted only after the last snapshot releases it.

Snapshots

A snapshot is an immutable view of the store at one instant. Creation copies the active memory table and takes a reference to each table file.

Writes, flushes, and compactions after the snapshot do not change what the snapshot sees. The snapshot reads the table files it holds, so compaction can replace those files without breaking the snapshot.

Snapshots never block writes. Reads over a snapshot use the same merge path as normal reads. Release a snapshot when you are done with it.

Read path

A read merges the memory table, any frozen table, and all sorted tables. The merge yields the newest entry for each key. The bloom filter lets a reader skip a table that cannot contain the key. The block cache holds decoded blocks so repeated reads avoid disk.

Recovery

On open, the database replays the write ahead log into the memory table. Recovery is idempotent. A torn tail is detected by its CRC32 and skipped. The manifest lists every table. Orphan files from a crash are removed.

On-disk format

Tables use a compact binary format.

• Data blocks hold serialized entries.
• A block index maps the first key of each block to its offset.
• A bloom filter covers every key in the table.
• A footer stores offsets, a version, and a CRC32.
• Each block and each log record carries a CRC32.

Sequence numbers make versions unique. They are per-write and never reused.

Configuration

Tune the database with Cinderstore::DB::Config.

config = Cinderstore::DB::Config.new
config.block_size = 4096
config.memtable_limit = 4_i64 * 1024 * 1024
config.bloom_fpp = 0.01
config.cache_blocks = 512
config.sync_writes = true
config.l0_compact_threshold = 4
config.compact_on_flush = true
config.max_levels = 7
config.level_ratio = 10.0
db = Cinderstore::DB.new("data", config)

max_levels caps the number of levels. level_ratio sets how much data a deeper level may hold. A higher ratio compacts less often. Level L holds up to memtable_limit * level_ratio ** L bytes.

Project layout

src/cinderstore.cr       Library entry point
src/cinderstore/         Core components
src/cinderstore/snapshot.cr  Point-in-time snapshot support
src/cli.cr               Command line tool
examples/demo.cr         Library walkthrough
examples/server_demo.cr  Wire protocol walkthrough
fixtures/catalog.csv     Sample product catalog
spec/                    Test suite

Test status

The suite runs with crystal spec. It has 108 examples. All pass on Windows and Linux. It covers the skip list, the memory table, the write ahead log, the bloom filter, and the block cache. It covers the tables, the iterators, and the database. It covers compaction by level, durability, snapshots, and the server protocol.

The CI workflow runs on GitHub Actions for Windows and Ubuntu. It checks formatting, runs the suite, runs both demos, and builds the binary.

Limitations

• Keys sort by byte value.
• Values are limited to 4 MB.
• Keys are limited to 4 KB.
• The server protocol is unencrypted. Use it on localhost only.
• compact_levels merges a whole level at once. A very large level makes a large merge. The level targets keep that merge rare.
• No multi-threaded runtime is required. The server uses fibers.
• Release snapshots before you close the database.

Roadmap

Planned:

• Release 0.5: optional checksum-free fast mode
• Release 0.6: batch writes and group commit
• Release 0.7: secondary indexes

Delivered:

• Release 0.4: level-based compaction. Tables cascade from level 0 to deeper levels. Each level stays within its size target. Tombstones survive until the deepest level.
• Release 0.3: snapshot iterators and consistent reads. Snapshots give a stable view of the store. Compaction keeps referenced files alive.

License

Cinderstore is licensed under the Apache License 2.0. See the LICENSE file.