Bitcask Key Listing

Kelly McLaughlin kelly at basho.com
Wed Aug 20 11:06:36 EDT 2014


Jason,

For key listing requests the bitcask in-memory key directory is scanned 
for each vnode participating in the covering set. The data structure is 
a hash table
which is ideal for direct accesses, but there is no way to guarantee 
ordering when the entires are hashed into the table so bitcask iterates 
over the all the
entries in the table and the keys matching the query are returned.

Then for on-disk data retrieval, each entry in the key directory 
contains information about how to locate the on-disk data for the key 
such as the cask file identifier
and the offset into the file where the entry resides. It sounds like you 
have already done some reading on bitcask, but in case you have not seen 
it before, this
bitcask intro document has some good illustrations of how things work: 
https://github.com/basho/bitcask/blob/develop/doc/bitcask-intro.pdf.

Hope that helps answer your questions.


Kelly

On 08/19/2014 04:51 PM, Jason Campbell wrote:
> 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