RE: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads <s nip>

[Thompson, B. B. <BRY...@sa...>]

Resend as plain text. -bryan

________________________________________
From: Thompson, Bryan B.=20
Sent: Tuesday, March 28, 2006 7:05 PM
To: 'Kevin Day'; JDBM Developer listserv
Subject: RE: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads
<snip>

Kevin,

Yes, prototypes may be the way to go.

My concern is that blocking is something that a tx may do for any =
resource
that it is accessing.=A0 However the notion of setting the bond between =
a tx
and a thread has been discussed in terms of a specific resource / =
lock.=A0 You
simply do not know at the Queue level (a single resource) whether or =
not the
transaction is blocked on waiting in a queue for another resource.=A0 =
E.g.,
this decision needs to be made with respect to all resource locks =
requested
by the tx, not with respect to a single resource.

-bryan

________________________________________
From: jdb...@li...
[mailto:jdb...@li...] On Behalf Of Kevin =
Day
Sent: Tuesday, March 28, 2006 6:59 PM
To: JDBM Developer listserv
Subject: re[2]: [Jdbm-developer] re[14]: 2PL: transactions, threads =
<snip>

Bryan-
=A0
Hey - I used to work for Motorolla - we had manuals of TLAs we had to =
carry
around...
=A0
Any reason to not hold a map of all locks keyed by transaction?=A0 I =
suppose
the locks could be held by the tx itself, but it kind of starts pushing =
the
locking code into the transaction management code.=A0 I could see where =
maybe
the locked *resource* could be held by the transaction (we will need
something like this for caching purposes anyway) - if you are already
maintaining a map of resource -> queues, could we combine those two to
provide the notification for lock release?
=A0
I really have no conceptual feel for the "correct" way for this to fall =
out
- I think that we need to do some high level thinking about the =
interactions
of the layers...=A0 A proof of concept implementation would be a very =
good
starting place for helping us get our heads around the problem space.
=A0
=A0
=A0
Back to the question about enforcing the behavior of the 'current'
transaction for the thread not changing if the tx is blocked, I want to =
make
sure that I fully understand your concern.=A0 Are you concerned about =
an
application calling setCurrentThreadTransaction() while another thread =
has
that transaction as *it's* current thread transaction?
=A0
Or something else?
=A0
Thanks!
=A0
- K
=A0
=A0
=A0
=A0
=A0=20

> Kevin,

Yes, you do have a thing for TLAs!

I think that there are unanswered questions below, notably. =A0It =
sounds like
a transaction probably needs to maintain a collection of all locks that =
it
has obtained and not yet released or requested and not yet obtained. =
=A0I do
not handle this in the locking package since I was trying to avoid =
making
decisions on the behalf of people who were designing their own =
Transaction
API. =A0However, maybe it would make sense if I did a sample design =
that
demonstrated how the locking API could be integrated for that purpose?

Bryan wrote:

Given that the thread associated with a transaction may not change =
while
that transaction is blocked, how are you going to enforce that at the
lockMgr level? =A0There are many, many possible Queue instances. =A0You
would need to know whether or not the transaction was blocked in any =
Queue
instance. =A0Are we going to use a thread local variable for that as =
well?
If so, it seems that this would have to be set by Queue.lock().

-bryan
________________________________________
From: jdb...@li...
[mailto:jdb...@li...] On Behalf Of Kevin =
Day=20
Sent: Tuesday, March 28, 2006 5:29 PM
To: 'JDBM Developer listserv '
Subject: [Jdbm-developer] re[14]: 2PL: transactions, threads <snip>

Bryan-
=A0
Gotcha.=A0 Gotta love those TLAs...
=A0
To answer the question about impact on the design I (actually,
Alex)=A0suggested:
=A0
I don't think there is much impact at all, except that the waits for =
graph
needs to hold transaction references, and not references to the current
thread.
=A0
As long as the call to lock() either includes the transaction as a
parameter, or does it's own thread local lookup to obtain the =
transaction,
then all is well.
=A0
If you have the transaction as a parameter, then we can always wrap the
library to allow for thread local storage of the current active
transaction.=A0 If you do the thread local thing internal to the lock =
library,
then we just use the library as is.
=A0
The biggest thing is that we have got to have the extra level of =
indirection
that allows us to provide a lock context that is not just the current
thread, but any object (e.g. Transaction) that we want to associate =
with the
current thread.=A0 The current javadocs in the header of the lock class =
you
emailed earlier=A0imply that the thread is itself the lock context, and =
I
think we will want to relax that a bit with one layer of indirection.
=A0
- K
=A0
=A0=20

> Kevin,

Dag is Directed Acyclic Graph. =A0The name TxDag came about since I was
already working on a DAG class and then I discovered that there were
special case optimizations for online deadlock detection designed to
support databases -- hence, TxDag.

