[Sheepdog] [PATCH v4 04/12] farm: add trunk object

[Liu Yuan]

On 12/29/2011 01:23 AM, Christoph Hellwig wrote:

> Is a hash really a good data structure here?  A tree would scale much
> better with the number of OIDs, which will be very different for
> different deployments.  For example the xfsprogs code has a nice btree
> library to borrow.


Umm, I had overlooked this comment.

IO requests will be processed in parallel in sheep, so if we use tree, I
think the lock contention is quite high.

Currently sheep(recover logic) has a hard limit for storage, that it can
support 2T objects at most. So 2T / ( 1024 * 4M) = 512, that at most
hash queue length will more or less be 512, so I think simple O(n)
search is acceptable. We could increase the HASH_BITS to get a shorter
queue length. In practice, most of the time, the queue length will not
be that long I think.

'btree' in your context is 'sel-balanced binary tree'? Yes, trees like
such as read-black tree will proved us O(log(n)) search, but we also
have to trade complexity. Yet, we need a global lock for the protection
of tree from parallel access.

That being said, let's start with simple & efficient hash lists, and
later if necessary, we can code more complex data structure.

Thanks,
Yuan