LevelDB: a fast and lightweight key/value database library
code.google.com
code.google.com
An interesting point to note is that Mobile CouchBase is primarily written in Erlang, so porting any existing key/value stores is not dependant on their native language being C or C++.
CREATE TABLE kv (key text PRIMARY KEY, value text);edit: it's actually full log-structured merge, sstables, memtables etc.
The only paper on this data structure seems to be: http://goo.gl/CVF1l
This paper is poorly written and quite honestly not useful to implement an LSM tree. Does anyone know of a better paper than this one?
http://code.google.com/p/leveldb/source/browse/trunk/doc/imp...
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
bitcask stores a fixed size record in memory for every key. So for databases with large number of keys, it may use too much memory for some applications.
bitcask can guarantee at most one disk seek per lookup I think. leveldb may have to do a small handful of disk seeks. To clarify, leveldb stores data in a sequence of levels. Each level stores approximately ten times as much data as the level before it. A read needs one disk seek per level. So if 10% of the db fits in memory, leveldb will need to do one seek (for the last level since all of the earlier levels should end up cached in the OS buffer cache). If 1% fits in memory, leveldb will need two seeks.
#include <boost/atomic.hpp>
class AtomicPointer { private: boost::atomic<void> rep_; public: AtomicPointer() { } explicit AtomicPointer(void v) { } inline void* Acquire_Load() const { return rep_.load(boost::memory_order_acquire); } inline void Release_Store(void* v) { rep_.store(v, boost::memory_order_release); } inline void* NoBarrier_Load() const { return rep_.load(boost::memory_order_relaxed); } inline void NoBarrier_Store(void* v) { rep_.store(v, boost::memory_order_relaxed); } };
Safe to assume the data fit into memory..whatever amount there was.
struct WriteOptions {
// If true, the write will be flushed from the operating system
// buffer cache (by calling WritableFile::Sync()) before the write
// is considered complete. If this flag is true, writes will be
// slower.
//
// If this flag is false, and the machine crashes, some recent
// writes may be lost. Note that if it is just the process that
// crashes (i.e., the machine does not reboot), no writes will be
// lost even if sync==false.
//
// In other words, a DB write with sync==false has similar
// crash semantics as the "write()" system call. A DB write
// with sync==true has similar crash semantics to a "write()"
// system call followed by "fsync()".
//
// Default: false
bool sync;
The benchmark numbers on the linked page were from a small million entry database that easily fits in the OS buffer cache.
(For those that aren't familiar, his bio is here: http://research.google.com/people/sanjay/index.html)
I had to roll my own b-tree library specifically to get this feature since nothing out-there had it.
Then lookup the n-th largest key and then pull the values?
eg. SELECT value from key_value_pairs order by size(key) LIMIT N
How would you use this approach to find say, the 195687th largest element in O(log(n)) time?
Edit: However, I do know I can write a SQL query to find this - an ordinary index plus limit should do this. It's just such an approach gets really awkward and so unpredictable when you are dealing with a lot of distinct columns and tables - why I implemented this with key-value DB (a custom index on top of Kyoto Cabinet).
Regardless of how many elements compose the key the calculation is the same. I'd be surprised if you couldn't approach O(log(n)) time with a good SQL implementation, some computed columns and/or indexed views.
Just wondering was the b-tree implementation you did a pure B-Tree or was the data structure itself modified in some way. eg. storing the number of elements to the left or right?
I used a B-tree modified by adding a member variable including the total number of children of each parent. Its so simple a modification I don't know why more implementations don't use it but, it seems they don't.
I suspect that you may find suitable code in the chromium source code. See leveldb's port_chromium.h.
-Jeff
bool CAS(db, key, oldvalue, newvalue) {
lock some mutex;
read key's value from db;
bool result = (value == oldvalue);
if (result) write key=>newvalue to db;
unlock;
return result;
}
> Only a single process (possibly multi-threaded) can access a particular database at a time.
But I presume Chrome is multiprocess by nature?
Hackers should be able to figure out which bests fits their particular use case.
I don't think Redis is a good comparison as that's an in-memory database so better suited for the 10% of hot data you'd need to cache. Whereas disk stores like TokyoCabinet and LevelDB would be great for storing the other 90-100%. If your use case involves a large dataset and you don't have terabytes of RAM lying around, that is.
However because of a fundamental difference in data structures (TokyoCabinet uses btrees for ordered storage; leveldb uses log structured merge trees), random write performance (which is important for our needs) is significantly better in leveldb. This part we did measure. IIRC, we could fill TokyoCabinet with a million 100-byte writes in less than two seconds if writing sequentially, but the time ballooned to ~2000 seconds if we wrote randomly. The corresponding slowdown for leveldb is from ~1.5 seconds (sequential) to ~2.5 seconds (random).
http://supertech.csail.mit.edu/papers/sbtree.pdf
I don't know for certain any open-source implementation, but I have heard COLAs are used in HBase.
Always good to have more tools in one's arsenal in that case. I'll drop one of you a message if I write a Lua binding for it (using LuaJIT+embedded k/v for data services atm).
thanks
A performance comparision with memcached would be interesting.
get/put/delete vs http://redis.io/commands