LevelDB: a fast and lightweight key/value database library

http://code.google.com/p/leveldb/

by adulau • 15 years ago

232 79 15 years ago

code.google.com

ma2rten• 15 years ago

Does someone have any idea, how the benchmark results compare to other databases (e.g. redis) ?

rb2k_2• 15 years ago

It doesn't seem to have a network interface. It is somewhat comparable to InnoDB or Tokyo/Kyoto Cabinet

davidhollander2• 15 years ago

Based on their numbers it looks slower than TokyoCabinet but still much faster than BerkleyDB. Would need to design a head to head benchmark.

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.

sghemawat6• 15 years ago

One of the leveldb authors here. TokyoCabinet is something we seriously considered using instead of writing leveldb. TokyoCabinet has great performance usually. I haven't done a careful head-to-head comparison, but it wouldn't surprise me if it was somewhat faster than leveldb for many workloads. Plus TokyoCabinet is more mature, has matching server code etc. and may therefore be a better fit for many projects.

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).

mcorrientes2• 15 years ago

Sounds like a possible redis or memcached replacement.

A performance comparision with memcached would be interesting.

latch2• 15 years ago

replacement is a strong word when you consider that you are talking about:

get/put/delete vs http://redis.io/commands

mcorrientes2• 15 years ago

sure, dependes of course if you're using redis only for a simple key value store.

emehrkay• 15 years ago

That is beautiful documentation.

18pfsmt• 15 years ago

It looks like this is a local storage tool, similar to sqlite. Is that correct? Lots of chromium devs on that list.

abarth2• 15 years ago

That's correct. We're using leveldb as the back-end for IndexedDB in Chrome.

est• 15 years ago

Please enlighten me, in the LevelDB page it said:

> Only a single process (possibly multi-threaded) can access a particular database at a time.

But I presume Chrome is multiprocess by nature?

leif3• 15 years ago

Anybody know what hardware those benchmarks were on? Is it actually durable? They mention problems with writeback caching, but are they at least durable from the OS perspective? How well does it scale?

latch2• 15 years ago

it says so on the page: CPU: 4 x Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz

Safe to assume the data fit into memory..whatever amount there was.

leif3• 15 years ago

more interested in disk (and workloads larger than memory, but it doesn't sound like that's their use case)

sghemawat6• 15 years ago

It is durable from an OS perspective. I started typing in a long explanation, but I think the comment for the "sync" field in the options.h file captures things well:

  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;

We don't have much experience with scaling to larger databases yet. There are known problems which will cause a (smallish) constant factor slowdown in write performance after the database becomes a few (10?) GB in size, but I don't recall the details all that well, and the implementation has changed somewhat since that experiment. I would like to characterize this better and fix things so we can support somewhere between 100GB-1TB databases well. It just hasn't become a priority yet.

The benchmark numbers on the linked page were from a small million entry database that easily fits in the OS buffer cache.

jedc• 15 years ago

Welcome to HN commenting, Sanjay!

(For those that aren't familiar, his bio is here: http://research.google.com/people/sanjay/index.html)

leif3• 15 years ago

Thanks!

JulianMorrison• 15 years ago

Writes being lost means what, a trashed file? Or merely an incomplete one?

necubi• 15 years ago

Note that this is not a database server, like Redis or Memcached. This is a database library, more along the lines of sqlite. In particular: "There is no client-server support builtin to the library. An application that needs such support will have to wrap their own server around the library" and only one process can access a database a time.

rb2k_2• 15 years ago

It's the same model that Tokyo/Kyoto Cabinet uses. The difference is that Tokyo/Kyoto Tyrant is an available network interface :)

yingfeng3• 15 years ago

LevelDB should not be compared with the storage model of TC, because leveldb could be looked on a bigtable that run on single node, which is a model that is optimzied for updating instead of reading. The application situation for leveldb is different with that of TC

amjith• 15 years ago

Hi Thank you for this explanation. My first thought was how is it different than Redis and then when I read no client-server support, I thought, this is worse than Redis. But then your comparison with sqlite makes it a little bit better. I can see a few use cases for it now. Thanks!

rajasharan• 15 years ago

I think saying it's not like 'Memcached' could be wrong. I can think of Memcached as a specialized case of LevelDB.

metabrew• 15 years ago

This is pretty neat, and different from many other "simple" KV stores, because it arranges things in key-order on disk, and permits forward/reverse iteration over keys. (ie, range queries are cheap)

edit: it's actually full log-structured merge, sstables, memtables etc.

cool-RR• 15 years ago

All the code files have this as a first line:

    // Copyright (c) 2011 The LevelDB Authors. All rights reserved.

I wonder how come it's not copyrighted to Google.

ivank• 15 years ago

That's what Google does when they set up a project that accepts contributions. Google Inc. is the author; see http://code.google.com/p/leveldb/source/browse/trunk/AUTHORS

azsromej• 15 years ago

The initial version written by the authors of MapReduce and BigTable

abarth2• 15 years ago

The idea behind this approach is to simplify the maintenance of the copyright line and to encourage collective ownership of the code. I'm told that some open-source projects have conflicts about who's name appears in which files, but I've not experienced that first-hand.

jhawk28• 15 years ago

This looks like it has similar goals to bitcask. The tradeoffs and differences would be nice to know.

sghemawat6• 15 years ago

leveldb is a persistent ordered map; bitcask is a persistent hash table (no ordered iteration).

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.

sriramk• 15 years ago

I just need to say - it's pretty cool to see Sanjay Ghemawat hanging out on HN.

stephth3• 15 years ago

Also worth noting: bitcask is written in erlang and leveldb in c++.

joe_the_user3• 15 years ago

What I would like to know is, is there support accessing values by nth-largest key?

I had to roll my own b-tree library specifically to get this feature since nothing out-there had it.

fleitz2• 15 years ago

Why not index size(key)?

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

joe_the_user3• 15 years ago

I don't get it,

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).

