Skip to content

Key-Value/Document store database library with btree and ARTree indexing methods, SSN-MVCC concurrency

License

Notifications You must be signed in to change notification settings

malbrain/database

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

malbrain/database

A working project for High-concurrency B-tree/ARTree Database source code in C. This project was created as a sub-module for the /www.github.com/malbrain/javascript-database project, but it can also be used by itself as a database/indexing library. The API is documented on the Wiki pages.

The testfiles directory exercises the basic functionality of the database, and can be used as a sample database application. For a more complete example of how MVCC and transactions can be implemented on the database core functionality, please see the javascript-database project, partcularly the js_db*.c files.

Clone the database project:

git clone --recursive https://github.com/malbrain/database.git

Compile the database library and standalone test module with ./build or build.bat.

Usage: standalone db_name -cmds=[wdf] -summary=[csrvikdn] -idxType=[012] -bits=# -xtra=# -inMem -stats -prng=# -debug -monitor -uniqueKeys -noDocs -noIdx -keyLen=# -minKey=abcd -maxKey=abce -drop -idxBinary=. -pipeline src_file1 src_file2 ... ]
  where db_name is the prefix name of the database document and index files
  cmds is a string of (w)rite/(d)elete/(f)ind commands, to run sequentially on each input src_file.
  summary scan is a string of (c)ount/(r)everse scan/(s)can/(v)erify/(i)terate/(k)ey list(d)ump doc(n)umber flags for a final scan after all threads have quit
  pennysort creates random 100 byte B64 input lines, sets keyLen to 10, line count from the file name
  idxType is the type of index: 0 = ART, 1 = btree1, 2 = btree2
  keyLen is key size, zero for whole input file line
  bits is the btree page size in bits
  xtra is the btree leaf page extra bits
  inMem specifies no disk files
  noDocs specifies keys only
  noIdx specifies documents only
  minKey specifies beginning cursor key
  maxKey specifies ending cursor key
  drop will initially drop database
  idxBinary utilize length counted fields separated by  the given deliminator in keys
  use prng number stream [012] for pennysort keys
  stats keeps performance and debugging totals and prints them
  uniqueKeys ensure keys are unique
  run cmds in a single threaded  pipeline using one input file at a time
  src_file1 thru src_filen are files of keys/documents separated by newline

Linux compilation command:

[karl@test7x64 xlink]# cc -std=c11 -O2 -g -o standalone standalone.c base64.c db*.c artree/*.c btree1/*.c btree2/*.c mutex/mutex.c rwlock/readerwriter.c -lpthread
**********************************************************************
** Visual Studio 2019 Developer Command Prompt v16.2.3
** Copyright (c) 2019 Microsoft Corporation
**********************************************************************
[vcvarsall.bat] Environment initialized for: 'x64'


c:\Users\Owner\Source\Repos\malbrain\database>testfiles\test1
Alpha testing of binary string fields
expect 13 sorted keys

standalone testdb -cmds=w -summary=skn -idxBinary=: testfiles/test1

thrd:0 cmd:w ARTree: begin
thrd:0 cmd:w file:testfiles/test1 load records
thrd:0 cmd:w file:testfiles/test1 records processed: 13
thrd:0 cmd:w end

 real 0m0.002s
 user 0m0.000s
 sys  0m0.000s

Index ARTree summary scan:
 forward index cursor
