README
¶
a fast flat-file index for constant datasets
This package specifies a file format and Go implementation for indexing constant datasets.
compactindex …
- is an immutable file format;
- maps arbitrary keys into offsets in an external flat file;
- consumes a constant amount of space per entry
- ~6-8 bytes, regardless of key size
- 3 bytes per enty
O(1)complexity queries, with2 + log2(10000)lookups worst- & average-case (binary search);- during construction, requires near-constant memory space and
O(n)scratch space with regard to entries per file; - during construction, features a constant >500k entry/s per-core write rate (2.5 GHz Intel laptop);
- works on any storage supporting random reads (regular files, HTTP range requests, on-chain, ...);
- is based on the "FKS method" which uses perfect (collision-free) hash functions in a two-level hashtable; [^1]
- is inspired by D. J. Bernstein's "constant database"; [^2]
- uses the xxHash64 non-cryptographic hash-function; [^3]
Refer to the Go documentation for the algorithms used and implementation details.
[^1]: Fredman, M. L., Komlós, J., & Szemerédi, E. (1984). Storing a Sparse Table with 0 (1) Worst Case Access Time. Journal of the ACM, 31(3), 538–544. https://doi.org/10.1145/828.1884 [^2]: cdb by D. J. Bernstein https://cr.yp.to/cdb.html [^3]: Go implementation of xxHash by @cespare: https://github.com/cespare/xxhash/
Interface
In programming terms:
fn lookup(key: &[byte]) -> Option<u64>
Given an arbitrary key, the index
- states whether the key exists in the index
- if it exists, maps the key to an integer (usually an offset into a file)
Examples
Here are some example scenarios where compactindex is useful:
- When working with immutable data structures
- Example: Indexing IPLD CAR files carrying Merkle-DAGs of content-addressable data
- When working with archived/constant data
- Example: Indexing files in
.tararchives
- Example: Indexing files in
- When dealing with immutable remote storage such as S3-like object storage
- Example: Storing the index and target file in S3, then using HTTP range requests to efficiently query data
Here are some things compactindex cannot do:
- Cannot add more entries to an existing index
- Reason 1: indexes are tightly packed, so there is no space to insert new entries (though
fallocate(2)withFALLOC_FL_INSERT_RANGEwould technically work) - Reason 2: the second-level hashtable uses a perfect hash function ensuring collision-free indexing of a subset of entries; inserting new entries might cause a collision requiring
- Reason 3: adding too many entries will eventually create an imbalance in the first-level hashtable; fixing this imbalance effectively requires re-constructing the file from scratch
- Reason 1: indexes are tightly packed, so there is no space to insert new entries (though
- Cannot iterate over keys
- Reason: compactindex stores hashes, not the entries themselves. This saves space but also allows for efficient random reads used during binary search
File Format (v0)
Encoding
The file format contains binary packed structures with byte alignment.
Integers are encoded as little endian.
File Header
The file beings with a 32 byte file header.
#[repr(packed)]
struct FileHeader {
magic: [u8; 8], // 0x00
max_value: u64, // 0x08
num_buckets: u32, // 0x10
padding_14: [u8; 12], // 0x14
}
magicis set to the UTF-8 string"rdcecidx". The reader should reject files that don't start with this string.num_bucketsis set to the number of hashtable buckets.max_valueindicates the integer width of index values.padding_14must be zero. (reserved for future use)
Bucket Header Table
The file header is followed by a vector of bucket headers.
The number of is set by num_buckets in the file header.
Each bucket header is 16 bytes long.
#[repr(packed)]
struct BucketHeader {
hash_domain: u32, // 0x00
num_entries: u32, // 0x04
hash_len: u8, // 0x08
padding_09: u8, // 0x09
file_offset: u48, // 0x10
}
hash_domainis a "salt" to the per-bucket hash function.num_entriesis set to the number of records in the bucket.hash_lenis the size of the per-record hash in bytes and currently hardcoded to3.padding_09must be zero.file_offsetis an offset from the beginning of the file header to the start of the bucket entries.
Bucket Entry Table
Each bucket has a vector of entries with length num_entries.
This structure makes up the vast majority of the index.
#[repr(packed)]
struct Entry {
hash: u??,
value: u??,
}
The size of entry is static within a bucket. It is determined by its components:
- The size of
hashin bytes equalshash_len - The size of
valuein bytes equals the byte aligned integer width that is minimally required to representmax_value
Documentation
¶
Overview ¶
Package compactindex is an immutable hashtable index format inspired by djb's constant database (cdb).
Design ¶
Compactindex is used to create secondary indexes over arbitrary flat files. Each index is a single, immutable flat file.
Index files consist of a space-optimized and query-optimized key-value-like table.
Instead of storing actual keys, the format stores FKS dynamic perfect hashes. And instead of storing values, the format contains offsets into some file.
As a result, the database effectively only supports two operations, similarly to cdb. (Note that the actual Go interface is a bit more flexible).
func Create(kv map[[]byte]uint64) *Index func (*Index) Lookup(key []byte) (value uint64, exist bool)
Buckets ¶
The set of items is split into buckets of approx 10000 records. The number of buckets is unlimited.
The key-to-bucket assignment is determined by xxHash3 using uniform discrete hashing over the key space.
The index file header also mentions the number of buckets and the file offset of each bucket.
Tables ¶
Each bucket contains a table of entries, indexed by a collision-free hash function.
The hash function used in the entry table is xxHash. A 32-bit hash domain is prefixed to mine collision-free sets of hashes (FKS scheme). This hash domain is also recorded at the bucket header.
Each bucket entry is a constant-size record consisting of a 3-byte hash and an offset to the value. The size of the offset integer is the minimal byte-aligned integer width that can represent the target file size.
Querying ¶
The query interface (DB) is backend-agnostic, supporting any storage medium that provides random reads. To name a few: Memory buffers, local files, arbitrary embedded buffers, HTTP range requests, plan9, etc...
The DB struct itself performs zero memory allocations and therefore also doesn't cache. It is therefore recommended to provide a io.ReaderAt backed by a cache to improve performance.
Given a key, the query strategy is simple:
- Hash key to bucket using global hash function
- Retrieve bucket offset from bucket header table
- Hash key to entry using per-bucket hash function
- Search for entry in bucket (binary search)
The search strategy for locating entries in buckets can be adjusted to fit the latency/bandwidth profile of the underlying storage medium.
For example, the fastest lookup strategy in memory is a binary search retrieving double cache lines at a time. When doing range requests against high-latency remote storage (e.g. S3 buckets), it is typically faster to retrieve and scan through large parts of a bucket (multiple kilobytes) at once.
Construction ¶
Constructing a compactindex requires upfront knowledge of the number of items and highest possible target offset (read: target file size).
The process requires scratch space of around 16 bytes per entry. During generation, data is offloaded to disk for memory efficiency.
The process works as follows:
- Determine number of buckets and offset integer width based on known input params (item count and target file size).
- Linear pass over input data, populating temporary files that contain the unsorted entries of each bucket.
- For each bucket, brute force a perfect hash function that defines a bijection between hash values and keys in the bucket.
- For each bucket, sort by hash values.
- Store to index.
An alternative construction approach is available when the number of items or target file size is unknown. In this case, a set of keys is first serialized to a flat file.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ErrCollision = errors.New("hash collision")
var ErrNotFound = errors.New("not found")
ErrNotFound marks a missing entry.
var Magic = [8]byte{'r', 'd', 'c', 'e', 'c', 'i', 'd', 'x'}
Magic are the first eight bytes of an index.
Functions ¶
func EntryHash64 ¶
EntryHash64 is a xxHash-based hash function using an arbitrary prefix.
Types ¶
type Bucket ¶
type Bucket struct {
BucketDescriptor
Entries *io.SectionReader
}
Bucket is a database handle pointing to a subset of the index.
type BucketDescriptor ¶
type BucketDescriptor struct {
BucketHeader
Stride uint8 // size of one entry in bucket
OffsetWidth uint8 // with of offset field in bucket
}
type BucketHeader ¶
BucketHeader occurs at the beginning of each bucket.
func (*BucketHeader) Hash ¶
func (b *BucketHeader) Hash(key []byte) uint64
Hash returns the per-bucket hash of a key.
func (*BucketHeader) Load ¶
func (b *BucketHeader) Load(buf *[bucketHdrLen]byte)
func (*BucketHeader) Store ¶
func (b *BucketHeader) Store(buf *[bucketHdrLen]byte)
type Builder ¶
type Builder struct {
Header
// contains filtered or unexported fields
}
Builder creates new compactindex files.
func NewBuilder ¶
NewBuilder creates a new index builder.
If dir is an empty string, a random temporary directory is used.
numItems refers to the number of items in the index.
targetFileSize is the size of the file that index entries point to. Can be set to zero if unknown, which results in a less efficient (larger) index.
func (*Builder) Insert ¶
Insert writes a key-value mapping to the index.
Index generation will fail if the same key is inserted twice. The writer must not pass a value greater than targetFileSize.
type DB ¶
DB is a compactindex handle.
func Open ¶
Open returns a handle to access a compactindex.
The provided stream must start with the Magic byte sequence. Tip: Use io.NewSectionReader to create aligned substreams when dealing with a file that contains multiple indexes.
type Entry ¶
Entry is a single element in a hash table.
func SearchSortedEntries ¶
SearchSortedEntries performs an in-memory binary search for a given hash.
Source Files