reverse link from bucket to keys

reverse link from bucket to keys

[sheng qiu]

Hi,

i have some question about bcache codes. by first looking, seems we
cannot know which keys are being stored in a specified bucket by
giving the bucket information.

is that true?

Thanks,
Sheng


--
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[Kent Overstreet]

On Sun, Jul 7, 2013 at 7:47 AM, sheng qiu <herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> Hi,
>
> i have some question about bcache codes. by first looking, seems we
> cannot know which keys are being stored in a specified bucket by
> giving the bucket information.
>
> is that true?

Yep, that's true

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

Thanks a lot for your reply.

Then i have a question about the bucket invalidation. when bcache
choose to replace a bucket, will the keys that reside on that bucket
still be in the btree? since you do not have information about which
keys reside on the bucket, how do you update the btree?

i can think out two ways, one is you periodically scan the btree nodes
and delete the stale nodes, the other way is when you get a cache hit
on stale nodes, then you delete it at that moment. How bcache does
this? Can you tell me the functions involve for these operations? i am
interested in this part of codes.

Thanks,
Sheng

On Sun, Jul 7, 2013 at 12:24 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
> On Sun, Jul 7, 2013 at 7:47 AM, sheng qiu <herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>> Hi,
>>
>> i have some question about bcache codes. by first looking, seems we
>> cannot know which keys are being stored in a specified bucket by
>> giving the bucket information.
>>
>> is that true?
>
> Yep, that's true



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[Kent Overstreet]

On Mon, Jul 08, 2013 at 09:44:41AM -0400, sheng qiu wrote:
> Hi Kent,
> 
> Thanks a lot for your reply.
> 
> Then i have a question about the bucket invalidation. when bcache
> choose to replace a bucket, will the keys that reside on that bucket
> still be in the btree? since you do not have information about which
> keys reside on the bucket, how do you update the btree?
> 
> i can think out two ways, one is you periodically scan the btree nodes
> and delete the stale nodes, the other way is when you get a cache hit
> on stale nodes, then you delete it at that moment. How bcache does
> this? Can you tell me the functions involve for these operations? i am
> interested in this part of codes.

This is documented in the code - start here:
http://evilpiepirate.org/git/linux-bcache.git/tree/drivers/md/bcache/bcache.h?h=bcache-dev

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

thanks for reply. i read the document in the code. just to make sure i
understand correctly, the stale key nodes are produced by invalidation
(replacement) of the buckets they reside on, right?
in another word, the stale key nodes might be the recently evict out data?

Thanks,
Sheng

On Mon, Jul 8, 2013 at 5:48 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
> On Mon, Jul 08, 2013 at 09:44:41AM -0400, sheng qiu wrote:
>> Hi Kent,
>>
>> Thanks a lot for your reply.
>>
>> Then i have a question about the bucket invalidation. when bcache
>> choose to replace a bucket, will the keys that reside on that bucket
>> still be in the btree? since you do not have information about which
>> keys reside on the bucket, how do you update the btree?
>>
>> i can think out two ways, one is you periodically scan the btree nodes
>> and delete the stale nodes, the other way is when you get a cache hit
>> on stale nodes, then you delete it at that moment. How bcache does
>> this? Can you tell me the functions involve for these operations? i am
>> interested in this part of codes.
>
> This is documented in the code - start here:
> http://evilpiepirate.org/git/linux-bcache.git/tree/drivers/md/bcache/bcache.h?h=bcache-dev



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

just a quick question about the bkey fields. The "high" member seems
to have some bits not used right now. from bits 37 to bits 54 seems to
be unused, right?
The reason i was asking is that i want to keep some additional
information in the bkeys,  if these bits are not used i might reuse
them without incur more storage.

Thanks,
Sheng

