S3 namespace index

S3 namespace index

Upcoming. This page describes the s3 branch. It is not part of a release, and details may change.

Part of S3 implementation. The namespace index holds the buckets, object versions, multipart uploads and blob references of the S3 endpoint. It lives in the package org.unigrid.hedgehog.s3.index (directory s3/index/) and is a log-structured merge tree whose runs and manifests are immutable blobs in network storage. Only the journal and the root file stay on the node, in <data>/s3/index.

Writers queue on one lock, flushes and compactions on another, and readers take the volatile current Snapshot without locking. Namespace is the typed interface: each mutation is one Transaction under the writer lock. Its guards run against the current state and throw ConditionFailedException, and then nothing is written.

Keys

Keys compare as unsigned bytes: a kind byte, then fields in the order S3 lists them. Numbers are big-endian. A text is UTF-8 with every 00 byte escaped as 00 FF and the terminator 00 01. That keeps a (61 00 01) before a followed by a NUL (61 00 FF 00 01), and that before ab (61 62 00 01). A text without its terminator is a byte prefix of every key that starts with it, which is how prefix listings seek.

Kind	Key layout	Value
01 bucket	01, text(bucket)	bucket record
02 version	02, text(bucket), text(key), u64(Long.MAX_VALUE minus sequence)	version record
03 upload	03, text(bucket), text(key), u64(sequence)	upload record
04 part	04, u64(upload sequence), u32(part number)	part record
05 reference	05, text(blob id)	reference count, LEB128
06 garbage	06, text(blob id)	due instant

Version keys invert the sequence, so the newest version of a key sorts first. A version or upload id is the write sequence in 16 hex digits; null names the version of an unversioned or suspended bucket.

Records

Codec writes lengths, counts and offsets as unsigned LEB128, refusing an overflow and more than ten bytes. A string is a length and UTF-8, an instant is long seconds and int nanoseconds, a nullable is a boolean byte and the value, and a map is written sorted, so a record always encodes to the same bytes. readCount checks a count against the bytes left, so a damaged count fails instead of sizing an allocation. seal appends a big-endian CRC32C.

Every value opens with Records.FORMAT, which is 1. Names and ids are left to the key. Bucket configurations are kept as the XML the client sent.

Record	Fields after the format byte, in order
bucket	created, location (nullable), versioning name, object lock (boolean), tags, configurations (maps)
version	null version (boolean), delete marker (boolean), last modified, ETag (nullable), parts (list), checksums, headers, metadata, tags (maps), retention (nullable mode and date), legal hold (boolean)
part	number, slices (list of blob id, offset, length), ETag (nullable), checksums, last modified (nullable)
upload	checksum algorithm and type (nullable), template version (the version fields from delete marker on)

The journal

A write counts as done once its journal record is forced to disk. The file is <data>/s3/index/journal.

Field	Encoding	Meaning
payload length	u32, big-endian	bytes of the payload that follows the header
checksum	u32, big-endian	CRC32C of the payload
sequence	u64, big-endian	the sequence of the batch; the payload starts here
slot count	LEB128	slots in the batch
per slot: key	LEB128 length, bytes	the index key
per slot: value	u8 present, then LEB128 length, bytes	the record; absent for a tombstone

A failed append truncates the file back to where the record began, since a half record would hide every later one from replay. If even that fails, the journal is broken and refuses further appends. Replay stops at the first short or checksum-failing record, the one a crash tore, and truncates there.

freeze() renames journal to journal.frozen and opens a fresh journal; release() deletes the frozen file. If journal.frozen exists when the index opens, a flush was interrupted: the frozen journal takes in the active one's records and replaces it. Records hold absolute values, so replaying one twice does no harm. Index files are rw-------, and directories are synced after renames.

Memtables and snapshots

Memtable is a ConcurrentSkipListMap keyed by a stamp of key and batch sequence, keys ascending as unsigned bytes and sequences descending. A read at snapshot sequence s takes the ceiling of (key, s), the newest slot at or below s, so a reader only ever sees whole batches.

