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

Paul Chapman wrote:

[...]

[...]


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.
http://www.db4o.com

Carl,

db4o was one of the sites I looked at when researching this project.

Remember, though, that I expect some users will want to run iterations over
days or weeks. Reason: to do low-priority verification of some of the data.
They won't be able to hold a session open all that time, let alone a
transaction.

Sounds like what Windows does when you're trying to do a ScanDisk.

ATM the client/server comms is synchronous. But I might look at adding
async behaviour later.

It's not an urgent or important problem. Thanks for your help.

Cheers, Paul

Carl,

If you have a chance to look at this, be my guest. Anyone is free to
comment, of course.

I've been looking at this in more detail, not particularly from the point of
view of iterators, but as a general approach to concurrent database sessions
belonging to different clients.

Each client is connected to the database via a "session" which is maintained
by the server.

The session is itself an object in the database, having a path from the
root. The session maintains as a field a set of all of the objects the
client has been told about (in this session). This ensures that the
concurrent garbage collector doesn't throw away objects which the client has
created, but hasn't yet stored in fields of other objects in the database
reachable from the root: all objects known to all logged-on client are safe
from GC.

A client (person, local process, remote batch program, etc) may interrogate
the database in two ways: (1) "browsing", during which other clients may be
modifying the database concurrently, and so successive enquiries may see
changing values, and (2) "transacting", which is the only time mutating
requests may be made, and during which the database will appear to the
transacting client to be exclusive. A client is browsing until a transation
is started, then is transacting until the transaction is either committed or
abandoned, then is browsing again, etc.

All changes made during a transaction are visible only to the client
performing the transaction. When a transaction is committed, all changes
requested by the client are made in a single, failproof, atomic action by
the server.

Things get interesting when the following sequence of events takes place:

(1) Client A begins a transaction
(2) Client A requests some info about object X
(3) Client B begins a transaction
(4) Client B requests that object X be mutated
(5) Client B commits
(6) Client A requests some more information about object X
(7) Client A requests that object X be mutated
(8) Client A commits

Client A must see the same X in steps (2) and (6), despite the fact the B
has mutated it. When client A commits, B's changes to X will be wiped out,
but that's what we'd expect.

OK, so that's the theory. How is it implemented in practice? Forgive me,
but I haven't studied ODBMS. What I now present (if correct!) is probably
well-known technology, but I've always enjoyed algorithmics, and so it's fun
to try to find my own solutions.

A client knows an object by a handle. The same handle always refers to the
same object (during a session, anyway -- I haven't yet decided whether
handles can change in the long term).

During a transaction, the server session object for that client maintains a
"substition map" (SM), initially empty. Whenever the client make a mutating
request, the server makes a copy of the object to be mutated (if it hasn't
already), and mutates the copy. It then stores an entry in the SM whose key
is the handle of the original object, and whose value is handle of the new
object.

All handles referred to by the client in requests during a transaction are
"translated" via the SM if necessary, so that the requests are actually
carried out on the copies.

If the transaction is abandoned, the copies are simply thrown away, and the
SM cleared. (The copies will probably hang around until the GC discards
them, although I might try and improve that later -- when I write the GC!)

If the transaction is committed, the server atomically *exchanges the
identities of each of the key-value pairs in the SM*, and then clears the
SM. That is to say, for an entry
handle-of-X : handle-of-X-copy
the server makes the first handle point to the mutated copy and the second
to the original. (This is a mutual become: in Smalltalk language.)

But that isn't quite the end of the story.

If some other client A is mid-transaction when a transaction by client B is
committed, client A may perceive a change in the database, which isn't
allowed. In particular, any object which A *hasn't* yet mutated will appear
to have changed when B's transaction exchanges identities.

So before B exchanges each pair of identities in its SM, it must show its SM
to all other sessions with transactions in progress. Each of those session
scans B's SM, and adds any entry whose key is found in its
"user-knows-about-this-object" set but not among the keys of its own SM to a
secondary substitution map.

Ie, if B's SM contains
handle-of-X : handle-of-X-copy
A adds
handle-of-X : handle-of-X-copy
to its secondary substition map. Then when B exchanges identities of X and
X-copy, A's entry will effectively say:
handle-of-X-copy : handle-of-X
which will ensure that if client A uses the only handle to X it knows about
(the first), the server will ensure that the *original* is still referred
to.

