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 -- sheepdog mailing list [email protected] http://lists.wpkg.org/mailman/listinfo/sheepdog
