LotsusDB is a fast k/v database compatible with LSM tree and B+ tree

LotusDB

LotsusDB is a fast k/v database compatible with LSM tree and B+ tree.

Key features:

  • Combine the advantages of LSM and B+ tree

  • Fast read/write performance

  • Much lower read and space amplification than typical LSM

Design Overview

LotusDB is inspired by a paper named SLM-DB in USENIX FAST ’19, and the Wisckey paper also helps a lot.

Quick Start

1.embedded usage: see examples.

Documentation

coming soon.

Contributing

see CONTRIBUTING.md

License

LotusDB is under the Apache 2.0 license. See the LICENSE file for details.

Owner
FlowerCorp
Provide stable, reliable and fast kv storage.
FlowerCorp
Comments
  • Is LotusDB better than RoseDB?

    Is LotusDB better than RoseDB?

    Hello,

    I am trying to determine which is the latest DB that I should be trying to use for an embedded application in development:

    RoseDB or LotusDB

    The miniDB seems to be stripped down version of RoseDB.

    Can you please let me know which is best to use?

  • the latest of lotusdb and the go.etcd.io/bblot of v1.3.6 not match

    the latest of lotusdb and the go.etcd.io/bblot of v1.3.6 not match

    the latest of lotusdb and the go.etcd.io/bblot of v1.3.6 not match https://github.com/flower-corp/lotusdb/blob/9bd9047f19ee551993c4ba85fee3d12ab57b3455/index/bptree.go#L115

    func (b *BPTree) Put(key, value []byte) (err error) {
    	var tx *bbolt.Tx
    	if tx, err = b.db.Begin(true); err != nil {
    		return
    	}
    	bucket := tx.Bucket(b.opts.BucketName)
    	if _, err = bucket.Put(key, value); err != nil {  // bucket.Put  need two return values here
    		_ = tx.Rollback()
    		return
    	}
    	return tx.Commit()
    }
    

    but go.etcd.io/bblot/bucket.go here only one return value https://github.com/etcd-io/bbolt/blob/fd5535f71f488dda0915f610b6ca8c77c9ca2c59/bucket.go#L280

    func (b *Bucket) Put(key []byte, value []byte) error {
    	if b.tx.db == nil {
    		return ErrTxClosed
    	} else if !b.Writable() {
    		return ErrTxNotWritable
    	} else if len(key) == 0 {
    		return ErrKeyRequired
    	} else if len(key) > MaxKeySize {
    		return ErrKeyTooLarge
    	} else if int64(len(value)) > MaxValueSize {
    		return ErrValueTooLarge
    	}
    
    	// Move cursor to correct position.
    	c := b.Cursor()
    	k, _, flags := c.seek(key)
    
    	// Return an error if there is an existing key with a bucket value.
    	if bytes.Equal(key, k) && (flags&bucketLeafFlag) != 0 {
    		return ErrIncompatibleValue
    	}
    
    	// Insert into node.
    	key = cloneBytes(key)
    	c.node().put(key, key, value, 0, 0)
    
    	return nil
    }
    
  • example can not run

    example can not run

    https://github.com/flower-corp/lotusdb/blob/main/examples/basic/basic_operation.go

    ../../../go/pkg/mod/github.com/flower-corp/[email protected]/index/bptree.go:114:12: assignment mismatch: 2 variables but bucket.Put returns 1 value ../../../go/pkg/mod/github.com/flower-corp/[email protected]/index/bptree.go:147:19: assignment mismatch: 2 variables but bucket.Put returns 1 value ../../../go/pkg/mod/github.com/flower-corp/[email protected]/index/bptree.go:185:19: assignment mismatch: 2 variables but bucket.Delete returns 1 value ../../../go/pkg/mod/github.com/flower-corp/[email protected]/index/bptree.go:205:10: assignment mismatch: 2 variables but tx.Bucket(b.opts.BucketName).Delete returns 1 value

  • whatever dirLock.Release returns in cf.Close will be discarded

    whatever dirLock.Release returns in cf.Close will be discarded

    whatever dirLock.Release returns in cf.Close will be discarded

    // Close close current colun family.
    func (cf *ColumnFamily) Close() error {
    	atomic.StoreUint32(&cf.closed, 1)
    	close(cf.closedC)
    	var err error
    	for _, dirLock := range cf.dirLocks {
    		err = dirLock.Release()
    	}
    	// sync all contents.
    	err = cf.Sync()
    	return err
    }
    
  • arena function GetBytes() add check offset logic

    arena function GetBytes() add check offset logic

    The function GetBytes() does not judge the situation that the offset is out of bounds.Add simple logic for detection.

    • The scope of the change does not include: Iterator : Value(); Skiplist : allocKey(); Skiplist : allocVal().

    • The scope of the changes includes: node : getKey(). method returns nil if not found.

    please confirm~

  • ci: add Windows matrix test

    ci: add Windows matrix test

    As per https://github.com/flower-corp/lotusdb/pull/45#issuecomment-1172886115, we can use a matrix strategy to run the unit tests on both Ubuntu and Windows.

    EDIT: This PR also fixes all the failing tests on Windows

  • test: use `T.TempDir` to create temporary test directory

    test: use `T.TempDir` to create temporary test directory

    A testing cleanup.

    This pull request replaces ioutil.TempDir with t.TempDir. We can use the T.TempDir function from the testing package to create temporary directory. The directory created by T.TempDir is automatically removed when the test and all its subtests complete.

    This saves us at least 2 lines (error check, and cleanup) on every instance, or in some cases adds cleanup that we forgot.

    Reference: https://pkg.go.dev/testing#T.TempDir

    func TestFoo(t *testing.T) {
    	// before
    	tmpDir, err := ioutil.TempDir("", "")
    	assert.NoError(t, err)
    	defer os.RemoveAll(tmpDir)
    
    	// now
    	tmpDir := t.TempDir()
    }
    
  • example shows error

    example shows error

    # github.com/flower-corp/lotusdb/index
    /root/go/pkg/mod/github.com/flower-corp/[email protected]/index/bptree.go:114:14: assignment mismatch: 2 variables but bucket.Put returns 1 value
    /root/go/pkg/mod/github.com/flower-corp/[email protected]/index/bptree.go:147:22: assignment mismatch: 2 variables but bucket.Put returns 1 value
    /root/go/pkg/mod/github.com/flower-corp/[email protected]/index/bptree.go:185:22: assignment mismatch: 2 variables but bucket.Delete returns 1 value
    /root/go/pkg/mod/github.com/flower-corp/[email protected]/index/bptree.go:205:13: assignment mismatch: 2 variables but tx.Bucket(b.opts.BucketName).Delete returns 1 value
    
  • Data Race Problem

    Data Race Problem

    ==================
    WARNING: DATA RACE
    Read at 0x00c0000ac288 by goroutine 33:
      github.com/flower-corp/lotusdb.(*valueLog).handleCompaction()
          go/pkg/mod/github.com/flower-corp/[email protected]/vlog.go:278 +0x1b8
      github.com/flower-corp/lotusdb.openValueLog.func2()
          go/pkg/mod/github.com/flower-corp/[email protected]/vlog.go:115 +0x38
    
    Previous write at 0x00c0000ac288 by main goroutine:
      github.com/flower-corp/lotusdb.(*LotusDB).OpenColumnFamily()
          go/pkg/mod/github.com/flower-corp/[email protected]/cf.go:138 +0x4f4
      github.com/flower-corp/lotusdb.Open()
          go/pkg/mod/github.com/flower-corp/[email protected]/db.go:39 +0x170
    
    Goroutine 33 (running) created at:
      github.com/flower-corp/lotusdb.openValueLog()
          go/pkg/mod/github.com/flower-corp/[email protected]/vlog.go:115 +0x584
      github.com/flower-corp/lotusdb.(*LotusDB).OpenColumnFamily()
          go/pkg/mod/github.com/flower-corp/[email protected]/cf.go:133 +0x49c
      github.com/flower-corp/lotusdb.Open()
          go/pkg/mod/github.com/flower-corp/[email protected]/db.go:39 +0x170
    ==================
    Found 1 data race(s)
    
  • the Arena function growBufSize() may have concurrency issue

    the Arena function growBufSize() may have concurrency issue

    https://github.com/flower-corp/lotusdb/blob/0f5d9df69c7fdcd1e8e3054e2a63f3a36441feca/arenaskl/arena.go#L125-L129

    When different goroutines run to the growBufSize(), newBuf allocated by one goroutine may replaced by another. Replacement of buf and newBuf is not atomic. I just modified the skl_test.go and found this error and I don't know if it is designed that way

    // TestConcurrentBasic tests concurrent writes followed by concurrent reads.
    func TestConcurrentBasic(t *testing.T) {
    	const n = 1000
    
    	// Set testing flag to make it easier to trigger unusual race conditions.
    	//l := NewSkiplist(NewArena(arenaSize))
           // Change NewArena size to a small one
            l := NewSkiplist(NewArena(10))
    	l.testing = true
    
    	var wg sync.WaitGroup
    	for i := 0; i < n; i++ {
    		wg.Add(1)
    		go func(i int) {
    			defer wg.Done()
    
    			var it Iterator
    			it.Init(l)
    
    			it.Put([]byte(fmt.Sprintf("%05d", i)), newValue(i))
    		}(i)
    	}
    	wg.Wait()
    
    	// Check values. Concurrent reads.
    	for i := 0; i < n; i++ {
    		wg.Add(1)
    		go func(i int) {
    			defer wg.Done()
    
    			var it Iterator
    			it.Init(l)
    
    			found := it.Seek([]byte(fmt.Sprintf("%05d", i)))
    			require.True(t, found)
    			require.EqualValues(t, newValue(i), it.Value())
    		}(i)
    	}
    	wg.Wait()
    	require.Equal(t, n, length(l))
    	require.Equal(t, n, lengthRev(l))
    }
    
