[concurrency-interest] implementing a DB write-behind algorithm

Jonathan P Lawrence jlawrence at uk.ibm.com
Mon May 8 12:09:12 EDT 2006


This response partly overlaps with some of last week's (notably those
discussing hijacking & CAS algorithms).
I've come across a *very* similar problem before, in connection with
batching log writes from multiple threads, using twin bounded size buffers
to hold the records prior to flushing them to a backing store.

The main design parameters were:
- multiple concurrent client threads writing records.
- twin bounded size buffers to hold records prior to flushing to the
backing store.
- a single asynchronous backend process to flush the filled buffers.

- Employs a controlling monitor component to manage interactions between
threads and the system. This involves hijacking, but only to trigger rather
than perform the backend writes.
- Buffers may be written to concurrently but exclusive access is required
to flush.  This ensures that the records have been fully written before the
buffers are flushed.
- Prevents overtaking (i.e. all records written by a thread appear in the
correct order in the backing store).
- Has been modelled in a formal process algebra and verified using an
automated model-checking tool.

Java implementation.

There is an existing Java implementation of the design which is really a
model of the intended target implementation on another platform, which
would have used low-level primitives such as CAS directly.
The implementation pre-dates JSR 166 and so it uses wait-notify and
synchronization (with highly granular scope) to manage concurrency, however
it could be easily adapted to use the new features such as concurrent
queues & atomic variables instead.

Optional extensions.
The following features could readily be added to the basic design:
- Thread may force record(s) it has written (i.e. request and block until
the record has been committed to the backing store).
- Such requests may be suspended (with timeout) to allow further records to
be added to a partially filled buffer.

If you are interested I could give more details here or offline.


Jonathan Lawrence
Java Technology Centre
IBM United Kingdom Ltd., Hursley Park, Winchester,  SO21 2JN.
Tel: +44 (0)1962 816197  Internal: 246197  Mobex: 272322
jlawrence at uk.ibm.com

More information about the Concurrency-interest mailing list