A Snapshot asks the active memtable, then the frozen one being flushed, then the runs newest first. The first hit wins, and a tombstone answers nothing. Scans merge their sources in a MergeCursor, where the newest source wins.

Runs

RunWriter streams sorted slots through a scratch file into a run blob: the sealed pages back to back, then the sealed run index, with no footer. The manifest records the run's size and the offset of its index, so a reader range-reads the index and then only the pages it needs, through the cache of S3 blob layer and cache.

A page closes at pageBytes (256 KiB) of keys and values. Prefix compression restarts with every page, so each page decodes on its own. A block read is bounded by maxBlockBytes (256 MiB) and must lie inside the run, as the manifest and the index may come from a damaged or forged blob. Decoding checks that keys ascend and that no key shares more bytes than the key before it holds.

A run page (Page)

Field	Encoding	Meaning
count	LEB128	entries in the page, at least 3 bytes each
per entry: shared	LEB128	leading bytes the key shares with the key before it, 0 for the first
per entry: rest	LEB128 length, bytes	the key after the shared bytes
per entry: value	u8 present, then LEB128 length, bytes	the record; absent for a tombstone
seal	u32, big-endian	CRC32C of everything before it

A run index (RunIndex, Bloom)

Field	Encoding	Meaning
format	u8	1
page count	LEB128	pages in the run
per page: offset, length	LEB128, LEB128	place of the sealed page in the run blob
per page: first key	LEB128 length, bytes	a key belongs in the last page starting at or before it
probes	u8	1 to 30
word count	LEB128	at least 1
words	u64 each, big-endian	the bits of the bloom filter
seal	u32, big-endian	CRC32C of everything before it

Decoded pages and indexes stay in a PageCache, an access-ordered LRU of cacheBytes (32 MiB) keyed by run and offset. Two readers that miss the same entry both load it rather than lock.

Run.get checks the run's first and last key, then the bloom filter, then the page. A key that was added always tests positive. The filter hashes a key to 64 bits with FNV-1a and mixes the result with the MurmurHash3 finalizer. Probe i sets bit (low + i × high) mod m, where low and high are the two 32-bit halves of the hash: double hashing that costs one hash per key.

Bloom.forKeys sizes the filter for the slots the run will hold. For n keys at b = bloomBitsPerKey (10) it takes m = clamp(n × b, 64, 2^30) bits, rounded up to whole 64-bit words, and k = clamp(round(b × ln 2), 1, 30) probes, which is 7 at 10 bits per key. The false-positive rate is then about (1 − e^(−kn/m))^k = (1 − e^(−0.7))^7, or 0.8 %: about one lookup in 120 of a key that a run lacks reads a page of that run for nothing.

Manifest and root

A Manifest blob names the sequence that every stored write is at or below, the runs newest first, and the superseded blobs waiting out their grace period before deletion. A manifest whose magic or format differs is refused as corrupt.

Field	Encoding	Meaning
magic	u32, big-endian	0x48484E53 (Manifest.MAGIC)
format	u8	1
sequence	u64, big-endian	every stored write is at or below it
run count	LEB128	runs, newest first
per run: id	string	blob id of the run
per run: size, index offset, entries	LEB128 each	bytes of the run blob, where its index starts, slots it holds
per run: first, last	byte strings	its smallest and largest key
pending count	LEB128	superseded blobs waiting for deletion
per blob: id, due	string, i64 seconds and i32 nanoseconds	the blob and when it may go
seal	u32, big-endian	CRC32C of everything before it

The local file <data>/s3/index/root holds the manifest's blob id as plain text, rw-------. The id grants read access to the whole namespace.

Writes, flushes and crashes

Tree.write runs the mutation under the writer lock, then journals a non-empty batch, applies it to the active memtable and publishes the new snapshot. A mutation that throws leaves no trace.

flush() persists any frozen memtable, freezes, and persists the frozen memtable again; the first step finishes a flush that failed earlier. The run keeps tombstones only if older runs exist, since without them there is nothing for a tombstone to hide.

