Lock Cookie

[Daniel Simpson]

Here is my lock method in my interface:

/**
     * Locks a record so that it can only be updated or deleted by this client.
     * Returned value is a cookie that must be used when the record is unlocked,
     * updated, or deleted. If the specified record is already locked by a different
     * client, the current thread gives up the CPU and consumes no CPU cycles until
     * the record is unlocked.
     *
     * @param recNo takes an <code>int</code> representing the record number
     * @return A <code>long</code> representing a cookie that must be used when
     * the record is unlocked, updated, or deleted
     * @throws RecordNotFoundException Indicates specified record does not exist or
     * is marked as deleted in the database file
     */
    public long lock(int recNo) throws RecordNotFoundException;

I am planning on using a map for key-value pairs representing the record # and lock cookie, respectively. My question is when I call lock, what type of number should be returned? A random number? One that is incremented? For those who have had success in their locking techniques, what did you do? Thanks!

[Dieskun Koper]

Hi Daniel,

The API seems to leave it up to you. What are you considering to return? Why?

Regards,
Dies (waiting)

[peter wooster]

Originally posted by Daniel Simpson:
I am planning on using a map for key-value pairs representing the record # and lock cookie, respectively. My question is when I call lock, what type of number should be returned? A random number? One that is incremented? For those who have had success in their locking techniques, what did you do? Thanks!

I simply increment a counter in the lock manager. This guarantees that the cookie will be unique for a considerable amount of time. (4 years if the lock attempts were every millisecond). Random numbers might be better if you are concerned about a user trying to hijack another user's lock, but that is not a requirement and the random number can repeat quickly.

[Andy Zhu]

I used a record id as a cookie. Basically, this id is a counter (for both regular and deleted records). Since in my assignment I don't have a field for id (B&S 2.2.2), I decided to use a cache technique so that I can apply the id to the data and also serve as the cookie. So far, my testing program on locking mechanism on my finished project doesn't show any problem with this arrangement. I also would like your opinion on this cookie management.

As I understand, the use of cookie is to identify the record, rather than the thread/client, if your locking mechanism is correct. Therefore, use of a record id as a cookie is perfect; I don't see how a random number can play here.

[Daniel Simpson]

Yeah, I lean towards Andy's implementation on this. I think it would be okay to return the record number as the lock cookie. Thanks for the help!

[Anton Golovin]

Hi, Andy. It's a great and elegant idea, but it defeats the purpose of having a cookie in the first place - every thread can request a record number, and if it became known that the record number is the cookie, there could be security issues...

[Jared Chapman]

I used a static instance of Random, shared by all clients, to generate a random long value to be used as a lock cookie.

Check out the following method from java.util.Random:

public long nextLong() - Returns the next pseudorandom, uniformly distributed long value from this random number generator's sequence. The general contract of nextLong is that one long value is pseudorandomly generated and returned. All 2^64 possible long values are produced with (approximately) equal probability.

Theoretically, it is possible that this implementation could return two equal values to two different clients and create a security issue. But taken in context, where there will be a relatively small number of users, a 1 : 2^64 chance is acceptable IMO.

As I understand, the use of cookie is to identify the record, rather than the thread/client, if your locking mechanism is correct. Therefore, use of a record id as a cookie is perfect; I don't see how a random number can play here.

I understand it to mean recNo identifies the record, and lockCookie identifies the owner of the lock on that record. But then again, I haven't passed yet.

[Matt Sheehan.]

Originally posted by Anton Golovin:
Hi, Andy. It's a great and elegant idea, but it defeats the purpose of having a cookie in the first place - every thread can request a record number, and if it became known that the record number is the cookie, there could be security issues...

I would argue that using the record number is the simplest way to generate a unique cookie for each record and that security issues involving the cookie are probably beyond the scope of the assignment.

Matt

[Daniel Simpson]

Originally posted by Anton Golovin:

Hi, Andy. It's a great and elegant idea, but it defeats the purpose of having a cookie in the first place - every thread can request a record number, and if it became known that the record number is the cookie, there could be security issues...

Originally posted by Matt Sheehan.:


I would argue that using the record number is the simplest way to generate a unique cookie for each record and that security issues involving the cookie are probably beyond the scope of the assignment.

Anton brought up a good point, but I do agree with Matt that security issues as such are beyond the scope of what the assigment requires. In later implementations, I can see how that could be dangerous. I think for this project however, either using a random long or the recNo should be sufficient.

[Ben Zung]

I agree with Jared. I used Random. And the cookie is checked against the existing ones to ensure the uniqueness -- an overhead, yes but if it is in reality, it probably worth it.

Ben

[Jan Groth]

hi there,

i built a cookie factory (one per application) which returns a long value, which is a composition from date-time and a incremental number. so i get the extra information of when the VM was started...

example:
200411300000000001
200411300000000002
...

not a big deal, but i'm thinking that security measures (like cookie hijacking) is definitly not an issue for good old Bodgitt & Scarper ;-)

