README
¶
BetaDB
BetaDB is a Key-Value single-machine database storage engine based on the Bitcask model. It also supports some basic Redis commands, and is compatible with the Redis serialization protocol (RESP).
General Features
Simple API
- Opening Datastore:
- Functions to open a new or existing BetaDB instance.
- CRUD Operations:
Getfunction retrieves values by key.Putfunction stores key-value pairs.Deletefunction removes keys from the datastore.
- Utility Functions:
ListKeyslists all keys in the datastore.Foldallows iteration over all key-value pairs.Mergecompacts data files and generates hint files.Syncensures any writes are synced to disk.Closeflushes pending writes and closes the datastore.
Log-Structured Storage
BetaDB utilizes a log-structured storage system that appends data sequentially to an active file in the directory. This approach minimizes the need for disk seeks, enhancing write performance. Once the active file reaches a certain size, it is closed, marked as immutable, and a new active file is created.
These immutable files ensure data integrity and simplify backup and recovery processes. Deletions are managed by writing a tombstone value for the key, which is subsequently removed during the merge process.
In-Memory Key Directory
BetaDB utilizes the in-memory key directory, or Keydir in the original Bitcask paper. This structure is an in-memory hash table that maps each key to a fixed-size structure containing the file ID, offset, and size of the most recent entry for that key. The Keydir is updated atomically with each new entry, ensuring that reads always fetch the latest data.
This design allows for fast lookups, requiring only a single disk seek to read a value, which significantly improves read performance.
Compaction and Merging
To manage space efficiently, BetaDB employs a compaction and merging process. Over time, the storage system may accumulate multiple versions of keys, increasing space usage. The merge process iterates over all immutable files, compacting them and retaining only the latest version of each key.
This process produces new compacted data files and associated hint files, which store metadata about the values in the corresponding data files. These hint files speed up the startup process by providing quick access to the metadata.
Crash Recovery
BetaDB implements a simple transaction feature. The integration ensures no data loss and simplifies recovery, eliminating the need for log replay. Recovery is further expedited by the use of hint files, which allow for faster scanning during startup.
Benchmarking
Please refer to benchmark directory to use the benchmarking scripts.
The benchmarking results highlight BetaDB's ability to provide high throughput and low latency for read and write operations, along with efficient memory utilization.
Disclaimer
This project is not intended for industrial application, and is for academic or research use only.
Documentation
¶
Index ¶
- Variables
- type Database
- func (db *Database) Backup(directory string) error
- func (db *Database) Close() error
- func (db *Database) Delete(key []byte) error
- func (db *Database) Fold(fn func(key []byte, value []byte) bool) error
- func (db *Database) Get(key []byte) ([]byte, error)
- func (db *Database) ListKeys() [][]byte
- func (db *Database) Merge() error
- func (db *Database) NewIterator(opts IteratorOptions) *Iterator
- func (db *Database) NewWriteBatch(options WriteBatchOptions) *WriteBatch
- func (db *Database) Put(key []byte, value []byte) error
- func (db *Database) Stat() *Stat
- func (db *Database) Sync() error
- type IndexerType
- type Iterator
- type IteratorOptions
- type Options
- type Stat
- type WriteBatch
- type WriteBatchOptions
Constants ¶
This section is empty.
Variables ¶
var ( ErrKeyIsEmpty = errors.New("the key is empty") ErrIndexUpdateFailed = errors.New("failed to update index") ErrKeyNotFound = errors.New("key is not found in the database") ErrDataFileNotFound = errors.New("data file is not found") ErrDataDirectoryCorrupted = errors.New("database directory might be corrupted") ErrExceedMaxBatchNum = errors.New("maximum batch numbers has been exceeded") ErrMergeIsInProgress = errors.New("merging is in progress, please try again later") ErrDatabaseIsUsing = errors.New("database directory is being used by another process") ErrMergeRatioUnreached = errors.New("merge ratio does not reach the option") ErrNoEnoughSpaceForMerge = errors.New("no enough space on disk for merging") )
var DefaultIteratorOptions = IteratorOptions{ Prefix: nil, Reverse: false, }
var DefaultOptions = Options{ DirectoryPath: os.TempDir(), DataFileSize: 256 * 1024 * 1024, SyncWrites: false, BytesPerSync: 0, IndexType: BTree, MMapAtStartUp: true, DataFileMergeRatio: 0.5, }
var DefaultWriteBatchOptions = WriteBatchOptions{ MaxBatchNum: 10000, SyncWrites: true, }
Functions ¶
This section is empty.
Types ¶
type Database ¶
type Database struct {
// contains filtered or unexported fields
}
Database defines a storage engine instance
func (*Database) Fold ¶
Fold obtains all data and performs the operations specified by the user the traversal is terminated when the function returns false
func (*Database) NewIterator ¶
func (db *Database) NewIterator(opts IteratorOptions) *Iterator
NewIterator initializes the Iterator struct
func (*Database) NewWriteBatch ¶
func (db *Database) NewWriteBatch(options WriteBatchOptions) *WriteBatch
NewWriteBatch initialize a new WriteBatch
type IndexerType ¶
type IndexerType = int8
const ( // BTree indicates btree index BTree IndexerType = iota + 1 // ART indicates Adaptive Radix Tree index ART // BPlusTree indicates b+tree index BPlusTree )
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator defines the iterator for user to operate
func (*Iterator) Rewind ¶
func (it *Iterator) Rewind()
Rewind returns to the starting point of the iterator, that is, the first data
func (*Iterator) Seek ¶
Seek finds the first target key that is greater than (or less than) or equal to the key passed in and starts traversing from this key
type IteratorOptions ¶
type IteratorOptions struct {
// Prefix denotes the iteration for the key with given prefix, default null
Prefix []byte
// Reverse indicates whether to traverse in reverse direction
// the default value is false, which means forward traversal
Reverse bool
}
IteratorOptions defines the index iterator configuration options
type Options ¶
type Options struct {
// DataDirectoryPath is the path to the data directory
DirectoryPath string
// DataFileSize is the size of the data file
DataFileSize int64
// SyncWrites indicates whether to sync for every write to disk
SyncWrites bool
// BytesPerSync indicates the cumulative number of bytes written before syncing to disk
BytesPerSync uint
// IndexType defines the type for index
IndexType IndexerType
// MMapAtStartUp indicates whether to use mmap to load the data file at startup
MMapAtStartUp bool
// DataFileMergeRatio indicates the threshold of the data file size to the merge size
DataFileMergeRatio float32
}
type Stat ¶
type Stat struct {
// KeyNum is the number of keys in the database
KeyNum uint
// DataFileNum is the number of data files
DataFileNum uint
// RecycleFileNum is the number of bytes of data that can be merged
ReclaimableSize int64
// DiskSize is the size of the data directory on disk
DiskSize int64
}
Stat stores engine statistics
type WriteBatch ¶
type WriteBatch struct {
// contains filtered or unexported fields
}
WriteBatch is a batch writing struct to ensure atomic transaction
func (*WriteBatch) Commit ¶
func (wb *WriteBatch) Commit() error
Commit commits the transaction writing the temporary data to data file and update memory index
func (*WriteBatch) Delete ¶
func (wb *WriteBatch) Delete(key []byte) error
Delete deletes the data in batch
type WriteBatchOptions ¶
type WriteBatchOptions struct {
// MaxBatchNum denotes the max data size within a batch
MaxBatchNum uint
// SyncWrites denotes whether to sync the disk when commiting
SyncWrites bool
}
WriteBatchOptions defines batch writing configuration options
Source Files
Directories