I need to work out some details yet about what happens to entries in the
secondary list when A attempts to mutate them, and also what happens if yet
another session attempts to modify X: some some of transitive operations are
going on here.

Does all this seem familiar? Does it look right?

Cheers, Paul

Paul Chapman wrote:
Thanks for the invitation!

You describe your thoughts very well, it is fun to follow.


[...]

ODBMS usually offer none to three of the following isolation
options:

(1) Page locking
If one transaction modifies objects on one page (a physical
implementation detail), the page is locked for modifications
by all other transactions until the transaction commits.

(2) Object locking
If one transaction modifies one object, the object is locked
for modifications by all other transactions until the transaction
commits.

(3) Optimistic transactions
If a transaction commits modified objects, the version number on
all objects is checked, whether it is still the same as it was
when the object was read.


If locking options (1) and/or (2) are provided, there usually
also is a method call to lock manually.

Furthermore some object databases provide notification handlers
for committed objects.


Typically all ODBMS implementations I know produce inconsistent
objects in step (6) of your example unless they lock object X
on read. That's why transparent persistency (lazy reading) is
very problematic in multi-user setups.


Optimistic transactions should notify you about your concurrent
update in step (8).



This theme is quite interesting. It exists in exactly the same
way for SQL databases, but bugs are much more difficult to
discover. They tend to occur unnoticed, "somewhere in the
mapping layer" and noone knows why.


For now I personally prefer optimistic transactions with object
version numbers.

In the long term I would like us to provide real
"read-back-in-time" transactions for db4o also:
That would mean that Client A would get information about
object X in step (6) of your example exactly the way it was
before the commit of Client B.


[...]

That's pretty much how we supply read committed transactions
with db4o.
....by keeping trees of indirected IDs with point to modified
objects.


This is prinicipally a nice idea but it may get you *lots* of
network traffic if you have multiple clients connected.

It also requires your clients to be able to handle pushed
updates to objects that may be doing something else at the
same time. The application programmer has to know a lot
about how the database works and provide sensible reactions
to update-notification-listeners.

Imagine you are using third-party-software: Your Swing or
SWT-GUI may just not be able to handle updates at all times
for all objects.

Although complete Server-To-Client-notification is the cleanest
possible approach for perfect "updated objects", I am afraid
this is more a theoretical setup than one that actually works
good in practice.