dhruvbird• 15 years ago

I don't think that's what the OP wants. The real result expected is supposed to be ordered by the value of the key itself rather than the size of the key.

stephth3• 15 years ago

This could be great news for iOS. AFAIK, this is the first K/V DB that could be built for iOS (c++) and has a free license that is compatible with the AppStore (Tokyo Cabinet uses LGPL and the author has shown no interest to me in adding a static linking clause, Berkeley DB requires an expensive commercial license, etc).

skidooer• 15 years ago

Not key/value, but Mobile CouchBase (CouchDB) supports iOS and apps using it have been approved for the App Store.

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++.

stephth3• 15 years ago

True. I haven't tried it and it looks promising, but currently it depends on packages like Erlang, Spidermonkey, and OpenSSL, so adding Mobile CouchBase to an app means increasing its size by about 42MB.

electrum• 15 years ago

What advantages does this have over the built-in SQLite?

beder• 15 years ago

It stores key/value pairs instead of relational data. I've been looking for something like this for a while as a replacement to NSUserDefaults.

br14• 15 years ago

Inserts are much faster due to the log-structured merge-tree.

gmarkov• 15 years ago

something similar + benchmarks http://stsdb.com

evangineer• 15 years ago

"STSdb is coded in 100% pure managed C#." & tri-licensed (GPL2/GPL3/Commercial) vs LevelDB's C++ & New BSD license.

Hackers should be able to figure out which bests fits their particular use case.

Emore• 15 years ago

@sghemawat: Are you planning on implementing atomic CAS operations?

sghemawat6• 15 years ago

We have no such plans. The library is designed so that concurrency control is outside its scope. If I needed it for an application, I might consider using some application level code that looks like:

    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;
    }

This should be not much slower than any hard-wired CAS we could provide from inside leveldb.

psaccounts4• 15 years ago

The implementation seems to use Log-Structured Merge Trees.

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?

timr2• 15 years ago

http://labs.google.com/papers/bigtable.html

psaccounts4• 15 years ago

But it doesn't really describe the LSM data structure!

br14• 15 years ago

Read "Cache-Oblivious Streaming B-trees" http://supertech.csail.mit.edu/cacheObliviousBTree.html It' LSM with faster searches.

psaccounts4• 15 years ago

Thanks for the pointer. Are there any known open-source implementations of the same?

joeshaw• 15 years ago

The leveling here reminds me a bit of how Lucene organizes and compacts its segments files. When you write documents to Lucene they are written to a segments file, usually one for each batch of documents you write. When searching, each of the segments files are searched for terms, so the more segments files you have, the slower the search tends to be. When segments files reach a certain size they are automatically compacted into other segments files. Users can (and should) then "optimize" their index, which compacts all the segments files into a single file. The log files and sorted tables of leveldb appear to work very similarly.

foobarbazetc2• 15 years ago

Anyone manage to compile this on OS X?

forgotusername• 15 years ago

You'll need a compiler from MacPorts: it wants C++0x which Apple's gcc doesn't support yet.

foobarbazetc2• 15 years ago

Argh... that makes it even harder to use on iOS. :)

jorlow2• 15 years ago

Chromium compiles leveldb using the standard Xcode toolchain, but has a dependency on Chromium's "base" library, so it's for sure possible. I can't tell you the exact steps, but I suspect it wouldn't be too hard to get the posix port compiling with Xcode as well though.

davisp2• 15 years ago

Managed to get it working last night:

http://code.google.com/p/leveldb/issues/detail?id=2

argvzero• 15 years ago

Was really psyched until I saw --std=c++0x in the Makefile. What 0x features does leveldb depend on, and can those dependencies be realistically removed?

sghemawat6• 15 years ago

The use of c++0x should be limited to the small AtomicPointer class in port_posix.h. The class uses <cstdatomic> for its implementation. If you can provide a different implementation of "acquire store" and "release load" for your architecture, you should be all set without the need for c++0x.

I suspect that you may find suitable code in the chromium source code. See leveldb's port_chromium.h.

davisp2• 15 years ago

I managed to get an initial patch up here:

http://code.google.com/p/leveldb/issues/detail?id=2

xinmans• 15 years ago

I suspect you need a newer version of gcc/g++ (one that supports the c++0x standard). You can probably download a later gcc package and then use that to install.

  -Jeff

On Wed, May 11, 2011 at 3:37 AM, conglin.deng <conglin.deng@aliyun-inc.com> wrote: > Hi jeff, > > > > I have checkout leveldb code from code.google.com, > > But when I run make command on the root folder, encounter a error as > below, > > > > /////////////////////////// > > [root@host]$make > > g++ -c -DLEVELDB_PLATFORM_POSIX -I. -I./include -std=c++0x -g2 > db/db_bench.cc -o db/db_bench.o > > cc1plus: error: unrecognized command line option "-std=c++0x" > > make: * [db/db_bench.o] Error 1 > > [root@host]$pwd > > /home/admin/leveldb > > [root@host]$ > > /////////////////////////// > > > > > > Would you please to tell me how to build and setup leveldb on a redhat > 5.4 env. Thanks very much! > > > > Thanks > > linc

yingfeng3• 15 years ago

I uses boost::atomic to make it usable without c++0x http://www.chaoticmind.net/~hcb/projects/boost.atomic/

#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); } };

LevelDB: a fast and lightweight key/value database library

Related Stories