README
¶
simplekv
A simple KV database implementation
TODO
- asm murmur3 perf
- clean code
- unit, benchmark test
structure
key features
- LSM 日志结构存储引擎，核心点在于顺序写日志，这样就能保证超快的写速度；
- 内存索引，KV红黑树实现，内存索引有大小限制；
- 超过内存限制(threshold)后，会将内存数据刷新到磁盘段文件中（segment file）；
- 在内存中保存了索引、数据方便快速查询，如果仍查不到则去搜索段文件；
- 如果一个 key 被写了多次，那么就会有很多重复的行，因此需要合并他们(compact)；
- 当需要刷内存索引至磁盘时，会先将磁盘中的段文件进行合并(compact)；
- 引入布隆过滤器来加快文件数据查询，不存在的 key 直接返回，避免读文件；
- sparse index（稀疏索引） 保存了部分 segment-file-offset 信息，方便在文件中搜索；
- 稀疏索引查询的时候找到比 key 小（对于二叉树的左孩子节点）的文件和索引，然后遍历文件，就能提升效率；
- WAL 日志用来恢复 memtable；
references
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type AppendLog ¶
type AppendLog struct {
// contains filtered or unexported fields
}
AppendLog 追加日志
func (*AppendLog) WriteString ¶
type BitArray ¶
type BitArray struct {
// contains filtered or unexported fields
}
BitArray refer https://developpaper.com/implementation-of-bit-array-in-golang/
type BloomFilter ¶
type BloomFilter struct {
// contains filtered or unexported fields
}
BloomFilter 布隆过滤器
func NewBloomFilter ¶
func NewBloomFilter(numItems int, falsePositivePob float64) *BloomFilter
NewBloomFilter 新建布隆过滤器
func (*BloomFilter) Add ¶
func (f *BloomFilter) Add(item string)
func (*BloomFilter) Check ¶
func (f *BloomFilter) Check(item string) bool
func (*BloomFilter) Pack ¶
func (f *BloomFilter) Pack() string
func (*BloomFilter) UnPack ¶
func (f *BloomFilter) UnPack(data string) error
type LineReader ¶
type LineReader struct {
// contains filtered or unexported fields
}
func NewLineReader ¶
func NewLineReader(path string, offset int64) (*LineReader, error)
func (*LineReader) Close ¶
func (r *LineReader) Close() error
func (*LineReader) ReadLine ¶
func (r *LineReader) ReadLine() (string, error)
func (*LineReader) ReadLineKV ¶
func (r *LineReader) ReadLineKV() (string, string, error)
type SizedMap ¶
type SizedMap struct {
// contains filtered or unexported fields
}
SizedMap map with size
func (*SizedMap) GetTotalSize ¶
GetTotalSize total size of kvs
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree LSM tree(og structure tree)
Source Files
Click to show internal directories.
Click to hide internal directories.