Commit graph

384 commits

Author SHA1 Message Date
Kresten Krab Thorup
ce898b5063 Don't do merge before inject 2012-04-26 08:17:48 +02:00
Kresten Krab Thorup
334d21971f sample 20 min run (MacBook Air/SSD) 2012-04-26 01:51:08 +02:00
Kresten Krab Thorup
3269e6fa96 Add lager dependency 2012-04-26 01:08:38 +02:00
Kresten Krab Thorup
51250d04da Initial work on hanoi:write 2012-04-26 01:02:56 +02:00
Kresten Krab Thorup
5e3cc8be51 Fix race condition with insert and bottom level 2012-04-26 01:01:34 +02:00
Kresten Krab Thorup
e147dd9d1e Improve merge work computation 2012-04-26 01:00:01 +02:00
Kresten Krab Thorup
5d95070669 Add debug loggin 2012-04-26 00:58:16 +02:00
Kresten Krab Thorup
6c8492c7d0 Use plain_rpc 2012-04-26 00:56:59 +02:00
Kresten Krab Thorup
085f400bb8 Do incremental merge before inject 2012-04-26 00:51:04 +02:00
Kresten Krab Thorup
d58ab9ea32 Introduce plain_rpc
Institutionalize the way hanoi_level handles RPC.
This is embodied in a new module, which should be
pushed to plain_fsm, but we'll keep it here for
now.
2012-04-26 00:49:57 +02:00
Gregory Burd
db116447fe Minor change. 2012-04-25 14:07:06 -04:00
Gregory Burd
e4d8615a99 Cleanup 2012-04-24 10:37:45 -04:00
Kresten Krab Thorup
86516d4b2d Add some notes on file descriptors to DESIGN.md 2012-04-24 14:07:15 +02:00
Kresten Krab Thorup
84f7fcc75b Update README a bit 2012-04-24 14:06:54 +02:00
Kresten Krab Thorup
a8a66a43a0 Add CRC32 data validation
If a KV entry does not validate CRC, then we simply
ignore it for now.

TODO: decide how to notify about broken KVs.
2012-04-24 13:49:00 +02:00
Kresten Krab Thorup
472ba4551e New visualizer
Shows 0..9 for merge activity at each level
Also prints disk size used and free
2012-04-24 01:43:53 +02:00
Kresten Krab Thorup
ff36e401b7 Incremental merge refactor, step #2
Now incremental merge has a new strategy.
In stead of doing the same amount of merge
work at all levels, we now compute the total
merge work load, and do as much as possible
on the first level, subtract work done, and
delegate to the next level, etc.

The effect of this is that we do more IO on
fewer files, improving sequential-ness of
the workload involved in the incremental merge.
2012-04-24 00:31:28 +02:00
Kresten Krab Thorup
9fb8a5e73f Refactor step #1, know current max_level
This refactoring just adds the stat to the
master gen_server of a Hanoi instance to 
know the current number of levels. Until now,
we've only held a reference to the current
top level.
2012-04-23 22:32:51 +02:00
Kresten Krab Thorup
755788ecfb Fix for hanoi store recovery
If we're opening a hanoi store configured with
smaller nursery size than the default, then
we need to make sure that we also open the
small levels.

Future feature is to actually squash the
smaller levels.
2012-04-23 14:14:12 +02:00
Kresten Krab Thorup
8b725cceaa Improve recovery
This improves recovery two-fold:

1. make sure that we actually wait for initial
   merge to complete (issue incremental_merge(0))

2. compute minimum required merge work for merge
   to establish invariant that there's room
   for a new nursery inject any time.
2012-04-23 13:53:42 +02:00
Kresten Krab Thorup
8796575053 Fix dumb errors 2012-04-23 13:49:17 +02:00
Kresten Krab Thorup
a1c8bb40bd Send step_done when merge ends also
… just to be nice, we'd get the {'DOWN', ...}
anyway
2012-04-23 04:55:10 +02:00
Kresten Krab Thorup
25b4099eec Only compress if compressed size is smaller 2012-04-23 04:23:52 +02:00
Kresten Krab Thorup
d37b227936 Implement compression + block size
option {compression, none|gzip|snappy}

... except right now using snappy is broken,
it seems that it causes bloom filters to
crash. Needs investigation.

option {block_size, 32768} 

