LevelDB: a fast and lightweight key/value database library • Hacker News Board

Re: LevelDB: a fast and lightweight key/value database library

#51

Post by ddispaltro » Mon, May 09, 2011, 1:31 AM UTC

est wrote: post #50

abarth wrote: post #17

Earlier quoted context omitted.

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

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?

I am guessing each chrome "tab" (read: process) has it's own db open, that is just a guess though.

Re: LevelDB: a fast and lightweight key/value database library

#52

Post by joeshaw » Mon, May 09, 2011, 1:40 AM UTC

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.

Re: LevelDB: a fast and lightweight key/value database library

#53

Post by timr » Mon, May 09, 2011, 2:06 AM UTC

psaccounts wrote: post #47

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?

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

Re: LevelDB: a fast and lightweight key/value database library

#54

Post by psaccounts » Mon, May 09, 2011, 2:38 AM UTC

timr wrote: post #53

psaccounts wrote: post #47

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?

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

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

Re: LevelDB: a fast and lightweight key/value database library

#55

Post by jbapple » Mon, May 09, 2011, 2:44 AM UTC

psaccounts wrote: post #33

lisper wrote: post #29

Earlier quoted context omitted.

Did you consider fractal trees? http://tokutek.com/presentations/bender-Scalperf-9-09.pdf

Is there a more useful technical paper on Fractal Trees? Better yet is there a open source implementation of the same?

Cache-oblivious streaming B-trees:

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.

Re: LevelDB: a fast and lightweight key/value database library

#56

Post by foobarbazetc » Mon, May 09, 2011, 3:15 AM UTC

Anyone manage to compile this on OS X?

Re: LevelDB: a fast and lightweight key/value database library

#57

Post by timr » Mon, May 09, 2011, 3:33 AM UTC

psaccounts wrote: post #54

timr wrote: post #53

Earlier quoted context omitted.

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

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

It describes the approach used here (cf. all of the discussion of the tablet system). The few differences are documented:

http://code.google.com/p/leveldb/source/browse/trunk/doc/imp...

Re: LevelDB: a fast and lightweight key/value database library

#58

Post by argvzero » Mon, May 09, 2011, 3:49 AM UTC

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?

Re: LevelDB: a fast and lightweight key/value database library

#59

Post by yingfeng » Mon, May 09, 2011, 3:51 AM UTC

rb2k_ wrote: post #19

necubi wrote: post #10

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.

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

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

Re: LevelDB: a fast and lightweight key/value database library

#60

Post by yingfeng » Mon, May 09, 2011, 4:03 AM UTC

lisper wrote: post #29

sghemawat wrote: post #22

Earlier quoted context omitted.

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. Howev…

Did you consider fractal trees? http://tokutek.com/presentations/bender-Scalperf-9-09.pdf

fractal trees should have a faster read performance with leveldb with a comparable updating performance. There does not exist any open source solution for such structure, while we could hope that www.acunu.com might provide an open source solution for similary Stratified B-tree http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-...