 |
Claims  |
|
|
We claim:
1. For managing a database of accessible records that contain resources of first and second types, each of a plurality of the resources of the second type being uniquely associated with
a respective resource of the first type, and for providing accesses to the resources in response to implementing instructions of user-requested transactions, a method comprising the steps of:
A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of composite lock modes, which pairs of the composite lock modes are compatible with each other, the lock manager maintaining a lock
table that identifies locked database resources and the composite lock modes in which they are locked, receiving lock requests that designate resources and composite lock modes in which those resources are to be locked, and responding to the lock
requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other transactions on the database
resources that the lock requests designate; and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock
requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped
from the resources of the first and second types that each resource of the second type is mapped to a resource identifier the same as that to which the resource of the first type associated therewith is mapped, the database-access operations implemented
by the instructions of the plurality of transaction routines including a set of operations that includes a plurality of operations of which each requires locks both on at least one resource of the first type and on the resource of the second type with
which it is associated, the lock requests applied to the lock manager by the instructions that implement such a transaction's operations requesting, in the absence of an already existing lock acquired by the given transaction, a composite lock whose mode
is associated with constituent first-resource-type and second-resource-type lock modes whose compatibility sets within a set of constituent lock modes would be sufficient to maintain serializability if the constituent first-resource-type and
second-resource-type lock modes individually locked the resources of the first and second resource types, respectively, on which that operation requires locks, a given composite lock mode being compatible with another composite lock mode if and only if
the constituent first-resource-type and second-resource-type lock modes associated with the given composite lock mode are respectively compatible with the first-resource-type and second-resource-type lock modes associated with that other composite lock
mode.
2. A method as defined in claim 1 wherein the resources of the first type are existing key values contained in respective accessible records and belonging to an ordered sequence of possible key values and the resources of the second type are
key-value ranges, each of a plurality of which extends from the existing key value associated therewith to an existing key value in front of the associated key value.
3. In a method for managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing
key value uniquely associated therewith to an existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, which method comprises the steps of:
A) providing a lock manager characterized by a compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the lock manager maintaining a lock table that identifies locked
database resources and the modes in which they are locked, receiving lock requests that designate resource and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate
whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate; and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock
requests to the lock manager and perform the associated database accesses only if the compatibility indication generated by the lock manager in response to the lock requests is positive, the improvement wherein the compatibility matrix includes at least
eight distinct lock modes.
4. For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value
uniquely associated therewith to an existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a method comprising the steps of:
A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including delete-next range,
insert-next-range, scan, and updated modes and indicating that the delete-next-range mode is incompatible with the insert-next range mode and the scan mode but compatible with the update mode which the compatibility matrix indicates to be incompatible
with the scan mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and
responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other
transactions on the database resources that the lock requests designate; and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock
requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource-identifiers in the lock requests being so mapped
from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of
transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the
given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operation scans;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of an already existing lock acquired by the
given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by
the given transaction, a lock of the insert-next-range mode and including a resource identifier that, before insertion of the record to be inserted, represents the key-value range that encompasses the key value thereof; and
iv) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the
given transaction, a lock of the update mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls,
whereby one transaction's scan of, or insertion of a record into, a key range from which a record has been deleted by another uncommitted transaction can be prevented without preventing the one transaction from updating the record whose key value
is associated with that key range.
5. A method as defined in claim 4 wherein:
A) the compatibility matrix includes a singleton-read mode and an update-scan mode;
B) the database-access operations implemented by the instructions of the plurality of transaction routines additionally include:
i) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing
lock acquired by the given transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read; and
ii) an update-scan operation that scans through key-value ranges and updates records having key values in those ranges, lock requests applied to the lock manager by the instructions that implement the update-scan operations requesting, in the
absence of an already existing lock acquired by the same transaction, locks of the update-scan mode and including resource identifiers that represent the key-value ranges through which the update-scan operation scans;
C) the compatibility matrix includes at least five distinct lock modes IU, IIn, ID, S and SIX, whose compatibility combinations are as follows:
D) the scan and singleton-read modes are both S, and the update, insert-next-range, delete-next-range, and update scan modes are IU, IIn, ID, and SIX, respectively;
E) the instructions that implement the update and update-scan operations apply to the lock manager lock requests that request locks whose modes are incompatible with mode S and include resource identifiers that represent the key values of the
records to be updated by those operations; and
F) the instructions that implement the insert and delete operations apply to the lock manager lock requests that request locks of a mode that is incompatible with mode S and include resource identifiers that represent the key values of the
records to be inserted and deleted, respectively, by those operations.
6. A method as defined in claim 5 wherein lock requests applied to the lock manager by the instructions that implement a given transaction's insert and delete operations request, in the absence of a lock previously acquired by the given
transaction, locks of the IIn and ID modes, respectively, and include resource identifiers that represent the key-value ranges associated with the key values of the records respectively to be inserted and deleted.
7. A method as defined in claim 4 wherein
A) the compatibility matrix includes a singleton-read mode and an update-scan mode;
B) the database-access operations implemented by the instructions of the plurality of transaction routines additionally include:
i) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing
lock acquired by the given transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read; and
ii) an update-scan operation that scans through key value ranges and updates records having key values in those ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's update-scan operations
requesting, in the absence of an already existing lock acquired by the given transaction, locks of the update-scan mode and including resource identifiers that represent the key-value ranges through which the update-scan operations scan;
C) the compatibility matrix includes at least seven distinct lock modes IS-S, IU-X, IIn-, IIn-X, ID, ID-S, ID-X, and S-, whose compatibility combinations are as follows:
D) the singleton-read, update, scan, update-scan, insert-next range, and delete-next-range modes are IS-S, IU-X, S-, ID-X, IIn-, and ID-, respectively; and
E) the instructions that implement the insert and delete operations in a transaction apply to the lock manager lock requests that, in the absence of a previous lock acquired by that transaction, respectively request locks of modes IIn-X and ID-X
and include resource identifiers that represent the key values of the records to be inserted and deleted, respectively, by those operations.
8. For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value
uniquely associated therewith to the existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a method comprising the steps of:
A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix:including delete-next-range,
singleton-read, and scan modes and indicating that the delete-next-range mode is incompatible with the scan mode but compatible with the singleton-read mode, the lock manager maintaining a lock table that identifies locked database resources and the
modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes
designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate; and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock
requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped
from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of
transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan-read operations requesting, in the absence of an already existing lock acquired by
the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operations scan;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of a previous existing lock acquired by the
given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing
lock acquired by the given transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read,
whereby a scan by one transaction of a key range from which a record has been deleted by another, uncommitted transaction can be prevented without preventing the one transaction from reading the record whose key value is associated with that key
range, and whereby deletion by one transaction of a record whose key value is immediately in front of that of an existing key value of a record read by another uncommitted transaction can be permitted without permitting deletion by the one transaction of
a record whose key is in a range that has been scanned by another uncommitted transaction.
9. For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value
uniquely associated therewith to the existing key value immediately in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a method comprising the steps of:
A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including scan,
singleton-read, and insert-next-range modes and indicating that the insert-next-range mode is compatible with the singleton-read mode but is incompatible with the scan mode, the lock manager maintaining a lock table that identifies locked database
resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether
the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate; and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock
requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped
from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of
transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the
given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operations scan;
ii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by the
same transaction, a lock of the insert-next-range mode and including a resource identifier that represents the key-value range that, before insertion of the record to be inserted, encompasses the key value thereof; and
iii) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing
lock acquired by the same transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read,
whereby insertion by one transaction of a record into a key range that has been deleted by another, uncommitted transaction can be prevented without preventing the one transaction from inserting a record into a key range associated with a key
value contained in a record accessed in a singleton-read operation by another uncommitted transaction.
10. For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value
uniquely associated therewith to the existing key value immediately in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a method comprising the steps of:
A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including a singleton update
mode, an update-scan mode, and an insert-next-range mode and indicating that the insert-next-range mode is incompatible with the update-scan mode but compatible with the singleton-update mode, the lock manager maintaining a lock table that identifies
locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that
indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate; and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock
requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped
from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of
transaction routines including at least:
i) an update-scan operation that scans through key value ranges and updates records having key values in those ranges, lock requests applied to the lock manager by the instructions that implement the update-scan operations requesting, in the
absence of an already existing lock acquired by the same transaction, locks of update-scan mode and including resource identifiers that represent the key-value ranges through which the update-scan operation scans;
ii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the
same transaction, a lock of the insert-next-range mode and including a resource identifier that represents the key-value range that, before insertion of the record to be inserted, encompasses the key value thereof; and
iii) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by
the same transaction, a lock of the update-next-range mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls,
whereby an insert by one transaction of a record into a range associated with the key value of a record updated by another uncommitted transaction can be permitted while insertion into a range in which another uncommitted transaction has
performed an update scan is prevented.
11. For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value
uniquely associated therewith to an existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a resource manager method comprising:
A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including delete-next-range,
insert-next-range, scan, and updated modes and indicating that the delete-next-range mode is incompatible with the insert-next range mode and the scan mode but compatible with the update mode which the compatibility matrix indicates to be incompatible
with the scan mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and
responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other
transactions on the database resources that the lock requests designate; and
B) providing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock
requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped
from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of
transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the
given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operation scans;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of an already existing lock acquired by the
given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by
the given transaction, a lock of the insert-next-range mode and including a resource identifier that, before insertion of the record to be inserted, represents the key-value range that encompasses the key value thereof; and
iv) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the
given transaction, a lock of the update mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls, whereby one transaction's scan of, or insertion of a record into, a key range
from which a record has been deleted by another uncommitted transaction can be prevented without preventing the one transaction from updating the record whose key value is associated with that key range.
12. The resource manager method according to claim 11 wherein:
A) the compatibility matrix includes a singleton-read mode and an update-scan mode;
B) the database-access operations implemented by the instructions of the plurality of transaction routines additionally include:
i) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing
lock acquired by the given transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read; and
ii) an update-scan operation that scans through key-value ranges and updates records having key values in those ranges, lock requests applied to the lock manager by the instructions that implement date-scan operations requesting, in the absence
of an already existing lock acquired by the same transaction, locks of the update-scan mode and including resource identifiers that represent the key-value ranges through which the update-scan operation scans;
C) the compatibility matrix includes at least five distinct lock modes IU, lin, ID, S and SIX, whose compatibility combinations are as follows:
D) the scan and singleton-read modes are both S, and the update, inset-next-range, delete-next-range, and update-scan modes are IU, IIn, ID, and SIX, respectively;
E) the instructions that implement the update and update-scan operations apply to the lock manager lock requests that request locks whose modes are incompatible with mode S and include resource identifiers that represent the key values of the
records to be updated by those operations; and
F) the instructions that implement the insert and delete operations apply to the lock manager lock requests that request locks of a mode that is incompatible with mode S and include resource identifiers that represent the key values of the
records to be inserted and deleted, respectively, by those operations.
13. The resource manager method according to claim 12 wherein lock requests applied to the lock manager by the instructions that implement a given transaction's insert and delete operations request, in the absence of a lock previously acquired
by the given transaction, locks of the IIn and ID modes, respectively, and include resou | | |