For db4o we get very frequent requests to provide this
functionality (which we don't have yet) and we will build it.
It will be very interesting to see it work live.


All this looks very familiar. You may like to scan old entries
in our db4o newsgroup with the search tool that we provide to
read up some more of my thoughts in the past:
http://www.db4odev.com/newsarchive/search.cmd

Try the following two searches:
Notification
Locking AND design


Is there anything already visible around your ODBMS project?

This is one of the most interesting discussions I have seen
in this newsgroup for ages. Please keep us posted with your
thoughts.


Best,
Carl
--
Carl Rosenberger
Chief Software Architect
db4objects Inc.
http://www.db4o.com

Carl,

Thanks very much for your carefully considered response.

Both of these may produce deadlocks, which of course must be checked for. A
request (direct or indirect) by the client for a lock which fails because a
deadlock is spotted would cause immediate failure of the transaction. I'm
trying to avoid that!

Again, this means the transaction may fail. I'm trying for something more
ambitious, I guess.

I am trying to stick to synchronous communication in order to keep the
client API as simple as humanly possible.

OK, so maybe soon you'll know one which doesn't.

Or two.

No, none at all. In this context, a "session" is a (Java) object maintained
by the server.

Each such session maintains a list of all the objects (object handles) the
client has asked about during the current transaction. When another session
on the server is asked by its client to commit a transaction, it circulates
its intended list of identity-exchanges.

When this session receives the list, it checks each OLD handle against its
list of known-to-client objects, and where one such is found, it adds an
entry to its MAINTAIN-OLD-VIEW map which maps the OLD handle to the NEW
object. When the other session finally swaps old-new object identities, our
session's map will now in effect map the OLD handle to the OLD object.

(There are some other details I have worked out but won't go into here.)

My db is a "shallow" db, in contrast to yours, which I would describe as
"deep". I am not attempting to map Java objects in a program to Java
objects in a persistent object store. My db in language-independent and
data-structure independent. It provides its own object model which all
languages (OO or non-OO) could use.

It may be that my approach may not work so well for you.

However, I have sketched out a solution to some deep-object-copy performance
problems which I myself have to deal with anyway, since some of my objects
*will* be deep in practice, even though the client won't see this deep
structure.

One kind of depth I have to deal with is that I keep for each dictionary
object an array of keys in insertion order. This array is itself an object.

If a copy of a dictionary has to be made for mutation by a
transaction-in-progress, I don't want to duplicate the key array unless it
is necessary. If the mutation of the dictionary merely replaces existing
fields with new values, the key array remains unchanged. If, however, keys
are added or removed, the key array must also be copied.

I call this "lazy deep copying". With every mutation request to an object,
a parameter which is a reference to a "lazy deep copier" (LDC) is supplied.
Whenever an object needs to change a subobject, it asks the LDC to give it a
handle to a "copy" of the object (if one is needed), and stores the handle
to the copy back where it got the original handle from, and then goes on to
mutate the subobject. Sometimes, of course, the "copy" will be the same as
the original (eg when the LDC has already copied a particular object).

Furthermore, some (logical) objects in the database may get very large. For
performance reasons (and so I don't blow memory!) I want to be able to break
them up into (physical) subobjects. The subobjects will be hidden from the
client -- indeed, only the subobjects' parent will know about them.

So again, if a request to copy a very large object is made, I can copy just
the top-level object, and create an LDC which will copy on demand those
subobjects which are mutated.

So suppose a 16 megafield dictionary object (at 8 bytes per field) is broken
down into 256 subobjects, each broken down into 256 subobjects, each
containing 256 actual fields. A transaction requests the mutation of a
single field. Instead of having to copy 128Mb to preserve the old view (for
other transactions or for rollback-on-fail), only 256*4 + 256*4 + 256*8 =
4Kb (plus a small overhead) has to be copied.

I have yet to implement this. But it'll come in the next week or so.

I will do that next.

I have one friendly alpha-tester in the US (I am in London) who has done a
couple of very simple TCP/IP tests, which just displays a browser tree on
the database root, and requests subtrees on expansion.

But I haven't yet written the session or transaction pieces yet, so it's
early days. (I hacked too much code in the past week, and I'm now pausing
to refactor while I think about sessions and transactions.)

Eventually I will probably go open-source with the db (unless you wanna buy
my algorithms exclusively .

I'll keep the ng posted on developments, then.

Meanwhile, I am interested to know how ambitious my design is.

It seems my design criteria have been:

(1) Simultaneous transactions in progress by multiple clients.

(2) No locking of any kind, ever.

(3) Fast commit (just some in-memory manipulation of handles).

(4) No transaction failure (assuming client has no logic errors).

(5) No asynchronous messaging of clients.

The main cost I incur for this is having to copy an object before mutation,
but copying is kept to a minimum by managing logical objects as trees of
small physical objects, and performing lazy deep copying.

To me, these requirements seemed "reasonable". But you seem to be
suggesting that I may be at the cutting edge. If I am, I have concerns
about the state-of-the-art.

I haven't used a formal database system since DBase II in the early 80s,
BTW, and I've never written a line of SQL. I've always done my own file
design.

Cheers, Paul

PS.

Googling "lazy deep copy" (with the quotes) produces no matches, while "lazy
deep copying" produces just one, which I'm about to peruse.,

Cheers, Paul

Carl,

Just browsing your forum.

Two interesting paragraphs from you caught my eye:

"All db4o operations are transactional. In my opinion this
is the simplest approach possible. Your code will always
behave the same and you don't have to worry whether you are
in a transaction or not."

"Can we do this simpler than everyone else?"

I am attracted by the first idea, although I am concerned about performance.
I expect most users will mostly be "browsing" most of the time. But I'll
give it some thought.

I expect to challenge you on the second para. But then I'll be offering
less functionality and WAY less performance, I suspect.

BTW, my ODBMS is currently being developed for fun, and solely for the
purpose of providing the tiny worldwide Game Of Life community with a place
to store their patterns! Nevertheless, I'm trying to do a proper, formal
job.

Cheers, Paul

Carl,

PPS.

I now see why you said this. From reading the forum, I see that you are
caching objects in clients. Currently, I am not (except for certain
immutable objects like symbols and classes). OEM clients can manually cache
at "their own risk", of course.

I may have to change my approach. But we'll see how it goes. See, I told
you that my perfomance wouldn't be as good as yours.

Cheers, Paul