[sheepdog] [PATCH v4 3/3] sheep: look up whole range of bitmap

[Liu Yuan]

On Sun, Mar 08, 2015 at 01:08:35PM +0900, Hitoshi Mitake wrote:
> Older sheepdog didn't have a functionality of recycling VID, so the
> get_vdi_bitmap_range() can detect correct range of bitmap. But newer
> sheepdog recycles VID. It can produce situations like below:

Which commit introduces the recycling VID? I think our current vid id allocation
algorithm is heavily rely on the assumption that "no recycling". Otherwise, a
redesign of the algorithm should be considered.

> The first state of VID bitmap:
> 0 0 1* 1* 1 0 0 0
> 1 is a VID bit of working VDI, 1* is a bit of snapshot. Assume the
> above 1 and 1* are used for VDI named "A" and its snapshots.
> 
> Then, a user tries to create VDI "B". sd_hash_vdi() returns VID which
> conflicts with existing bits for A.
> 0 0 1* 1* 1 0 0 0
>        ^
>        |
>        sd_hash_vdi() returns VID which conflicts with the
>        above bit.
> 
> So B acquires the left most free bit
> 0 0 1* 1* 1 1 0 0
>             ^
>             |
>             B acquires this bit.
> 
> Then, the user deletes A and its snapshots. All of the family members
> are deleted. The bitmap becomes like below
> 0 0 0 0 0 1 0 0
>       ^
>       |
>       B's original VID sd_hash_vdi() calculates.
> 
> Now sheep fails to lookup VID of B, because the VID calculated by
> sd_hash_vdi() is zero.
> 
> This is the reason of the looking up whole range of bitmap. Of course
> it is ugly and costly. But its cost is equal or less than "dog vdi
> list"'s one.

I think this is too costly, meaning the more vdi you created, the more time
will be used to create one vdi. After we have more than half the bitmap is set,
every create of new vdi will take a long time to finish because we have to read
all the existing inode and check the name. It is unacceptable and will be a big
scaling problem in this manner. I guess this will not only affect vdi create but
also other functions, to name a few, snapshoting, cloning, which we advertise to
do it in lighting fast time.

thanks,
Yuan