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

[Casey Duncan]

On Thu, 04 Mar 2004 00:04:36 -0500
John Belmonte <john at neggie.net> wrote:

> I finally got through the first round of concurrency testing on my
> app. 
>     Despite being a high-write application, virtually no write
>     conflicts 
> occur-- with one major exception.  I have a job queue, which is a
> BTree keyed by scheduled job time.  It's the only BTree in my app that
> doesn't have random keys.  Incoming requests to my server tend to
> generate a few jobs, and unfortunately they must be scheduled at
> various constant time periods in the future.  As a result,
> simultaneous requests generate jobs scheduled for approximately the
> same time, mapping to the same area of the BTree, and causing write
> conflicts.
> 
> Short of adding some random offset to scheduled job times, which I
> feel would not be very effective (depends on BTree size, etc.), does
> anyone have ideas for designing around this bottleneck?

Perhaps you could create a layered structure of BTrees to lessen the
chance of conflict. For example you could have a top-level btree whose
keys are "time slices" each once containing all of the jobs scheduled
during that slice. If the slices were fixed size then this could be an
IOBTree perhaps.

These timeslice keys could also be populated in blocks to try to limit
the number of concurrent add operations on this tree, but this might not
be necessary.

The values for each slice would be a btree of job key -> job. This would
make lookups slightly more expensive, but would at least eliminate
conflicts for jobs added concurrently to different timeslices.

Whether this would help depends on the clustering of the times jobs are
scheduled in your app. Also, you will need to try to find the "optimal"
timeslice width for your app. You could make it narrower in an attempt
to keep fewer jobs in each slice. 

-Casey