LSM trees

# pip install rocksdict   (Python bindings for RocksDB; rocksdict 0.3.29)
# Numbers are from one run on an M1 laptop; yours will differ.
import os, shutil, time
import rocksdict as r

shutil.rmtree("/tmp/lsm", ignore_errors=True)
opt = r.Options(raw_mode=True)
opt.create_if_missing(True)
opt.set_write_buffer_size(8 << 20)                   # 8 MB memtable
opt.set_level_compaction_dynamic_level_bytes(False)
opt.set_max_bytes_for_level_base(16 << 20)           # L1 16 MB, L2 160 MB, L3 1.6 GB
opt.set_target_file_size_base(4 << 20)               # 4 MB SST files
opt.enable_statistics()
table = r.BlockBasedOptions()
table.set_bloom_filter(10, False)                    # 10 bits per key, about 1% false positives
opt.set_block_based_table_factory(table)
db = r.Rdict("/tmp/lsm", opt)

def stat(name):
    line = next(l for l in opt.get_statistics().splitlines() if l.startswith(name + " "))
    return int(line.split()[-1])

def mb(n):
    return f"{n / 1e6:,.0f} MB"

keys = [os.urandom(16) for _ in range(2_000_000)]
for k in keys:
    db.put(k, os.urandom(100))                       # 116 bytes per pair, random order
db.flush()
time.sleep(10)                                       # let background compaction finish
user = len(keys) * 116
disk = stat("rocksdb.flush.write.bytes") + stat("rocksdb.compact.write.bytes")
print("you wrote", mb(user), "| SST files got", mb(disk), f"({disk / user:.1f}x)")
# you wrote 232 MB | SST files got 1,279 MB (5.5x)
print("files per level:", [db.property_int_value(f"rocksdb.num-files-at-level{i}") for i in range(4)])
# files per level: [2, 3, 39, 20]

for _ in range(100_000):
    db.get(os.urandom(16))                           # keys that don't exist
print("file reads skipped by Bloom filters:", stat("rocksdb.bloom.filter.useful"))
# file reads skipped by Bloom filters: 362647

size = lambda: mb(db.property_int_value("rocksdb.total-sst-files-size"))
print("on disk:", size())                            # on disk: 255 MB
for k in keys[:1_000_000]:
    db.delete(k)                                     # each delete writes a tombstone
db.flush()
print("after deleting half:", size())                # after deleting half: 206 MB
db.compact_range(None, None)                         # rewrite everything, drop tombstones
print("after a full compaction:", size())            # after a full compaction: 127 MB
db.close()