greets,
jan

[Anton Golovin]

I agree with you guys. When I read Andy's idea, though, it is a very good solution, but only for this implementation. For future implementations, in theory, it should be revised. I would put this into the comments.

It's also an elegant solution. But one should document it.

[Matt Sheehan.]

A compromise would be to break the cookie up into two parts, a random number and the record number. Like this:

private long getLockCookie(int recordNo) {
    long cookie = random.nextInt();
    cookie <<= 32;
    cookie += recordNo;
    return cookie;
}

Then you have a security of a random number without having to worry about duplicates for different records.

[Andy Zhu]

Hey, guys:

I didn't know my posting bring such a discussion in the past days.
First, Mat: don't do this. your compromised implementation is wrong:
record a: 1, rand = 33, cookie: 34
record b: 11, rand = 23, cookie: 34
You know what's going on.

Anton, you did bring a potential issue to my suggested solution. I would like to know: why this is not generalizeable.

Let's go back to the original, to see if my solution is justifiable. Here is the specifications for the relevant locking mechanism (I am a foreigner so if my understanding is wrong, please point me out):

// Locks a record so that it can only be updated or
// deleted by this client. Returned value is a cookie
// that must be used when the record is unlocked,
// updated, or deleted. If the specified record is
// already locked by a different client, the current
// thread gives up the CPU and consumes no CPU cycles
// until the record is unlocked.
public long lockRecord(long recNo)
throws RecordNotFoundException;

// Releases the lock on a record. Cookie must be the cookie
// returned when the record was locked; otherwise throws
// SecurityException.
public void unlock(long recNo, long cookie)
throws SecurityException;

As we can see from above specs: a cookie is to serve 2 purposes:
a. identify the client;
b. identify the record.

Now, can I prove my solution correct? If one implements the locking mechnism correct, then:
1. At any time, only one client can get a lock, no matter singleton or multiton; (otherwise, I guarrentee you are in trouble ); so if the cookie itself, which is generated when the client obtains its lock, is unique, then the client can be uniquely identified: point a proved.
2. no matter singleton or multiton (see my other posting summerizing locking mechanism a couple of thread before), record id is unique: proved b.
3. The unique record id is returned to client in lockRecord as a cookie: proved assumption in point 1.

Therefore, I proved the correctness of my cookie scheme. Is there any hidden assumption (pertaining to this scjd project)? Yes:

the client uses the cookie to operate on only the VERY ONE related record. if it operates on several records, locking fails. Is this satisfied in scjd. You know what I am talking about: Sun's api guarranttees.

Anton: is this what you mean generalizeable? I don't know whether and how oracle or udb handle mutliple records operation simultaneously at the access layer. But I think for a legitimate software dealing with one-table database, this scheme should be standable. Even for multiple tables, small modification still makes it work. The key here is that a correct locking guaranttees a unique cookie for a single client, and a record id is unique.

Now, if one understands, the issue itself may not be a cookie; it is how one implements locking.

Comparison to the other proposed random cookie scheme: if peter calculated correctly, I have a guarantteed unique id for quite some years; In the same amount of time, random scheme issues a statistically expected unique id.

So far, I don't have a client queue as some one suggested. I don't see in my locking scheme there is a need for this queue. I think this queue is served in random scheme. From my proofs, it is easy to prove that random needs extra work to guaranttee the uniqueness.


Remarks: Sun, please don't mark me down if I just cut and paste this information in my scjd documentation which I am writing .

Thank you for going with me for this lengthy reasoning. And, any comments are welcomed.

Just missed the addressing of so mentioned security issue. First, it is a potential issue, although Sun is quiet about it now. Second, I propose a suggested mod: use a random number for the first record. Combine this method with my category 2 (in my other thread: revisiting role of ....) locking level.
[ December 02, 2004: Message edited by: Andy Zhu ]

[ December 02, 2004: Message edited by: Andy Zhu ]
[ February 15, 2005: Message edited by: Andy Zhu ]

[Matt Sheehan.]

Originally posted by Andy Zhu:

First, Mat: don't do this. your compromised implementation is wrong:
record a: 1, rand = 33, cookie: 34
record b: 11, rand = 23, cookie: 34
You know what's going on.

That would be the case if not for the bit shift. The random int is shifted to the left 32 bits and the right 32 bits is the record number. This allows for random numbers but ensures that different records cant ever have the same cookie value.

What you get is:
record a: 1, rand = 33, cookie: 33 * 2 ^ 32 + 1
record b: 11, rand = 23, cookie: 23 * 2 ^ 32 + 11

[Andy Zhu]

Hey, Mat: sorry I didn't read your code carefully. But, in my assignment, recNo is a long. How about yours?

[Matt Sheehan.]

Originally posted by Andy Zhu:
Hey, Mat: sorry I didn't read your code carefully. But, in my assignment, recNo is a long. How about yours?

In mine the cookie was a long and the record number was an int. Anyway, I submitted mine a few weeks ago and I just used the record number.