Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

LevelDB: a fast and lightweight key/value database library

code.google.com

Post reply on HN
Print view View original

41–50 of 82 posts

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

#41

Post by fleitz »

joe_the_user wrote: post #40
fleitz wrote: post #31

Earlier quoted context omitted.

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

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 Ky…

Why does lots of columns and tables make this approach awkward? Sure you might need a couple computed columns, and a little table de normalization, but IMHO most of where NoSQL gets it's performance is from de normalization.

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?

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

#43

Post by davidhollander »

sghemawat wrote: post #22
davidhollander wrote: post #12

Earlier quoted context omitted.

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 y…

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…

> difference in data structures

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

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

#44

Post by joe_the_user »

fleitz wrote: post #41
joe_the_user wrote: post #40

Earlier quoted context omitted.

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 Ky…

Why does lots of columns and tables make this approach awkward? Sure you might need a couple computed columns, and a little table de normalization, but IMHO most of where NoSQL gets it's performance is from de normalization. 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…

You certainly could do a SQL implementation. For my purposes, each of the many queries was going to involve something like at least six lines of logic (it was "find the nth value satisfying X, Y, and Z condition"). Debugging and trying make sure the indices worked correctly for each query looked uglier than creating a whole different structure - my structure was native C++ so there wasn't the translation issues of SQL.

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.

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

#46

Post by skidooer »

stephth wrote: post #36

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

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

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

#47

Post by psaccounts »

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?

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

#48

Post by evangineer »

gmarkov wrote: post #42

something similar + benchmarks http://stsdb.com

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

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

#49

Post by stephth »

skidooer wrote: post #46
stephth wrote: post #36

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

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

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.

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

#50

Post by est »

abarth wrote: post #17
18pfsmt wrote: post #5

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

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?

Post reply on HN