The basic idea for deadlock detection is that when one transaction must
wait for a lock, you make an assertion:

x WAITS_FOR y

Where x is the transaction that is waiting and y is _each_ of the
transactions that are currently in the granted group for that
resource (the transactions that have a lock on the resource). =A0So,
if there are 5 transactions with a share (S) lock on some resource,
and another transaction seeks an exclusive (X) lock on the same
resource, then you would assert 5 WAITS_FOR relation, so that is
5 new edges in the WAITS_FOR graph.

A deadlock results iff adding those assertions would result in a cycle
in the WAITS_FOR graph. =A0If a deadlock would result, then the =
WAITS_FOR
graph is NOT modified and a deadlock condition is reported by throwing
a DeadlockException.

I will think some more about the requirement for releasing all locks
when a transaction completes. =A0The twist is that this special case =
can
be handled more efficiently by TxDag (Bayer wrote about this =
optimization
when he described the algorithm). =A0Basically the protocol for a tx =
that
completes is that it must call some method that is responsible for
efficiently releasing all locks and clearing the row and column for
that transaction from the internal matrices in the TxDag class.

There may be a grand unified CC architecture. =A0This was the subject =
of
the FLASK project. =A0I am not close enough to see it right now -- I am
just trying to get the locking system nailed so that we can move on.

It is perfectly reasonable that the locking package will be repackaged
by jdbm along the lines that you were proposing, in which case only the
jdbm design will need to be "aware". =A0However the use of intention =
and
implicit locks will require some drill down in order for the =
application
to see any benefit.

So, I still have the question, how does this impact the design that you
are suggesting?

-bryan

-----Original Message-----
From: jdb...@li...
To: JDBM Developer listserv
Sent: 3/28/2006 4:00 PM
Subject: re[12]: [Jdbm-developer] 2PL: transactions, threads and locki =
n
g (rese nd!)

Bryan-

