NX: File Consistency

[Javini Javono]

Hi,
I've decided to implement record locking, because it could be
that even if it is not necessary (the businsess might only have
4 clients), it probably is in the exam if for no other reason
than to exericise our knowledge of multi-threading,
wait, and notifyAll.
For this question, assume that you are using a physical
random access file, and that the file is not stored in memory.
As pointed out in different posts in the past, the following appears
to be true, but keep in mind that I am not talking about the
actual objects and methods Sun requires; instead, I'm talking
about concepts mostly. It's quite possible that considering
Sun's ambiguous statements makes the project appear far
more complicated than it really is. Thus, if we for a minute
ignore the Java interface and required classes and methods
Sun provides, we can create a simple, if crude, workable
and logically correct model.
This summary does not pretend to be the only way to do things,
but it is the minimal way to do things correctly without
corrupting the file (that is, it may not be fastest, the smartest,
and the like).
My summary may contain errors since I am a greenhorn:
I.
Reads and writes to the random access file cannot be multi-threaded,
so at a low level, you need one singleton object where each method
is synchronized:
public synchronized void write(long recordNumber, String data) {}
and only this singleton object talks to the random access file.
Call this class FileTalk. It also has a read() method. It may have
other low-level methods; but again, every method must be
synchronized. You want these methods to be low-level so that
they do their work quickly; in fact, it could be stated that this
class literally locks the complete database; that is why it must
have elementary methods and not complex ones.
II.
Above FileTalk, you have a multithreaded object called BusinessTalk,
and it holds one reference to the FileTalk singleton. Thus, for instance,
at any given point in time, any single method in BusinessTalk could
be servicing multiple threads.
Pretend, for a moment, that BusinessTalk is a servlet, for those who
know more about servlets than they know about RMI. A servlet
can be instantiated one or more times, and each instantiation can
be multi-threaded. As long as BusinessTalk is thread safe, and
alll instances of BusinessTalk run within the same JVM, and as
long as there is only one FileTalk class (and one Locks class),
we should not run into any problems. In a sense, I suspect
that in RMI, BusinessTalk could be instantiated more than one
simultaneously and certainly each instantiation could be multi-
threaded.
III.
To implement locking, we will define a Vector called Locks
(again, may not be the most efficient, but I'm only
considering concepts at this point). The
length of the Vector will be equal to the number of logical records
in the file. For simplicity, we will assume that the size of the file
never changes. Each element of the vector contains a unique Object
reference. The Object reference is only used to implement locking
using wait() and notifyAll(). There can only be one Vector locks,
so we'll make it a singleton.
IV.
It may not be necessary to implement locking when the business operation
simply consists of reading one record. But, let's consider this case because
it is the simplest case within the BusinessTalk class.

public String read(long recordNumber) {}
   while (locks[recordNumber] is not being used by any other thread) {
      returnedString = fileTalk.read(recordNumber);
      break;
   } else {
      locks[recordNumber].wait();  //Wait for record to be unlocked by another thread.
   }
   //We are done, so notify any waiting threads waiting for this
   //particular record to be unlocked.
   locks[recordNumber].notifyAll();
}

I've never written code using wait() and notifyAll(), but I've seen its
used in books; the above example may be completely wrong as
far as talking to the Java interpreter (or the compiler); but, conceptually,
it shows how things would work, and how they use an Object
which is associated with a particular file record as the locking
mechanism. Thus, five threads could be hitting this method at once:
2 threads asking to read record 100, 1 thread asking to read record 101,
and one thread asking to read record 102, and they can all co-exist
within this method without messing anything up.
V.
Now, let's consider another business case; this case involves three steps:
1. Read a record in the file.
2. Undergoing a long computational step.
3. Writing to the same record.

public void longComputation(long recordNumber) {
   String information = this.read(recordNumber);
   information = doLongComputation(information);
   this.write(recordNumber, information);
}

