It is a Key/Value store that implements bucketing based on extendible hashing
The server.go file is a simple http server that answers on the 2233 port.
There are 3 endpoints :
curl -XGET http://hostname:2233/v1/data/path/to/fs/?id=<key>
curl -XPUT -d 'value' http://hostname:2233/v1/data/path/to/fs/?id=<key>
curl -XGET http://hostname:2233/v1/meta/path/to/fs/
curl -XGET http://hostname:2233/v1/debug/path/to/fs/?page_id=<id_of_the_page_to_display>
- /v1 is the version number of the API
- /path/to/fs/ is a filesystem absolute path to a folder (existing or not, it will create if not)
- GET /data
/path/to/fs/?id=keyis the url to get the value of the specified key. It returns a JSON - PUT /data
/path/to/fs/?id=keyis the url to put the value of the specified key. It returns StatusOk if it is inserted - GET /meta
/path/to/fs/is the url to print metadata of the table. It returns a JSON formatted response - PUT /debug
/path/to/fs/?id_page=keyis the url to print the dump of a specific page
The goal of this project is to explore and to reinvent the wheel of well known, state of the art, algorithms and data structures. For experimental and learning purpose only, not production ready.
The datastructure is a persistent hashtable. There is no separation between the index and the data, they are in the same file That is the reason why a record cannot be bigger than a bucket currently (no handling for big record)
A Directory is a table of buckets called "Page". It is the structure used to know where a bucket points physicaly to the data file
dir := &Directory{
Table: []int{0, 1, 3, 2, 0, 1, 3, 2},
Gd: 2,
LastPageId: 3,
data: []byte{...},
}
The Table array stores the ids of the pages (i.e pointers). To retrieve a page, the algorithm
hash(key) and lookups to the Table what index it points to. Then it does a subset
of the data byte slice with Table[ hash(key) ] * 4096, and casts it to a Page structure.
When a new Page is required because there is no free space, LastPageId + 1 is use to be the next
pointer filled in the Table array to point to the new Page (so it points at the end of the File => (LastPageId + 1) * 4096).
A Page is a byte array of 4096 bytes length, append only. Trailer : It stores actual usage of the Page at 4094 bytes (unint16), and local depth at 4092 bytes (unint16)
| Record 1 | Record 2 | Record 3 | Record 1 v2 | LOCAL_DEPTH | PAGE_USE |
A Record is a byte array with a key, a value and the headers :
type Record interface {
Key() []byte
Val() []byte
KeyLen() uint16
ValLen() uint16
}
type ByteRecord []byte
| ... | k | e | y | v | a | l | u | e | 0x5 | 0x0 | 0x3 | 0x0 | ... |
Actual public methods :
- put : append the record at the offset given by
Page.use()value - get : read in reverse way, starting from the end and iterating until the key is found, or the beginning
This design allows updating values for a given key without doing lookup before inserting (put is O(1) if the Page is not full). When the Page is full, the Directory.split() method skips the old values of the same key and re-insert just the latest
go get github.com/BenJoyenConseil/bluckdb
If you run a go program for the first time, do not forget to setup your GOPATH : export GOPATH=$HOME/Dev/go
go run server.go
It runs an httpserver with an instance of MmapKVStore
BenchmarkBluckDBPut 1000000 1359 ns/op -> 1,3 µs
BenchmarkBluckDBGet 1000000 1406 ns/op -> 1,4 µs
BenchmarkPutNaiveDiskKVStore-4 200000 6250 ns/op -> 6,2 µs
BenchmarkGetNaiveDiskKVStore-4 30 44017416 ns/op -> 44 ms
BenchmarkPutHashMap-4 1000000 1385 ns/op -> 1,3 µs
BenchmarkGetHashMap-4 2000000 711 ns/op -> 0,7 µs