OK - this is kind of what I was expecting (I'm still trying to get my
head around the graph theory - but that's an effort for another day).

For my own info, what does 'Dag' stand for? =A0I'm assuming that 'Tx'
stands for transaction?

Anyway, the centralized TxDag object is beginning to take on the role =
of
a centralized lock manager - from a development perspective, I
definitely see where keeping these concerns separated is desired -
definitely don't change that. =A0But as a consumer of the library, I =
guess
I'm expecting to see an interface that allows me to use locking without
having to get my hands dirty with exactly how the locking is taking
place.

What I'm envisioning is that this just becomes part of the layering of
the architecture. =A0The lock manager becomes a layer that ties the
locking queues, deadlock detection system, etc... together into a
cohesive whole that the rest of us can use transparently. =A0I'm still =
not
certain that having a separate 'lock manager' is the best way to go
about achieving this - but I'm leaning in the direction of wanting to
keep the details of the locking system separate from the resources that
are actually being locked.

I'm also trying to think about how this all plays with optimistic
locking - I haven't done enough reading into techniques in this area -
is it sufficient to just compare read and write sets for transactions,
or is this something that can be done using the exact same lock
sub-system interface, just with different behavior (i.e. instead of
blocking, it would be non-blocking, and it would capture meta data that
could be used for optimistic conflict detection during commit).

If the same interface could be used, then it makes for a very elegant
solution - the lock manager can be swapped out quite easily.

Did you ever find some resources you were happy with on optimistic
locking implementation strategies?

Thanks!

- Kevin

=A0
=A0=A0=A0=A0>=20
Kevin,=20

Deadlock detection is handled by the TxDag class in the same package.
The TxDag class maintains a directed acyclic graph of WAITS_FOR edges
induced by transactions waiting on locks for resources. =A0The Queue =
class
constructor requires a TxDag instance as one of its parameters, and all
Queue instances for the same database should use the same TxDag
instance. =A0TxDag implements the online deadlock detection algorithm
described by Bayer and provides atomic updates when multiple edges need
tobe added at once =A0if adding those edges would result in a cycle, =
then
no changes are made and a DeadlockException is thrown out of
TxDag.addEdges() and out of Queue.lock(), which calls TxDag.addEdges(). =


The TxDag class is based on an in memory boolean[][] matrix W to store
the edges and an in memory int[][] matrix M to store the data computed
by the deadlock detection algorithm (the closure of the WAITS_FOR
relations is maintained as path counts between vertices of the graph).
A vertex corresponds to a transaction. =A0Transactions are =
automatically
assigned row/column indices as edges are added to the graph. =A0When a
transaction completes, the application must invoke TxDag.removeEdges(
Object tx, waiting :=3D false ). =A0This removes all edges involving =
that
transactions and also reclaims the index assigned to that transaction.
Other than that, the TxDag is maintained automatically by the Queue
objects. =A0=A0Only the rows and columns in M that correspond to =
vertices
with at least one edge ( x WAITS_FOR y ) are actually used in the
computation, so this minimizes the overall cost of updating the =
closure.


Given that deadlock detection is being handled through coordination
across Queue instances using a shared TxDag instance, how does this
change the design?=20

-bryan=20


From: =A0<mailto:jdb...@li...>
jdb...@li...
<mailto:jdb...@li...>
[mailto:jdb...@li...] On Behalf Of Kevin
Day
Sent: Tuesday, March 28, 2006 2:23 PM
To: JDBM Developer listserv
Subject: re[10]: [Jdbm-developer] 2PL: transactions, threads and lockin
g (rese nd!)=20


Bryan-=20



It may very well be that we don't need a lock manager - but I'm not
clear on how we can do deadlock detection if there isn't some sort of
central repository of locks... =A0I think this is where the Queue get()
call comes in in the code segment you wrote?=20



I'm not entirely sure of how a user of the locking subsystem would get
the queue for the resource that is being locked - or is there some =
other
mechanism that you had in mind that I'm not intuiting? =A0Or was the =
idea
to have the resource itself hold a reference to it's own queue?=20



That pushes the requirement for recid -> object mapping out of the
locking sub-system, which may be desirable (otherwise, as you describe,
you wind up with weak hash maps all over the place) - but it tightly
couples the locking subsystemwith the resource design. =A0This could be
problematic if we want to have optimistic locking vs 2PL, etc... =A0I'm
not sure...=20



Maybe the record manager itself needs to hold meta data about a given
record (including it's resource queue)?=20



These are architectural decisions that I think it's time to start
digging into.=20



- K=20





=A0


> Resend as plain test to get around the listserve message size limit.
-bryan

________________________________________
From: Thompson, Bryan B.=20
Sent: Tuesday, March 28, 2006 12:32 PM
To: 'Kevin Day '; ''JDBM Developer listserv ' '
Subject: RE: re[8]: [Jdbm-developer] 2PL: transactions, threads and
lockin g
(rese nd!)

Kevin,

There seems to be an API mismatch still. =A0There is no single "lock
manager",
rather there is a queue per resource. =A0It seems that we need to =
deepen
our
examples a little bit so that we can show the relationship between =
these
things. =A0Let me just focus on the fetch operation for a minute.

void DATA fetch(recid){
=A0=A0=A0lockMgr.assertCurrentTransaction(this); // this will throw an
exception
if the current tx for the thread is not 'this'
=A0=A0=A0lockMgr.lock(recid, READ);
=A0=A0=A0// do actual fetch
}

If I accept this as written, then I would infer:

lockMgr.lock( long recid, mode )
{
=A0=A0Object transaction =3D getCurrentThreadTransaction(); // error if =
not
defined.
=A0=A0Queue queue =3D get( recid ); // creates queue if none exists for =
that
resource
=A0=A0queue.lock( transaction, mode ); // blocks if lock not available;
error
if deadlock would result.
}

Note that lockMgr.get( long recid ) should use a weak value hash map so
that
we can GC Queues for resources that are no longer in use. =A0If we =
don't
do
this then we will swiftly run out of memory.=20

The thread that would block is the thread in which lockMgr.lock is
invoked.=20
The synchronization logic inside of Queue.lock() needs to operate on
threads, so Queue would need to track the thread in which lock() was
invoked
for each request that blocked. =A0This is required in order to =
notifyAll()
the
thread when the lock is available. =A0The rest of the queue state (the
granted
group and pending requests queue) and the state for the deadlock
detection
algorithm (TxDag) can be based on transaction objects.

Given that the thread associated with a transaction may not change =
while
that transaction is blocked, how are you going to enforce that at the
lockMgr level? =A0There are many, many possible Queue instances. =A0You
would
need to know whether or not the transaction was blocked in any Queue
instance. =A0Are we going to use a thread local variable for that as =
well?
If
so, it seems that this would have to be set by Queue.lock().

-bryan=20
<
=A0=A0=A0=A0
------------------------------------------------------- This SF.Net
email is sponsored by xPML, a groundbreaking scripting language that
extends applications into web and mobile media. Attend the live webcast
and join the prime developer group breaking into this new coding
territory!
http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D110944&bid=3D241720&dat=3D=
121642
_______________________________________________ Jdbm-developer mailing
list Jdb...@li...
https://lists.sourceforge.net/lists/listinfo/jdbm-developer

<



-------------------------------------------------------
This SF.Net email is sponsored by xPML, a groundbreaking scripting =
language
that extends applications into web and mobile media. Attend the live =
webcast
and join the prime developer group breaking into this new coding =
territory!
http://sel.as-us.falkag.net/sel?cmd

<