And, without doing much work, we have shown that we can
use the simpler methods of this class to read, continue
in our own thread to do a long computation without
stopping other threads from proceeding, and then
finally write out our information.
[Note: the write method may need checks to make sure
that in the intervening moments the record is still
"the same" record we thought it was; but, that starts
to get into details, though they are important details.]
VI.
So, from a conceptual standpoint, and disregarding
the nuts and bolts (exceptions, correct calls and correct
form with respect to using wait() and notifyAll(), and
a whole host of other issues which are waiting behind
the scenes), this simple model, suggested by another
post, seems quite sufficient (if not elegant).
VII.
The only thing left to consider--again mentioned in
other posts, as I am not that familiar with the
knitty-gritty rules of implementing a database--
is that the BusinessTalk class must be logically correct.
This would involve an investigation of looking
at every case carefully, to ensure that no other
thread has come in and "surprised" you. Thus,
in the above example in Section V, while the
long computation is occuring (or just even between
the two calls to read() and write()), the state of the
record or records you were working with could
have changed. This involves finding other solutions,
and on this part I now speculate as I have no
experience in these matters:
1. Involves, as stated in another post, how to logically
assemble a system where simultaneously operating
threads using the business methods of
BusinessTalk act as if all the BusinessTalk
methods were each synchronized. Does anyone know of
on-line resources discussing this theory in more more
detail or of books discussing these ideas?
2. Possibly might involve the concept of "lock hierarchies".
Here I'm speculating, but, for instance, in the BusinessTalk
method called longComputation(), you might change the
hierarchy of the locking mechanism (that is, use wait()
and notifyAll() within the longComputation() method itself,
and perhaps or perhaps not use it within the simpler
read() and write() methods since you already have the lock;
but, I'd need to think about this further.
Conclusion
---------
The above represent what I have learned at this web site
on a topic I knew little about. The information may be
wrong, but please feel free to correct it.
Further Iterations
---------------
Assuming that one uses the crude model above to create
an application which meets the functional requirements
(what needs to be done, not how), then one can be proud
for mastering the techniques involved.
However, based upon other posts, one could be automatically
flunked if you don't, to whatever degree actually exists,
exactly use the interfaces and classes as Sun requires (assuming
that you can figure out what Sun requires .
Thus, one way to proceed is to use a crude model such as
outlined above to create a logically correct application;
and, you would have tested the application. This is probably
where the real learning experience is and where the hardest
problems will have to be solved.
The next step would be to now say, "okay, how can I still
maintain a logically correct application and satisfy what
could be considered unusual or bad implementation
details imposed upon me by Sun." This is the iterative
approach; you first solve the core problem, and then
you solve a less complex problem, that of reorganizing your
classes and methods to satisfy Sun's demands. Some
people are smart enough to two both these iterative
steps at once; however, if this topic is completely
new to you, you might be advised to do one iterative
step at a time. Essentially, satisfying Sun's demands
is more like a short-term puzzle: it probably is not
too complicated. But, if you try to solve both Sun's
puzzle and the core issues simultaneously, you might,
perhaps, get overly confused or bogged down, or worse,
be so side-tracked by Sun's prematurely introduced
implementation details that you miss a core point in this
learning experience.
Thanks,
Javini Javono
[ January 09, 2004: Message edited by: Javini Javono ]

[Andrew Monkhouse]

Hi Javini,
In general that seems reasonable. Now for some nitpicking:

Reads and writes to the random access file cannot be multi-threaded,
so at a low level, you need one singleton object where each method
is synchronized:

At a low level you need one single object - this may or may not be a Singleton.
There are very few occassions when you really need a Singleton. One good question you could ask yourself is "is there any possibility that sometime in the future someone might want to instantiate another instance of this class?". For example is it remotely possible that you might one day have another database table to read, so you might want to have another instance of your database file reader? If the answer is yes, then you probably do not want to have a Singleton.

Call this class FileTalk. It also has a read() method. It may have other low-level methods; but again, every method must be synchronized.

It may not be necessary to have every method synchronized.
Consider for a moment the "read" method. You might decide to do several operations inside that read method:

// check that the record number is valid
// seek to the file position
// read the record
// break the record into fields
// convert the fields from bytes into Strings

How much of that really needs to be synchronized? I think only steps 2 and 3. So in this case, the read() method may not need to be synchronized, but it will either contain a synchronized block, or it will call a private synchronized method.
Of course you may decide to move those other operations out to your BusinessTalk class, in which case I withdraw my objection.

To implement locking, we will define a Vector called Locks (again, may not be the most efficient, but I'm only considering concepts at this point).

If I may make a suggestion - if you are only considering concepts, then you may find it better to talk about "a Collection called Locks". That way you will not get people arguing about which is the best collection and/or arguing that you should never use Vectors.

      locks[recordNumber].wait();  //Wait for record to be unlocked by another thread.
   ....
   locks[recordNumber].notifyAll();

If you are waiting / notifying on the object within the Collection, and using that object as your indicator that the record is locked, then that object will have to be a mutable object. This means that you cannot use Boolean as your object, as it is immutable.

Now, let's consider another business case; this case involves three steps:
1. Read a record in the file.
2. Undergoing a long computational step.
3. Writing to the same record.

public void longComputation(long recordNumber) {
   String information = this.read(recordNumber);
   information = doLongComputation(information);
   this.write(recordNumber, information);
}

And, without doing much work, we have shown that we can use the simpler methods of this class to read, continue in our own thread to do a long computation without stopping other threads from proceeding, and then finally write out our information.
[Note: the write method may need checks to make sure that in the intervening moments the record is still "the same" record we thought it was; but, that starts to get into details, though they are important details.]

Ahhh, but this is where you need the locking - not down at the read() level.

public void longComputation(long recordNumber) {
   lock(recordNumber);
   String information = this.read(recordNumber);
   // confirm this record is what we think it should be
   validate(recordNumber);
   information = doLongComputation(information);
   this.write(recordNumber, information);
   unlock(recordNumber);
}

Now there is no chance that you are going to do that long computation on a record that has already been booked. And there is no chance that anyone else could have modified the record while you were doing the long computation since you own the lock on that record.
If I may make a suggestion - you may get more responses if you reduce the size and scope of your postings. It takes a lot to read through a post of that size, and many people will not put in that sort of effort. (I personally also prefer to have the browser wrap the lines rather than being forced to accept your line wrapping.)
Regards, Andrew