README
¶
SNTable
Custom SSTable implementation
for Go. Instead of arbitrary bytes strings, this implementation assumes numeric 8-byte (uint64)
keys. Blocks can be stored uncompressed or compressed with Snappy (default)
or Zstandard.
Examples
Writer:
package main
import (
"log"
"os"
"github.com/bsm/sntable"
)
func main() {
// create a file
f, err := os.CreateTemp("", "sntable-example")
if err != nil {
log.Fatalln(err)
}
defer f.Close()
// wrap writer around file, append (neglecting errors for demo purposes)
w := sntable.NewWriter(f, nil)
_ = w.Append(101, []byte("foo"))
_ = w.Append(102, []byte("bar"))
_ = w.Append(103, []byte("baz"))
// close writer
if err := w.Close(); err != nil {
log.Fatalln(err)
}
// explicitly close file
if err := f.Close(); err != nil {
log.Fatalln(err)
}
}
Reader:
package main
import (
"log"
"os"
"github.com/bsm/sntable"
)
func main() {
// open a file
f, err := os.Open("mystore.snt")
if err != nil {
log.Fatalln(err)
}
defer f.Close()
// get file size
fs, err := f.Stat()
if err != nil {
log.Fatalln(err)
}
// wrap reader around file
r, err := sntable.NewReader(f, fs.Size())
if err != nil {
log.Fatalln(err)
}
val, err := r.Get(101)
if err == sntable.ErrNotFound {
log.Println("Key not found")
} else if err != nil {
log.Fatalln(err)
} else {
log.Printf("Value: %q\n", val)
}
}
Stats, Lies, Benchmarks
$ go version
go version go1.12.5 linux/amd64
$ sudo sh -c 'sync; echo 3 > /proc/sys/vm/drop_caches'
$ go test -bench=. -benchmem
goos: linux
goarch: amd64
pkg: github.com/bsm/sntable/bench
Benchmark/bsm/sntable_10M_plain-4 500000 2381 ns/op 208 B/op 4 allocs/op
Benchmark/golang/leveldb_10M_plain-4 200000 6763 ns/op 10301 B/op 6 allocs/op
Benchmark/syndtr/goleveldb_10M_plain-4 300000 5134 ns/op 691 B/op 6 allocs/op
Benchmark/bsm/sntable_10M_snappy-4 1000000 2324 ns/op 208 B/op 4 allocs/op
Benchmark/golang/leveldb_10M_snappy-4 200000 6630 ns/op 10301 B/op 6 allocs/op
Benchmark/syndtr/goleveldb_10M_snappy-4 200000 5917 ns/op 696 B/op 6 allocs/op
Documentation
¶
Overview ¶
Package sntable contains a custom SSTable implementation which, instead of arbitrary bytes strings, assumes 8-byte numeric keys.
Data Structure Documentation ¶
Store ¶
A store contains a series of data blocks followed by an index and a store footer.
Store layout: +---------+---------+---------+-------------+--------------+ | block 1 | ... | block n | block index | store footer | +---------+---------+---------+-------------+--------------+ Block index: +----------------------------+--------------------+----------------------------------+--------------------------+--------+ | last cell block 1 (varint) | offset 2 (varint) | last cell block 2 (varint,delta) | offset 2 (varint,delta) | ... | +----------------------------+--------------------+----------------------------------+--------------------------+--------+ Store footer: +------------------------+------------------+ | index offset (8 bytes) | magic (8 bytes) | +------------------------+------------------+
Block ¶
A block comprises of a series of sections, followed by a section index and a single-byte compression type indicator.
Block layout: +-----------+---------+-----------+---------------+---------------------------+ | section 1 | ... | section n | section index | compression type (1-byte) | +-----------+---------+-----------+---------------+---------------------------+ Section index: +----------------------------+-------+----------------------------+-------------------------------+ | section offset 2 (4 bytes) | ... | section offset n (4 bytes) | number of sections (4 bytes) | +----------------------------+-------+----------------------------+-------------------------------+
Section ¶
A section is a series of key/value pairs where the first key is stored as a full uint64 while subsequent keys are delta encoded.
+----------------+----------------------+------------------+----------------------+----------------------+------------------+-------+ | key 1 (varint) | value len 1 (varint) | value 1 (varlen) | key 2 (varint,delta) | value len 2 (varint) | value 2 (varlen) | ... | +----------------+----------------------+------------------+----------------------+----------------------+------------------+-------+
Index ¶
- Variables
- type BlockReader
- type Compression
- type Iterator
- type Reader
- func (r *Reader) Append(dst []byte, key uint64) ([]byte, error)
- func (r *Reader) Get(key uint64) ([]byte, error)
- func (r *Reader) GetBlock(bpos int) (*BlockReader, error)
- func (r *Reader) NumBlocks() int
- func (r *Reader) Seek(key uint64) (*Iterator, error)
- func (r *Reader) SeekBlock(key uint64) (*BlockReader, error)
- type SectionReader
- type Writer
- type WriterOptions
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrNotFound = errors.New("sntable: not found")
ErrNotFound is returned by the reader when a key cannot be found.
Functions ¶
This section is empty.
Types ¶
type BlockReader ¶
type BlockReader struct {
// contains filtered or unexported fields
}
BlockReader reads a single block.
func (*BlockReader) GetSection ¶
func (r *BlockReader) GetSection(spos int) *SectionReader
GetSection gets a single section.
func (*BlockReader) NumSections ¶
func (r *BlockReader) NumSections() int
NumSections returns the number of sections in this block.
func (*BlockReader) Pos ¶
func (r *BlockReader) Pos() int
Pos returns the index position the current block within the table.
func (*BlockReader) Release ¶
func (r *BlockReader) Release()
Release releases the block reader and frees up resources. The reader must not be used after this method is called.
func (*BlockReader) SeekSection ¶
func (r *BlockReader) SeekSection(key uint64) *SectionReader
SeekSection seeks the section for a key.
type Compression ¶
type Compression byte
Compression is the compression codec
const ( SnappyCompression Compression = iota NoCompression ZstdCompression )
Supported compression codecs
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator is a convenience wrapper around BlockReader and SectionReader which can (forward-) iterate over keys across block and section boundaries.
type Reader ¶
type Reader struct {
// contains filtered or unexported fields
}
Reader instances can seek and iterate across data in tables.
Example ¶
package main
import (
"log"
"os"
"github.com/bsm/sntable"
)
func main() {
// open a file
f, err := os.Open("mystore.snt")
if err != nil {
log.Fatalln(err)
}
defer func() { _ = f.Close() }()
// get file size
fs, err := f.Stat()
if err != nil {
log.Fatalln(err)
}
// wrap reader around file
r, err := sntable.NewReader(f, fs.Size())
if err != nil {
log.Fatalln(err)
}
val, err := r.Get(101)
if err == sntable.ErrNotFound {
log.Println("Key not found")
} else if err != nil {
log.Fatalln(err)
} else {
log.Printf("Value: %q\n", val)
}
}
Output:
func (*Reader) Append ¶
Append retrieves a single value for a key. Unlike Get it doesn't appends it to dst instead of allocating a new byte slice. It may return an ErrNotFound error.
func (*Reader) GetBlock ¶
func (r *Reader) GetBlock(bpos int) (*BlockReader, error)
GetBlock returns a reader for the n-th block.
type SectionReader ¶
type SectionReader struct {
// contains filtered or unexported fields
}
SectionReader reads an individual section within a block.
func (*SectionReader) Key ¶
func (r *SectionReader) Key() uint64
Key returns the key if the current entry.
func (*SectionReader) More ¶
func (r *SectionReader) More() bool
More returns true if more data can be read in the section.
func (*SectionReader) Next ¶
func (r *SectionReader) Next() bool
Next advances the cursor to the next entry within the section and returns true if successful.
func (*SectionReader) Pos ¶
func (r *SectionReader) Pos() int
Pos returns the index position the current section within the block.
func (*SectionReader) Release ¶ added in v0.1.1
func (r *SectionReader) Release()
Release releases the section reader and frees up resources. The reader must not be used after this method is called.
func (*SectionReader) Seek ¶
func (r *SectionReader) Seek(key uint64) bool
Seek positions the cursor before the key.
func (*SectionReader) Value ¶
func (r *SectionReader) Value() []byte
Value returns the value of the current entry. Please note that values are temporary buffers and must be copied if used beyond the next cursor move.
type Writer ¶
type Writer struct {
// contains filtered or unexported fields
}
Writer instances can write a table.
Example ¶
package main
import (
"log"
"os"
"github.com/bsm/sntable"
)
func main() {
// create a file
f, err := os.CreateTemp("", "sntable-example")
if err != nil {
log.Fatalln(err)
}
defer func() { _ = f.Close() }()
// wrap writer around file, append (neglecting errors for demo purposes)
w := sntable.NewWriter(f, nil)
_ = w.Append(101, []byte("foo"))
_ = w.Append(102, []byte("bar"))
_ = w.Append(103, []byte("baz"))
// close writer
if err := w.Close(); err != nil {
log.Fatalln(err)
}
// explicitly close file
if err := f.Close(); err != nil {
log.Fatalln(err)
}
}
Output:
func NewWriter ¶
func NewWriter(w io.Writer, o *WriterOptions) *Writer
NewWriter wraps a writer and returns a Writer.
type WriterOptions ¶
type WriterOptions struct {
// BlockSize is the minimum uncompressed size in bytes of each table block.
// Default: 4KiB.
BlockSize int
// BlockRestartInterval is the number of keys between restart points
// for delta encoding of keys.
//
// Default: 16.
BlockRestartInterval int
// The compression codec to use.
// Default: SnappyCompression.
Compression Compression
// BloomBitsPerKey enables an in-file bloom filter with this many bits per
// key. 10 gives a ~1% false-positive rate. Zero (the default) disables the
// filter and keeps the file format identical to older versions.
//
// A filter lets the reader answer "definitely absent" without reading a
// data block, which is a large win when most lookups miss.
BloomBitsPerKey int
// BloomExpectedKeys sizes the bloom filter up front so the writer never has
// to buffer keys. It is required when BloomBitsPerKey > 0. A rough estimate
// is fine: too low only raises the false-positive rate, it never causes a
// false negative.
BloomExpectedKeys int
}
WriterOptions define writer specific options.
Source Files
Directories