README
¶
Starskey is a fast embedded key-value store package for GO! Starskey implements a multi-level, durable log structured merge tree.
Features
- Leveled partial merge compaction Compactions occur on writes. If any disk level reaches its maximum size, half of the sstables are merged into a new sstable and placed into the next level. This algorithm is recursive until the last level. At the last level, if full, we merge all sstables into a new sstable. During merge operations, tombstones (deleted keys) are removed when a key reaches the last level.
- Simple API with Put, Get, Delete, Range, FilterKeys, Update (for txns), PrefixSearch, LongestPrefixSearch, DeleteByRange, DeleteByFilter, DeleteByPrefix.
- Acid transactions You can group multiple operations into a single atomic transaction. If any operation fails the entire transaction is rolled back. Only committed operations within a transaction roll back. These transactions would be considered fully serializable. Transactions themselves are also thread safe so you can add operations to them safety.
- Configurable options You can configure many options such as max levels, memtable threshold, bloom filter,succinct range filters, logging, compression and more.
- WAL with recovery Starskey uses a write ahead log to ensure durability. Memtable is replayed if a flush did not occur prior to shut down. On sorted runs to disk the WAL is truncated.
- Key value separation Keys and values are stored separately for sstables within a klog and vlog respectively.
- Bloom filters Each sstable has an in memory bloom filter to reduce disk reads. Bloom filters are used to check if a key exists in an SST instead of scanning it entirely.
- Succinct Range Filters If enabled, each sstable will use a SuRF instead of a bloom filter; This will speed up range, prefix queries. Will use more memory than bloom filters. Only a bloom filter OR a SuRF filter can be enabled.
- Fast up to 400k+ ops per second.
- Compression S2, and Snappy compression is available.
- Logging Logging to file is available. Will write to standard out if not enabled.
- Thread safe Starskey is thread safe. Multiple goroutines can read and write to Starskey concurrently. Starskey uses one global lock to keep things consistent.
- T-Tree memtable the memory table is a balanced in-memory tree data structure, designed as an alternative to AVL trees and B-Trees for main-memory.
Discord
Chat everything Starskey @ our Discord Server
Bench
Use the benchmark program at bench to compare Starskey with other popular key value stores/engines.
Basic Example
Below is a basic example of how to use Starskey.
Mind you examples use skey as the variable name for opened starskey instance(s).
import (
"fmt"
"github.com/starskey-io/starskey"
)
func main() {
skey, err := starskey.Open(&starskey.Config{
Permission: 0755, // Dir, file permission
Directory: "db_dir", // Directory to store data
FlushThreshold: (1024 * 1024) * 24, // 24mb Flush threshold in bytes, for production use 64mb or higher
MaxLevel: 3, // Max levels number of disk levels
SizeFactor: 10, // Size factor for each level. Say 10 that's 10 * the FlushThreshold at each level. So level 1 is 10MB, level 2 is 100MB, level 3 is 1GB.
BloomFilter: false, // If you want to use bloom filters
SuRF: false, // If enabled will speed up range queries as we check if an sstable has the keys we are looking for.
Logging: true, // Enable logging to file
Compression: false, // Enable compression
CompressionOption: starskey.NoCompression, // Or SnappyCompression, S2Compression
// Internal options
// Optional: &OptionalConfig{
// BackgroundFSync: .. If you don't want to fsync writes to disk (default is true)
// BackgroundFSyncInterval: .. Interval for background fsync, if configured true (default is 256ms)
// TTreeMin: .. Minimum degree of the T-Tree
// TTreeMax: .. Maximum degree of the T-Tree
// PageSize: .. Page size for internal pagers
// BloomFilterProbability: .. Bloom filter probability
// },
}) // Config cannot be nil**
if err != nil {
// ..handle error
}
key := []byte("some_key")
value := []byte("some_value")
// Write key-value pair
if err := skey.Put(key, value); err != nil {
// ..handle error
}
// Read key-value pair
v, err := skey.Get(key)
if err != nil {
// ..handle error
}
// Value is nil if key does not exist
if v == nil {
// ..handle error
}
fmt.Println(string(key), string(v))
// Close starskey
if err := skey.Close(); err != nil {
// ..handle error
}
}
Range Keys
You can provide a start and end key to retrieve a range of keys values.
results, err := skey.Range([]byte("key900"), []byte("key980"))
if err != nil {
// ..handle error
}
// results is [][]byte where each element is a value
for _, value := range results {
fmt.Println(string(value)) // Each result is just the value
}
Filter Keys
You can filter keys to retrieve values based on a filter/compare method.
compareFunc := func(key []byte) bool {
// if has prefix "c" return true
return bytes.HasPrefix(key, []byte("c"))
}
results, err := skey.FilterKeys(compareFunc)
if err != nil {
// ..handle error
}
Prefix Searches
Starskey supports optimized prefix searches.
Longest Prefix Search
You can search for longest key with a common prefix.
result, n, err := skey.LongestPrefixSearch([]byte("common_prefix"))
if err != nil {
// ..handle error
}
Prefix Search
You can search for keys value's with a common prefix.
results, err := skey.PrefixSearch([]byte("ke"))
if err != nil {
// ..handle error
}
Acid Transactions
Using atomic transactions to group multiple operations into a single atomic transaction. If any operation fails the entire transaction is rolled back. Only committed operations roll back.
txn := skey.BeginTxn()
if txn == nil {
// ..handle error
}
txn.Put([]byte("key"), []byte("value"))
// or txn.Delete([]byte("key"))
if err := txn.Commit(); err != nil {
// ..handle error
}
OR
You should use Update if you want to say Get a value, modify it and then Put it back as an atomic operation.
Say you want to increment a value, below is an example of how to do that.
err = skey.Update(func(txn *starskey.Txn) error {
value, err := txn.Get([]byte("key"))
if err != nil {
return err
}
// Increment value
i, err := strconv.Atoi(string(value))
if err != nil {
return err
}
i++ // Increment value
txn.Put([]byte("key"), []byte(strconv.Itoa(i))) // Put back incremented value, this update is atomic
return nil // Commit
})
if err != nil {
// ..handle error
}
err = skey.Update(func(txn *starskey.Txn) error {
txn.Put([]byte("key"), []byte("value")) // or txn.Delete, txn.Get
// ..
return nil // Commit
})
if err != nil {
// ..handle error
}
Delete
Delete a key value pair from starskey.
if err := skey.Delete([]byte("key")); err != nil {
// ..handle error
}
Delete operations removing multiple key values return an n value which is the amount of keys deleted.
Delete by range
Delete key values within a range.
if n, err := skey.DeleteByRange([]byte("startKey"), []byte("endKey")); err != nil {
// ..handle error
}
// n is amount of keys deleted
Delete by filter
Delete key values based on a filter/compare method. You're comparing a key with a function and if it returns true the key is deleted.
compareFunc := func(key []byte) bool {
// if has prefix "c" return true
return bytes.HasPrefix(key, []byte("c"))
}
if n, err := skey.DeleteByFilter(compareFunc); err != nil {
// ..handle error
}
// n is amount of keys deleted
Delete by key prefix
Delete key values with a common prefix.
if n, err := skey.DeleteByPrefix([]byte("key")); err != nil {
// ..handle error
}
// n is amount of keys deleted
Key Lifecycle
A key once inserted will live in the memtable until it is flushed to disk. Once flushed to disk it will live in a sstable at l1 until it is compacted. Once compacted it will be merged into a new sstable at the next level. This process is recursive until the last level. At the last level if full we merge all sstables into a new sstable.
If a key is deleted it will live on the same way until it reaches last level at which point it will be removed entirely.
Memory and disk sorting
The sorting internally would be lexicographical (alphabetical), meaning it will sort based on the byte-by-byte comparisons of slices. We use bytes.Compare to sort keys in memory and on disk.
Documentation
¶
Overview ¶
Package starskey
(C) Copyright Starskey
Original Author: Alex Gaetano Padula
Licensed under the Mozilla Public License, v. 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
https://www.mozilla.org/en-US/MPL/2.0/
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
Index ¶
- Variables
- type CompressionOption
- type Config
- type KLogRecord
- type Level
- type OperationType
- type OptionalConfig
- type SSTable
- type Starskey
- func (skey *Starskey) BeginTxn() *Txn
- func (skey *Starskey) Close() error
- func (skey *Starskey) Delete(key []byte) error
- func (skey *Starskey) DeleteByFilter(compare func(key []byte) bool) (int, error)
- func (skey *Starskey) DeleteByPrefix(prefix []byte) (int, error)
- func (skey *Starskey) DeleteByRange(startKey, endKey []byte) (int, error)
- func (skey *Starskey) FilterKeys(compare func(key []byte) bool) ([][]byte, error)
- func (skey *Starskey) Get(key []byte) ([]byte, error)
- func (skey *Starskey) LongestPrefixSearch(key []byte) ([]byte, int, error)
- func (skey *Starskey) PrefixSearch(prefix []byte) ([][]byte, error)
- func (skey *Starskey) Put(key, value []byte) error
- func (skey *Starskey) Range(startKey, endKey []byte) ([][]byte, error)
- func (skey *Starskey) Update(fn func(tx *Txn) error) error
- type Txn
- type TxnOperation
- type TxnRollbackOperation
- type VLogRecord
- type WAL
- type WALRecord
Constants ¶
This section is empty.
Variables ¶
var ( WALExtension = ".wal" // Write ahead log extension VLogExtension = ".vlog" // value log extension KLogExtension = ".klog" // key log extension LogExtension = ".log" // debug log extension BloomFilterExtension = ".bf" // bloom filter extension SuRFExtension = ".srf" // SuRF extension SSTPrefix = "sst_" // SSTable prefix LevelPrefix = "l" // Level prefix, i.e l1, l2, l3, etc. PageSize = 128 // Page size (default), smaller is better. The pager handles overflowing in sequence. 1024, or 1024 will cause VERY large files. SyncInterval = time.Millisecond * 256 // File sync interval (default) Tombstone = []byte{0xDE, 0xAD, 0xBE, 0xEF} // Tombstone value TTreeMin = 12 // Minimum degree of the T-Tree (default) TTreeMax = 32 // Maximum degree of the T-Tree (default) BloomFilterProbability = 0.01 // Bloom filter probability (default) )
Global system variables
Functions ¶
This section is empty.
Types ¶
type CompressionOption ¶ added in v0.0.3
type CompressionOption int
const ( NoCompression CompressionOption = iota SnappyCompression S2Compression )
Compression options
type Config ¶
type Config struct {
Permission os.FileMode // Directory and file permissions
Directory string // Directory to store the starskey files
FlushThreshold uint64 // Flush threshold for memtable
MaxLevel uint64 // Maximum number of levels
SizeFactor uint64 // Size factor for each level
BloomFilter bool // Enable bloom filter
Logging bool // Enable log file
Compression bool // Enable compression
CompressionOption CompressionOption // Desired compression option
SuRF bool // Enable SuRF
Optional *OptionalConfig // Optional configurations
}
Config represents the configuration for starskey instance
type KLogRecord ¶
type KLogRecord struct {
Key []byte // The key
ValPageNum uint64 // The page number of the value in the value log
}
KLogRecord represents a key log record
type Level ¶
type Level struct {
// contains filtered or unexported fields
}
Level represents a disk level
type OperationType ¶
type OperationType int
OperationType represents the type of operation for a WAL record and transactions
const ( Put OperationType = iota Delete Get )
type OptionalConfig ¶ added in v0.1.5
type OptionalConfig struct {
BackgroundFSync bool // You can optionally opt to not fsync writes to disk
BackgroundFSyncInterval time.Duration // Interval for background fsync, if configured true
TTreeMin int // Minimum degree of the T-Tree
TTreeMax int // Maximum degree of the T-Tree
PageSize int // Page size
BloomFilterProbability float64 // Bloom filter probability
}
OptionalConfig represents optional configuration for starskey instance Mainly configurations for internal data structures and operations BackgroundFSync default is true BackgroundFSyncInterval default is 256ms TTreeMin default is 12 TTreeMax default is 32 PageSize default is 128 BloomFilterProbability default is 0.01
type SSTable ¶
type SSTable struct {
// contains filtered or unexported fields
}
SSTable represents a sorted string table
type Starskey ¶
type Starskey struct {
// contains filtered or unexported fields
}
Starskey represents the main struct for the package
func (*Starskey) DeleteByFilter ¶ added in v0.1.3
DeleteByFilter deletes all keys that match the given filter function
func (*Starskey) DeleteByPrefix ¶ added in v0.1.4
DeleteByPrefix deletes all keys that match the given prefix and returns the number of keys deleted.
func (*Starskey) DeleteByRange ¶ added in v0.1.3
DeleteByRange deletes all keys in the given range [startKey, endKey]
func (*Starskey) FilterKeys ¶
FilterKeys retrieves values from the database that match a key filter
func (*Starskey) LongestPrefixSearch ¶ added in v0.1.4
LongestPrefixSearch finds the longest matching prefix for a given key Returns the value associated with the longest prefix and the length of the matched prefix
func (*Starskey) PrefixSearch ¶ added in v0.1.4
PrefixSearch finds all keys that match the given prefix
type Txn ¶
type Txn struct {
// contains filtered or unexported fields
}
Txn represents a transaction
type TxnOperation ¶
type TxnOperation struct {
// contains filtered or unexported fields
}
TxnOperation represents an operation in a transaction
type TxnRollbackOperation ¶
type TxnRollbackOperation struct {
// contains filtered or unexported fields
}
TxnRollbackOperation represents a rollback operation in a transaction
type VLogRecord ¶
type VLogRecord struct {
Value []byte // The value
}
VLogRecord represents a value log record
type WAL ¶
type WAL struct {
// contains filtered or unexported fields
}
WAL represents a write-ahead log
type WALRecord ¶
type WALRecord struct {
Key []byte // Key
Value []byte // Value
Op OperationType // Operation type
}
WALRecord represents a WAL record
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package bloomfilter
|
Package bloomfilter |
|
Package pager
|
Package pager |
|
Package ttree
|
Package ttree |
|
Package ttree
|
Package ttree |