... writes data to disk in chunks of ~32k.
2012-04-23 03:49:08 +02:00
Kresten Krab Thorup
14ef03e06a Initial options
Now we're ready to handle some options
2012-04-23 02:20:47 +02:00
Kresten Krab Thorup
0718d33d7a Add {sync_strategy, sync | {seconds, N} | none}
We should add o_sync also like bitcask
2012-04-23 02:20:12 +02:00
Kresten Krab Thorup
3b451d5863 Fix folding
The "blocking range fold" only works for modest
data sets, otherwise it gets prohibitively slow,
so for now we always do "snapshot range fold".
2012-04-23 02:10:18 +02:00
Kresten Krab Thorup
ca98b124ff Merge remote-tracking branch 'refs/remotes/origin/master' 2012-04-22 23:55:07 +02:00
Kresten Krab Thorup
8f5f62cf70 Switch order ABCX -> CBAX in visualizer
This makes it so that the youngest file is
always more left, and older files are always
more right.
2012-04-22 23:53:31 +02:00
Kresten Krab Thorup
99fb1bee74 When opening a level, enforce just enough merge
When re-opening a Hanoi data store, we need to
reestablish the invariant that there is always
room to inject a data file at the top level.

In a worst case scenario, every level has all of
A, B, and C; and thus needs to merge A+B -> X
fully in order to accommodate what the parent 
will inject. 2*BTREE_SIZE(Level) >= sizeof(A+B)
2012-04-22 23:49:39 +02:00
Kresten Krab Thorup
8694cc118f Specify infinity as gen_server:call timeout 2012-04-22 23:30:25 +02:00
Gregory Burd
67315ca796 Implementation notes belong in "DESIGN.md", not "README.md". 2012-04-22 09:27:17 -04:00
Kresten Krab Thorup
d17e448615 new visualizer 2012-04-22 15:14:14 +02:00
Gregory Burd
85b09530ee Update todo items. 2012-04-21 17:24:37 -04:00
Gregory Burd
638f2d56ee Merge pull request #3 from basho/rename-to-hanoi
Rename "lsm_btree" to "hanoi".
2012-04-21 12:30:07 -07:00
Gregory Burd
43f095b3f0 Rename "lsm-btree" to "hanoi". 2012-04-21 15:20:39 -04:00
Gregory Burd
fec14a1c51 Put the copyright/license header into a few overlooked files. 2012-04-19 18:09:01 -04:00
Gregory Burd
bd3e638a96 Merge branch 'master' into gsb-merge-krab-20120419 2012-04-19 18:03:19 -04:00
Gregory Burd
197914939c Removed redundant function. 2012-04-19 18:00:06 -04:00
Gregory Burd
23f6d76a72 Merge branch 'krab-incremental-merge' into gsb-merge-krab-20120419
Conflicts:
	src/lsm_btree.erl
	src/lsm_btree.hrl
2012-04-19 16:54:23 -04:00
Kresten Krab Thorup
6289602045 Improve incremental merge
This change makes incremental merge be concurrent 
with filling up the nursery. So in stead of waiting
for an incremental merge to complete before returning
from insert, it

- blocks waiting for a possible previous incremental merge to complete
- issues a new incremental merge.

This improves put latencies, but not throughput.
2012-04-19 22:33:27 +02:00
Kresten Krab Thorup
ee90944c62 Implement incremental insert
This slows down insert to be log2(N), where N is
the total number of objects in the store.  The upside
is that it also removes the terrible worst case
scenarios for insert.
2012-04-19 19:57:39 +02:00
Kresten Krab Thorup
3d80b164d5 Introduce 3rd file in each level to reduce worst-case
Now, each level is comprised of 3 files,

   A=Oldest, B=Older, C=Old

As in [Overmars and Leeuwen, 1983]. As soon as we have A & B,
we initiate a merge, (to the M=New) file, i.e. we merge more
eagerly than previously.

Next step in this refactoring is to add a scheduler that enforces
some merge activity as part of a PUT.
2012-04-19 16:07:11 +02:00
Gregory Burd
3e85a266a8 More things to do... 2012-04-18 17:40:21 -04:00
Gregory Burd
b14887f9da Merge branch 'master' of github.com:basho/lsm_btree 2012-04-18 17:12:50 -04:00
Gregory Burd
1da9a858d1 Keep track of todo items here 2012-04-18 17:12:40 -04:00
Gregory Burd
0a72ca1df9 The Log-Structured Merge-Tree (LSM-Tree) by Patrick O'Neil, Edward Cheng Dieter Gawlick, Elizabeth O'Neil 2012-04-18 17:06:24 -04:00
Gregory Burd
3f02eadc27 Too large a nursery opens up the potential for long (in seconds) merges. 2012-04-18 16:49:57 -04:00
Kresten Krab Thorup
4e53b0a083 Allow fold worker to send {fold_results, PID, KVs}
Not just individual KVs, but lists of KVs
2012-04-18 09:28:59 +02:00
Kresten Krab Thorup
b70d2af1da Add doc to lsm_btree.hrl 2012-04-18 09:26:54 +02:00