Idempotent ODBMS iterators

Discussion in 'Java' started by Paul Chapman, Feb 16, 2005.

  1. Paul Chapman

    Paul Chapman Guest

    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

    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
    Paul Chapman, Feb 16, 2005
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stefano

    idempotent in ASP.NET 2.0

    Stefano, Sep 29, 2004, in forum: ASP .Net
    Sep 29, 2004
  2. jlowery05
    Chris Uppal
    Mar 15, 2006
  3. Patrick K. O'Brien

    Object Database (ODBMS) for Python

    Patrick K. O'Brien, Aug 28, 2003, in forum: Python
    Patrick K. O'Brien
    Aug 28, 2003
  4. Patrick K. O'Brien

    Re: Object Database (ODBMS) for Python

    Patrick K. O'Brien, Aug 29, 2003, in forum: Python
    Patrick K. O'Brien
    Sep 1, 2003
  5. Niki Spahiev

    Re: Object Database (ODBMS) for Python

    Niki Spahiev, Sep 1, 2003, in forum: Python
    Paul D. Fernhout
    Sep 1, 2003
  6. Michael Ekstrand

    Idempotent XML processing

    Michael Ekstrand, Aug 19, 2005, in forum: Python
    Will McCutchen
    Aug 19, 2005
  7. Robert Kern

    Re: Idempotent XML processing

    Robert Kern, Aug 19, 2005, in forum: Python
    Will McCutchen
    Aug 19, 2005
  8. GinTon
    Ilias Lazaridis
    Sep 19, 2006