Step	What it does	A crash after this step leaves
1. freeze	Renames journal to journal.frozen and starts a new memtable	The old root; both journals replay every write
2. Store the run	Writes the frozen memtable as a run blob	The old root and both journals; the run is named by nothing
3. Store the manifest	Writes a manifest that lists the new run first	The old root and both journals; run and manifest are named by nothing
4. Replace root	Writes root.tmp, forces it, moves it over root atomically and syncs the directory	The new root holds the writes; the frozen journal replays once more, harmlessly
5. Swap the snapshot	Readers move from the frozen memtable to the new run	As after step 4
6. release	Deletes journal.frozen	A complete flush

Moving the root file is the single step that commits. Tree.open resumes at the larger of the manifest's and the journal's highest sequence.

Compaction

Tree.compact merges a size-tiered window of the newest runs: the newest, then each older run no larger than those taken together. That keeps the number of runs about logarithmic in the size of the namespace, while the small, new runs merge most often. Above maxRuns (12) runs it merges all of them. A merge that reaches the oldest run drops tombstones.

Replaced runs and the previous manifest wait in the manifest's pending list for grace (1 hour), longer than any read that may still use them, before sweep() deletes them.

maintain() flushes once the memtable holds 16 MiB or 30 seconds after the oldest unflushed write, then compacts and sweeps. It runs every 5 seconds on the daemon thread namespace-maintenance, and at once when a write takes the unflushed bytes past 16 MiB. A failed round leaves every write in the journal for the next one.

Blob references

Copies and completed multipart uploads share blobs, so References counts the referrers of a blob in its 05 key, within the same transaction as the change. A count that reaches zero becomes a 06 garbage key due after the grace period, and a new reference removes it again.

sweepGarbage picks up to 1000 due blobs from a snapshot. Under the writer lock it claims those still at zero into the set deleting, in which a new reference fails, deletes them, and only then removes their garbage keys, so a crash in between deletes them again.

Listings and versions

Lister walks the keys under a prefix and rolls them up at the delimiter. After a common prefix it seeks past every key under it, so a listing costs a seek per common prefix, not a step per key. Entries and common prefixes count together against at most 1000. A version 2 continuation token is the last key in unpadded URL-safe Base64, and it is not signed.

Mounting and durability

--s3root mounts the namespace another root id names in place of the local one; see S3 endpoint. Unless the local root already names that id, Tree.adopt refuses with "The directory holds unflushed writes of another namespace" while journal is non-empty or journal.frozen exists. A mounted manifest is read only up to maxBlockBytes. One node writes a namespace at a time.

Settings

NamespaceConfig holds the settings of the index. The daemon uses the defaults; there are no options for them.

Setting	Default	Effect
flushBytes	16 MiB	Memtable size that triggers a flush
flushInterval	30 s	Age of the oldest unflushed write that triggers a flush; bounds what a lost node takes with it
maintenanceInterval	5 s	Time between maintenance rounds; zero leaves maintenance to the caller
pageBytes	256 KiB	Keys and values that close a run page
bloomBitsPerKey	10	Bloom filter bits per key
cacheBytes	32 MiB	Budget of the decoded page and index cache
maxBlockBytes	256 MiB	Largest run page, run index or manifest a read accepts
grace	1 h	How long a superseded run, manifest or released object blob survives
maxRuns	12	Run count above which a compaction merges all runs

In the source

• s3/src/main/java/org/unigrid/hedgehog/s3/index/Namespace.java: the typed interface, maintenance and the garbage sweep
• s3/src/main/java/org/unigrid/hedgehog/s3/index/Tree.java: writes, flushes, compaction and mounting
• s3/src/main/java/org/unigrid/hedgehog/s3/index/Keys.java, Records.java, Codec.java: keys and records
• s3/src/main/java/org/unigrid/hedgehog/s3/index/Journal.java, Memtable.java, Snapshot.java: the node-local half
• s3/src/main/java/org/unigrid/hedgehog/s3/index/RunWriter.java, Run.java, Page.java, RunIndex.java, Bloom.java, PageCache.java: runs
• s3/src/main/java/org/unigrid/hedgehog/s3/index/Manifest.java, References.java, Lister.java: the manifest, blob references and listings
• s3/src/main/java/org/unigrid/hedgehog/s3/index/NamespaceConfig.java: the settings