Bitcask Key Listing

Jason Campbell xiaclo at xiaclo.net
Tue Aug 19 18:51:29 EDT 2014


Hello Kelly,

Thanks for the detailed response, but I'm still a bit confused.  I understand the overhead over the covering set, and the key listing will only complete as fast as the slowest node.  The data transfer shouldn't be much for a small key set though.  So assuming we aren't doing something crazy like trying to stream billions of keys, it should be roughly the same speed as getting those keys from 1/3 of the nodes.

As far as bitcask being unordered, I'm not sure how that is possible.  I understand it's on-disk format is log structured, which although ordered by last-modified time, is fairly useless for most purposes.  But in-memory it has to be able to satisfy requests for a random key name in fairly fixed time to meet the latency guarantees that are expected of it.  I would expect it to be some kind of search tree, in which case, it could be used to filter partial ranges (like a bucket lookup) just as easily as a full key lookup.  It could also be a hash of the key, at which point it would be useless for partial ranges, but then so would the bitcask memory calculator, as it would be a fixed size per record, not variable with the length of the bucket and key.

I don't know Erlang well enough to jump into the bitcask source, and the papers I have found explain the keydir and data structures well enough, but not how a request is able to look up a key in memory.  Is it using a b-tree?

Thanks,
Jason

----- Original Message -----
From: "Kelly McLaughlin" <kelly at basho.com>
To: "Jason Campbell" <xiaclo at xiaclo.net>, "riak-users" <riak-users at lists.basho.com>
Sent: Wednesday, 20 August, 2014 1:26:36 AM
Subject: Re: Bitcask Key Listing

Jason,

There are two aspects to to a key listing operation that make it 
expensive relative to normal gets or puts.

The first part is that, due to the way data is distributed in Riak, key 
listing requires a covering set of vnodes to participate in
order to determine the list of keys for a bucket. A minimal covering set 
of vnodes works out to 1/N nodes in the cluster where N
is the n_val of the bucket. By default this is 3 so in the default case 
a key listing request must send a request to and receive
responses from 1/3 of the nodes in the cluster. This incurs network 
traversal overhead as the keys from each vnode are returned
and the speed to completion is limited by the slowest vnode in the 
covering set. This is true regardless of the backend in use.

The second part is specific to bitcask. Bitcask is an unordered backend 
and the consequence of this when doing a key listing is
that all of the keys stored by a vnode that participates in a key 
listing request must be scanned. It doesn't matter if there are
2 keys or 2000 keys for the bucket being queried, they all must be 
scanned. This is a case where all the keys being stored in memory
is beneficial to performance, but as the amount of data stored increases 
so does the expense to scan over it. The leveldb backend is
ordered and we are able to take advantage of that fact to only scan over 
data for the bucket in question, but for bitcask that is
not an option.

At this time there is nothing in the works to specifically improve key 
listing performance. It is certainly something we are aware of,
but at this time there are other things with higher priority.

Hope that helps answer your question.


Kelly


On 08/19/2014 05:17 AM, Jaston Campbell wrote:
> I currently maintain my own indexes for some things, and use natural keys where I can, but a question has been nagging me lately.
>
> Why is key listing slow?  Specifically, why is bitcask key listing slow?
>
> One of the biggest issues with bitcask is all keys (including the bucket name and some overhead) must fit into RAM.  For large amounts of keys, I understand the coordination data transfer will hurt, but shouldn't things like list buckets (or listing keys from small buckets) be fast?
>
> Is there a reason this is slow, and is there a plan to fix it?
>
> Thanks,
> Jason
>
> _______________________________________________
> riak-users mailing list
> riak-users at lists.basho.com
> http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com


_______________________________________________
riak-users mailing list
riak-users at lists.basho.com
http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com




More information about the riak-users mailing list