Idempotent ODBMS iterators

External Since: Feb 17, 2005 Posts: 3

I am building a client/server ODBMS in Java.

It occurred to me that one way of helping to guarantee the consistency of
the database was to ensure that all atomic requests were idempotent -- that
is, that if a particular request is performed more than once, it will leave
the database in the same (logical) state as it would if the operation had
been performed once only.

This occured to me when I discovered that, by chance or unconscious design,
almost all of the operations I had designed were idempotent.

For example, rather than an atomic "append" operation, which would not be
idempotent for obvious reasons, my implementation requires that the client
(in effect) perform the following three idempotent operations (while the
table is locked, of course) [pseudocode]:

size = table.size;
table.redim(size + 1);
table[size] = item;

Note that the following code would have the same effect:

size = table.size;
size = table.size;
table.redim(size + 1);
table.redim(size + 1);
table[size] = item;
table[size] = item;

(Of course one could provide an "append" operation to the client, but
execute it in the server as three idempotent operations like those above,
logging each one separately. The advantage in having idempotent *client*
operations is that the client, too, can use logging to allow resumption
after a catastrophic failure.)

Now, after a brief survey of my code, I discovered that just one operation
is not
idempotent: the "next method" for a map iterator. I'd like to rectify this.

A database map maintains an expandable array of keys ("key-array") in
insertion order. A map iterator, which is itself always stored as an object
in the database (while there is a reference to it), keeps an index into the
key-array. If a key is removed, its entry in the key-array is replaced with
null. If an entry is added, the key is appended to the key-array. An
iterator automatically skips over null entries; it fails graceully when the
end of the key-array is reached.

Since database access is generally asynchronous, a map's keys may change
while an iterator is running over it. (An iteration could, in principle, be
done incrementally by a client over days or weeks, without locking. So no
"ConcurrentModificationException" should be "thrown".) This produces
worst-case behaviour in which a key might be encountered more than once,
when it has been removed and then re-inserted. Clients are (supposed to be)
aware of this, and it is the best solution I can think of which does not
require a potentially expensive key-array copy operation to be made when an
iterator is created. (Most long-term client iterations are expected to be
maintenance tasks, each of whose steps should itself be idempotent, so a
repeated key shouldn't be a problem.)

Now, I could remove the iterator facility, and require clients to maintain
and increment their own key-array index (and check for null entries
explicitly). Trouble is, during concurrent server maintenance of the
database, I want to be able to compact the key-arrays of maps from time to
time, and to do so safely requires that all iterators currently "in use" by
clients are in the database (and recognizable as such) and can therefore
have their indices changed (atomically) when keys are moved during
compaction.

One possible solution is to have the "next method" return a brand new
iterator with an incremented index. Performing this operation twice on the
same original iterator would obviously produce two iterators both at the
same iteration point. But this is going to create a huge amount of garbage.

(Again, I could implement the "next method" in the server as a sequence of
locally idempotent operations, but I'd like client-side idempotency as well
if possible.)

Can anyone think of any other solution, which minimizes the work done by the
server both to create and to increment the iterator?

Cheers, Paul

External Since: Feb 03, 2005 Posts: 2

Paul Chapman wrote:

[...]

> Since database access is generally asynchronous, a map's keys may
> change while an iterator is running over it.

[...]

> Can anyone think of any other solution, which minimizes the work
> done by the server both to create and to increment the iterator?

Four possible approaches:

(1) Read-back-in-time isolation between clients. Every
transaction sees all objects in the state they were in
when the transaction started.

(2) Locking collections. When an iterator is running on
a collection, lock it for updates.

(3) Server-Side iterator failure. Throw an exception
back at the client when the client tries to continue
an iterator that does not work anymore, because the
next element has been deleted.

(4) Server-To-Client notification. Send a message to the
client when changes to a Map are committed.

This sure isn't easy and there is no "right" solution.
The best solution will depend upon the application.

Good luck with your object database!

Best,
Carl
--
Carl Rosenberger
Chief Software Architect
db4objects Inc.
<a rel="nofollow" style='text-decoration: none;' href="http://www.db4o.com" target="_blank">http://www.db4o.com</a>