How to handle version count overflow

[oliver789]

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

 

[lord.zoltar]

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.

 

[oliver789]

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 ;-).

 

[Lew]

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.

 

[oliver789]

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

 

[Martin Gregorie]

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...

 

[oliver789]

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

 

[Martin Gregorie]

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.

 

[lord.zoltar]

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.

 

[Lew]

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/sta...tml/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.

 

[Roedy Green]

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

 

[oliver789]

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

 

[Eric Sosman]

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.

 

[Lew]

     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.

 

[RedGrittyBrick]

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.

 

[Eric Sosman]

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

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

 

[Olli Plough]

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