Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > How to handle version count overflow

Reply
Thread Tools

How to handle version count overflow

 
 
oliver789@web.de
Guest
Posts: n/a
 
      06-09-2009
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
 
Reply With Quote
 
 
 
 
lord.zoltar@gmail.com
Guest
Posts: n/a
 
      06-09-2009
On Jun 9, 9:25*am, (E-Mail Removed) 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.
 
Reply With Quote
 
 
 
 
oliver789@web.de
Guest
Posts: n/a
 
      06-09-2009
> 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 .

 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      06-09-2009
http://www.velocityreviews.com/forums/(E-Mail Removed) 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
 
Reply With Quote
 
oliver789@web.de
Guest
Posts: n/a
 
      06-09-2009
> 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
 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      06-09-2009
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 |
 
Reply With Quote
 
oliver789@web.de
Guest
Posts: n/a
 
      06-09-2009
>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
 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      06-09-2009
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 |
 
Reply With Quote
 
lord.zoltar@gmail.com
Guest
Posts: n/a
 
      06-09-2009
On Jun 9, 4:26*pm, (E-Mail Removed) 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.
 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      06-10-2009
(E-Mail Removed) 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Re: Where to get stand alone Dot Net Framework version 1.1, version2.0, version 3.0, version 3.5, version 2.0 SP1, version 3.0 SP1 ? MowGreen [MVP] ASP .Net 5 02-09-2008 01:55 AM
Re: Where to get stand alone Dot Net Framework version 1.1, version 2.0, version 3.0, version 3.5, version 2.0 SP1, version 3.0 SP1 ? PA Bear [MS MVP] ASP .Net 0 02-05-2008 03:28 AM
Re: Where to get stand alone Dot Net Framework version 1.1, version 2.0, version 3.0, version 3.5, version 2.0 SP1, version 3.0 SP1 ? V Green ASP .Net 0 02-05-2008 02:45 AM
Delta Count Overflow in Simulation Isaac VHDL 2 08-18-2003 09:57 AM



Advertisments