*}-Wz1;TD-
0fssx}~[oB
5HA\z%qt{%
AsfAGHM5om
Q)JN)R9z-L
abc:def
abcd:ef
abcde:f
my+=5r7(N|
mz4VCN@a#"
o4FoBkqERn
uI^EYm8s=|
~sHd0jDv6X
 Index scan complete
 Total keys 13

 real 0m0.005s
 user 0m0.000s
 sys  0m0.015s

Total memory allocated: 3.616 MB
Bytes per key: 291692

ARTree Index type 1 blks allocated: 00000002
ARTree Index type 2 blks allocated: 00000001
ARTree Index type 5 blks allocated: 00000016
ARTree Index type 6 blks allocated: 00000013
ARTree Index type 8 blks allocated: 00000022
ARTree Index type 9 blks allocated: 00000010

ARTree Index type 1 blks freed    : 00000001
ARTree Index type 8 blks freed    : 00000001
ARTree Index type 9 blks freed    : 00000002


**********************************************************************


c:\Users\Owner\Source\Repos\malbrain\database>testfiles\test2
"40M random 10 byte keys, single threaded insertions into each index type"

standalone.exe testdb -stats -cmds=w -summary=vc -idxType=2 -bits=16  -inMem -noDocs -pennysort 40000000

thrd:0 cmd:w Btree2: begin
thrd:0 cmd:w random keys:40000000
thrd:0 cmd:w file:40000000 records processed: 40000000
thrd:0 cmd:w end

 real 1m14.259s
 user 1m13.843s
 sys  0m0.406s

Index Btree2 summary scan:
 forward index cursor
 key order verification
 index key count
 Index scan complete
 Total keys 40000000

 real 0m2.508s
 user 0m2.500s
 sys  0m0.000s

Total memory allocated: 2154.231 MB
Bytes per key: 56

standalone.exe testdb -stats -cmds=w -summary=vc -idxType=1 -bits=16  -inMem -noDocs -pennysort 40000000

thrd:0 cmd:w Btree1: begin
thrd:0 cmd:w random keys:40000000
thrd:0 cmd:w file:40000000 records processed: 40000000
thrd:0 cmd:w end

 real 0m53.759s
 user 0m53.531s
 sys  0m0.218s

Index Btree1 summary scan:
 forward index cursor
 key order verification
 index key count
 Index scan complete
 Total keys 40000000

 real 0m2.383s
 user 0m2.375s
 sys  0m0.000s

Total memory allocated: 1027.947 MB
Bytes per key: 26


**********************************************************************


c:\Users\Owner\Source\Repos\malbrain\database>testfiles\test3
"40M random 10 byte keys, multi-threaded insertions into Adaptive Radix Tree index""

standalone testdb -prng=2 -stats -cmds=w -summary=vc -idxType=0 -bits=16  -inMem -noDocs -pennysort -threads=4 10000000
thread 0 launched for file 10000000 cmds w
thread 1 launched for file 10000000 cmds w
thread 2 launched for file 10000000 cmds w
thread 3 launched for file 10000000 cmds w

thrd:3 cmd:w ARTree: begin
thrd:3 cmd:w random keys:10000000
thrd:3 cmd:w file:10000000 records processed: 10000000
thrd:3 cmd:w end

 real 0m8.588s
 user 0m33.812s
 sys  0m0.546s

thrd:1 cmd:w ARTree: begin
thrd:1 cmd:w random keys:10000000
thrd:1 cmd:w file:10000000 records processed: 10000000
thrd:1 cmd:w end

 real 0m8.592s
 user 0m33.812s
 sys  0m0.546s

thrd:0 cmd:w ARTree: begin
thrd:0 cmd:w random keys:10000000
thrd:0 cmd:w file:10000000 records processed: 10000000
thrd:0 cmd:w end

 real 0m8.596s
 user 0m33.812s
 sys  0m0.546s

thrd:2 cmd:w ARTree: begin
thrd:2 cmd:w random keys:10000000
thrd:2 cmd:w file:10000000 records processed: 10000000
thrd:2 cmd:w end

 real 0m8.615s
 user 0m33.843s
 sys  0m0.546s

Index ARTree summary scan:
 forward index cursor
 key order verification
 index key count
 Index scan complete
 Total keys 40000000

 real 0m18.537s
 user 0m18.532s
 sys  0m0.000s

Total memory allocated: 3164.795 MB
Bytes per key: 82

ARTree Index type 1 blks allocated: 12468681
ARTree Index type 2 blks allocated: 01688726
ARTree Index type 3 blks allocated: 00266305
ARTree Index type 6 blks allocated: 40000000
ARTree Index type 8 blks allocated: 92558615
ARTree Index type 9 blks allocated: 00000065

ARTree Index type 1 blks freed    : 01688726
ARTree Index type 2 blks freed    : 00266305
ARTree Index type 8 blks freed    : 12468616
ARTree Index type 9 blks freed    : 00000065


**********************************************************************


c:\Users\Owner\Source\Repos\malbrain\database>testfiles\test4
"40M random 10 byte keys, multi-threaded insertions into btree1 index"

standalone testdb -prng=2 -stats -cmds=w -summary=vc -idxType=1 -bits=16  -inMem -noDocs -pennysort -threads=4 10000000
thread 0 launched for file 10000000 cmds w
thread 1 launched for file 10000000 cmds w
thread 2 launched for file 10000000 cmds w
thread 3 launched for file 10000000 cmds w

thrd:1 cmd:w Btree1: begin
thrd:1 cmd:w random keys:10000000
thrd:1 cmd:w file:10000000 records processed: 10000000
thrd:1 cmd:w end

 real 0m16.332s
 user 1m5.046s
 sys  0m0.250s

thrd:0 cmd:w Btree1: begin
thrd:0 cmd:w random keys:10000000
thrd:0 cmd:w file:10000000 records processed: 10000000
thrd:0 cmd:w end

 real 0m16.359s
 user 1m5.140s
 sys  0m0.250s

thrd:3 cmd:w Btree1: begin
thrd:3 cmd:w random keys:10000000
thrd:3 cmd:w file:10000000 records processed: 10000000
thrd:3 cmd:w end

 real 0m16.383s
 user 1m5.171s
 sys  0m0.250s

thrd:2 cmd:w Btree1: begin
thrd:2 cmd:w random keys:10000000
thrd:2 cmd:w file:10000000 records processed: 10000000
thrd:2 cmd:w end

 real 0m16.460s
 user 1m5.250s
 sys  0m0.265s

Index Btree1 summary scan:
 forward index cursor
 key order verification
 index key count
 Index scan complete
 Total keys 40000000

 real 0m2.383s
 user 0m2.375s
 sys  0m0.000s

Total memory allocated: 1032.647 MB
Bytes per key: 27


**********************************************************************


c:\Users\Owner\Source\Repos\malbrain\database>testfiles\test5
"10M random 10 byte keys, insertions then searches in ARTree index"

standalone testdb -prng=2 -stats -cmds=wf -summary=vc -idxType=0 -bits=16  -inMem -noDocs -pennysort 10000000

thrd:0 cmd:w ARTree: begin
thrd:0 cmd:w random keys:10000000
thrd:0 cmd:w file:10000000 records processed: 10000000
thrd:0 cmd:w end

 real 0m5.872s
 user 0m5.750s
 sys  0m0.125s

thrd:0 cmd:f ARTree: begin
thrd:0 cmd:f random keys:10000000
thrd:0 cmd:f file:10000000 records processed: 10000000
thrd:0 cmd:f end

 real 0m4.297s
 user 0m4.297s
 sys  0m0.000s

Index ARTree summary scan:
 forward index cursor
 key order verification
 index key count
 Index scan complete
 Total keys 10000000

 real 0m3.682s
 user 0m3.672s
 sys  0m0.000s

Total memory allocated: 868.290 MB
Bytes per key: 91

ARTree Index type 1 blks allocated: 02309998
ARTree Index type 2 blks allocated: 00271819
ARTree Index type 3 blks allocated: 00266275
ARTree Index type 6 blks allocated: 10000000
ARTree Index type 8 blks allocated: 22336227
ARTree Index type 9 blks allocated: 00000065

ARTree Index type 1 blks freed    : 00271819
ARTree Index type 2 blks freed    : 00266275
ARTree Index type 8 blks freed    : 02309933
ARTree Index type 9 blks freed    : 00000065


**********************************************************************


c:\Users\Owner\Source\Repos\malbrain\database>testfiles\test5
"10M random 10 byte keys, insertions then searches in ARTree index"

standalone testdb -prng=2 -stats -cmds=wf -summary=vc -idxType=0 -bits=16  -inMem -noDocs -pennysort 10000000

thrd:0 cmd:w ARTree: begin
thrd:0 cmd:w random keys:10000000
thrd:0 cmd:w file:10000000 records processed: 10000000
thrd:0 cmd:w end

 real 0m5.901s
 user 0m5.703s
 sys  0m0.203s

thrd:0 cmd:f ARTree: begin
thrd:0 cmd:f random keys:10000000
thrd:0 cmd:f file:10000000 records processed: 10000000
thrd:0 cmd:f end

 real 0m4.336s
 user 0m4.343s
 sys  0m0.000s

Index ARTree summary scan:
 forward index cursor
 key order verification
 index key count
 Index scan complete
 Total keys 10000000

 real 0m4.278s
 user 0m4.266s
 sys  0m0.000s

Total memory allocated: 868.853 MB
Bytes per key: 91

ARTree Index type 1 blks allocated: 02309998
ARTree Index type 2 blks allocated: 00271819
ARTree Index type 3 blks allocated: 00266275
ARTree Index type 6 blks allocated: 10000000
ARTree Index type 8 blks allocated: 22336227
ARTree Index type 9 blks allocated: 00000065

ARTree Index type 1 blks freed    : 00271819
ARTree Index type 2 blks freed    : 00266275
ARTree Index type 8 blks freed    : 02309933
ARTree Index type 9 blks freed    : 00000065


**********************************************************************


c:\Users\Owner\Source\Repos\malbrain\database>testfiles\test6
"40M random 10 byte keys, multi-threaded insertions then searches in btree1 index"

standalone testdb -prng=2 -stats -cmds=w -summary=vc -idxType=0 -bits=16 -noDocs -pennysort -threads=4 10000000
thread 0 launched for file 10000000 cmds w
thread 1 launched for file 10000000 cmds w
thread 2 launched for file 10000000 cmds w
thread 3 launched for file 10000000 cmds w

thrd:1 cmd:w ARTree: begin
thrd:1 cmd:w random keys:10000000
thrd:1 cmd:w file:10000000 records processed: 10000000
thrd:1 cmd:w end

 real 0m9.490s
 user 0m34.671s
 sys  0m2.562s

thrd:0 cmd:w ARTree: begin
thrd:0 cmd:w random keys:10000000
thrd:0 cmd:w file:10000000 records processed: 10000000
thrd:0 cmd:w end

 real 0m9.514s
 user 0m34.718s
 sys  0m2.562s

thrd:2 cmd:w ARTree: begin
thrd:2 cmd:w random keys:10000000
thrd:2 cmd:w file:10000000 records processed: 10000000
thrd:2 cmd:w end

 real 0m9.522s
 user 0m34.750s
 sys  0m2.562s

thrd:3 cmd:w ARTree: begin
thrd:3 cmd:w random keys:10000000
thrd:3 cmd:w file:10000000 records processed: 10000000
thrd:3 cmd:w end

 real 0m9.578s
 user 0m34.781s
 sys  0m2.578s

Index ARTree summary scan:
 forward index cursor
 key order verification
 index key count
 Index scan complete
 Total keys 40000000

 real 0m18.846s
 user 0m18.828s
 sys  0m0.015s

Total memory allocated: 3165.380 MB
Bytes per key: 82

ARTree Index type 1 blks allocated: 12468681
ARTree Index type 2 blks allocated: 01688726
ARTree Index type 3 blks allocated: 00266305
ARTree Index type 6 blks allocated: 40000000
ARTree Index type 8 blks allocated: 92558615
ARTree Index type 9 blks allocated: 00000065

ARTree Index type 1 blks freed    : 01688726
ARTree Index type 2 blks freed    : 00266305
ARTree Index type 8 blks freed    : 12468616
ARTree Index type 9 blks freed    : 00000065


standalone testdb -prng=2 -stats -cmds=f -summary=vc -idxType=0 -bits=16 -noDocs -pennysort -threads=4 10000000
thread 0 launched for file 10000000 cmds f
thread 1 launched for file 10000000 cmds f
thread 2 launched for file 10000000 cmds f
thread 3 launched for file 10000000 cmds f

thrd:1 cmd:f ARTree: begin
thrd:1 cmd:f random keys:10000000
thrd:1 cmd:f file:10000000 records processed: 10000000
thrd:1 cmd:f end

 real 0m6.206s
 user 0m23.578s
 sys  0m1.234s

thrd:2 cmd:f ARTree: begin
thrd:2 cmd:f random keys:10000000
thrd:2 cmd:f file:10000000 records processed: 10000000
thrd:2 cmd:f end

 real 0m6.289s
 user 0m23.812s
 sys  0m1.234s

thrd:0 cmd:f ARTree: begin
thrd:0 cmd:f random keys:10000000
thrd:0 cmd:f file:10000000 records processed: 10000000
thrd:0 cmd:f end

 real 0m6.357s
 user 0m23.937s
 sys  0m1.234s

thrd:3 cmd:f ARTree: begin
thrd:3 cmd:f random keys:10000000
thrd:3 cmd:f file:10000000 records processed: 10000000
thrd:3 cmd:f end

 real 0m6.393s
 user 0m23.984s
 sys  0m1.234s

Index ARTree summary scan:
 forward index cursor
 key order verification
 index key count
 Index scan complete
 Total keys 40000000

 real 0m18.281s
 user 0m18.281s
 sys  0m0.000s

Total memory allocated: 0.443 MB
Bytes per key: 0


**********************************************************************


c:\Users\Owner\Source\Repos\malbrain\database>testfiles\test7
"40M random 10 byte keys, multi-threaded insertions then subset cursor over btree1 index"

standalone testdb -prng=2 -stats -cmds=w -summary=k -idxType=1 -bits=16 -minKey=aaaA -maxKey=aaaK -noDocs -pennysort -threads=4 10000000
thread 0 launched for file 10000000 cmds w
thread 1 launched for file 10000000 cmds w
thread 2 launched for file 10000000 cmds w
thread 3 launched for file 10000000 cmds w

thrd:3 cmd:w Btree1: begin
thrd:3 cmd:w random keys:10000000
thrd:3 cmd:w file:10000000 records processed: 10000000
thrd:3 cmd:w end

 real 0m16.527s
 user 1m5.546s
 sys  0m0.562s

thrd:0 cmd:w Btree1: begin
thrd:0 cmd:w random keys:10000000
thrd:0 cmd:w file:10000000 records processed: 10000000
thrd:0 cmd:w end

 real 0m16.563s
 user 1m5.640s
 sys  0m0.562s

thrd:1 cmd:w Btree1: begin
thrd:1 cmd:w random keys:10000000
thrd:1 cmd:w file:10000000 records processed: 10000000
thrd:1 cmd:w end

 real 0m16.583s
 user 1m5.703s
 sys  0m0.562s

thrd:2 cmd:w Btree1: begin
thrd:2 cmd:w random keys:10000000
thrd:2 cmd:w file:10000000 records processed: 10000000
thrd:2 cmd:w end

 real 0m16.675s
 user 1m5.796s
 sys  0m0.562s

Index Btree1 summary scan:
 forward index cursor
 min key: <aaaA>
 max key: <aaaK>
aaaBCw`d42
aaaBONxqOK
aaaBm90ePd
aaaCctIYQw
aaaCgdnoHA
aaaCpkDRZ6
aaaD@tGrtK
aaaDL4uFgu
aaaDihSWuY
aaaDyhKhZg
aaaE0tam4P
aaaFiGHVmr
aaaG5S2Vod
aaaHQtKXpk
aaaHyG0MNI
aaaI4R9OlN
aaaIJp7aPf
aaaJBwd`ex
aaaJjg1Fhs
aaaKQGRIk0
aaaKcxeoHS
aaaKfOd4i3
aaaKshGObR
 Index scan complete
 Total keys 23

 real 0m0.019s
 user 0m0.000s
 sys  0m0.000s

Total memory allocated: 1031.715 MB
Bytes per key: 47036151

About

Key-Value/Document store database library with btree and ARTree indexing methods, SSN-MVCC concurrency

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published