On Tue, Jul 9, 2013 at 11:24 AM, sheng qiu <herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> Hi Kent,
>
> thanks for reply. i read the document in the code. just to make sure i
> understand correctly, the stale key nodes are produced by invalidation
> (replacement) of the buckets they reside on, right?
> in another word, the stale key nodes might be the recently evict out data?
>
> Thanks,
> Sheng
>
> On Mon, Jul 8, 2013 at 5:48 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
>> On Mon, Jul 08, 2013 at 09:44:41AM -0400, sheng qiu wrote:
>>> Hi Kent,
>>>
>>> Thanks a lot for your reply.
>>>
>>> Then i have a question about the bucket invalidation. when bcache
>>> choose to replace a bucket, will the keys that reside on that bucket
>>> still be in the btree? since you do not have information about which
>>> keys reside on the bucket, how do you update the btree?
>>>
>>> i can think out two ways, one is you periodically scan the btree nodes
>>> and delete the stale nodes, the other way is when you get a cache hit
>>> on stale nodes, then you delete it at that moment. How bcache does
>>> this? Can you tell me the functions involve for these operations? i am
>>> interested in this part of codes.
>>
>> This is documented in the code - start here:
>> http://evilpiepirate.org/git/linux-bcache.git/tree/drivers/md/bcache/bcache.h?h=bcache-dev
>
>
>
> --
> Sheng Qiu
> Texas A & M University
> Room 332B Wisenbaker
> email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
> College Station, TX 77843-3259



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

i am sorry to bother you again. i am reading the movinggc.c, i am
really interested in this piece of codes. So if i enable the copy_gc,
this piece of codes will be active. My question is after the gc_moving
confirmed the gc_moving_threshold, it began to scan the bkeys. i do
not quite understand how you fill the moving_gc_keys, do you go
through all the current btree nodes to find proper keys for migration
(the bucket.used_sectors < threshold)? or you do incremental scans?

i will be appreciated if you can explain some more about it.

Thanks,
Sheng

On Wed, Jul 10, 2013 at 11:22 AM, sheng qiu <herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> Hi Kent,
>
> just a quick question about the bkey fields. The "high" member seems
> to have some bits not used right now. from bits 37 to bits 54 seems to
> be unused, right?
> The reason i was asking is that i want to keep some additional
> information in the bkeys,  if these bits are not used i might reuse
> them without incur more storage.
>
> Thanks,
> Sheng
>
> On Tue, Jul 9, 2013 at 11:24 AM, sheng qiu <herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>> Hi Kent,
>>
>> thanks for reply. i read the document in the code. just to make sure i
>> understand correctly, the stale key nodes are produced by invalidation
>> (replacement) of the buckets they reside on, right?
>> in another word, the stale key nodes might be the recently evict out data?
>>
>> Thanks,
>> Sheng
>>
>> On Mon, Jul 8, 2013 at 5:48 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
>>> On Mon, Jul 08, 2013 at 09:44:41AM -0400, sheng qiu wrote:
>>>> Hi Kent,
>>>>
>>>> Thanks a lot for your reply.
>>>>
>>>> Then i have a question about the bucket invalidation. when bcache
>>>> choose to replace a bucket, will the keys that reside on that bucket
>>>> still be in the btree? since you do not have information about which
>>>> keys reside on the bucket, how do you update the btree?
>>>>
>>>> i can think out two ways, one is you periodically scan the btree nodes
>>>> and delete the stale nodes, the other way is when you get a cache hit
>>>> on stale nodes, then you delete it at that moment. How bcache does
>>>> this? Can you tell me the functions involve for these operations? i am
>>>> interested in this part of codes.
>>>
>>> This is documented in the code - start here:
>>> http://evilpiepirate.org/git/linux-bcache.git/tree/drivers/md/bcache/bcache.h?h=bcache-dev
>>
>>
>>
>> --
>> Sheng Qiu
>> Texas A & M University
>> Room 332B Wisenbaker
>> email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
>> College Station, TX 77843-3259
>
>
>
> --
> Sheng Qiu
> Texas A & M University
> Room 332B Wisenbaker
> email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
> College Station, TX 77843-3259



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[Kent Overstreet]

On Wed, Jul 10, 2013 at 11:22:22AM -0400, sheng qiu wrote:
> Hi Kent,
> 
> just a quick question about the bkey fields. The "high" member seems
> to have some bits not used right now. from bits 37 to bits 54 seems to
> be unused, right?
> The reason i was asking is that i want to keep some additional
> information in the bkeys,  if these bits are not used i might reuse
> them without incur more storage.

