Sparkey – Key/value storage by Spotify • Hacker News Board

Re: Sparkey – Key/value storage by Spotify

#31

Post by krka » Mon, Sep 02, 2013, 6:08 PM UTC

StefanKarpinski wrote: post #30

jdp wrote: post #27

Another cool project is bam[1], a constant key/value server built on similar principles. A single input file (in this case, a TSV file instead of the SPL log file) and an index file. The cool thing about bam is that it uses the CMPH[2] library to generate a minimal perfect hash function over the keys in the input file before putting them in the index file. [1]: https://github.com/StefanKarpinski/bam [2]: http://cmph.…

Wow, didn't expect this to make a mention on the front page of HN today. I never did convince Etsy to let me deploy bam in production, but it's so simple that it should be doable without much fuss. I mainly built it as a proof-of-concept to show that serving static data does not have to be difficult – and that loading large static data sets into a relational database is a truly wasteful, terrible approach. Are you ac…

Bam looks really interesting, definitely a lot simpler than Sparkey, and the basic principle is the same. I have been hesitant to use perfect hashing for Sparkey since I wasn't sure how well it holds up for really large data sets (close to a billion keys). Impressive to write it in less than 300 lines of clean code!

Re: Sparkey – Key/value storage by Spotify

#32

Post by jetz » Mon, Sep 02, 2013, 6:49 PM UTC

There is LMDB (http://symas.com/mdb/) storage solution for read heavy workloads. Alternative to LevelDB or CDB.

Re: Sparkey – Key/value storage by Spotify

#33

Post by jetz » Mon, Sep 02, 2013, 6:55 PM UTC

levosmetalo wrote: post #16

I remember my interview at Spotify where we discussed how to implement thumbnail display service in the most effective way. What we actually came to is something along the lines of this library. I always like it when a company focus on their real problems in job interviews and manage to avoid the brain teaser trap. That way you can have a feeling about the job that you are going to work on there, and see if you reall…

If you're familiar with thumbnail display you know Facebook has Haystack for efficient image serving. It goes very low end. Sparkey or CDB or BAM (mentioned in this post) could be much less complex and can do similar work. Why did they go Haystack route I dont get it.

Re: Sparkey – Key/value storage by Spotify

#34

Post by iampims » Mon, Sep 02, 2013, 7:25 PM UTC

woogley wrote: post #14

sorbits wrote: post #10

Earlier quoted context omitted.

According to GitHub, last commit (which is also initial checkin) is two years old.

The project is hosted at Google Code. Last commit was Aug 21: https://code.google.com/p/leveldb/source/detail?r=748539c183...

There is also the basho fork of LevelDB (https://github.com/basho/leveldb) which adds a few nice things.

If you're interested in the internals of LevelDB, I strongly recommend watching this talk http://www.youtube.com/watch?v=vo88IdglU_8 (slides here https://speakerdeck.com/basho/optimizing-leveldb-for-perform...)

Re: Sparkey – Key/value storage by Spotify

#35

Post by krka » Mon, Sep 02, 2013, 7:31 PM UTC

I have now created a very simple benchmark suite to give you some rough performance numbers, and updated the README to include some sample numbers for one specific machine.

Re: Sparkey – Key/value storage by Spotify

#36

Post by staunch » Mon, Sep 02, 2013, 7:57 PM UTC

rohansingh wrote: post #28

levosmetalo wrote: post #16

I remember my interview at Spotify where we discussed how to implement thumbnail display service in the most effective way. What we actually came to is something along the lines of this library. I always like it when a company focus on their real problems in job interviews and manage to avoid the brain teaser trap. That way you can have a feeling about the job that you are going to work on there, and see if you reall…

Thanks :-) That is a go-to interview question for us and we actually all do it slightly differently and take it in different directions depending on your expertise or specialization. It is really closely aligned to what our core service is (distributing and streaming files) and is a great chance to talk with the interviewee and figure out where their strengths are. Totally encourage other people to interview this way…

I also like this style, but you have to be very mindful of the fact that you've been thinking about the problem 1000x more than the candidate. The Curse of Knowledge[1] haunts the interview process. I haven't tried it much, but maybe it would be better to always use a fresh problem in each interview that not even you had seen. Maybe selected from StackOverflow.

1. http://en.m.wikipedia.org/wiki/Curse_of_knowledge

Re: Sparkey – Key/value storage by Spotify

#37

Post by seiji » Mon, Sep 02, 2013, 10:21 PM UTC

jflatow wrote: post #29

Similar also to DiscoDB, which does support compression, and uses perfect hashing for constant time-lookup with minimal disk access. Not only that but it provides lightning-fast conjunctive normal form queries, a.k.a logical combinations of primitive keys. Plus it has Python / Erlang bindings. http://discodb.rtfd.org https://github.com/jflatow/discodb

Yeah, my first two thoughts were discodb and bitcask http://basho.com/hello-bitcask/ too.

Re: Sparkey – Key/value storage by Spotify

#38

Post by seiji » Mon, Sep 02, 2013, 10:30 PM UTC

jetz wrote: post #33

levosmetalo wrote: post #16

I remember my interview at Spotify where we discussed how to implement thumbnail display service in the most effective way. What we actually came to is something along the lines of this library. I always like it when a company focus on their real problems in job interviews and manage to avoid the brain teaser trap. That way you can have a feeling about the job that you are going to work on there, and see if you reall…

If you're familiar with thumbnail display you know Facebook has Haystack for efficient image serving. It goes very low end. Sparkey or CDB or BAM (mentioned in this post) could be much less complex and can do similar work. Why did they go Haystack route I dont get it.

Are you asking why they didn't use Haystack? Haystack isn't released publicly as far as I can tell (plus, just because another company writes something doesn't mean it's actually good).

Re: Sparkey – Key/value storage by Spotify

#39

Post by jeltz » Mon, Sep 02, 2013, 10:43 PM UTC

seiji wrote: post #38

jetz wrote: post #33

Earlier quoted context omitted.

If you're familiar with thumbnail display you know Facebook has Haystack for efficient image serving. It goes very low end. Sparkey or CDB or BAM (mentioned in this post) could be much less complex and can do similar work. Why did they go Haystack route I dont get it.

Are you asking why they didn't use Haystack? Haystack isn't released publicly as far as I can tell (plus, just because another company writes something doesn't mean it's actually good).

No, I think he is asking why Facebook isn't using something like CDB.

Re: Sparkey – Key/value storage by Spotify

#40

Post by jetz » Mon, Sep 02, 2013, 11:41 PM UTC

seiji wrote: post #38

jetz wrote: post #33

Earlier quoted context omitted.

If you're familiar with thumbnail display you know Facebook has Haystack for efficient image serving. It goes very low end. Sparkey or CDB or BAM (mentioned in this post) could be much less complex and can do similar work. Why did they go Haystack route I dont get it.

Are you asking why they didn't use Haystack? Haystack isn't released publicly as far as I can tell (plus, just because another company writes something doesn't mean it's actually good).

Sorry not being clear enough. Yes I was kind of asking why they didnt try simpler options. When you look at their paper on Haystack you see that it's essentially a constant local database.