NutsDB a simple, fast, embeddable and persistent key/value store written in pure Go.
NutsDB a simple, fast, embeddable and persistent key/value store written in pure Go.

A simple, fast, embeddable, persistent key/value store written in pure Go. It supports fully serializable transactions and many data structures such as list, set, sorted set.

Jan 9, 2023
rosedb is a fast, stable and embedded key-value (k-v) storage engine based on bitcask.
rosedb is a fast, stable and embedded key-value (k-v) storage engine based on bitcask.

rosedb is a fast, stable and embedded key-value (k-v) storage engine based on bitcask. Its on-disk files are organized as WAL(Write Ahead Log) in LSM trees, optimizing for write throughput.

Dec 28, 2022
An embedded key/value database for Go.

Bolt Bolt is a pure Go key/value store inspired by Howard Chu's LMDB project. The goal of the project is to provide a simple, fast, and reliable datab

Dec 30, 2022
LevelDB key/value database in Go.

This is an implementation of the LevelDB key/value database in the Go programming language. Installation go get github.com/syndtr/goleveldb/leveldb R

Jan 9, 2023
RocksDB/LevelDB inspired key-value database in Go

Pebble Nightly benchmarks Pebble is a LevelDB/RocksDB inspired key-value store focused on performance and internal usage by CockroachDB. Pebble inheri