Correct, they're unused.

Re: reverse link from bucket to keys

[Kent Overstreet]

On Wed, Jul 10, 2013 at 05:14:49PM -0400, sheng qiu wrote:
> Hi Kent,
> 
> i am sorry to bother you again. i am reading the movinggc.c, i am
> really interested in this piece of codes. So if i enable the copy_gc,
> this piece of codes will be active. My question is after the gc_moving
> confirmed the gc_moving_threshold, it began to scan the bkeys. i do
> not quite understand how you fill the moving_gc_keys, do you go
> through all the current btree nodes to find proper keys for migration
> (the bucket.used_sectors < threshold)? or you do incremental scans?

Incremental scans - the keybuf code scans the btree until it has some
arbitrary number of keys in a red black tree; the copy gc code pulls
keys out of that one at a time to move them and the keybuf code refills
itself by scanning incrementally as needed.

Re: reverse link from bucket to keys

[sheng qiu]

i see. Thanks a lot for your explain. i have some further questions
below, i will be appreciated if you have time to answer.

by "arbitrary number", can i understand it as the user can decide how
many keys in the keybuf or something else?
when the keybuf code try to refill itself, it continues scan following
"last_scan" or it start over from the beginning? if try to scan all
the existing keys per round, will it be very costly?

Thanks,
Sheng




On Wed, Jul 10, 2013 at 7:02 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
> On Wed, Jul 10, 2013 at 05:14:49PM -0400, sheng qiu wrote:
>> Hi Kent,
>>
>> i am sorry to bother you again. i am reading the movinggc.c, i am
>> really interested in this piece of codes. So if i enable the copy_gc,
>> this piece of codes will be active. My question is after the gc_moving
>> confirmed the gc_moving_threshold, it began to scan the bkeys. i do
>> not quite understand how you fill the moving_gc_keys, do you go
>> through all the current btree nodes to find proper keys for migration
>> (the bucket.used_sectors < threshold)? or you do incremental scans?
>
> Incremental scans - the keybuf code scans the btree until it has some
> arbitrary number of keys in a red black tree; the copy gc code pulls
> keys out of that one at a time to move them and the keybuf code refills
> itself by scanning incrementally as needed.



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

i do not know if this is a problem or i did not understand correctly.
when i enable the copy_gc, at first the gc_moving_threshold is larger
than the bucket size (512KB), i guess maybe initially they are set to
1<<14 -1, after some time, seems all the bucket are set to use all the
sectors it own, which is 1024 in my case. I guess this is because
SET_GC_SECTORS_USED(bucket.size) is called while returning a free
bucket for new allocation.  then the gc_moving_threshold became 1024
(512KB), and no bucket's GC_SECTORS_USED is smaller than this value.
So no gc_moving event at all.

at first, i thought the bcache code would set 0 sectors used for each
new allocated bucket, and then update GC_SECTORS_USED whenever fill
data into the bucket. In that way, we can track how many data are
valid within a bucket.

Do i misunderstanding anything? i am a little confused.

Thanks,
Sheng

On Wed, Jul 10, 2013 at 10:16 PM, sheng qiu <herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> i see. Thanks a lot for your explain. i have some further questions
> below, i will be appreciated if you have time to answer.
>
> by "arbitrary number", can i understand it as the user can decide how
> many keys in the keybuf or something else?
> when the keybuf code try to refill itself, it continues scan following
> "last_scan" or it start over from the beginning? if try to scan all
> the existing keys per round, will it be very costly?
>
> Thanks,
> Sheng
>
>
>
>
> On Wed, Jul 10, 2013 at 7:02 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
>> On Wed, Jul 10, 2013 at 05:14:49PM -0400, sheng qiu wrote:
>>> Hi Kent,
>>>
>>> i am sorry to bother you again. i am reading the movinggc.c, i am
>>> really interested in this piece of codes. So if i enable the copy_gc,
>>> this piece of codes will be active. My question is after the gc_moving
>>> confirmed the gc_moving_threshold, it began to scan the bkeys. i do
>>> not quite understand how you fill the moving_gc_keys, do you go
>>> through all the current btree nodes to find proper keys for migration
>>> (the bucket.used_sectors < threshold)? or you do incremental scans?
>>
>> Incremental scans - the keybuf code scans the btree until it has some
>> arbitrary number of keys in a red black tree; the copy gc code pulls
>> keys out of that one at a time to move them and the keybuf code refills
>> itself by scanning incrementally as needed.
>
>
>
> --
> Sheng Qiu
> Texas A & M University
> Room 332B Wisenbaker
> email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
> College Station, TX 77843-3259



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

