greg/hanoidb
1
0
Fork 0
Code Issues 10 Pull requests 3 Projects Releases Packages Wiki Activity
384 commits 4 branches 0 tags 2.4 MiB
Commit graph

384 commits

This branch
This branch
All branches
Author SHA1 Message Date
Erik Søe Sørensen
49c8d5b06f Clarify level handling in writer. 2012-01-16 07:50:31 +08:00
Erik Søe Sørensen
fa39f85a00 README: Explain 'LSM' and provide link to paper. 2012-01-16 07:49:58 +08:00
Kresten Krab Thorup
771d18f9f7 Implement lsm_btree:fold_range/5 
First implementation of range fold

Range folding doesn't prohibit insert/lookup or
merge operations, but each level can only have
one range fold operation active.

Thus, worst case active range folds can double
space requirements, because it holds hard-linked
copies of used btree files.
 2012-01-16 00:37:52 +01:00
Kresten Krab Thorup
2923ef8eff Bugfix merged in basho/ebloom 
so we can go back to depending on basho/ebloom
 2012-01-11 00:14:45 -04:00
Kresten Krab Thorup
f2629c3fd2 Improve nursery handling 
- Code moved to separate module
- Recovery now operational; re-opening a
  tree will actually read the nursery log.

We use a sequential log file for the nursery
and also keep inserted {K,V} in memory
only 32 K/V pairs at a time.

NURSERY_SIZE = (1 bsl TOP_LEVEL)
configured in src/lsm_btree.htl
 2012-01-10 18:04:13 -04:00
Kresten Krab Thorup
3945abe45a Merge branch 'statem-failing-lookups' of https://github.com/jlouis/lsm_btree 2012-01-08 10:39:26 +01:00
Jesper Louis Andersen
793f8e3a3a Optimize open dict check. 
A dict is open and with keys if its size is greater than 0. Go through
the dicts one by one with lists:any/2 and use that to optimize the
check. Ought to run faster than traversing the full set.
 2012-01-08 00:01:18 +01:00
Jesper Louis Andersen
60af669400 Implement failing key lookup. 
We generate a set of names that are highly unlikely to be in the tree
as well because this makes it way easier for the ?SUCHTHAT macro to
succeed.
 2012-01-07 23:35:27 +01:00
Jesper Louis Andersen
c8b9a6183f Work on failing keys. Optimize generator. 
To make failing keys work we must be able to produce a key in fewer
failures then currently. So encode the picker for non-empty trees
directly so it is much faster and doesn't try to do it by generating a
case and then asking "is this one good enough?". A simple
dict:filter/2 does it.
 2012-01-07 22:58:38 +01:00
Jesper Louis Andersen
6b8683bb08 Implement failing lookups in the driver. 2012-01-07 22:57:01 +01:00
Kresten Krab Thorup
fab3bf8427 Minor typo 2012-01-07 18:49:20 +01:00
Kresten Krab Thorup
eae41cec83 Update REAME 2012-01-07 17:54:35 +01:00
Kresten Krab Thorup
15736dd82a Rename modules fractal_btree -> lsm_btree 2012-01-07 17:17:48 +01:00
Kresten Krab Thorup
db2399ee4a Rename fractal_btree -> lsm_btree, phase I 2012-01-07 17:14:52 +01:00
Kresten Krab Thorup
1feef35d33 Add option to test with 'TRIQ' or 'PROPER' 2012-01-07 15:44:31 +01:00
Kresten Krab Thorup
03350aa096 Add close to shame tests 2012-01-07 15:16:57 +01:00
Kresten Krab Thorup
99a6985eed Allow put(Key, Binary|'deleted') 
Last missing piece to make delete work it seems
 2012-01-07 14:49:25 +01:00
Kresten Krab Thorup
5ca4443f04 Remove warning 2012-01-07 14:48:10 +01:00
Kresten Krab Thorup
11d135c3ed Merge branch 'statem-test' of https://github.com/jlouis/fractal_btree 2012-01-07 14:46:22 +01:00
Jesper Louis Andersen
84d4b56779 test_tree_simple_2: correctly close down the fractal Btree. 2012-01-07 14:21:38 +01:00
Kresten Krab Thorup
07c4df29ec Fix unit test 
We currently have no check for concurrently
opening the same fractal_btree; we probably need
to implement a simple locking mechanism.
 2012-01-07 13:56:14 +01:00
Kresten Krab Thorup
0064b0405e Refix readme 2012-01-07 13:55:03 +01:00
Jesper Louis Andersen
b99a206494 Restructure file, add deletion. 
A refactoring run made the code more digestible. Also add the needed
clauses for handling random deletion.
 2012-01-07 12:44:07 +01:00