Dec 29, 2022
Key-value database stored in memory with option of persistence
Key-value database stored in memory with option of persistence

Easy and intuitive command line tool allows you to spin up a database avaliable from web or locally in a few seconds. Server can be run over a custom TCP protocol or over HTTP.

Aug 1, 2022
ZedisDB - a key-value memory database written in Go

ZedisDB - a key-value memory database written in Go

Sep 4, 2022
Simple Distributed key-value database (in-memory/disk) written with Golang.

Kallbaz DB Simple Distributed key-value store (in-memory/disk) written with Golang. Installation go get github.com/msam1r/kallbaz-db Usage API // Get

Jan 18, 2022
A HTTP RESTful type kv database which embedded some frequently-used mid-ware.

A HTTP RESTful type kv database which embedded some frequently-used mid-ware.

Apr 4, 2022
FlashDB is an embeddable, in-memory key/value database in Go
FlashDB is an embeddable, in-memory key/value database in Go

FlashDB is an embeddable, in-memory key/value database in Go (with Redis like commands and super easy to read)

Dec 28, 2022
moss - a simple, fast, ordered, persistable, key-val storage library for golang

moss provides a simple, fast, persistable, ordered key-val collection implementation as a 100% golang library.

Dec 18, 2022
Fast key-value DB in Go.
Fast key-value DB in Go.

BadgerDB BadgerDB is an embeddable, persistent and fast key-value (KV) database written in pure Go. It is the underlying database for Dgraph, a fast,

Jan 1, 2023
Distributed cache and in-memory key/value data store. It can be used both as an embedded Go library and as a language-independent service.

Olric Distributed cache and in-memory key/value data store. It can be used both as an embedded Go library and as a language-independent service. With

Jan 4, 2023
Consul is a distributed, highly available, and data center aware solution to connect and configure applications across dynamic, distributed infrastructure.

Consul Website: https://www.consul.io Tutorials: HashiCorp Learn Forum: Discuss Consul is a distributed, highly available, and data center aware solut

Jan 2, 2023
A key-value db api with multiple storage engines and key generation
A key-value db api with multiple storage engines and key generation

Jet is a deadly-simple key-value api. The main goals of this project are : Making a simple KV tool for our other projects. Learn tests writing and git

Apr 5, 2022
KV - a toy in-memory key value store built primarily in an effort to write more go and check out grpc

KV KV is a toy in-memory key value store built primarily in an effort to write more go and check out grpc. This is still a work in progress. // downlo

Dec 30, 2021
🔑A high performance Key/Value store written in Go with a predictable read/write performance and high throughput. Uses a Bitcask on-disk layout (LSM+WAL) similar to Riak.

bitcask A high performance Key/Value store written in Go with a predictable read/write performance and high throughput. Uses a Bitcask on-disk layout

Sep 26, 2022
A MongoDB compatible embeddable database and toolkit for Go.
A MongoDB compatible embeddable database and toolkit for Go.

lungo A MongoDB compatible embeddable database and toolkit for Go. Installation Example Motivation Architecture Features License Installation To get s

Jan 3, 2023
Exp-tree: go library for parsing expression tree

Vinshop expression tree Exp-tree is go library for parsing expression tree Installation go get -u github.com/vinshop/exp-tree Quick start Format Expre

May 11, 2022
⚡ Rux is an simple and fast web framework. support middleware, compatible http.Handler interface. 简单且快速的 Go web 框架,支持中间件,兼容 http.Handler 接口

Rux Simple and fast web framework for build golang HTTP applications. NOTICE: v1.3.x is not fully compatible with v1.2.x version Fast route match, sup

Dec 8, 2022