i think i get a little clear about your codes. so initially each newly
allocated buckets are SET_GC_SECTORS_USED(bucket.size), then during
the btree gc, you update the bucket by accumulate the still valid key
data. So if the bucket has more valid data left, it should be
accumulated more for each round at the btree gc. I think this is fine.
But at the movinggc code, when you calculate how many sectors to move
for each bucket, you directly add the current GC_SECTORS_USED(bucket),
which is actually the accumulated value (relative value), not the
actual valid size of data within the bucket. Is this correct? I guess
that's why i ended up with the threshold equal to newly allocated
bucket size.

If i misunderstanding anything, please correct me.

Thanks,
Sheng

On Thu, Jul 11, 2013 at 9:45 AM, sheng qiu <herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> Hi Kent,
>
> i do not know if this is a problem or i did not understand correctly.
> when i enable the copy_gc, at first the gc_moving_threshold is larger
> than the bucket size (512KB), i guess maybe initially they are set to
> 1<<14 -1, after some time, seems all the bucket are set to use all the
> sectors it own, which is 1024 in my case. I guess this is because
> SET_GC_SECTORS_USED(bucket.size) is called while returning a free
> bucket for new allocation.  then the gc_moving_threshold became 1024
> (512KB), and no bucket's GC_SECTORS_USED is smaller than this value.
> So no gc_moving event at all.
>
> at first, i thought the bcache code would set 0 sectors used for each
> new allocated bucket, and then update GC_SECTORS_USED whenever fill
> data into the bucket. In that way, we can track how many data are
> valid within a bucket.
>
> Do i misunderstanding anything? i am a little confused.
>
> Thanks,
> Sheng
>
> On Wed, Jul 10, 2013 at 10:16 PM, sheng qiu <herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>> i see. Thanks a lot for your explain. i have some further questions
>> below, i will be appreciated if you have time to answer.
>>
>> by "arbitrary number", can i understand it as the user can decide how
>> many keys in the keybuf or something else?
>> when the keybuf code try to refill itself, it continues scan following
>> "last_scan" or it start over from the beginning? if try to scan all
>> the existing keys per round, will it be very costly?
>>
>> Thanks,
>> Sheng
>>
>>
>>
>>
>> On Wed, Jul 10, 2013 at 7:02 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
>>> On Wed, Jul 10, 2013 at 05:14:49PM -0400, sheng qiu wrote:
>>>> Hi Kent,
>>>>
>>>> i am sorry to bother you again. i am reading the movinggc.c, i am
>>>> really interested in this piece of codes. So if i enable the copy_gc,
>>>> this piece of codes will be active. My question is after the gc_moving
>>>> confirmed the gc_moving_threshold, it began to scan the bkeys. i do
>>>> not quite understand how you fill the moving_gc_keys, do you go
>>>> through all the current btree nodes to find proper keys for migration
>>>> (the bucket.used_sectors < threshold)? or you do incremental scans?
>>>
>>> Incremental scans - the keybuf code scans the btree until it has some
>>> arbitrary number of keys in a red black tree; the copy gc code pulls
>>> keys out of that one at a time to move them and the keybuf code refills
>>> itself by scanning incrementally as needed.
>>
>>
>>
>> --
>> Sheng Qiu
>> Texas A & M University
>> Room 332B Wisenbaker
>> email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
>> College Station, TX 77843-3259
>
>
>
> --
> Sheng Qiu
> Texas A & M University
> Room 332B Wisenbaker
> email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
> College Station, TX 77843-3259



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[Kent Overstreet]

