How to handle version count overflow

Discussion in 'Java' started by oliver789@web.de, Jun 9, 2009.

  1. Guest

    Hello,

    my problem is mostly a general database locking problem. Since I use
    Java and hibernate I post the problem here. Seems that the plain
    database people don't understand once Java or hibernate come into
    play. I also posted to the hibernate forum but got no reply. So I'm
    trying my luck here...

    I have the special problem that there can be races between threads/
    servers to insert a new entry into some table. To handle this I have a
    locking table with a specific entry for every operation where a race
    condition can happen. This specific entry is updated in the same
    transaction in which the insert is done. In case of an optimistic
    locking exception thrown by hibernate some thread knows that it didn't
    come in first. So it knows it only needs to reload the data and thus
    gets the data as inserted by the first thread. The locking table has a
    unique constraint defined to make sure that there can only be one
    entry for each operation where there can be a race. When the operation
    is started the respective entry is loaded and stored in a thread local
    variable. And when the operation has finished a session.merge(...) is
    done on the entry in the thread local variable.

    So far so good. Now comes the problem: It is only a question of time
    till the version count of some entry in the locking table will reach
    its maximal value beyond it cannot be incremented any more, because
    the field width of the version count would be exceeded. In my scenario
    this will take several months or maybe years till it will happen. But
    it will definitely happen one day. So I'm looking for a solution for
    this. What would be nice would be to simply reset the version count to
    0. But this would certainly result in an optimistic locking exception
    in case some thread local variable exists that still has a reference
    to the entry loaded before the version count reset.

    The solution I have found so far is too complicated. Maybe someone
    else has a better idea. What I do is the following:

    If the version count has reached the max value another entry is
    created which is then in the following incremented. Problem here is
    that there can be races conditions in between the change over from the
    initial entry to the follow-up entry. Now starts the difficult part
    how to handle this. I thought of a third entry that is updated when
    the second entry is inserted. Unhappily, this does not work with the
    @Transactional annotation in Spring. I would have to do a flush to get
    this to work and in the past I have only seen session.flush(...)
    resulting in some deadlock. So I have this wild solution I don't like,
    because to complicated:

    1. Max version count: M. N is some number << M. (much smaller than M)
    2. When the version count has reached M - N, the second entry is
    created
    3. In the following the session.merge(...) is done on both entries
    till M has been reached. From that moment on the merge is only done on
    the second entry. The idea is here that with N being sufficiently
    large also the longest operations will have been finished till M has
    been reached.
    4. The first entry is deleted.
    5. When for the second entry M - N has been reached, the same
    procedure repeats resulting in the first entry being created again and
    the second one being deleted once M has been reached.

    The advantage of this approach is that the number of entries does not
    grow beyond 2. The other approach would be not to delete the former
    entry but keep on creating new entries. I don't like this since this
    for my taste is a little "messy".

    Thanks to every body who kept on reading this long post up to this
    point :). Maybe someone out there has a simpler solution. Would be
    nice.

    Cheers, Oliver
     
    , Jun 9, 2009
    #1
    1. Advertising

  2. Guest

    On Jun 9, 9:25 am, wrote:
    >
    > The solution I have found so far is too complicated. Maybe someone
    > else has a better idea. What I do is the following:
    >
    > If the version count has reached the max value another entry is
    > created which is then in the following incremented. Problem here is
    > that there can be races conditions in between the change over from the
    > initial entry to the follow-up entry. Now starts the difficult part
    > how to handle this. I thought of a third entry that is updated when
    > the second entry is inserted. Unhappily, this does not work with the
    > @Transactional annotation in Spring. I would have to do a flush to get
    > this to work and in the past I have only seen session.flush(...)
    > resulting in some deadlock. So I have this wild solution I don't like,
    > because to complicated:
    >
    > 1. Max version count: M. N is some number << M. (much smaller than M)
    > 2. When the version count has reached M - N, the second entry is
    > created
    > 3. In the following the session.merge(...) is done on both entries
    > till M has been reached. From that moment on the merge is only done on
    > the second entry. The idea is here that with N being sufficiently
    > large also the longest operations will have been finished till M has
    > been reached.
    > 4. The first entry is deleted.
    > 5. When for the second entry M - N has been reached, the same
    > procedure repeats resulting in the first entry being created again and
    > the second one being deleted once M has been reached.
    >
    > The advantage of this approach is that the number of entries does not
    > grow beyond 2. The other approach would be not to delete the former
    > entry but keep on creating new entries. I don't like this since this
    > for my taste is a little "messy".
    >
    > Thanks to every body who kept on reading this long post up to this
    > point :). Maybe someone out there has a simpler solution. Would be
    > nice.
    >
    > Cheers, Oliver


    Have you actually calculated how long it will take until the version
    count will hit the maximum value for that field?

    If the version count is not being used for anything other than
    locking, it sounds like the simplest thing to do would be reset it
    when no clients are actually using it. How you determine this, well,
    I'm not sure. Maybe another table with records of which client is
    trying to use which locks. When there are no clients vying for a given
    lock, reset the lock's version count.
     
    , Jun 9, 2009
    #2
    1. Advertising

  3. Guest

    > Have you actually calculated how long it will take until the version
    > count will hit the maximum value for that field?
    >
    > If the version count is not being used for anything other than
    > locking, it sounds like the simplest thing to do would be reset it
    > when no clients are actually using it. How you determine this, well,
    > I'm not sure. Maybe another table with records of which client is
    > trying to use which locks. When there are no clients vying for a given
    > lock, reset the lock's version count.- Zitierten Text ausblenden -
    >
    > - Zitierten Text anzeigen -


    Yes, resetting the count at a time where no client is active is
    another idea. Whenever some critical operation is started an operation
    counter is incremented and decremented when it has finished. So when
    the operation counter is 0, the version counter can be reset to 0.
    Unhappily, at second sight problems occur: When the operation counter
    is 0 and the version counter is being reset another thread could come
    in between. You need something like a third versioned entry to make
    this thread safe as well. Starting to get tedious now ... ;-). Then,
    when the VM crashes also decrementing the operation counter in a
    finally block will not be enough to make sure it is decremented. So
    you need to reset the counter when the server starts up. Now if there
    are several servers accessing the same database there are problems
    with this as well ...

    Another idea I got just now is to lock the entire table for select/
    insert/update when the version counter needs to be reset. Costly, but
    justifiable as the version counter only after a long time runs into
    overflow. But an update to reset the version counter still needs to be
    done. So locking the table for update doesn't work. You can lock it
    for select, but some operation may have started just before you did
    that. Another race condition here. Oh no ...

    Maybe I just make the version count field 19 digits in width (aka Java
    Long), shoot myself into the food and go home ... Some poor developer
    in 100 years time will have to analyze the problem then and figure out
    that the version count needs to be reset ;-).

    Regards, Oliver

    P.S.: I still like to find a simple thread safe solution for this
    problem whether it is of practical importance or not. It's just fun to
    think about it ;-).
     
    , Jun 9, 2009
    #3
  4. Lew Guest

    wrote:
    > P.S.: I still like to find a simple thread safe solution for this
    > problem whether it is of practical importance or not. It's just fun to
    > think about it ;-).


    Thread safety and database concurrency are different issues. Thread safety
    concerns only matters within the JVM; database concurrency only matters within
    the DBMS.

    Most professional DBMSes handle concurrent access quite well without extra
    effort.

    Thread safety requires only that you properly coordinate access to shared
    in-memory state in the program.

    --
    Lew
     
    Lew, Jun 9, 2009
    #4
  5. Guest

    > Thread safety and database concurrency are different issues.

    Each Java Thread creates it's own (hibernate) transaction when
    accessing the database and closes it when finished. So, this has
    nothing to do with java.util.concurrent.* stuff but is about DBMS
    transactions.

    /Oliver
     
    , Jun 9, 2009
    #5
  6. On Tue, 09 Jun 2009 07:52:25 -0700, oliver789 wrote:

    >
    > Another idea I got just now is to lock the entire table for select/
    > insert/update when the version counter needs to be reset. Costly, but
    > justifiable as the version counter only after a long time runs into
    > overflow. But an update to reset the version counter still needs to be
    > done. So locking the table for update doesn't work. You can lock it for
    > select, but some operation may have started just before you did that.
    > Another race condition here. Oh no ...
    >
    > Maybe I just make the version count field 19 digits in width (aka Java
    > Long), shoot myself into the food and go home ... Some poor developer in
    > 100 years time will have to analyze the problem then and figure out that
    > the version count needs to be reset ;-).
    >

    If the time it will take to overflow the version count field is extremely
    long compared with the updating program's run time there's no problem.
    You could probably use an int if the program is only accessed from a few
    adjacent time zones and is taken down every day or week for housekeeping
    and/or backups. Just reset the version count table during program
    initialisation before the threads are started. This could be fast, since
    it can be a single, table-wide UPDATE operation.

    For a 24/7, globally accessed system it may be possible to maintain a set
    of version count table rows and an associated thread dispatcher for each
    time zone. That would allow threads associated with the zone to be
    quiesced and the counts reset during a quiet time for that time zone. The
    pause would only last long enough for current threads to end and the
    UPDATE to complete, so the impact on throughput should be minimal.

    Of course, if the program is intended to run for several years with very
    high data volumes being processed you may have to do something rather
    more complex...


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Jun 9, 2009
    #6
  7. Guest

    >Just reset the version count table during program
    >initialisation before the threads are started. This could be fast, since
    >it can be a single, table-wide UPDATE operation.


    I also had this idea. Problem is that there are several servers that
    have no way to communicate from VM to VM (TMI, JMS, etc.) and must
    therefore "communicate" by changing values in a shared database. When
    a server starts up it doesn't know whether the other ones are running.
    Let's say the user may start up as many servers as needed depending on
    the load. Then incrementing a counter every time a server starts up is
    also not sufficient, because you don't know how many will be started
    up.

    > That would allow threads associated with the zone to be
    > quiesced and the counts reset during a quiet time for that time zone.


    This is a nice idea. I like this one. Unhappily, my application is too
    simple: it does not run 24 hour and only spans one time zone.

    >Can't he just let the version counter wrap around, from 99...99
    >back to 00...00 again?


    The optimistic locking mechanism would have no way to tell whether
    someone just wants to reset the counter or whether some locking
    exception has occured. This would only work if you were sure that no
    thread is accessing the lock entry for a given time period which is
    also hard to enforce.

    >A final thought on the "use a Java long" approach: There is
    >no danger, I repeat *no* danger that such a counter will wrap
    >around in a mere hundred years.


    Yes, you are right. I just felt intrigued by the problem and was
    wondering whether a pure algorithmic solution could be found that were
    free from glitches.

    Then ..., well ... The application is not accessed by end users during
    the night and uses a Quartz scheduler. The last job runs around 6 pm.
    So somewhen after midnight it should be really safe to reset that
    counter once in a year or so. Could be easily done by defining a
    separate Quartz job for this.

    Hope nobody feels annoyed now :))). My post was really about finding
    an algorithmic solution for the problem without any "cheap" solutions
    like resetting the counter during the night. Unhappily, there are just
    too many workarounds that in practice are sufficient so that you
    cannot fight some argument why you are not just sticking to such a
    workaround. But as such the "version count overflow problem" was
    interesting. Think I need to change over from a table with two entries
    to a Turing machine with 2 bands or something and then no workarounds
    are possible any more and we are back to the pure "version count
    overflow problem with an undetermined number of severs, infinite
    workload, operating 24 hours and version counts smaller than
    2^16" :))).

    Regards, Oliver
     
    , Jun 9, 2009
    #7
  8. On Tue, 09 Jun 2009 13:26:41 -0700, oliver789 wrote:

    >> That would allow threads associated with the zone to be quiesced and
    >> the counts reset during a quiet time for that time zone.

    >
    > This is a nice idea. I like this one. Unhappily, my application is too
    > simple: it does not run 24 hour and only spans one time zone.
    >

    Continuing the thought experiment.....

    This mechanism can be extended over several VMs/applications though at a
    cost. This would require the thread dispatchers in each application to
    record their state and/or active thread count in a dispatcher state
    table. Datestamping this row would be helpful for monitoring and
    recovering from process failures. That allows the process responsible for
    handling the reset to use the state table to request a quiesce, see when
    all threads have been quiesced, do the reset and notify the dispatchers
    that they can continue. With proper design you could get quite fine-
    grained control over who quiesces, which threads they hold up and when
    they do it.

    However, if you take it this far, you do get recovery issues if one or
    more applications fail, but the aforementioned timestamp would help here.
    However, as its a database problem that is being solved, I'd still use
    the database to handle cross-process co-ordination states rather than
    introducing another mechanism.


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Jun 9, 2009
    #8
  9. Guest

    On Jun 9, 4:26 pm, wrote:
    >
    > Then ..., well ... The application is not accessed by end users during
    > the night and uses a Quartz scheduler. The last job runs around 6 pm.
    > So somewhen after midnight it should be really safe to reset that
    > counter once in a year or so. Could be easily done by defining a
    > separate Quartz job for this.
    >


    Why wait a year? Why not just do it nightly, as a part of the regular
    shutdown procedure? Or startup procedure?

    In the case where the application was available 24/7 with no regular
    downtime, you might have been able to use a single-purpose server to
    JUST control the locks in the database, which all the other servers
    talk to. Allow that lock-control server to decide when to roll-around
    the version numbers.
     
    , Jun 9, 2009
    #9
  10. Lew Guest

    wrote:
    > Each Java Thread creates it's [sic] own (hibernate) transaction when
    > accessing the database and closes it when finished. So, this has


    Just to be clear, you are discussing how your code specifically uses
    Hibernate. It's certainly possible generally for code to use Hibernate in a
    thread-unsafe way.

    > nothing to do with java.util.concurrent.* stuff but is about DBMS
    > transactions.


    I was responding to your comment,
    > I still like to find a simple thread safe solution for this
    > problem whether it is of practical importance or not.


    Lots of thread issues in Java have nothing to do with java.util.concurrent.*
    stuff.

    The other half of my response to you was:
    > Most professional DBMSes handle concurrent access quite well without extra effort.


    What I am not seeing is what about your situation defeats the DBMS's
    concurrency capabilities. I am slightly suspicious that use of an explicit
    "locking table" might contribute to a problem. What about built-in JPA (i.e.,
    Hibernate) version attributes?
    <http://docs.jboss.org/hibernate/stable/annotations/reference/en/html/entity.html#entity-mapping-entity-version>

    As to your rollover question, rollover can only happen infrequently,
    presumably with a low enough frequency that no outstanding transaction will be
    holding on to a low enough version number from a previous rollover time to be
    confusing at the next one. If a version number (v) shows up less than (MAX/n)
    when all others have version numbers above (MAX - MAX/n), where n is pretty
    far below MAX and (MAX + 1) is rollover-equivalent to zero, it's a safe bet
    that for now, that low version number really means the equivalent of (MAX + 1
    + v), compared to all those high-numbered versions. By the time there's a
    risk of confusion, no outstanding transaction should be above (MAX - MAX/n)
    any more; they'll all be in lower number ranges.

    --
    Lew
     
    Lew, Jun 10, 2009
    #10
  11. Roedy Green Guest

    On Tue, 9 Jun 2009 06:25:41 -0700 (PDT), wrote,
    quoted or indirectly quoted someone who said :

    >my problem is mostly a general database locking problem.


    I don't know how precisely you would apply to your situation, but
    often in analogous situations you have a counter than you increment
    and decrement. When all the locks are gone, it is back down to zero.
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com

    Never discourage anyone... who continually makes progress, no matter how slow.
    ~ Plato 428 BC died: 348 BC at age: 80
     
    Roedy Green, Jun 10, 2009
    #11
  12. Guest

    All right guys. I have to tell you that we were all dumb, because
    there is no problem! When the version counter max value has been
    reached you just set it to 0. Version counts don't need to be
    consecutive to make sure that optimistic locking works. So there is no
    problem with setting the count from 9...9 to 0. There would only be a
    problem if there were still a Java lock domain object with a version
    count of 0 stored in some thread local variable on which a
    session.merge(...) has not been done with yet. After the corresponding
    record has been updated 9...9 times in the meanwhile this is not only
    extremely unlikely but surely not the case.

    Only problem is that in the hibernate interface there is no way to
    tell what the version count max value is. So hibernate wouldn't set
    the counter to 0 to avoid overflow resulting in a database exception
    being propagated through hibernate to your application.

    Cheers, Oliver
     
    , Jun 10, 2009
    #12
  13. Eric Sosman Guest

    wrote:
    > All right guys. I have to tell you that we were all dumb, because
    > there is no problem! When the version counter max value has been
    > reached you just set it to 0. Version counts don't need to be
    > consecutive to make sure that optimistic locking works. So there is no
    > problem with setting the count from 9...9 to 0. There would only be a
    > problem if there were still a Java lock domain object with a version
    > count of 0 stored in some thread local variable on which a
    > session.merge(...) has not been done with yet. After the corresponding
    > record has been updated 9...9 times in the meanwhile this is not only
    > extremely unlikely but surely not the case.


    I object to the "we were all dumb" remark, because this
    is *exactly* the approach I described.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Jun 10, 2009
    #13
  14. Lew Guest

    wrote:
    >> All right guys. I have to tell you that we were all dumb, because
    >> there is no problem! When the version counter max value has been
    >> reached you just set it to 0. Version counts don't need to be
    >> consecutive to make sure that optimistic locking works. So there is no
    >> problem with setting the count from 9...9 to 0. There would only be a
    >> problem if there were still a Java lock domain object with a version
    >> count of 0 stored in some thread local variable on which a
    >> session.merge(...) has not been done with yet. After the corresponding
    >> record has been updated 9...9 times in the meanwhile this is not only
    >> extremely unlikely but surely not the case.

    >


    Eric Sosman wrote:
    >      I object to the "we were all dumb" remark, because this
    > is *exactly* the approach I described.
    >


    I described the same approach, too, prior to reading Eric's post and
    thinking, "Hmm, he already said that. Aren't I the little copycat?"

    I guess I'm not dumb, either.

    --
    Lew
     
    Lew, Jun 10, 2009
    #14
  15. Re: [OT] Re: How to handle version count overflow

    Eric Sosman wrote:
    > Lew wrote:
    >> wrote:
    >>>> All right guys. I have to tell you that we were all dumb, because
    >>>> there is no problem! When the version counter max value has been
    >>>> reached you just set it to 0. Version counts don't need to be
    >>>> consecutive to make sure that optimistic locking works. So there is no
    >>>> problem with setting the count from 9...9 to 0. There would only be a
    >>>> problem if there were still a Java lock domain object with a version
    >>>> count of 0 stored in some thread local variable on which a
    >>>> session.merge(...) has not been done with yet. After the corresponding
    >>>> record has been updated 9...9 times in the meanwhile this is not only
    >>>> extremely unlikely but surely not the case.

    >>
    >> Eric Sosman wrote:
    >>> I object to the "we were all dumb" remark, because this
    >>> is *exactly* the approach I described.
    >>>

    >>
    >> I described the same approach, too, prior to reading Eric's post and
    >> thinking, "Hmm, he already said that. Aren't I the little copycat?"
    >>
    >> I guess I'm not dumb, either.

    >
    > You'n me, Lew, we probably rate a few millieinsteins apiece. (See
    > <http://c2.com/cgi/wiki?MilliEinstein> for the "millieinstein" I had
    > in mind, but see also <http://en.wikipedia.org/wiki/Einstein_(unit)>:
    > it turns out there actually *is* a unit called the "einstein!")
    >


    I searched the intarwebs for "units of humility" but the intarwebs
    failed me.

    --
    RGB
     
    RedGrittyBrick, Jun 11, 2009
    #15
  16. Eric Sosman Guest

    Re: [OT] Re: How to handle version count overflow

    RedGrittyBrick wrote:
    >
    > I searched the intarwebs for "units of humility" but the intarwebs
    > failed me.


    The unit is unspecified, but the quantity is always
    humble pi.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Jun 11, 2009
    #16
  17. Olli Plough Guest

    The problem with hibernate throwing an exception when the version
    count's field width is exceeded is simply to make the field wider than
    the number of digits in 2^32 or 2^64 or whatever. Then the count
    simply rolls over, becomes -2^32 or whatever and that's it.

    /Oliver
     
    Olli Plough, Jun 11, 2009
    #17
    1. Advertising

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. Isaac
    Replies:
    2
    Views:
    3,892
    Arvind Kumar
    Aug 18, 2003
  2. V Green
    Replies:
    0
    Views:
    885
    V Green
    Feb 5, 2008
  3. PA Bear [MS MVP]
    Replies:
    0
    Views:
    1,001
    PA Bear [MS MVP]
    Feb 5, 2008
  4. MowGreen [MVP]
    Replies:
    5
    Views:
    2,045
    PA Bear [MS MVP]
    Feb 9, 2008
  5. efelnavarro09
    Replies:
    2
    Views:
    955
    efelnavarro09
    Jan 26, 2011
Loading...

Share This Page