Re: Adding compression support for bluestore.

[Igor Fedotov <ifedotov@mirantis.com>]

On 21.03.2016 18:14, Allen Samuels wrote:
>>
>> That's an interesting proposal but I can see following caveats here (I beg
>> pardon I  misunderstood something):
>> 1) Potentially uncontrolled extent map growth when extensive (over)writing
>> takes place.
> Yes, a naïve insertion policy could lead to uncontrolled growth, but I don't think this needs to be the case. I assume that when you add an "extent", you won't increase the size of the array unnecessarily, i.e., if the new extent doesn't overlap an existing extent then there's no reason to increase the size of the map array -- actually you want to insert the new extent at the <smallest> array index that doesn't overlap, only increasing the array size when that's not possible. I'm not 100% certain of the worst case, but I believe that it's limited to the ratio between the largest extent and the smallest extent. (i.e., if we assume writes are no larger than -- say -- 1MB and the smallest are 4K, then I think the max depth of the array is 1M/4K => 2^8, 256. Which is ugly but not awful -- since this is probably a contrived case. This might be a reason to limit the largest extent size to something a bit smaller (say 256K)...
It looks like I misunderstood something... It seemed to me that your 
array grows depending on the maximum amount of block versions.
Imagine you have 1000 writes 0~4K and 1000 writes 8K~4K
I supposed that this will create following array:
[
0: <0:{...,4K}, 8K:{...4K}>,
...
999: <0:{...,4K}, 8K:{...4K}>,
]

what's happening in your case?

>> 2) Read/Lookup algorithmic complexity. To find valid block (or detect
>> overwrite) one should sequentially enumerate the full array. Given 1) that
>> might be very ineffective.
> Only requires one log2 lookup for each index of the array.
This depends on 1) thus still unclear at the moment.
>> 3) It's not dealing with unaligned overwrites. What happens when some
>> block is partially overwritten?
> I'm not sure I understand what cases you're referring to. Can you give an example?
>
Well, as far as I understand in the proposal above you were operating 
the entire blocks (i.e. 4K data)
Thus overwriting the block is a simple case - you just need to create a 
new block "version" and insert it into an array.
But real user writes seems to be unaligned to block size.
E.g.
write 0~2048
write 1024~3072

you have to either track both blocks or merge them. The latter is a bit 
tricky for the compression case.




--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html