On Thu, Jul 11, 2013 at 09:45:25AM -0400, sheng qiu wrote:
> Hi Kent,
> 
> i do not know if this is a problem or i did not understand correctly.
> when i enable the copy_gc, at first the gc_moving_threshold is larger
> than the bucket size (512KB),

I haven't looked at the copy gc code in ages, but if I remember the
algorithm I used - the threshold is set based on how many buckets we
want to free up, so if most of the buckets are reclaimable threshold >
bucket size is what I'd expect.

> i guess maybe initially they are set to
> 1<<14 -1, after some time, seems all the bucket are set to use all the
> sectors it own, which is 1024 in my case. I guess this is because
> SET_GC_SECTORS_USED(bucket.size) is called while returning a free
> bucket for new allocation.  then the gc_moving_threshold became 1024
> (512KB), and no bucket's GC_SECTORS_USED is smaller than this value.
> So no gc_moving event at all.
> at first, i thought the bcache code would set 0 sectors used for each
> new allocated bucket, and then update GC_SECTORS_USED whenever fill
> data into the bucket. In that way, we can track how many data are
> valid within a bucket.

When we allocate a bucket we generally fill it up right away - we don't
make it available for GC (the ->pin refcount) until after we're finished
writing to it, at which point GC_SECTORS_USED is going to = bucket_size.

So that's why the alloc code just sets GC_SECTORS_USED(b,
ca->sb.bucket_size) when you allocate it.

But then over time, as new writes come in - when those writes are
overwriting data that's already in the cache, now GC will notice those
buckets aren't full of (live) data anymore.

Re: reverse link from bucket to keys

[Kent Overstreet]

On Thu, Jul 11, 2013 at 11:02:01AM -0400, sheng qiu wrote:
> Hi Kent,
> 
> i think i get a little clear about your codes. so initially each newly
> allocated buckets are SET_GC_SECTORS_USED(bucket.size), then during
> the btree gc, you update the bucket by accumulate the still valid key
> data. So if the bucket has more valid data left, it should be
> accumulated more for each round at the btree gc. I think this is fine.
> But at the movinggc code, when you calculate how many sectors to move
> for each bucket, you directly add the current GC_SECTORS_USED(bucket),
> which is actually the accumulated value (relative value), not the
> actual valid size of data within the bucket. Is this correct? I guess
> that's why i ended up with the threshold equal to newly allocated
> bucket size.

That "sectors_to_move" we're calculating isn't for any one bucket, it's
how many _total_ sectors we're going to move this iteration.

The reason is we've got a fixed size reserve of buckets that can be
allocated for moving gc - we may not be able to allocate more than that.

But when we start copying data out of buckets, we always want to copy
out of the buckets that had the least amount of live data in them. So we
take our heap of buckets with the smallest GC_SECTORS_USED(), and pop
buckets off the top until sectors_to_move is under our reserve - that
is, until we've got few enough buckets that we know we'll be able to
move all the data in them.

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

thanks for the explain above. my concern is that the GC_SECTORS_USED
does not get you the correct valid data size within each bucket. for
example, the GC_SECTORS_USED might return you larger than the bucket
size, while when you go to match the reserved_sectors, you might get
wrong.  i do not know if you get my meaning. A simple way is run some
test while enable the GC code, you will see how it work actually. If
it's my misunderstanding, i am glad to hear from you later.

Thanks,
Sheng

