README
¶
HFile v1 implementation in Go
HFile is a KV file format (borrowed from HBase, based on SSTables) used at foursquare as the storage format for our distributed KV store quiver.
HFiles are designed to be simultaneously a) easily to generate incrementally (metadata is flushed at the end) and b) easy to serve / search as-is (thanks to an index), making them friendly to pipelines that regenerate large datasets and need to bulk-load them into production regularly.
Summary of HFile format
On-disk, an HFile consists of:
- some number of blocks,
- an index, specifying the offset and length of each block along with its first key
- a fixed-size, fixed-layout trailer of metadata
Each block contains some number of key-value pairs, each in the form of two 4-byte sizes i and j, followed by i bytes of key and j bytes of value.
Finding data in an Hfile
Callers likely want to construct a Reader per file, and a Scanner per request.
Scanners are stateful (see below) and are not threadsafe.
Reader
Readers mmap a file, read the trailer to find the index and load the index into memory. When a specific block's data is requested, the reader uses the index's offsets to find its data, decompresses it if needed and returns it.
Scanner
A scanner looks up a key by binary searching the reader's block index, comparing the firstKey until it finds the last block with a starting key less than or equal to the requested key. It then iterates through the key-value pairs of the block until it finds a matching key, or returns nothing if it finds a greater key or the end of the block.
Sorting requested keys
Scanners keep a reference to the most-recently loaded block, and their position within said block. Subsequent lookups only binary search the remaining blocks, and, when searching the current block, only search forward from the current position. This saves substantial repeated searching, but requires that keys be looked up in ascending order.
Scanners can be Reset() to return to their initial state.
Scanners keep track of the last key they looked up, and will error if a smaller key is requested.
Writer
Writers support creating an hfile by repeatedly passing key-value pairs to Write(k,v), in ascending order by key, before calling Close() to flush the index and metadata.
Writers buffer written k-v pairs until they reach blockSize, after which the next new key written will flush the block (optionally compressed) to the underlying storage and start a new one. NB: Since all k-v pairs for a given key must appear in the same block, emiting too many values for the same key, or very large values, can cause blocks to grow well beyond blockSize.
NewWriter wraps any io.WriteCloser. NewLocalWriter provides a helper that uses a local file at supplied path.
Authors
Documentation
¶
Index ¶
- Variables
- func After(a, b []byte) bool
- func GenerateMockHfile(path string, keyCount, blockSize int, compress, verbose, progress bool) error
- func GenerateMockMultiHfile(path string, keyCount, blockSize int, compress, verbose, progress bool) error
- func MockKeyInt(i int) []byte
- func MockMultiValueInt(i, k int) []byte
- func MockValueForMockKey(key []byte) []byte
- func MockValueInt(i int) []byte
- func WriteMockIntPairs(w *Writer, keyCount int, progress bool, multi bool) error
- type Block
- type CollectionConfig
- type CollectionSet
- type FileInfo
- type Iterator
- func (it *Iterator) AllForPrefixes(prefixes [][]byte, limit int32, lastKey []byte) (map[string][][]byte, []byte, error)
- func (it *Iterator) Key() []byte
- func (it *Iterator) Next() (bool, error)
- func (it *Iterator) Release()
- func (it *Iterator) Reset()
- func (it *Iterator) Seek(requested []byte) (bool, error)
- func (it *Iterator) Value() []byte
- type LoadMethod
- type OrderedOps
- type Reader
- func (r *Reader) CalculateBloom(falsePosRate float64) error
- func (r *Reader) DisableBloom()
- func (r *Reader) EnableBloom()
- func (r *Reader) FindBlock(from int, key []byte) int
- func (r *Reader) FirstKey() ([]byte, error)
- func (r *Reader) GetBlockBuf(i int, dst []byte) ([]byte, error)
- func (r *Reader) GetIterator() *Iterator
- func (r *Reader) GetScanner() *Scanner
- func (r *Reader) MightContain(key []byte) bool
- func (r *Reader) PrintDebugInfo(out io.Writer, includeStartKeys int)
- type Scanner
- type Trailer
- type Writer
Constants ¶
This section is empty.
Variables ¶
var CompressionNone = uint32(2)
var CompressionSnappy = uint32(3)
var DataMagic = []byte("DATABLK*")
var IndexMagic = []byte("IDXBLK)+")
var TrailerMagic = []byte("TRABLK\"$")
Functions ¶
func GenerateMockHfile ¶
func GenerateMockMultiHfile ¶
func MockKeyInt ¶
func MockMultiValueInt ¶
func MockValueForMockKey ¶
func MockValueInt ¶
Types ¶
type CollectionConfig ¶
type CollectionConfig struct {
// The Name of the collection.
Name string
// The Hfile itself.
SourcePath string
// A local copy of SourcePath, if SourcePath is remote, otherwise the same as SourcePath.
LocalPath string
// If the collection data should be kept in-memory (via mlock).
LoadMethod LoadMethod
// Should operations on this collection emit verbose debug output.
Debug bool
// This "collection" may, in fact, be a partition (subset) of some larger (sharded) collection.
ParentName string
ShardFunction string
Partition string
TotalPartitions string
// contains filtered or unexported fields
}
type CollectionSet ¶
type CollectionSet struct {
Collections map[string]*Reader
// contains filtered or unexported fields
}
func LoadCollections ¶
func LoadCollections(collections []*CollectionConfig, cache string, downloadOnly bool, stats *report.Recorder) (*CollectionSet, error)
func TestdataCollectionSet ¶
func TestdataCollectionSet(name string, count int, compress bool, load LoadMethod) (*CollectionSet, error)
type Iterator ¶
type Iterator struct {
OrderedOps
// contains filtered or unexported fields
}
func NewIterator ¶
func (*Iterator) AllForPrefixes ¶
func (*Iterator) Key ¶
A copy of the current key it.key is a pointer into a buffer that may get recycled for another block, thus the copy.
func (*Iterator) Next ¶
Load a kv pair into it.key/it.value and advance the iterator. Return true if a kv pair was loaded (eg can call Key), or false if at EOF.
func (*Iterator) Seek ¶
Position the iterator at-or-after requested key by seeking forward from current position.
If already at-or-after, this is a no-op. Otherwise, if the requested key exists, it will be positioned there, otherwise at the first key greater than the requested one. Returns true if, after positioning, the iterator is on a valid key (eg not at EOF), same as Next.
type OrderedOps ¶
type OrderedOps struct {
// contains filtered or unexported fields
}
func (*OrderedOps) CheckIfKeyOutOfOrder ¶
func (s *OrderedOps) CheckIfKeyOutOfOrder(key []byte) error
func (*OrderedOps) ResetState ¶
func (s *OrderedOps) ResetState()
func (*OrderedOps) Same ¶
func (s *OrderedOps) Same(key []byte) bool
type Reader ¶
type Reader struct {
CollectionConfig
FileInfo
Trailer
// contains filtered or unexported fields
}
func NewReaderFromConfig ¶
func NewReaderFromConfig(cfg CollectionConfig) (*Reader, error)
func (*Reader) CalculateBloom ¶
func (*Reader) DisableBloom ¶
func (r *Reader) DisableBloom()
func (*Reader) EnableBloom ¶
func (r *Reader) EnableBloom()
func (*Reader) GetIterator ¶
func (*Reader) GetScanner ¶
func (*Reader) MightContain ¶
type Scanner ¶
type Scanner struct {
// When off, maybe be faster but may return incorrect results rather than error on out-of-order keys.
EnforceKeyOrder bool
OrderedOps
// contains filtered or unexported fields
}
func NewScanner ¶
type Writer ¶
type Writer struct {
OrderedOps
// contains filtered or unexported fields
}
Source Files
Directories