[ZODB-Dev] design issue: job queue is concurrency bottleneck

[Tim Peters]

John, how many things do you expect to store in one of your job queues?  If
it's only a few hundred (or less), you can use a Bucket instead of a BTree.
A single Bucket won't suffer a write conflict unless multiple transactions
try to delete, or add, or change the value associated with, the same key.

Lookup is log-time either way.  Insertion and deletion in a Bucket can take
time proportional to the number of entries, but the constant factor is very
small (these are basically just calls to C's memmove()).

> ...
> From what I can tell, the BTree conflict resolution cannot handle
> certain cases of adding new keys.

I spelled that all out last week:  any case involving a bucket split or
bucket removal cannot be resolved.  OO trees suffer the most bucket splits,
and II trees the least (that's one reason Zope favors II trees whenever
possible); OI and IO are in the middle.  None of that's obvious  -- it
follows from that the different flavors of tree have different maximum
leaf-node bucket sizes, which is in turn a heuristic attempt to keep pickle
sizes "not too big" and "not too small".  A Bucket is a fine thing to use if
you don't expect large collections.