On Thu, Jul 11, 2013 at 10:10 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
> On Thu, Jul 11, 2013 at 11:02:01AM -0400, sheng qiu wrote:
>> Hi Kent,
>>
>> i think i get a little clear about your codes. so initially each newly
>> allocated buckets are SET_GC_SECTORS_USED(bucket.size), then during
>> the btree gc, you update the bucket by accumulate the still valid key
>> data. So if the bucket has more valid data left, it should be
>> accumulated more for each round at the btree gc. I think this is fine.
>> But at the movinggc code, when you calculate how many sectors to move
>> for each bucket, you directly add the current GC_SECTORS_USED(bucket),
>> which is actually the accumulated value (relative value), not the
>> actual valid size of data within the bucket. Is this correct? I guess
>> that's why i ended up with the threshold equal to newly allocated
>> bucket size.
>
> That "sectors_to_move" we're calculating isn't for any one bucket, it's
> how many _total_ sectors we're going to move this iteration.
>
> The reason is we've got a fixed size reserve of buckets that can be
> allocated for moving gc - we may not be able to allocate more than that.
>
> But when we start copying data out of buckets, we always want to copy
> out of the buckets that had the least amount of live data in them. So we
> take our heap of buckets with the smallest GC_SECTORS_USED(), and pop
> buckets off the top until sectors_to_move is under our reserve - that
> is, until we've got few enough buckets that we know we'll be able to
> move all the data in them.



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[Kent Overstreet]

On Thu, Jul 11, 2013 at 10:22:02PM -0400, sheng qiu wrote:
> Hi Kent,
> 
> thanks for the explain above. my concern is that the GC_SECTORS_USED
> does not get you the correct valid data size within each bucket. for
> example, the GC_SECTORS_USED might return you larger than the bucket
> size, while when you go to match the reserved_sectors, you might get
> wrong.  i do not know if you get my meaning. A simple way is run some
> test while enable the GC code, you will see how it work actually. If
> it's my misunderstanding, i am glad to hear from you later.

I'm not sure I follow - if GC_SECTORS_USED was > bucket size that'd
probably be a bug, but I don't see how that could happen - could you
explain?

Re: reverse link from bucket to keys

[sheng qiu]

sure, in your btree.c code, when you do btree gc, you update the
bucket's used sectors by min(unsigned, GC_SECTORS_USED(b)+key_size(),
1<<14-1). this might get you larger than the bucket size. since the
newly allocated bucket is set to bucket size already. so each round
you will accumulate the key_size(). i print the information at that
point, and see GC_SECTORS_USED > bucket size.

Thanks,
Sheng

On Thu, Jul 11, 2013 at 10:25 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
> On Thu, Jul 11, 2013 at 10:22:02PM -0400, sheng qiu wrote:
>> Hi Kent,
>>
>> thanks for the explain above. my concern is that the GC_SECTORS_USED
>> does not get you the correct valid data size within each bucket. for
>> example, the GC_SECTORS_USED might return you larger than the bucket
>> size, while when you go to match the reserved_sectors, you might get
>> wrong.  i do not know if you get my meaning. A simple way is run some
>> test while enable the GC code, you will see how it work actually. If
>> it's my misunderstanding, i am glad to hear from you later.
>
> I'm not sure I follow - if GC_SECTORS_USED was > bucket size that'd
> probably be a bug, but I don't see how that could happen - could you
> explain?



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[Kent Overstreet]

On Thu, Jul 11, 2013 at 10:29:23PM -0400, sheng qiu wrote:
> sure, in your btree.c code, when you do btree gc, you update the
> bucket's used sectors by min(unsigned, GC_SECTORS_USED(b)+key_size(),
> 1<<14-1). this might get you larger than the bucket size. since the
> newly allocated bucket is set to bucket size already. so each round
> you will accumulate the key_size(). i print the information at that
> point, and see GC_SECTORS_USED > bucket size.

Hey, I think you're right - btree_gc_start() is supposed to be zeroing
out GC_SECTORS_USED() (the same place it does SET_GC_MARK(b,
GC_MARK_RECLAIMABLE)) - but that's missing. Thanks!

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

sorry to bother you again. i got another question. it's about the
bucket->pin. Can you explain what's the usage for this data member?
i see only bucket with pin value "0" can be invalidated. And only "0"
valued pin bucket's prio will be decreased within the
bch_rescale_priorities(). But every time when you write data to
bucket, you increase that bucket's pin, and i did not see when it will
be decreased. This makes me a little confused. Or do i miss anything
where you might reset it?

i am appreciated for your help.

Thanks,
Sheng

