P
Paul Chapman
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? I know that this is a
general software-design question, but I thougt I'd try the smart people here
first.
Cheers, Paul
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? I know that this is a
general software-design question, but I thougt I'd try the smart people here
first.
Cheers, Paul