Database system with methods for parallel lock management

• US 5,832,484 A
• Filed: 07/02/1996
• Issued: 11/03/1998
• Est. Priority Date: 07/02/1996
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Sankaran, Mohan, Krishnan, Vaikom Bala
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): Jung, David Yiuk
• Application Number:
  US08/673,893
• Time in Patent Office: 854 Days
• Field of Search: 707/1-206, 364/134, 364/228-246, 395/406, 395/670-678, 395/680-688
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

Database system and methods are described for improving scalability of multi-user database systems by improving management of locks used in the system. The system provides multiple server engines, with each engine having a Parallel Lock Manager. More particularly, the Lock Manager decomposes the single spin lock traditionally employed to protect shared, global Lock Manager structures into multiple spin locks, each protecting individual hash buckets or groups of hash buckets which index into particular members of those structures. In this manner, contention for shared, global Lock Manager data structures is reduced, thereby improving the system'"'"'s scalability. Further, improved "deadlock" searching methodology is provided. Specifically, the system provides a "deferred" mode of deadlock detection. Here, a task simply goes to sleep on a lock; it does not initiate a deadlock search. At a later point in time, the task is awakened to carry out the deadlock search. Often, however, a task can be awakened with the requested lock being granted. In this manner, the "deferred" mode of deadlock detection allows the system to avoid deadlock detection for locks which are soon granted.

Claims

1. In a multi-tasking database system having a server storing a database connected to a plurality of clients, said database system providing a plurality of database engines for processing requests from the clients for database operations, an improved method for providing access to objects provided by the database system, the method comprising:

providing each database engine with a lock manager for controlling access to objects in the database system;

storing lock management data structures which can be shared among all database engines, said lock management data structures storing locking information about a first plurality of locks that comprise a plurality of lock types for protecting access to objects in the database system which are shared;

controlling access to said lock management data structures through at least one hash table comprising a plurality of hash buckets, each hash bucket being associated with a particular lock type from said plurality of lock types provided by the system;

protecting access to said lock management data structures themselves with a second plurality of locks that comprise spin locks; and

providing parallel access to different ones of said first plurality of locks provided by the database system by associating each spin lock from said second plurality of locks with a particular group of hash buckets.

2. The method of claim 1, wherein each database engine operates on a separate processor of a symmetric multi-processor computer system.

3. The method of claim 1, wherein said lock manager controls access to a particular object by granting a lock to that particular object, the lock being selected from said first plurality of locks.

4. The method of claim 3, wherein objects which can be locked by said first plurality of locks include database tables, database pages, and memory buffers.

5. The method of claim 3, wherein each lock granted from said first plurality of locks can be either an exclusive lock or a shared lock.

6. The method of claim 1, wherein each hash bucket maintains a queue of lock requests for a particular object.

7. The method of claim 6, wherein said queue has a head and a tail, and wherein the immediate lock request appearing at the head of the queue represents a lock from said first plurality of locks which is currently granted.

8. The method of claim 6, wherein locks from said first plurality of locks which can coexist share equivalent positions in the queue.

9. The method of claim 8, wherein locks from said first plurality of locks which can coexist include shared locks.

10. The method of claim 1, further comprising:

receiving a request from a task for access to a particular hash bucket; and

in response to said request, asserting the spin lock associated with the hash bucket and providing the task access to locking information maintained at the particular hash bucket.

11. The method of claim 10, further comprising:

receiving a second request from another task for access to another hash bucket, said another hash bucket being associated with another spin lock; and

in response to said second request, asserting said another spin lock and providing said another task access to said another hash bucket, while at the same time continuing to provide access to said particular hash bucket which was first requested.

12. The method of claim 1, further comprising:

receiving a request for access to a particular object;

in response to said request, examining the hash bucket associated with the particular object for determining whether a lock from said first plurality of locks exists to protect the object;

if a lock does not already exist to protect the object, creating a lock object storing locking information about the particular object and linking that lock object onto the hash bucket; and

posting a lock request for access to the particular object by appending the lock request to the lock object if no other lock requests exist for the particular object, or appending the lock request to the end of the last lock request which has been previously appended.

13. The method of claim 12, further comprising:

if the lock request being appended has no other lock request which preceeds it, immediately granting a lock from said first plurality of locks for protecting the particular object.

14. The method of claim 12, wherein the lock request is appended to another pre-existing lock request with which it can coexist.

15. The method of claim 1, further comprising:

if a lock from said first plurality of locks is needed for a particular object by a task but such a lock is not currently available, placing the task to sleep while it waits for the lock to become available.

16. The method of claim 15, further comprising:

after a pre-selected amount of time, awakening the sleeping task for initiating a deadlock search among tasks which are sleeping on locks.

17. The method of claim 16, wherein said pre-selected amount of time is sufficiently long so that at least some of the tasks sleeping on locks will be granted locks from said first plurality of locks before being awakened for initiating deadlock searching.

18. The method of claim 16, wherein tasks which have been sleeping on locks the longest are awakened first for deadlock searching.

19. The method of claim 16, wherein deadlock searching includes examining locking information for another task which holds the lock the task performing the deadlock search is currently waiting on.

20. The method of claim 19, further comprising:

reverting to a single spin lock from said second plurality of locks for protecting lock management data structures when only one database engine is active in the system.

21. In a multi-tasking database system, in which tasks may deadlock on one another while waiting for locks for accessing objects to be granted, said locks being created from a plurality of transactional lock types available in the system for protecting objects having shared access, an improved method of deadlock detection, the method comprising:

upon receiving a request from a certain task for a particular lock which can not yet be granted from said locks, placing the certain task to sleep while waiting for the particular lock to be granted;

setting an alarm for periodically determining which task has been sleeping the longest on a lock;

if the particular lock can be granted from said locks, awakening said certain task for continuing execution with access to the object controlled by the particular lock; and

if the alarm triggers before the certain task has been granted the particular lock, awakening the certain task for undertaking deadlock detection.

22. The method of claim 21, wherein said placing a task to sleep step includes performing a context switch of the system so that the task does not consume processor cycles of the system while the task is sleeping.

23. The method of claim 21, wherein said alarm comprises an alarm handler which increments a counter for each sleeping task, so that a task which has been sleeping the longest can be readily determined.

24. The method of claim 21, wherein said system includes a user-configurable delay setting for indicating how often said alarm should periodically trigger.

25. The method of claim 24, wherein said delay setting is set equal to about 100 milliseconds.

26. The method of claim 24, wherein said delay setting is set equal to 0 for indicating that deadlock detection should occur immediately upon a task waiting on a lock.

27. The method of claim 24, wherein said delay setting is optimized to a particular user application which runs on the system, so that overhead incurred for deadlock detection is minimized.

28. The method of claim 21, wherein deadlock detection comprises:

constructing a directed dependency graph for representing dependencies among tasks which are sleeping.

29. The method of claim 28, further comprising:

detecting a deadlock upon finding a cycle in said directed dependency graph, said cycle representing a dependency of a particular task which cycles through other tasks back to the particular task.

30. The method of claim 29, further comprising:

upon detecting a deadlock which is initiated by said certain task, waking the deadlock by victimizing said certain task.