On Thu, Jul 11, 2013 at 10:41 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
> On Thu, Jul 11, 2013 at 10:29:23PM -0400, sheng qiu wrote:
>> sure, in your btree.c code, when you do btree gc, you update the
>> bucket's used sectors by min(unsigned, GC_SECTORS_USED(b)+key_size(),
>> 1<<14-1). this might get you larger than the bucket size. since the
>> newly allocated bucket is set to bucket size already. so each round
>> you will accumulate the key_size(). i print the information at that
>> point, and see GC_SECTORS_USED > bucket size.
>
> Hey, I think you're right - btree_gc_start() is supposed to be zeroing
> out GC_SECTORS_USED() (the same place it does SET_GC_MARK(b,
> GC_MARK_RECLAIMABLE)) - but that's missing. Thanks!



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[Kent Overstreet]

On Tue, Jul 16, 2013 at 11:14:29AM -0400, sheng qiu wrote:
> Hi Kent,
> 
> sorry to bother you again. i got another question. it's about the
> bucket->pin. Can you explain what's the usage for this data member?
> i see only bucket with pin value "0" can be invalidated. And only "0"
> valued pin bucket's prio will be decreased within the
> bch_rescale_priorities(). But every time when you write data to
> bucket, you increase that bucket's pin, and i did not see when it will
> be decreased. This makes me a little confused. Or do i miss anything
> where you might reset it?

It's to keep buckets from being garbage collected after they're
allocated but before we've added a pointer to them to the btree.

I've actually been meaning to get rid of it, and just keep a refcount on
the open buckets (the ones pick_data_bucket() uses) and have garbage
collection mark those buckets too.

Originally I also used it for preventing buckets from being invalidated
while we were reading from them (on cache hit), but I got rid of that
ages ago for performance reasons - now it just checks after the read
finishes if it was invalidated, and if so rereads from the backing
device.

Re: reverse link from bucket to keys

[sheng qiu]

Hi Kent,

Thanks for you previous reply. I know bcache does not care write hit,
but is there a easy way to check write hit for write request?
If i reuse the search_recurse() as what you do for read request, will
it has any impact?

Thanks,
Sheng

On Tue, Jul 16, 2013 at 4:59 PM, Kent Overstreet <kmo-PEzghdH756F8UrSeD/g0lQ@public.gmane.org> wrote:
> On Tue, Jul 16, 2013 at 11:14:29AM -0400, sheng qiu wrote:
>> Hi Kent,
>>
>> sorry to bother you again. i got another question. it's about the
>> bucket->pin. Can you explain what's the usage for this data member?
>> i see only bucket with pin value "0" can be invalidated. And only "0"
>> valued pin bucket's prio will be decreased within the
>> bch_rescale_priorities(). But every time when you write data to
>> bucket, you increase that bucket's pin, and i did not see when it will
>> be decreased. This makes me a little confused. Or do i miss anything
>> where you might reset it?
>
> It's to keep buckets from being garbage collected after they're
> allocated but before we've added a pointer to them to the btree.
>
> I've actually been meaning to get rid of it, and just keep a refcount on
> the open buckets (the ones pick_data_bucket() uses) and have garbage
> collection mark those buckets too.
>
> Originally I also used it for preventing buckets from being invalidated
> while we were reading from them (on cache hit), but I got rid of that
> ages ago for performance reasons - now it just checks after the read
> finishes if it was invalidated, and if so rereads from the backing
> device.



-- 
Sheng Qiu
Texas A & M University
Room 332B Wisenbaker
email: herbert1984106-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org
College Station, TX 77843-3259

Re: reverse link from bucket to keys

[Kent Overstreet]

On Wed, Jul 17, 2013 at 06:28:40PM -0400, sheng qiu wrote:
> Hi Kent,
> 
> Thanks for you previous reply. I know bcache does not care write hit,
> but is there a easy way to check write hit for write request?
> If i reuse the search_recurse() as what you do for read request, will
> it has any impact?

Well, the question would be where you would track it - for read hits,
we're tracking by bucket on the cache device, not by lba on the backing
device.

But since writes are always COW - they're always going to a new bucket -
tracking write hits by bucket wouldn't really make sense.

What are you trying to do?