Jesper Louis Andersen
c80d7d1a6a Add deletion support to the driver. 2012-01-07 12:44:07 +01:00
Jesper Louis Andersen
e10208462b Make it much less likely to open up a new btree. 2012-01-07 12:44:07 +01:00
Kresten Krab Thorup
aa0fa64928 Merge branch 'statem-test' of https://github.com/jlouis/fractal_btree 2012-01-07 01:19:29 +01:00
Jesper Louis Andersen
fcff982050 Utilize the new lookup of existing keys in PropEr. 
This patch implements another possible command: Lookup of keys that
already exist in the tree somewhere. We use a dict as the test tool:
the postcondition verifies that the value obtained from the fractal
btree matches the one we put in the dict earlier.
 2012-01-07 01:02:09 +01:00
Jesper Louis Andersen
fd87d7963a Improve driver cleanup, implement lookup of existing keys. 
If we decide to stop the driver, we should not reply back before we
have a clean state with all BTrees closed.

Also, implement lookup of existing keys in the tree.
 2012-01-07 01:00:31 +01:00
Jesper Louis Andersen
372a05619c Improve the test stale btree removal. 
Also delete the "simple" Btree in between test runs so we have a clean
slate of what is happening.
 2012-01-07 00:58:57 +01:00
Kresten Krab Thorup
0f64e199b5 Minor read me updates 2012-01-07 00:29:06 +01:00
Kresten Krab Thorup
c53db4ba20 Don't start sasl in tree_test 2012-01-07 00:28:46 +01:00
Kresten Krab Thorup
3d0c36c3bc Add option to evict tombstones in merge 2012-01-07 00:28:26 +01:00
Kresten Krab Thorup
5b4a4551a9 Reduce verbosity 2012-01-07 00:27:20 +01:00
Kresten Krab Thorup
120609f8ac Delete X files so levels can reopen cleanly 2012-01-07 00:26:44 +01:00
Kresten Krab Thorup
61f0aa26d2 Merge branch 'level_mainloop_simplification' of git://github.com/eriksoe/fractal_btree 2012-01-06 23:48:40 +01:00
Kresten Krab Thorup
f31a771bc3 Merge jlouis/fractal_btree statem-test 2012-01-06 23:23:39 +01:00
Jesper Louis Andersen
01d0007168 Split tests to where they belong. Add simple statem test. 
; Split the writer tests to the writer parts. This is not entirely
  correct since they both read and write, but oh, well.
; Provide a simple statem test which opens trees and puts values.
 2012-01-06 22:58:07 +01:00
Jesper Louis Andersen
de8d09231e Preliminary cleanup of test cases. 
This is not the "right" way to do it since it should be internalized,
but for a start it will do until we fix it.
 2012-01-06 22:55:07 +01:00
Kresten Krab Thorup
3e5a315b18 Erik's ebloom has the fix 
Switch back to basho/ebloom when his pull req
is accepted.
 2012-01-06 22:53:26 +01:00
Kresten Krab Thorup
b6fe048a6f A performance comparison w/InnoDB 
Bottom line is that we're currently roughly
at-par with InnoDB; our gets are a bit slower
but we're using 50MB RAM, when InnoDB uses 1G.
 2012-01-06 22:30:12 +01:00
Jesper Louis Andersen
0674ae3332 Introduce proper as a dependency. 2012-01-06 21:22:41 +01:00
Jesper Louis Andersen
fcf7af36ca Provide a Makefile for running dialyzer. 
While here, also dump another slew of goodies in the makefile.
 2012-01-06 21:22:23 +01:00
Erik Søe Sørensen
091df9392e levelpresence.sh: Add dynamicer mode. 2012-01-06 13:56:52 +01:00
Erik Søe Sørensen
dac9b31266 Merge branch 'master' of github.com:eriksoe/fractal_btree 
Conflicts:
	src/fractal_btree_level.erl
 2012-01-06 13:56:32 +01:00
Kresten Krab Thorup
4e8602043f Implement range_fold 2012-01-06 02:06:25 +01:00
Kresten Krab Thorup
9a624f963e Rename read_leaf_node -> next_leaf_node 2012-01-06 02:06:00 +01:00
Kresten Krab Thorup
b21e253324 Store child-refs as {Pos,Size} so we can pread 
This allows us to use file:pread to read a
child-node, rather than two separate reads
(one for node block size, and then one for 
the node block itself).

Also, encode the level# in node header, so that
scanning leafs doesn't need to decode the
node contents for inner nodes.
 2012-01-06 00:29:05 +01:00
Kresten Krab Thorup
2f985d8576 Fix indentation 2012-01-06 00:02:29 +01:00
Kresten Krab Thorup
e12544d0be A bit more README / background info 2012-01-06 00:02:00 +01:00
Erik Søe Sørensen
90ae581213 level: Calculate the size of the merged file correctly - again. 2012-01-05 21:09:36 +01:00