Comments (3)
Haven't gone through all of the design docs yet, but would love two see two things added:
- time complexities for the various operations and a comparison to the current setup
- references to the literature, where it has inspired various features, etc.
from bitcask.
Unfortunately I don't have any reference paper for this. I would love to know if you know of any to avoid wasting my time on bad paths. My naive search for "spill to disk hash table" didn't really turn up anything relevant. Searching for "hot data and virtual memory" got me some pages of Readings in Database Systems, which I promptly bought. But the paper in question was about executing joins and no other paper in there seem similar enough. So I'm down $60, but no reference.
As for the time complexity: without considering the fact that some pages are memory mapped and thus there is the probability of a heavy penalty for operations once you consume the entire memory buffer, the data structure is a very plain hashtable where items with the same hash are laid out sequentially in pages instead of in a list, for example. The table is never rehashed. So in theory it is still O(1) + cost of scanning a series of pages which is proportional to the data set size. I am not sure how to compute time complexities that are more meaningful for the interesting scenarios where any number of the pages might generate I/O. If you assume that we can not recommend its use if the hot data does not fit in memory, because you fall off the memory/disk cliff, you could say that it should stay in the vicinity of O(1) + k * num_keys or something.
from bitcask.
@engelsanchez Looks forward to it, but is there any news about the implement?
I just come up with a simple implement, replace the keydir data struct with a LevelDB instance, the implement is easy, but not for the time complex and any other criticals.
from bitcask.
Related Issues (20)
- A bitcask file can get merged repeatedly [JIRA: RIAK-1844] HOT 8
- bitcask NIF doesn't compile cleanly on OS X 10.10 [JIRA: RIAK-1574] HOT 2
- Startup crash trying to read key from corrupted data file [JIRA: RIAK-1819] HOT 5
- Repeated crashes during merge operations [JIRA: RIAK-1903] HOT 4
- Can't manually force a merge, error - efile_driver_unavailable [JIRA: RIAK-2036] HOT 5
- Include Bitcask data file count in merge info messages. [JIRA: RIAK-2039]
- Potential Process Leak [JIRA: RIAK-2227] HOT 2
- Lock file staleness check could be more robust [JIRA: RIAK-2230]
- question about read concurrency [JIRA: RIAK-2330] HOT 1
- Operation aborts if any file contains a corrupt key [JIRA: RIAK-2371] HOT 1
- rebar abort [JIRA: RIAK-2485] HOT 5
- Errors in `merge_single_tombstone` and `open_file` `append` mode [JIRA: RIAK-2733] HOT 2
- bitcask:merge/1 keeps file descriptors of deleted files open [JIRA: RIAK-2814] HOT 2
- File Open behaves differently between NIF and Erlang modes [JIRA: RIAK-2895] HOT 1
- bitcask failed to merge.merge_locked,locked
- c_src/bitcask_nifs.c: pair of bad % specifiers ?
- Build broken with OTP 21: use of the deprecated get_stacktrace/0 in dependency meck HOT 3
- Call bitcask_merge_worker:merge(DirName) is error
- How to run YCSB workload for bitcask?
- In the bitcask intro paper we see it being mentioned that bitcask is able to support datasets larger than 10 X system memory. I am trying to understand how? HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from bitcask.