On Wed, Feb 24, 2010 at 6:01 PM, Kim Minh Kaplan
<address@hidden> wrote:
Jeff Johnson:
> BTW, can someone describe -- even superficially -- what is
> being attempted with the PTree store? Any details are welcomed,
> I'm not yet able to read OCAML code well enough to recognize
> what type of store is being attempted.
The use of the prefix tree is described in the two articles Set
Reconciliation with Nearly Optimal Communication Complexity and
Practical Set Reconciliation. You will find them on the Google code
page¹. The mathematics are quite involved though. It is the
information that is needed for two servers to know what keys they need
to exchange.
Indeed. The data structure is called a prefix-tree in the paper (hence PTree). Basically, it's a binary tree that holds a special kind of checksum for different subsets of the keyspace, dividing the space of keys up as you go down the tree.
> The PTree deadlock is easily reproduced, and (with db_stat) a
> detailed deadlock diagnosis could be attempted.
How would that be?
> Is there interest in adding DB_INIT_LOCK to the PTree store?
While I do not see any practical interest in doing this, the symptom
smells like a bug hanging in there that could very well be related to
the problem Arnold experienced recently. There would definitely be
interest in correcting it.
¹ http://code.google.com/p/sks-keyserver/
--
Kim Minh