Documentation
¶
Overview ¶
Package lookup provides a key-value store backed data structure which finds and stores a short, unique binary identifier for a longer piece of binary data using an efficient, non-cryptographic hash function.
A new lookup Table can be created with the NewTable() function. Advanced users can use the NewTableWithOptions() function to tweak the underlying parameters, but the defaults were chosen based on testing and should provide a good balance of performance and storage efficiency.
Shortened identifiers are created or retrieved using the idempotent Table.GetOrCreateID method.
Using the default algorithm which uses the first 4 bytes of a 64-bit FNV-1a hash and then increases the length the the case of collisions, identifiers will be 4 bytes long and retrieved with a single KV-store lookup in the vast majority of cases and will sometimes be 5 or rarely 6 bytes long and require 2 to 3 total reads. In some rare cases (which have not appeared in tests), identifiers may be longer or require more lookups.
Given a shortened identifier, the underlying binary data can be retrieved with the Table.GetValue method.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type KVStore ¶
type KVStore interface {
// Get returns nil iff key doesn't exist. Panics on nil key.
Get(key []byte) []byte
// Set sets the key. Panics on nil key or value.
Set(key, value []byte)
}
KVSTore is the interface for key-value stores that Tables operate on.
type Table ¶
type Table interface {
// GetOrCreateID is an idempotent method for creating or retrieving an unique
// shortened identifier for the provided binary value.
GetOrCreateID(store KVStore, value []byte) []byte
// GetID returns the shortened identifier for the provided binary value if
// it exists or nil.
GetID(store KVStore, value []byte) []byte
// GetValue returns the binary data (if any) corresponding to the provided shortened identifier.
GetValue(store KVStore, id []byte) []byte
}
Table is the interface for interacting with a lookup table.
func NewTable ¶
NewTable creates a new lookup table for the provided, optional KVStore prefix using default parameters. Default parameters are currently set to use the first 4-bytes of the FNV-1a 64-bit, non-cryptographic hash. In the case of a collision, more bytes of the hash will be used for disambiguation but this happens in a minority of cases except for massively large data sets.
func NewTableWithOptions ¶
func NewTableWithOptions(options TableOptions) (Table, error)
NewTableWithOptions creates a Table with custom options. Most users should just use NewTable with the default values.
type TableOptions ¶
type TableOptions struct {
// NewHash is a function which returns a new hash.Hash instance.
NewHash func() hash.Hash
// MinLength is the minimum number of hash bytes that will be used to create a lookup identifier.
MinLength int
// Prefix is an optional prefix to be pre-pended to all KVStore keys.
Prefix []byte
}
TableOptions is used to specify custom table options and should only be used by advanced users.
Source Files