home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / CONTRIB / MBASE / MBASE51.TAR / mbase51 / tech / chapter.6 < prev    next >
Encoding:
Text File  |  1993-09-04  |  12.3 KB  |  238 lines
  1. Tech Chapter 6 - Locking                                          MetalBase 5.1
  2. -------------------------------------------------------------------------------
  3.  
  4.  
  5. Because MetalBase does not run on a client/server basis (there is no huge
  6.    superuser-running program which performs queries when requested), processes
  7.    must fight each other for access to relations.  In order to ensure database
  8.    integrity, a system of locking has been implemented which provides a timing
  9.    for enlarging atomic-level operations; those which should be accomplished in
  10.    their entireity before another process may use the relation.  *nix-style
  11.    file locking is not portable enough to be useful here, much to my dismay...
  12.    many sites don't have any such ability through the standard compiler; worse,
  13.    on some systems (Xenix among them), calls succeed but they don't do
  14.    anything.
  15.  
  16. Version 5.0 and above support two forms of locking, one of which is transparent
  17.    and used by the system internally, the other being exposed to the user.
  18.    "Temporary locks" are placed by the system to enlarge the timescale of
  19.    atomic operations, to ensure concurrent querying/updating will not corrupt
  20.    the database.  These locks are placed on the relation automatically, during
  21.    all operations--adding, updating, deleting, and querying the database, as
  22.    well as in the process of allowing the user to place the more permanent
  23.    exclusive locks.
  24.  
  25.  
  26. TEMPORARY LOCKS ---------------------------------------------------------------
  27.  
  28.  
  29. Temporary locks are used to give a single process control over a relation for
  30.    a short period of time, from a fraction of a second (needed at the beginning
  31.    of a service call to ensure no exclusive lock is in place) to a few seconds
  32.    or more (for the duration of an index update).  The basic algorithm relies
  33.    on the fact that each process has a unique identifier in the range 0-65535;
  34.    MetalBase 5.1 uses the process ID for this.  In essence, each relation
  35.    stamps its identifier into a specific place in the relation, and reads back
  36.    what is there--if it reads its own process ID, it continues with its work,
  37.    leaving the stamp (and thus a temporary lock) in place.
  38.  
  39. That is a far oversimplified version.  In reality, because of the way most
  40.    multi-user systems work, a scheme with only one such check will always grant
  41.    a lock to any relation; the write-our-PID followed by read-the-byte will
  42.    almost always return the PID simply because the write and read are so close
  43.    together that they are almost guaranteed to be processed in sequence,
  44.    without allowing other processes to vie for the lock.  There is also the
  45.    issue of a process having terminated, leaving a temporary lock in place; in
  46.    that case, the relation would be useless until such a lock could be cleared.
  47.    Moreover, in practice, such a scheme would give control to the same process
  48.    over and over, not allowing any other process a chance to work (in
  49.    benchmarks, three terminals running the same program to add records
  50.    constantly over 30 seconds ended up with results of the form: 1st==500
  51.    records, 2nd==2 records, 3rd==0 records).
  52.  
  53. The first problem is the granting of a temporary lock to one process at any
  54.    given time--this is done by iterating the check described above three times:
  55.  
  56.      set_hack(): read the three hack-lock positions (6 bytes)
  57.                  if our PID is in any, write a zero there and goto set_hack()
  58.                  if all three aren't zeroes, goto set_hack()
  59.                  write our PID in the third
  60.  
  61.                  read the three hack-lock positions
  62.                  if first and second aren't zeroes, goto set_hack()
  63.                  if third isn't our PID, goto set_hack()
  64.                  write our PID in the second
  65.  
  66.                  read the three hack-lock positions
  67.                  if first isn't zeroes, goto set_hack()
  68.                  if second and third aren't our PID, goto set_hack()
  69.                  write our PID in the first
  70.  
  71.                  read the three hack-lock positions
  72.                  if any of the three aren't our PID, goto set_hack()
  73.  
  74.      clr_hack(): read the three hack-lock positions (6 bytes)
  75.                  if all three aren't our PID,
  76.                     (error case 1--abort)
  77.                  write zeroes in all three
  78.  
  79. Iterating the process in this fashion shrinks the window for a race condition
  80.    to such an extent that it's negligible... and that solves the first of the
  81.    three problems.  The second would be distribution of resources; as the
  82.    example above, just letting them take their chances doesn't cut it.  To
  83.    more evenly distribute access to a relation, a hack lock, as described
  84.    above, is used to gain access to a thirty-position queue, of the form:
  85.  
  86.  elcks hacklocks  queue
  87.   [ ]   [ | | ]   [ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ]
  88.  
  89. The leftmost position in the queue is position #0, indicating a temporary lock
  90.    is in place.  Once a relation has gained control via a hack lock, it reads
  91.    the 60 bytes of queue and finds the first empty slot (denoted by a 0 PID).
  92.    It then places its own PID in that position and clears the hacklock for any
  93.    other process to use.  If the position found free is #0, it has just placed
  94.    a temporary lock and the process can go about its service.  Otherwise, the
  95.    process will enter the following loop:
  96.  
  97.              A: read queue position (CURPOS -1)
  98.                 if non-zero, go to A
  99.                 write our PID in position (CURPOS -1)
  100.                 write zero in position (CURPOS)
  101.                 CURPOS -= 1
  102.                 if (CURPOS == 0)  break -- temporary lock is in place
  103.                 otherwise, goto A
  104.  
  105. This loop works without placing hacklocks before reading because exactly one
  106.    process is guaranteed to be reading a position in the queue at any given
  107.    time, and the free space will bubble from the left to right as temporary
  108.    locks are freed*.  Note that if a position in the queue can't be found to
  109.    start with, the system will return MB_BUSY.  This method ensures equal time
  110.    for equal requests, for up to thirty processes simultaneously; note that
  111.    many more processes can be run at once on a relation, but only thirty
  112.    queries will be serviced at any time.  This is an extremely reasonable
  113.    restriction.
  114.  
  115.     * this is almost correct; extremely quick operations may happen so quickly
  116.       that holes can develop in the queue while other processes haven't yet
  117.       taken over the next available slot.  The handling of these 'queueholes'
  118.       is described in the source code in mb_lock.c; the essence of the
  119.       algorithm is that we busywait until the holes disappear.
  120.  
  121. The third and final problem with regard to locking is the most nerve-wracking;
  122.    if a process dies leaving a lock in place, other processes would wait
  123.    forever for the lock to be cleared.  Originally, the BLAST utility (replaced
  124.    by MBDIAG) was the only way to remove these locks; pre-release 5.0 was able
  125.    to detect this condition under some circumstances, but it was too flaky to
  126.    rely upon.  In essence, since inter-process communication is a no-no for
  127.    portability, MetalBase needed a way to determine if a process were still
  128.    active or not...  to that end, the temporary-lock queue has been equipped
  129.    with a strobe byte for each position:
  130.  
  131.  elcks hacklocks  queue
  132.   [ ]   [ | | ]   [ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ]
  133.                   < : : : : : : : : : : : : : : : : : : : : : : : : : : : : : >
  134.                   strobes
  135.  
  136. Whenever a process is either waiting in the queue for a turn, or when a process
  137.    has a temporary lock in place and is querying or updating the database, it
  138.    is constantly incrementing a byte found in the current lock position's
  139.    strobe... to be exact, within the queue, the strobe is changed every second;
  140.    within a query, whenever the depth is a multiple of 5; within an update,
  141.    at various locations initially followed by a call at every _balance() call.
  142.    If a process waiting in the queue finds that ten seconds go by without
  143.    a strobe being changed, it determines itself justified in taking over the
  144.    position, under the assumption that the old process is dead.  Note that
  145.    this approach will not work well with DOS networks, which often bring long
  146.    lag-times which would destroy concurrency... not always, but often enough
  147.    to worry about.  IPC would be the best way to improve this, but there is
  148.    no standard which does not require superuser access and device drivers on
  149.    any *nix platform, and that's unacceptable for MB.
  150.  
  151. When jockying for a hacklock, if three seconds elapse without a request being
  152.    accepted, a process will erase all three bytes and try again.  If a process
  153.    halts with an exclusive lock in place (mb_rmv(), mb_exit() and mb_die()
  154.    remove any locks before closing, so that's not a problem--the process must
  155.    be halted by a signal or power cycle), the exclusive lock must be removed
  156.    with MBDIAG before the relation will be useful again; exclusive locks will
  157.    not be cleared automatically, as we cannot force the user to strobe a byte
  158.    every second while it is in place.
  159.  
  160.  
  161. EXCLUSIVE (RELATION-WIDE) LOCKS -----------------------------------------------
  162.  
  163.  
  164. An exclusive lock is placed by a user using mb_lck(), and removed with mb_unl()
  165.    [these two functions were forgotten in the 4.0 release--sorry].  Once an
  166.    exclusive lock is placed, any action requested by another process will fail
  167.    with the error MB_LOCKED, until the lock is removed.
  168.  
  169. The flow for mb_lck() and mb_unl() are as follows:
  170.  
  171.    mb_lck():  set temporary lock on relation
  172.               read exclusive-lock PID
  173.               if (PID == ours)  clear temp lock; stupid--you already locked it
  174.               if (PID != 0)     clear temp lock; return MB_LOCKED by another
  175.               write our PID in the exclusive-lock byte
  176.               clear temp lock; return MB_OKAY
  177.  
  178.    mb_unl():  set temporary lock on relation
  179.               read exclusive-lock PID
  180.               if (PID == ours)
  181.                  write 0 there
  182.               clear temp lock; return MB_OKAY
  183.  
  184. This simple procedure is sufficient, because all requests of the relation must
  185.    pass the following check before operating (a temporary lock must be in place
  186.    before calling this routine):
  187.  
  188.    _chk_elck(): check exclusive-lock PID
  189.                 if (PID != 0 && PID != ours)  return MB_LOCKED
  190.                 return MB_OKAY
  191.  
  192. These routines are slightly more complicated in the source, because there is
  193.    a bit of duality of information--each relation structure also retains flags
  194.    indicating whether the relation is temp-locked and/or exclusive-locked.
  195.    There are more failure conditions because of this, which ensures that locks
  196.    will not be placed when they should not be.
  197.  
  198.  
  199. EXCLUSIVE (RECORD-LEVEL) LOCKS ------------------------------------------------
  200.  
  201.  
  202. There are none in MetalBase 5.1--let me know if you need this, so I'll know
  203. what to spend my time on.  It'll be in a later version--just a matter of when.
  204. That, by the way, is what the 128 bytes in the .REL-file header are reserved
  205. for.
  206.  
  207.  
  208. LOCKFILES ---------------------------------------------------------------------
  209.  
  210.  
  211. The kind of work described above--all the busyloops and so forth--really,
  212.    really slow down access to a relation... the fewer things a file is doing at
  213.    any given time, the more you can get accomplished.  So the locking mechanism
  214.    has been moved off to a separate file, named after the relation (with the
  215.    extension replaced with ".LCK") and placed in a temporary directory (see the
  216.    troubleshooting documentation, under MB_TMPDIR).  This file is created
  217.    every time mb_inc() is called, if it does not already exist.
  218.  
  219. There is exactly one lockfile for each relation, kept in a common temporary
  220.    directory.  You can delete the lockfile at any time, as long as you're sure
  221.    there is no one using the relation at the time (this would be a Bad Thing to
  222.    delete if the relation is in use).  Deleting the lockfile will erase any
  223.    remaining exclusive lock, and reset the number of users on the relation to
  224.    zero.
  225.  
  226.  
  227. LOCKFILE FORMAT ---------------------------------------------------------------
  228.  
  229.  
  230. Pos  #/Bytes   Description
  231.  
  232.   0   2.......Unused as of MetalBase 5.1
  233.   2   2.......PID of exclusive lock, 0 == none
  234.   4   6.......Three hacklock PIDs (see lock.dox)
  235.  10  60.......Thirty temporary-lock queue positions (see lock.dox)
  236.  70  30.......Thirty temporary-lock strobes (see lock.dox)
  237.  
  238.