Database System With Methods for Parallel Lock Management

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

The present invention relates generally to information processing environments and, more particularly, to mechanisms for controlling allocation of locks on information stored in a data processing system, such as a Database Management System (DBMS).

Computers are very powerful tools for storing and providing access to vast amounts of information. Computer databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical database is an organized collection of related information stored as "records" having "fields" of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.

Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a database management system or DBMS is typically provided as a software cushion or layer. In essence, the DBMS shields the database user from knowing or even caring about underlying hardware-level details. Typically, all requests from users for access to the data are processed by the DBMS. For example, information may be added or removed from data files, information retrieved from or updated in such files, and so forth, all without user knowledge of underlying system implementation. In this manner, the DBMS provides users with a conceptual view of the database that is removed from the hardware level. The general construction and operation of a database management system is known in the art. See e.g., Date, C., An Introduction to Database Systems, Volume I and II, Addison Wesley, 1990; the disclosure of which is hereby incorporated by reference.

DBMS systems have long since moved from a centralized mainframe environment to a de-centralized or distributed environment. One or more PC "client" systems, for instance, may be connected via a network to one or more server-based database systems (SQL database server) acting as a DBMS. Commercial examples of these "client/server" systems include Powersoft.TM. clients connected to one or more Sybase SQL Server.TM. database servers. Both Powersoft.TM. and Sybase SQL Server.TM. are available from Sybase, Inc. of Emeryville, Calif.

As the migration to client/server continues, each day more and more businesses are run from mission-critical systems which store information on server-based SQL database systems, such as Sybase SQL Server.TM.. As a result, increasingly higher demands are being placed on server-based SQL database systems. Accordingly, there is much interest in improving the performance of such systems, particularly in terms of execution speed and reliability.

One area where system performance sometimes has been found to be lacking is the server functionality responsible for coordinating access of multiple clients to shared database objects, specifically the aspect of "locking" database objects. Locking mechanisms are employed on DBMSs to prevent multiple tasks from concurrently sharing a resource (e.g., reading or writing a database record) in a manner which leads to inconsistency of the resource. Common concurrency problems include lost updates, uncommitted dependencies, and inconsistent analyses. These problems and some locking mechanisms designed to address them are described in the general database literature; see, e.g., Nath, A., The Guide to SQL Server, Second Edition, Addison-Wesley Publishing Company, 1995, which is hereby incorporated by reference for all purposes.

Briefly, certain tasks require "exclusive" access, while other tasks need only "shared" access. When a client accesses a database record for the purpose of updating that record, the client must take out an exclusive "lock" on that record to ensure that while the task is using the record, another task cannot concurrently modify (and in some cases also not read) the record. For example, if a first user updates a data record to reflect a recent transaction, a lock on that record assures the user that no other users can concurrently modify the record while his or her transaction is being processed.

In one approach to lock management, such as found in Sybase SQL Server.TM. (System 10), different locks are provided in shared memory and are made available by a global resource manager commonly referred to as a lock manager. When a task requires access to a record, the lock manager determines whether an appropriate lock can be granted, and, if so, allocates such a lock to the task. If the lock manager finds an existing lock on the record, it either queues a request for the lock or grants a concurrent lock to the task, depending upon the nature of the existing lock and the type of access required (i.e., whether the locks can co-exist).

Access to the lock manager in such a system is limited by a single spin lock on the lock manager itself. This spin lock must be taken by any task requiring access to the lock manager for the purpose of obtaining a lock on a database record or for any other purpose. This approach prevents other tasks from simultaneously accessing any other locks through the lock manager. On the one hand, providing a single spin lock for the lock manager simplifies system design: lock-related procedures such as deadlock detection can be conducted easily. On the other hand, the single spin lock also becomes a bottleneck to providing scalability, that is, providing additional server engines on the same network. Specifically, the single spin lock approach hampers system scalability, since any additional engine provided must contend for the same single spin lock.

One approach to solving this problem might be to provide multiple instances of the lock manager itself. Such a solution quickly leads to communications problems, however. For example, each request for a new lock would require that the multiple instances of the lock manager communicate the request among themselves to ensure that the requested lock is actually available (i.e., does not conflict with other granted locks). Further, deadlock detection becomes quite complicated: deadlock searches would now have to be conducted over the multiple lock managers, each of which could deallocate or allocate locks while another lock manager is being searched.

Thus, what is needed is an improved database system with methods for allocating locks that allows system throughput to scale with the number of database engines on a network, while not requiring an unduly complicated communications protocol.

The present invention comprises a Client/Server Database System with methods for providing parallel lock management. In an exemplary embodiment, the system includes one or more Clients (e.g., Terminals or PCs) connected via a Network to a Server. The Server, operating under a server operating system (e.g., Windows NT) includes a Database Server System, such as Sybase SQL Server.TM.. Clients, operating under client applications, store data in and retrieve data from one or more database tables resident on the Server by submitting SQL commands, some of which specify "queries"--criteria for selecting particular records of a table.

Operation of a client application requires access to various objects in the system, such as a database table, a data page, an index page, a memory buffer, or the like. Specifically, the Access Methods within the server employ various Resource Governors which controls allocation of such Server resources as buffer caches, locks, and the like. For these functions, the Resource Governors employ separate managers such as a buffer manager for controlling the contents of buffer caches employed by the server to buffer database records.

One such resource governor or manager is a Parallel Lock Manager (hereinafter, simply "Lock Manager") of the present invention. It provides lock management for the Resource Governors' internal clients (e.g., Access Methods)--controlling all client locking. The Lock Manager allocates locks, deallocates/releases locks, searches for deadlocks, and the like. The Lock Manager manages different lock types, each one for controlling access to a different type of system resource. Exemplary lock types include address locks, table locks, pages locks, and semaphore locks. Here, an address lock locks a memory address--a buffer. The semaphore locks control access to a system log table(s) so that tasks can make log entries as necessary. Thus, when a task is ready to log its transaction, it first takes out a semaphore lock. Both address and semaphore locks are system internal locks (i.e., not typically visible to user applications). The table locks control access to tables within the database, and page locks control access to individual pages (e.g., index pages and data record pages) stored in the database. Both the page locks and table locks are user visible locks. Each may be processed indirectly (e.g., through SQL statements) by a user application. Although there are different lock types, the Lock Manager largely views the different lock types generically--applying the same or similar management methodology to each type.

The Lock Manager provides an internal application programming interface ("API") to its internal clients, such as the Access Methods. Because the Lock Manager is a global resource, identical copies are provided in each engine of a database network (as identical pieces of server code). In particular, an SMP (symmetric multi-processor) embodiment of the Database Server System supports multiple database engines (i.e., multiple instances of the engine), up to an arbitrary number of database engines. Each engine includes a Lock Manager instance. Even though there are multiple instances of the Lock Manager, the engines share a single, global set of data structures.

Conventionally, such structures were protected by a single spin lock. Such an approach robs a system's ability to scale in an SMP environment, due to contention among the multiple server engines for the single spin lock. To reduce this contention for these shared data structures, therefore, the present invention provides the Lock Manager (of each engine) with methods for parallel lock management--decomposing the (prior) single spin lock into multiple spin locks, each protecting individual hash buckets or groups of hash buckets.

Decomposing the (prior) spin lock into multiple spin locks greatly reduces contention for the Lock Manager's data structures and thereby improves the system's scalability. At the same time, however, existing lock management methodology, such as conventional "deadlock" searching, depended on the simplicity of a single spin lock for protecting these interdependent structures--that is, that Lock Manager's data structures were all frozen by a single spin lock (i.e., would not be changed by another task). Accordingly, implementation of parallel lock management requires improved "deadlock" searching methodology.

Access to particular lock types is controlled via hash tables, one table for each lock type. Each hash table has one or more spin locks, each spin lock for controlling a subset or range of one or more hash buckets for the table. In this manner, contention is substantially reduced: locks only block when two tasks each concurrently require access to hash buckets covered by the same spin lock. In previous systems, in contrast, a single spin lock was always used to protect such structures and, thus, always presented a bottleneck.

By associating groups of hash buckets with a particular spin lock, spin locks in the system of the present invention are conserved. The number of spin locks employed for each hash table is user (administrator) configurable. The simplest use is to configure the system such that the minimum number of spin locks is employed: one spin lock for each hash table. Even at this minimum, contention is reduced: processing a lock request of one type of lock (e.g., page lock) will not block access to other types of locks (e.g., address locks). At the other extreme, the user can allocate one spin lock for each and every bucket (up to the number of spin locks available in the system). Here, increasing the number of spin locks increases parallelism available with a give lock type--contention for other hash buckets within a given table decreases as the number of spin locks assigned to that table increases. In typical use, the user will configure or tune use of available spin locks to optimize system performance. In this manner, contention for access to the Lock Manager can be reduced while preserving efficient use of system spin locks, thereby allowing the system to appropriately scale up as more engines are added to the system.

Decomposing the (prior) spin lock into multiple spin locks greatly reduces contention for the Lock Manager's data structures and thereby improves the system's scalability. At the same time, however, existing lock management methodology, such as conventional "deadlock" searching, depended on the simplicity of a single spin lock for protecting these interdependent structures--that is, that Lock Manager's data structures were all frozen by a single spin lock (i.e., would not be changed by another task). Accordingly, implementation of parallel lock management requires improved "deadlock" searching methodology.

"Deadlock" is a well-known scenario when two or more tasks go to sleep waiting (directly or indirectly) for each other to release their respective locks on resources that they are accessing. To detect a deadlock, a database system performs a deadlock search for examining sleeping tasks to identify any "cycles," i.e., a dependency chain which points back to the sleeping task that initiated the search. The presence of such a cycle indicates a deadlock. When one is identified, the server chooses a "deadlock victim" from among the tasks making up the cycle to break the deadlock.

To avoid deadlocks, a system must be able to detect deadlocks among sleeping tasks. Conventionally, each task undertakes deadlock searching immediately after it begins waiting on a lock request. A common approach is to employ a depth-first search of the dependency graph (a tree data structure), looking for cycles. If a cycle is found, the deadlock can be broken by selecting a deadlock victim. In many instances, however, a task's requested lock is immediately or quickly granted, therefore rendering deadlock searching moot. In many cases, therefore, immediate deadlock searching incurs unnecessary overhead and, thus, hurts system performance.

To address this inefficiency, the system of the present invention provides "deferred" deadlock detection. Here, a task simply goes to sleep on a lock; it does not initiate a deadlock search. Routinely, the task will be awakened with the lock being granted. If a deadlock is present, however, the task will not be awakened with a granted lock. To address this second case, the system provides a deferred mode of deadlock detection. For this mode, the system provides a user-configurable, periodic alarm. The user configures the alarm for delaying or "deferring" deadlock detection up to a certain time period. In a preferred embodiment, the delay is set to a default time period of 100 milliseconds. Setting the time period to 0 milliseconds indicates that deadlock detection is not deferred.

As before, a task using deferred mode continues to initiates the deadlock searching. However, "when" the task actually initiates deadlock searching changes. If the time period for the alarm is greater than zero, the task will not initiate the search at the time of sleeping on the lock. Instead, a periodic alarm handler will increment a counter until the specified time period is reached. The alarm handler works in conjunction with an "engine scheduler" to make sure that, if a task sleeps on a lock request for more than the configured time period, the task is awakened. This time, however, the task is awakened to initiate deadlock searching. More specifically, the alarm handler checks a "lock sleeptask queue" (described below) to see if there is a sleeping task that has waited for at least the "deadlock checking period." If such a task is found, the task is awakened so that it can perform its own deadlock search. In a preferred embodiment, only a single deadlock search may be conducted at any given time. Therefore, a semaphore (rdlc.sub.-- status) is employed to control the process. If a deadlock search is being conducted by a first task, a second task may have to wait longer than the "deadlock checking period" period before initiating its own deadlock search.

FIG. 1A is a block diagram illustrating a computer system in which the present invention may be embodied.

FIG. 1B is a block diagram illustrating a software subsystem for controlling the operation of the computer system of FIG. 1A.

FIG. 2A is a block diagram of a client/server system in which the present invention may be embodied.

FIG. 2B is a block diagram of an SMP client/server system in which the present invention may be preferably embodied.

FIG. 2C is a block diagram illustrating shared Lock Manager structures in the client/server system of FIG. 2B which are, before modification in accordance with the present invention, under control of a single spin lock.

FIG. 3A is a block diagram of a Lock Manager illustrating shared Lock Manager structures which have been modified in accordance with the present invention.

FIG. 3B is a block diagram illustrating layout and use of hash tables provided by the shared Lock Manager structures.

FIG. 4A is a diagram illustrating use of data structures "hanging" off a hash table entry ("hash bucket") for representing a request for an exclusive lock.

FIG. 4B is a diagram illustrating use of data structures for representing multiple requests for exclusive locks.

FIG. 4C is a diagram illustrating use of data structures for representing multiple requests for shared locks.

FIG. 4D is a diagram illustrating use of data structures for representing multiple requests for both shared and exclusive locks.

FIG. 4E is a diagram illustrating addition of a new request for an exclusive lock.

FIG. 4F is a diagram illustrating addition of a new request for a shared lock.

FIG. 5A is a diagram representing lock record (i.e., lock "request") and semawait data structures that correspond to a simple deadlock.

FIG. 5B is a diagram of a "direct dependency graph" generated during a deadlock search of the data structures shown in FIG. 5A.

FIG. 6A is a diagram of a dependency graph of a hypothetical arrangement of tasks as those tasks might be queued at the beginning of a deadlock search.

FIGS. 6B-C are diagrams of dependency graphs illustrating use of sequence numbers in the present invention for detecting "spurious deadlocks" for the tasks of FIG. 6A.

FIG. 7 is a diagram of a dependency graph for a deadlock search uncovering a cycle in which the initiating task did not form part of the cycle (known as the "innocent bystander deadlock").

FIG. 8 is a diagram of a dependency graph for a deadlock search uncovering multiple cycles.

FIG. 9 is a block diagram illustrating a method of the present invention for improved management of global "free" locks.

The following description will focus on the presently preferred embodiment of the present invention, which is operative in a network environment executing client/server database applications. The present invention, however, is not limited to any particular application or environment. Instead, those skilled in the art will find that the present invention may be advantageously applied to any application or environment where contention for resources occurs and some locking mechanism is employed, including non-SQL database management systems and the like. The description of the exemplary embodiments which follows is, therefore, for the purpose of illustration and not limitation.

Definitions

At the outset, it is helpful to briefly review database terms which will be used in the subsequent discussion of the construction and operation of the system and methods of the present invention. The definitions are provided to assist in understanding the preferred embodiments described herein.

A "database object" is an article stored in one or more databases. Examples of such database objects include tables, tuples, logs for databases, statistics pages, views, stored procedures, and the like. Such database objects may have attributes such as sizes, names, types, and so forth. In addition, a database object is a "resource" employed by the database during normal functioning. Examples of such resource-type database objects include buffers and semaphores. In the context of this invention, locks can be placed on some or all of these database object types.

A "semaphore" is an indicator, such as a flag, used to govern access to shared system resources, for maintaining order among processes that are competing for use of resources.

A "task" is a program in execution together with virtual memory containing instructions, data, and context information, such as descriptors for open files and communication channels. In the context of this invention, tasks and processes will be used interchangeably, although conventionally "process" may refer to only the program in the execution component of a task.

A "lock manager" is any database entity or collection of entities that control access to locks on database objects. Typically, tasks requesting locks on particular database objects lodge their requests with a lock manager.

A "hash table" is a look-up table associated with particular objects in a collection of resources such as individual locks accessible through a lock manager. It provides pointers to the various objects currently provided. The location of a pointer within the hash table is a function of certain attributes of the object (i.e., "hash function") associated with the pointer. When access to a particular object is required, the system indexes into the appropriate entry in the hash table for determining whether the object is available and takes action accordingly.

"Hash buckets" are provided for holding information about the objects indexed in a hash table. If there are more objects than hash buckets, then the additional objects can be "chained off" at least some hash buckets. This may be desirable when a relatively large number of locks are provided by the system.

Transactional locks, or simply "locks," are employed by the system to coordinate OLTP (on-line transactional processing). Typical transactional locks include, for instance, a table lock and a page lock. These locks can be shared or exclusive. An "exclusive" lock, when held by a given process, completely excludes all other processes from accessing the locked object. A "non-exclusive" or "shared" lock, on the other hand, permits certain types of shared access while the lock is held by a given process. For example, if a first process takes out a non-exclusive lock on a data page, a second process may be permitted to read data records from that page even while the first process holds the lock. However, the non-exclusive lock might prevent the second process from writing to any data records contained in the locked data page.

In contrast to transactional locks, "spin" locks operate at a lower level (i.e., at the operating system level) to control system-critical resources. These locks are characterized by the fact that a task will continue to "spin"--that is, continues to execute--if a resource is not immediately available (i.e., if the lock is not immediately granted). Ordinarily, when a task requests a lock, such as a transactional lock, the requesting task will "sleep" on the lock if it is not immediately available (e.g., the lock is currently held by another task). When "sleeping," the task is in effect placed in a suspended state until some point in time when it is "awakened." For instance, a task sleeping on a lock will be awakened when the underlying database management system is ready to grant the lock (and, accordingly, grant access to the desired data structure). When a task is put to "sleep," the underlying system switches tasks, from the now sleeping one to one which is awake. In this manner, processor resources can be conserved: a sleeping task consumes no processor resources while sleeping.

A task or context switch itself is not cost-free: system resources are required for swapping out the context of one task for another. For instance, the then-current state of the task to be put to sleep must be stored, while the system switches to another task. Once the task is awakened, the system must restore the state information for the awaking task. For certain system critical resources, the overhead incurred with such a task switch is unacceptable. By spinning instead of sleeping, a task can avoid the overhead and cost of a context switch. To ensure that waiting tasks do not spin too long, spin locks typically contain only very few instructions, so that they are held for only a very short duration. Spin locks are employed within the system of the present invention to control access to low-level system resources, such as important lock management data structures which are shared.

Standalone System Hardware

The invention may be embodied on a computer system such as the system 100 of FIG. 1A, which comprises a central processor 101, a main memory 102, an input/output controller 103, a keyboard 104, a pointing device 105 (e.g., mouse, track ball, pen device, or the like), a screen display device 106, and a mass storage 107 (e.g., hard or fixed disk, removable disk (e.g., "floppy"), optical disk, magneto-optical disk, or flash memory). Processor 101 includes or is coupled to a cache memory 109 for storing frequently accessed information; memory 109 may be an on-chip cache or external cache (as shown). Additional output device(s) 108, such as a printing device, may be included in the system 100 as desired. As shown, the various components of the system 100 communicate through a system bus 110 or similar architecture. In a preferred embodiment, the system 100 includes an IBM-compatible personal computer system, available from a variety of vendors (including IBM of Armonk, N.Y.).

Standalone System Software

Illustrated in FIG. 1B, a computer software system 150 is provided for directing the operation of the computer system 100. Software system 150, which is stored in system memory 102 and on mass storage or disk memory 107, includes a kernel or operating system (OS) 140 and a windows shell 145. One or more application programs, such as application software 155, may be "loaded" (i.e., transferred from storage 107 into memory 102) for execution by the system 100. The system also includes a user interface 160 for receiving user commands and data as input and displaying result data as output.

Also shown, the software system 150 includes a Relational Database Management System (RDBMS) front-end or "client" 170. The RDBMS client 170 may be any one of a number of database front-ends, including PowerBuilder.TM., dBASE.RTM., Paradox.RTM., Microsoft.RTM. Access, or the like. In an exemplary embodiment, the front-end will include SQL access drivers (e.g., Borland SQL Links, Microsoft ODBC drivers, Intersolv ODBC drivers, and the like) for accessing SQL database server tables in a Client/Server environment.

Client/Server Database Management System

While the present invention may operate within a single (standalone) computer (e.g., system 100 of FIG. 1A), the present invention is preferably embodied in a multi-user computer system, such as a Client/Server system. FIG. 2A illustrates the general structure of a Client/Server Database System 200. As shown, the system 200 comprises one or more Client(s) 210 connected to a Server 230 via a Network 220. Specifically, the Client(s) 210 comprise one or more standalone Terminals 211 connected to a Database Server System 240 using a conventional network. In an exemplary embodiment, the Terminals 211 may themselves comprise a plurality of standalone workstations, dumb terminals, or the like, or comprise personal computers (PCs) such as the above-described system 100. Typically, such units would operate under a client operating system, such as Microsoft Windows/MS-DOS for PC clients.

The Database Server System 240, which comprises Sybase SQL Server.TM. (available from Sybase, Inc. of Emeryville, Calif.) in an exemplary embodiment, generally operates as an independent process (i.e., independently of the clients), running under a server operating system such as Microsoft Windows NT (Microsoft Corp. of Redmond, Wash.), NetWare (Novell of Provo, Utah), or UNIX (Novell). The Network 220 may be any one of a number of conventional network systems, including a Local Area Network (LAN) or Wide Area Network (WAN), as is known in the art (e.g., using Ethernet, IBM Token Ring, or the like). The Network includes functionality for packaging client calls in the well-known SQL (Structured Query Language) command syntax, together with any parameter information, into a format (of one or more packets) suitable for transmission across a cable or wire, for delivery to the Database Server 240.

Client/server environments, database servers, and networks are well documented in the technical, trade, and patent literature. For a discussion of database servers and client/server environments generally and SQL Server.TM. particularly, see, e.g., Nath, A., The Guide to SQL Server, Second Edition, Addison-Wesley Publishing Company, 1995 (previously incorporated by reference). Additional documentation of SQL Server.TM. is available from Sybase, Inc. as SQL Server Documentation Set (Catalog No. 49600). For a discussion of a computer network employing Microsoft Networks/OpenNet File Sharing Protocol, see METHOD AND SYSTEM FOR OPPORTUNISTIC LOCKING IN A NETWORKED COMPUTER SYSTEM, Intl. Application No. PCT/US90/04570, Intl. Publication No. WO 91/03024, Intl. Publication Date Mar. 7, 1991. For a general introduction to a Local Area Network operating under NetWare, see Freed, L. et al., PC Magazine Guide to Using NetWare, Ziff-Davis Press, 1991. A more detailed discussion is available in NetWare 3.x and 4.x and accompanying documentation, which is available from Novell of Provo, Utah. The disclosures of each of the foregoing are hereby incorporated by reference.

In operation, the Client(s) 210 store data in or retrieve data from one or more database tables 250, shown in FIG. 2. Typically resident on the Server 230, each table itself comprises one or more horizontal rows or "records" (tuples) together with vertical columns or "fields." A database record includes information which is most conveniently represented as a single unit. A record for an employee, for example, may include information about the employee's ID Number, Last Name and First Initial, Position, Date Hired, Social Security Number, and Salary. Thus, a typical record includes several categories of information about an individual person, place, or thing. Each of these categories, in turn, represents a database field. In the foregoing employee table, for example, Position is one field, Date Hired is another, and so on. With this format, tables are easy for users to understand and use. Moreover, the flexibility of tables permits a user to define relationships between various items of data, as needed.

In operation, the Clients issue one or more SQL commands to the Server. SQL commands may specify, for instance, a query for retrieving particular data (i.e., data records meeting the query condition) from the table 250. The syntax of SQL (Structured Query Language) is well documented; see, e.g., the above mentioned An Introduction to Database Systems. In addition to retrieving the data from Database Server tables, the Clients also include the ability to insert new rows of data records into the table; Clients can also modify and/or delete existing records in the table.

For enhancing the speed in which the Database Server stores, retrieves, and presents particular data records, the Server maintains one or more database indexes on the table. A database index, typically maintained as a B-Tree data structure, allows the records of a table to be organized in many different ways, depending on a particular user's needs. An index may be constructed as a single disk file storing index key values together with unique record numbers. The former is a data quantity composed of one or more fields from a record; the values are used to arrange (logically) the database file records by some desired order (index expression). The latter are unique pointers or identifiers to the actual storage location of each record in the database file. Both are referred to internally by the system for locating and displaying records in a database file.

In operation, the SQL statements received from the one or more Clients 210 (via network 220) are processed by Engine 260 of the Database Server System 240. The Engine 260 itself comprises a Parser 261, Normalizer 263, Compiler 265, Execution Unit 269, Access Methods 270, and Resource Governors 272. Specifically, the SQL statements are passed to the Parser 261 which converts the statements into a query tree--a binary tree data structure which represents the components of the query in a format selected for the convenience of the system. In this regard, the Parser 261 employs conventional parsing methodology (e.g., recursive descent parsing).

The query tree is normalized by the Normalizer 263. Normalization includes, for example, the elimination of redundant data. Additionally, the Normalizer performs error checking, such as confirming that table names and column names which appear in the query are valid (e.g., are available and belong together). Finally, the Normalizer can also look up any referential integrity constraints which exist and add those to the query.

After normalization, the query tree is passed to the Compiler 265, which includes an Optimizer 266 and a Code Generator 267. The Optimizer is responsible for optimizing the query tree. The Optimizer performs a cost-based analysis for formulating a query execution plan. The Optimizer will, for instance, select the join order of tables (e.g., when working with more than one table); it will select relevant indexes (e.g., when indexes arc available). The Optimizer, therefore, performs an analysis of the query and picks the best execution plan, which in turn results in particular ones of the Access Methods being invoked during query execution.

The Code Generator 267, on the other hand, converts the query tree into a set of instructions suitable for satisfying the query. These instructions are passed to the Execution Unit 269. Operating under the control of these instructions, the Execution Unit 269 generates calls into lower-level routines, such as the Access Methods 270, for retrieving relevant information (e.g., row 255) from the database table 250. After the plan has been executed by the Execution Unit, the Server returns a query result or answer table back to the Client(s).

To retrieve information, the Access Methods 270 must at times make use of resources provided by the Server. To do so, the Access Methods 270 employ Resource Governors 272 which control allocation of such Server resources as buffer caches, locks, and the like. For these functions, Resource Governors 272 employ separate managers such as a buffer manager for controlling the contents of buffer caches employed by the server to buffer database records.

Parallel Lock Manager 274 (hereinafter, simply "Lock Manager") is one such resource governor or manager. It provides lock management for the Resource Governors' internal clients (e.g., Access Methods 270)--controlling all client locking. The Lock Managers allocate locks, deallocate/release locks, searche for deadlocks, and the like. The Lock Manager 274 manages different lock types, each one for controlling access to a different type of system resource. Lock types include address locks, table locks, pages locks, and semaphore locks. The name of each lock suggests its functionality. For instance, an address lock locks a memory address--a buffer. The address locks control access to objects in memory, such as database buffer caches. Specifically, an address lock is a lock on a memory location having a particular specified buffer address. The semaphore locks control access to a system log table(s) so that tasks can enter log entries as necessary. Thus, when a task is ready to log its transaction, it first takes out a semaphore lock. Both address and semaphore locks are system internal locks (i.e., not typically visible to user applications). The table locks control access to tables within the database, and page locks control access to individual pages (e.g., index pages and data record pages) stored in the database. Both the page locks and table locks are user visible locks. Each may be processed indirectly (e.g., through SQL statements) by a user application. Although there are different lock types, the Lock Manager 274 largely views the different lock types generically--applying the same or similar management methodology to each type.

As Access Methods 270 must grab locks to access specific records in the database, the Access Methods 270 represent an internal client of the Lock Manager--communicating directly with Lock Manager 274 for obtaining such locks. In this regard, Lock Manager 274 provides an internal application programming interface ("API") to its internal clients, such as the Access Methods 270. Note that because the Lock Manager 274 is a global resource, identical copies are provided in each engine of a database network (as identical pieces of server code).

Of particular interest herein is an embodiment of the present invention in the Client/Server System 200 operating on an symmetric multi-processor (SMP) computer system. Such an embodiment is shown in FIG. 2B, as Client/Server System 200a. The system includes an SMP server 230a providing an SMP Database Server System 240a. Here, the SMP Database Server System supports multiple database engines (i.e., multiple instances of the engine 260), including engines 260a through 260n, up to an arbitrary number of database engines.

Ideally, as more processors are added to the SMP server 230a, the Database Server 240a can scale up with additional database engines. Note, however, that certain resources must be shared among the multiple engines, such as global resources require for accessing a common database table. Shared data structures or resource 290, shown in FIG. 2B, is one such resource. So that each engine "sees" the same resource (i.e., has a consistent view), access is protected by a "spin" lock--a well known SMP synchronization mechanism employed for controlling access to lower-level, system critical resources. Note particularly that, as more engines are added to the system, the contention for the shared resource 290 increases. This presents a single bottleneck for all engines.

The shared global structures of the Lock Manager 274 is shown in particular detail in FIG. 2C as shared resource 290. These shared structures, which represent the locking status among multiple users running on multiple engines, are preferred over per-engine data structures. In particular, providing multiple instances of lock management data structures would require less-efficient interprocess communication management--an approach to be avoided. Instead, therefore, the preferred approach is a single set of data structures which are shared among the multiple engine instances.

The layout of the data structures is designed to facilitate this sharing. In particular, the structures comprise hash tables for processing requests for different lock types in the system, including an "address" hash table 291, "table" hash table 292, and "page" hash table 293. In particular, information about which of the various locks have been "taken out" is stored by the particular hash table associated with each lock type. For instance, the address lock hash table 291 manages address locks; the table lock hash table 292 manages table locks; and the page lock hash table 293 manages page locks. Each hash table itself includes a plurality of "hash buckets" for storing information about locks and lock requests from various tasks. For instance, the table hash table 292 includes 101 available hash buckets. The address hash table and the page hash table, on the other hand, both have 1031 available hash buckets.

Given the multi-processing nature of the system of the present invention, access to the hash tables must occur with SMP synchronization. Suppose, for example, that a user task from engine 260a--task.sub.1 --desires to acquire a page lock on the object 294. A page lock is represented by page hash table 293. The task must index into the hash table, for bucket #3. There, the task determines whether the task can be granted the lock or the task must wait for the lock. During this lock operation, task, protects the Lock Manager's structures 290 from change by another task, by tasking out a spin lock. After task.sub.1 has completed the lock operation, it releases the spin lock.

Prior to modification in accordance with the present invention, the Lock Manager's shared data structures 290 were protected by a single spin lock (LOCK.sub.-- SPIN), which serialized access to the address, page, and table hash tables. Whenever a task held this spin lock, it protected the shared Lock Manager data structures entirely (against concurrent changes by other tasks). This approach, to a large extent, simplifies system design. At the same time, however, the approach leads to high contention among multiple engines for the single spin lock. For the example above, for instance, while task, was processing a page lock, another task, say task.sub.2, cannot process a request for an address lock.

To reduce this contention, therefore, the present invention provides the Lock Manager 274 with methods for parallel lock management--decomposing the (prior) single spin lock into multiple spin locks, each protecting individual hash buckets or groups of hash buckets. Decomposing the (prior) spin lock into multiple spin locks greatly reduces contention for the Lock Manager's data structures and thereby improves the system's scalability. At the same time, however, existing lock management methodology, such as conventional "deadlock" searching, depended on the simplicity of a single spin lock for protecting these interdependent structures--that is, that Lock Manager's data structures were all frozen by a single spin lock (i.e., would not be changed by another task). Accordingly, implementation of parallel lock management requires improved "deadlock" searching methodology. Details of the construction and operation of the Lock Manager for achieving this will be described below.

Improving system scalability: Parallel Lock Manager

A. Increasing scalability by removing single spin lock bottleneck

Given the multi-processing nature of the system of the present invention, access to the hash tables occurs using the multi-processor synchronization spin lock technique previously described for FIG. 2C. To improve system scalability, however, the spin lock technique is modified. Specifically, the single spin lock (LOCK.sub.-- SPIN) employed for protecting the Lock Manager's hash table data structures is decomposed into a configurable number of spin locks, employed in conjunction with other spin locks as follows:

(1) Configurable number of spin locks (LOCK.sub.-- SPIN) for:

(a) Address lock hash table;

(b) Page lock hash table;

(c) Table lock hash table;

(2) One spin lock for semaphore locks;

(3) One spin lock for a freelock list (LOCK.sub.-- FREELIST.sub.-- SPIN); and

(4) One spin lock for a sleep task queue (LOCK.sub.-- SLEEPTASK.sub.-- SPIN).

The scenario of one engine running is handled as a special case: the Lock Manager will allocate only one spin lock, to avoid wasting memory on spin locks for a single-engine server.

FIG. 3A illustrates the modification necessary for implementing this design, with particular emphasis on management of address, page, and table locks. In general, each hash table has one or more spin locks, each spin lock for controlling a subset or range of one or more hash buckets for the table. In the exemplary embodiment depicted in FIG. 3A, for instance, the 1031 hash buckets of address lock hash table 302 are controlled by a plurality of spin locks 312 (numbering 10, by default). In a similar fashion, the 101 hash buckets of table lock hash table 304 are controlled by a plurality of spin locks 314 (numbering 5, by default), and the 1031 hash buckets of page lock hash table 306 are controlled by a plurality of spin locks 316 (numbering 10, by default). Thus, for example, a first one of the page spin locks 316 controls access to hash buckets 1-104 for the page lock hash table 306. In this manner, contention is substantially reduced: locks only block when two tasks each concurrently require access to hash buckets covered by the same spin lock. In previous systems, in contrast, a single spin lock was always used to protect such structures and, thus, always presented a bottleneck.

By associating groups of hash buckets with a particular spin lock, spin locks in the system of the present invention are conserved. As described below, the number of spin locks employed for each hash table is user (administrator) configurable. The simplest use is to configure the system such that the minimum number of spin locks is employed: one spin lock for each hash table. Even at this minimum, contention is reduced: processing a lock request of one type of lock (e.g., page lock) will not block access to other types of locks (e.g., address locks). At the other extreme, the user can allocate one spin lock for each and every bucket (up to the number of spin locks available in the system). Here, increasing the number of spin locks increases parallelism available with a given lock type--contention for other hash buckets within a given table decreases as the number of spin locks assigned to that table increases. In typical use, the user will configure or tune use of available spin locks to optimize system performance; the default settings shown in FIG. 3A provide good results for an embodiment scaling up to ten processors. In this manner, contention for access to the Lock Manager can be reduced while preserving efficient use of system spin locks, thereby allowing the system to appropriately scale up as more engines are added to the system.

B. Hash bucket storage: chain of lock records/objects

Each hash bucket stores locking information which is maintained by the Lock Manager 274. Specifically, each hash bucket stores information about which task holds a particular lock. More particular, each hash bucket is capable of chaining lock data structures--lock records or objects--off of it, for storing detailed locking information.

FIG. 3B illustrates this approach. Each object currently "locked" is represented by a "lock object" associated with a particular hash bucket. In the example shown in FIG. 3B, hash bucket 321 of hash table 320 includes two lock objects 330 and 340 "hanging off" it (i.e., linked to it via pointers). Hash bucket 324, on the other hand, contains a single lock object 350; hash bucket 326 contains three lock objects 360, 370, and 380. If no locks associated with a given hash bucket are currently taken, then the hash bucket or entry is empty--no lock objects will be found hanging off such a hash bucket. This is the case with hash buckets 322 and 328 shown in FIG. 3B. This approach of hanging multiple locks off each hash bucket (i.e., the hash bucket overflow structures shown in FIG. 3B) allows a large number of locks to be represented with relatively few hash buckets. The address hash table 302 illustrated in FIG. 3A, for instance, can represent 10,000 or more address locks with only 1031 hash buckets.

To actually index into a particular hash bucket, the system employs a "hashing function" which is based on the number of available buckets. Construction of various hashing functions, as well as hash table techniques in general, are well described in the technical and trade literature; see e.g., Bark, R. Hashing: From Good to Perfect, The C Users Journal, pp. 41-52, the disclosure of which is hereby incorporated by reference. For the address hash table, a simple hash function of "modulo 1031" may be employed. Here, indicia for address lock 1 is stored in hash bucket 1, indicia for address lock 2 is stored in hash bucket 2, indicia for address lock 1030 is stored in ("hanging off" of) hash bucket 1030, indicia for address lock 1031 is stored in hash bucket 1031, and so on. Note, however, that address lock 1032, also "hashes" to hash bucket 1: it has a value of 1 when evaluated with the hash function. Thus, hash bucket 1 stores indicia of address lock 1, address lock 1032, address lock 2033, an so forth and so on. Each one of the address locks therefore represents a separate overflow structure which forms an overflow chain hanging off a particular bucket.

C. Processing lock requests

The Lock Manager processes requests for any type of lock generally as follows. Initially, the Lock Manager receives a task's request for a lock from Access Methods 270. In response to this request, the Lock Manager goes to the hash table associated with the type of lock requested and hashes into the location specified as the address of the object for which the lock is sought; as described above, the Manager takes out the spin lock associated with the bucket being indexed into. At that bucket, the Lock Manager can determine whether any lock objects are present at that location. If no lock object is found at the indexed-into hash bucket, the desired lock is immediately available and can be provided to the requesting task. If, on the other hand, one or more other tasks have previously requested a lock on the item at that location, the Lock Manager must queue the present request.

Regardless of whether an object is already found at the hash bucket of the desired lock, when a task requests that lock, the Lock Manager creates a lock record for the task and queues that request--that is, links it into the chain of lock objects hanging off the hash bucket. After the request is queued, the Lock Manager checks to determine whether that request is at the head of the queue. A lock request (lock record) is at the head of the queue when no other lock object precedes it. In such a case, the lock is immediately available and the request is "granted." If not, however, the task "sleeps" on the lock request.

The process is perhaps best illustrated by way of example, using an address lock (an exclusive lock). It should be noted, however, that the Lock Manager handles lock requests for other lock types (and other lock strengths, e.g., "intent" locks) in an analogous manner. As shown in FIG. 4A, a hash bucket provides a lock object 410 for address 1. Such a lock object is generated upon a first request for a lock. Here, a request for address lock 1 comes to the Lock Manager from a first task. The Lock Manager evaluates the hash function to identify the appropriate hash bucket for address lock 1, grabbing the spin lock for the group of hash buckets containing that hash bucket. Now, the Lock Manager can traverse the overflow chain in that hash bucket, looking for any lock objects. If the Lock Manager finds no lock object for the address lock 1 on the overflow chain, the Lock Manager automatically creates lock object 410 for address lock 1 and queues that object to the overflow chain.

After the lock object is created, the Lock manager creates a "lock request" 411 for the first task and queues that lock request to a semawait (described below) which is connected to the lock object, as shown in FIG. 4A. The lock record, in this example, is a data structure indicating the task's request for an exclusive lock and includes various pieces of information about the task including the task's process ID. After the lock request 411 has been created and queued, the Lock Manager determines whether that lock record is at the head of the queue off of lock object 410. Because it is, in this example, the requesting task is granted the lock on address 1. The spin lock on the hash bucket is then released.

Next suppose that another request for access to the address 1 lock arrives. This scenario is illustrated in FIG. 4B. The Lock Manager again evaluates the appropriate hash function, grabs a spin lock for the identified hash bucket, and traverses the structures provided in that hash bucket. In this scenario, the Lock Manager finds lock object 410 associated with address lock 1032. Because a lock object currently exists for address lock 1 (i.e., object 410), the Lock Manager need not create a new lock object. The Lock Manager does, however, create a new lock request 413 and appends it to a queue of lock requests hanging off lock object 410. The Lock Manager then determines whether the newly-created lock request 413 is at the head of the queue. In the example of FIG. 4B, it is not at the head as the task associated with lock request 411 currently holds an exclusive lock on the address lock. Therefore, the second task must wait for the lock; at this point, it can go to sleep.

A waiting task's request is granted only after all tasks in front of it in the queue have released their locks. As various tasks release the lock, the lock requests of other tasks move forward to the head of the queue. In one particular embodiment when a task releases its lock, it first dequeues its lock request and determines which task follows it in the queue. It then wakes up that task. At this point, the newly awakened task resumes execution with the newly-granted lock.

In the example of FIG. 4B, when the task associated with lock request 411 releases the lock (address 1), the task dequeues the lock request 411, thereby causing the lock request 413 to move to the head of the queue. The task associated with the request 413 then wakes and continues execution with a lock on address 1. When it no longer requires the lock, it releases the lock, dequeues lock request 413, and wakes any subsequent task, whereupon the lock is passed on to yet another task.

The foregoing example illustrates an address lock--an exclusive lock. For an exclusive lock, if the request is at the head of the queue, the request is granted, as no two exclusive lock requests can simultaneously reside at the head of queue. Page and table locks, in contrast, may be either exclusive or shared (non-exclusive). As noted, a non-exclusive lock may permit one or more other non-exclusive locks to be taken out on the same object (e.g., database page). To implement non-exclusive or shared locks, the Lock Manager chains another data structure, a semawait, in addition to the above-described lock object and lock request data structures. The semawait indicates the position in the queue; each position has one or more shared lock requests or a single exclusive lock request. For efficiency in system design, all of these locking data structures share the same size and are allocated from the freelock list (described in detail below).

One exemplary process for generating an overflow chain for page locks will now be described with reference to FIG. 4C. Initially, a first task requests a non-exclusive lock on a page 2. In response, the Lock Manager identifies the appropriate hash bucket for the page 2 lock, takes out a spin lock on the associated subset of hash buckets, and hashes into the identified hash bucket. Assuming that the page 2 lock is not currently taken, Lock Manager 274 discovers that no lock object exists for page 2 and creates lock object 420. Because the page lock request is for a non-exclusive lock, Lock Manager 274 then creates a semawait 430 which it appends directly off of page object 420, at the head of queue. Note that semawaits are employed only for non-exclusive locks. After the semawait structure has been created and queued, the Lock Manager creates a first non-exclusive lock request 431, appended directly off of semawait 430, and containing information about the first task. The first task then releases the spin lock on the subset of hash buckets.

Next, a second task also requests a non-exclusive lock on page 2. At this point, the Lock Manager grabs the appropriate spin lock, hashes into the hash bucket, and discovers page lock object 420 with semawait 430 and non-exclusive lock request 431. The Lock Manager then produces a second non-exclusive lock request 433, which it queue up (i.e., appends directly to the prior non-exclusive lock record 431). Both the first and second tasks now hold non-exclusive locks on page 2 and continue executing with shared access to page 2.

Now, consider a third task which requests an exclusive lock on page 2. This scenario is illustrated in FIG. 4D. Because this exclusive lock is incompatible with the non-exclusive locks currently held on page 2, the third task's request cannot be granted immediately. Thus, Lock Manager 274 generates a semawait 440 with a lock request 441 for the third task and queues it to the main overflow chain off the lock object for page 2. At this point, the third task will wait for the prior semawait to be dequeued; at this point, it can go to sleep.

Next, consider a fourth task which also requests an exclusive lock of page 2. Again, this request cannot be granted because the desired exclusive lock would not be lock compatible with the currently held non-exclusive locks. Further, note that this exclusive lock would not be lock compatible with the prior exclusive lock, as exclusive locks cannot co-exist on the same object. Thus, Lock Manager 274 generates yet another semawait 450 and appends it to the overflow chain with a lock request 451 for another exclusive lock, as illustrated in FIG. 4E. The fourth task now waits on this newly-added lock request; it can sleep at this point.

Finally, consider a fifth task which requests a non-exclusive lock on page 2. This non-exclusive lock is lock compatible with the currently held non-exclusive locks of the first and second tasks. As shown in FIG. 4F, therefore, the Lock Manager links the corresponding lock request 435 to the first semawait 430, thereby granting the newly-requested non-exclusive lock to the fifth task.

After the first, second, and fifth tasks deallocate their non-exclusive locks, semawait 430 and its non-exclusive lock requests are dequeued. As a result, the second semawait 440 and its exclusive lock request 441 move to the head of the queue. Concurrently therewith, the third task wakes up and continues execution with an exclusive lock on page 2. When this task subsequently deallocates its exclusive lock structures, the third semawait 450 and its exclusive lock request 451 move to the head of the queue. The fourth task thus continues execution with its requested exclusive lock on page 2. Thereafter, the task dequeues the lock request. After all lock requests and semawaits have been dequeued, the lock object itself is de-allocated.

Note that the above scenario for handling requests for both exclusive and non-exclusive locks could allow the third and fourth tasks to remain waiting indefinitely while additional requests for non-exclusive locks are received and queued off of the first semawait 430. To address the situation, the Lock Manager is preferably designed such that a queued request for an exclusive lock waits on no more than a certain number of non-exclusive lock requests lodged after it was queued (i.e., "skip" factor). In one particular preferred embodiment, a task requesting an exclusive lock will allow no more than four non-exclusive locks requests to be queued before it, after it has made its request for the exclusive lock. In this case, if an fifth request for a non-exclusive lock comes in, a new semawait is created and appended to the end of the overflow chain (behind any lock requests for exclusive locks). In this manner, subsequent requests for non-exclusive locks are queued through a subsequent semawait, rather than the semawait in front of the exclusive lock record.

D. Deadlock Detection in the Parallel Lock Manager

"Deadlock" is a well-known scenario when two or more tasks go to sleep waiting (directly or indirectly) for each other to release their respective locks on resources that they are accessing. To detect a deadlock, a database system performs a deadlock search for examining sleeping tasks to identify any "cycles," i.e., a dependency chain which points back to the sleeping task that initiated the search. The presence of such a cycle indicates a deadlock. When one is identified, the server chooses a "deadlock victim" from among the tasks making up the cycle to break the deadlock. The system chooses a victim by any appropriate scheme. In one embodiment, the system chooses as a victim that task having used the least amount of CPU time. If there is more than one task with the least amount of CPU time, the task last visited among them is chosen. The transaction of the deadlock victim's task is rolled back. A general description of deadlock can be found in the abovementioned An Introduction to Database Systems (at pages 415-417).

A simple deadlock is illustrated in FIG. 5A, with a "directed dependency graph" for the deadlock represented in FIG. 5B. Assume that a first task, T1, requests a page lock on a page 10. As shown in FIG. 5A, a lock object 501 is created for page 10 to which the task appends a semawait 510 having lock request 511. Since no other task has a lock request queued for page 10, the lock is granted to first task. Now, a second task, T2, requests a lock on a page 20. In a corresponding manner, as shown in FIG. 5A, a lock object 541 is created for page 20 to which the second task appends a semawait 550 having lock request 551. Since no other task has a lock request queued for page 20, the lock is granted to first task.

Now, consider a request from the second task for a lock on page 10 (with the requested lock not being lock compatible with the existing lock). Because the fist task already holds a lock on page 10, the second task queues up its request (semawait 520 and lock request 521) and goes to sleep waiting for the lock on page 10 to be released. Note particularly that the second task is going to sleep while holding its lock on page 20. The first task, in a corresponding manner, now requests a lock on page 20 (with the requested lock not being lock compatible with the existing lock). The first task queues up its request (semawait 560 and lock request 561); since this is the first request, a lock object 541 is created from the page 20. Because the second task already holds a lock on page 20, the first task goes to sleep waiting for the lock on page 20 to be released. Under these circumstances, a deadlock has resulted. The locks on pages 10 and 20 will remain in perpetuity absent some intervention from the system, thus preventing both the first task and the second task from continuing execution.

FIG. 5B illustrates this "cycle" diagrammatically with directed dependency graph 570. As shown, the first task (T1) holds a lock on a first object (obj1) and is waiting for a lock on a second object (obj2). At the same time, the second task (T2) holds a lock on the second object (obj2) while waiting for a lock on the first object (obj1). Here, the locks (L1 and L2) represent "edges" of the graph. The T2 task created the L1 edge between T2 and T1. Then the T1 task created the L2 edge between T1 and T2.

To avoid deadlocks, a system must be able to detect deadlocks among sleeping tasks. Conventionally, each task undertakes deadlock searching immediately after it begins waiting on a lock request. A common approach is to employ a depth-first search of the dependency graph (a tree data structure), looking for cycles. If a cycle is found, the deadlock can be broken by selecting a deadlock victim. In many instances, however, a task's requested lock is immediately or quickly granted, therefore rendering deadlock searching moot. In many cases, therefore, immediate deadlock searching incurs unnecessary overhead and, thus, hurts system performance.

To address this inefficiency, the system of the present invention provides "deferred" deadlock detection. Here, a task simply goes to sleep on a lock; it does not initiate a deadlock search. Routinely, the task will be awakened with the lock being granted. If a deadlock is present, however, the task will not be awakened with a granted lock. To address this second case, the system provides a deferred mode of deadlock detection. For this mode, the system provides a user-configurable, periodic alarm. The user configures the alarm for delaying or "deferring" deadlock detection up to a certain time period. In a preferred embodiment, the delay is set to a default time period of 100 milliseconds. Setting the time period to 0 milliseconds indicates that deadlock detection is not deferred.

As before, a task using deferred mode continues to initiates the deadlock searching. However, "when" the task actually initiates deadlock searching changes. If the time period for the alarm is greater than zero, the task will not initiate the search at the time of sleeping on the lock. Instead, a periodic alarm handler will increment a counter until the specified time period is reached. The alarm handler works in conjunction with an "engine scheduler" to make sure that, if a task sleeps on a lock request for more than the configured time period, the task is awakened. This time, however, the task is awakened to initiate deadlock searching. More specifically, the alarm handler checks a "lock sleeptask queue" (described below) to see if there is a sleeping task that has waited for at least the "deadlock checking period." If such a task is found, the task is awakened so that it can perform its own deadlock search. In a preferred embodiment, only a single deadlock search may be conducted at any given time. Therefore, a semaphore (rdlc.sub.-- status) is employed to control the process. If a deadlock search is being conducted by a first task, a second task may have to wait longer than the "deadlock checking period" period before initiating its own deadlock search.

In the present invention, the deadlock search is accomplished by examining the above-described locking structures--lock objects, semawaits, and lock records (as well as other data structures)--for identifying sleeping tasks that may be part of a cycle. This task is complicated by the fact that locks are managed in parallel: because multiple spin locks are employed on the Lock Manager data structures, the appropriate spin lock must be grabbed before the deadlock search can extract the necessary information from a particular hash bucket. To ensure that performance is not hampered, the system of the present invention preferably implements deadlock searches by repeatedly grabbing and releasing locks on hash buckets without holding more than one hash bucket spin lock at any given time. Specifically, during the deadlock search, the task performing the search first grabs the spin lock on the hash bucket for the first lock investigated in the search. Then after retrieving and recording the necessary information from data structures in that hash bucket, the Lock Manager releases the spin lock and takes out the spin lock on the hash bucket holding information about the next lock in the chain. After the relevant information is extracted from the second hash bucket, its spin lock is released, and so forth and so on.

Because the Lock Manager employs multiple spin locks when traversing Lock Manager data structures (namely, the hash buckets and their chains), deadlock detection should account for changes in lock status during the course of the search. Note that the various spin locks on the hash buckets are not frozen during the search so locks may be released and/or granted after the search is started but before it ends. Thus, deadlock searching itself is are dynamic--occurring while the system itself continues to operate. As a result, care must be taken to ensure that the data structures relied upon remain consistent. In contrast, if a single spin lock is provided for the entire Lock Manager, as was the case in with prior art systems, no data structures within the Lock Manager can change during the course of the deadlock search. That approach is simpler, but systems implementing that approach are effectively frozen while deadlock detection is underway.

Although deadlock searching in the system of the present invention occurs while the certain Lock Manager data structures are changing, the deadlock itself (i.e., the data structures associated therein) will not change. This is a unique property which can be exploited for providing improved deadlock detection methodology of the present invention. Specifically, if data structures change, then there is no deadlock and, hence, no need to continue the search.

The search algorithm detects deadlocks by forming a "directed dependency graph" (such as that shown in FIG. 5B) among tasks waiting for locks. In a directed dependency graph, each node is labeled by a task which is waiting for a lock. Consider the directed dependency graph 601, shown in FIG. 6A, at the point when T3 (third task) is adding the L3 (lock request) edge. The sequence of events is indicated by a sequence numbers (SN). Here, T1 (lock request L1) is waiting on T2 which, in turn, waits on T3 (lock request L2). Now, T3 adds the L3 "edge" (i.e., it wants the L3 lock which T4 holds).

In this example, task T1 would initiate the deadlock search, since it has waited longer. T1 holds a hash bucket spin lock for seeing what T1 is waiting on (specifically, what semawait). Here, T1 is waiting on T2. This information is recorded with a timestamp, whereupon the spin lock for the bucket is dropped. Now, the search examines T2, under spin lock protection (i.e., a different spin lock), to determine what it is waiting on. Again, the information is recorded with a timestamp, whereupon the spin lock for the T2 hash bucket is dropped.

Note that the sequence repeats: grabbing spin lock, recording information, and dropping spin lock for traversing the chain. Because spin locks are not held at the point of traversing from on member of the chain to another, the state of the chain can change--the data structures are potentially changing on-the-fly--while deadlock detection is underway. This is not a problem, however. Recall the unique property of a deadlock that it will not change. If anything is changing on-the-fly, then it is not a deadlock.

As noted, the search algorithm traverses lock object, semawait, and lock record data structures in appropriate hash buckets to generate the dependency graph. The system must detect deadlocks and avoid detection of spurious deadlocks. A spurious deadlock includes an apparent "edge" which has been recorded but which no longer exists as a result of on-the-fly changes to data structures. Since such a cycle is spurious, it must be distinguished from a true deadlock.

FIG. 6A illustrates how a spurious deadlock (caused by a cycle formed after a search was initiated) may arise and be recognized. Recall that, in FIG. 6A, four tasks are sleeping. The order in which the tasks went to sleep is indicated by the sequence number; "sn=0" representing the first sleep event, "sn=1" representing the next sleep event, and so forth and so on.

At a given point, task T1--the longest waiting task, will be awakened by the alarm routine for beginning a deadlock search. Suppose that, while the search is being conducted, task T2 releases the lock on which task T3 was waiting: edges L2 and L3 are now eliminated. Assume, however, that the deadlock search does not recognize this--possibly because it has already traversed edge L2. Now assume further that while the search is progressing, task T3 goes to sleep waiting on task T1 to release a lock. At that instant, the dependency graph would appear as shown in FIG. 6B. However, because the search traversed edge L2 before it was eliminated, the system may be lead to believe that the dependency graph appears as shown in FIG. 6C, with the dashed line for L2 assumed to exist. Thus, because the deadlock search is being conducted on a dynamic system, the searching task may believe that a deadlock exists when in fact none does.

To reduce the risk of detecting spurious deadlocks, the search algorithm preferably restricts its traversal to only those dependency edges that were already formed when the search started. The search is limited to those edges having "sequence numbers" less than or equal to the sequence number in existence for the task when the search began. Each number is an incrementally-increasing number assigned to a task which has to wait for a lock. During the search, the system uses the lock wait sequence number on the lock sleeptask queue to detect and discard edges that were formed after the search started. When performing deadlock detection, any edge the task is traversing which has a sequence number which is less than or equal that for the task will be examined. If the sequence number is greater than that for task, a new edge has formed and, thus, deadlock search need not be continued. Any new cycles formed from new edges may be detected by later searches (initiated after the cycles are formed). For the case of FIG. 6C, the search would disregard edge L7 having a sequence number of 3 because that edge was created after the search began. Specifically, when the search begins, the initiating task grabs the spin lock on the sleeptask queue and identifies the sequence number at that time. With this number, it can decide whether to record or ignore edges it encounters in its search.

FIG. 7 illustrates how the deadlock search method treats a cycle in which the initiating task does not part of the cycle. Initially, a task T1 queues a lock request L1 but is blocked because of a shared lock held by two tasks T2 and T5. It detects no deadlock when it traverses the edge (L1) to T5; however, it does identify a cycle when it traverses to task T4 through a task T3. At this point, the dependency graph contains a path in T1, T2, T3, and T4, with a cycle. Note, however, that T1 is not participating in the cycle and, thus, can be ignored. Nevertheless, the detection method does identify this as an "innocent bystander" deadlock. In a preferred embodiment, the search method does not try to break these types of deadlocks because of the expense involved. To choose an optimal set of victims, the method would have to record all the cycles it detects. Then it would have to select victims in a way that breaks all cycles, but leaves the least number of tasks victimized.

A task initiating a deadlock search can be involved in not just one cycle but in multiple cycles. This situation is illustrated in FIG. 8. As shown, the detection method detects a first cycle involving tasks T1, T2, T3, T4 and lock requests L1, L2, L3, and L4. It chooses one of the tasks, T1, T2, T3, and T4 as a possible victim, and the selection is recorded. The algorithm continues and eventually traverses edge L5, detecting the cycle involving T1, T2, T5, and T6 and lock requests L1, L5, L6, and L7. In a preferred embodiment, the system instead automatically rolls back the task initiating a deadlock search when that search determines that the initiating task forms part of two different cycles. Here, the detection method chooses T1 as the victim to minimize the number of deadlock victims selected.

To limit the time that may be required to undertake a deadlock search, the system set a limit on the maximum number of nesting (recursions) performed in any search. In one embodiment, a variable "recursion level" is zero when the search algorithm begins and is incremented for each new level of recursion. If the value of the recursion level variable exceeds a preset maximum, the task initiating the search is chosen as the deadlock victim.

E. Improved "free" lock management: caching "free" locks

The actual locks themselves represent resources in the system represented internally by various underlying lock data structures. Each lock is either "free" (i.e., available for use) or "allocated" (i.e., in use). These data structures are maintained on a global "freelock" list in shared memory and which is available to all server engines. Lock requests are satisfied, in part, by allocating lock data structures from this list. The approach of a single global freelock list presents a bottleneck--a single point of contention, however. More particularly, many of the performance gains of parallel lock management would remain unrealized if a bottleneck elsewhere in the process remained uncorrected. The present invention addresses this problem by providing improved methodology for global freelist management.

Contention for the global freelock list is reduced by reducing the number of accesses to it. According to the present invention, each engine now has its own list of freelock structures, known as the "engine freelock cache." Specifically, the Lock Manager 274 implements engine-specific freelock lists, one per engine, in addition to the server's global freelock list. The general operation is as follows. When a task executing on a particular engine requires a lock structure, the task "grabs" the structure from its engine's freelock cache. If no more freelock structures are available to the task (i.e., its engine's freelock list is exhausted), a (user configurable) number of lock are "moved" (logically) from the global freelock list to the engine's freelock cache. Actual access to this global freelock list for this operation (i.e., for logically moving freelock structures to and from the individual engine caches) occurs under the control of the abovementioned single freelock list spin lock; this spin lock is the LOCK.sub.-- FREELIST.sub.-- SPIN spin lock. When a task releases a lock structure, the structure is returned to the engine's freelock cache. To ensure better utilization of lock resources (i.e., ensure proper load balancing), freelock structures are moved (logically) back from the engine's freelock cached to the global freelock list when the number of structures or elements in the engine freelock cache exceeds a configurable threshold. Since this operation touches the global freelock list, it also occurs under spin lock protection.

Actual "movement" of locks is logical not physical. Here, the locks are not physically moved from a global list memory location to the engine-specific freelock caches but, instead, remain in the shared memory location allocated for the global freelock list at start up time. Changes are made to the pointers that link the lock structures together, so that when locks are "moved," they are no longer referenced as part of a "free" lock on the global freelock list.

FIG. 9 diagrammatically illustrates the above-described approach. As shown, a global freelock list 900 containing a global freelock list 910. These are available to the Lock Manager of each engine. As shown, for instance, "free" locks in list 910 are available to engine freelock caches such as cache 920 for engine 0, cache 930 for engine 1, and cache 940 for engine 2. Thus, one group of freelocks 921 has been transferred from list 900 to cache 920, another group of freelocks 931 is transferred to cache 930, yet another group of freelocks 940 is transferred to cache 941, and so forth and so on, up to an arbitrary number of engines. In the preferred embodiment, the actual size of each engine freelock cache and therefore the number of "free" locks which each holds is user configurable. With this approach of binding certain freelocks to particular engine caches, less contention exists for the global freelock list 900. Specifically, if a server engine requires a lock, it first looks to its own freelock cache, without tying up the global freelock list (and contending for its single spin lock). Only when no more freelock structures are left in an engine's own cache will a configurable number of freelock structures be moved from the global freelock list to the engine's own freelock cache.

F. Tuning lock management: user configurable settings

In preferred exemplary embodiments of the present invention, the end user--a database administrator (DBA) or application programmer--can configure the operation of the Lock Manager. The user may effect this by setting certain configuration parameters, for example. Such parameters control, for example, the deadlock search, the spin lock decomposition, and the freelock cache.

In some cases, for instance, it may be desirable to allow the user (e.g., system administrator or application programmer) to eliminate the deadlock search mechanism altogether. This might be appropriate when an application is running in which a deadlock is impossible, or at least highly unlikely. Such an application occurs when each task of the application is acting on independent data subsets. By allowing the administrator user to turn off the deadlock search mechanism for these classes of applications, system performance can be improved.

Even in those applications requiring deadlock searching, the user can configure the system by specifying when to begin deadlock searching--immediately when a task waits on a lock or at a later point in time (i.e., deferred). Here, the user specifies a "deadlock checking period" time--that is, when the time when system will perform deadlock searching. Upon the user specifying that checking should begin immediately (i.e., delay of 0), the system performs deadlock checking as soon as a task waits on a lock. Here, the system will catch a deadlock immediately, but the approach is computationally more expensive. Accordingly, the default mode of operation is to specify a delay period--deferred mode.

With deferred mode, the system does not do deadlock checking at the time of the "sleep" but, instead, defers it to some later point in time. This approach has a particular advantage. If the lock (which the task is waiting on) actually gets granted during the wait, deadlock checking is avoided altogether. In other words, there can be no deadlock since the lock was granted. Thus, the system administrator can, when for appropriate applications, configure the system to be smarter about deadlock checking.

Another exemplary user configurable parameter is the spin lock decomposition on the hash tables of the Lock Manager. As described above, the Lock Manager includes one or more spin locks on each of hash table. In one embodiment, the administrator user may configure the actual number of spin locks employed for each hash table. Thus, for example, a database administrator may configure the Lock Manager such that one spin lock is provided for every 100 hash buckets in the database pages, hash table, or every 10 hash buckets in the database pages hash table, and so forth, up to one spin lock for each hash bucket. In this manner, the user can configure the system for increased parallelism, for those environments having resources supporting an increased number of spin locks.

Still further, the Lock Manager may be designed such that the end user may specify the size of a "freelock cache." As noted, all locks provided by the Lock Manager are designated as either free or allocated. In this embodiment, the end user may specify what percentage of the total locks may be designated as freelocks for the database engines. It may also specify how many freelocks are transferred from the global freelock list to a server freelock cache when there are no more freelocks left in a server's freelock cache.

Internal operation

A. Lock Manager API

In an exemplary embodiment, the Parallel Lock Manager surfaces an application programming interface (API) to its internal clients (i.e., other modules within the database server). For purposes of implementing the present invention, the Lock Manager API preferably remains unchanged--that is, the present invention is implemented in a fashion which does not disrupt the interface to the Lock Manager. Instead, the internal operation of the Lock Manager--apart from the API--is modified for incorporating method steps of the present invention.

In the presently preferred embodiment, the Lock Manager in the system of the present invention supports the following API.

The first API call, lock.sub.-- address at lines 6-8, comprises the API call to "grab" an address lock. The address lock returned is added to a context chain (ctxchain), which comprises a chain of locks which have been queued up. The lock.sub.-- address API function would be called, for instance, by an internal client which desires to lock an index page in memory.

The next API call, lock.sub.-- logical at lines 10-13, serves to acquire a logical lock. A logical lock, which can be employed to lock a page or a table, can be held for the duration of a transaction. An address lock, in contrast, is typically held for only a brief period of time; it is not held for the duration of a transaction.

The lock.sub.-- multiple API call, at line 15, serves to process an array of lock (logical) requests. In operation, lock.sub.-- multiple calls lock.sub.-- logical repeatedly, for processing the lock requests. The lock.sub.-- multiple function returns all the requested locks (together), sleeping if need be for obtaining the requested locks.

The lock.sub.-- psema API call, at lines 17-19, is employed for a special locking purpose: locking the log page (i.e., the last page of the log). The lock.sub.-- psema function serves to hold a lock briefly--releasing the held lock at the end of the log operation. The lock.sub.-- vsema call, at lines 21-22, functions in a similar manner.

The lm.sub.-- internal.sub.-- ctxchain.sub.-- release API call, at lines 24-25, serves to release locks which have been queued up in the context chain. The API call is invoked indirectly through lock.sub.-- ctxchain.sub.-- release. The lock.sub.-- release API call, at lines 27-28, serves simply to release a lock. The particular lock being released is indicated via a lock record which is passed in as a parameter to the function.

On occasion, a requested lock might not be available for granting. Accordingly, the Lock Manager also includes a lock.sub.-- wait API call, as shown at lines 30-31. In operation, the API call waits on the lock (indicated by the passed in lock record) until the lock is granted. If a client does not receive a lock which it has requested, the client undertakes responsibility for calling lock.sub.-- wait, for waiting for the lock to be granted. As described in further detail below, only when the system is waiting on a lock will it undertake deadlock searching. In such a case, the Lock Manager invokes the internal function lock.sub.-- perform.sub.-- deadlock.sub.-- search (described below) which performs deadlock searching.

B. Lock Manager data structures

Before describing operation of the Lock Manager API functions in further detail, it is first helpful to describe data structures which are employed by the functions. A first data structure, op (i.e., operation), serves as a flag for indicating a type of lock operation required. This data structure may be constructed simply as an enumerated (integer) type as follows.

LOCK.sub.-- ACQUIRE is a flag indicating that the operation desired is to acquire a lock. LOCK.sub.-- NOWAIT is a flag also indicating that a lock should be acquired; however, the flag also indicates that the system should not wait for a lock to be acquired. LOCK.sub.-- RELEASE is a flag indicating that the operation desired is to release the lock. The LOCK.sub.-- VERIFY flag indicates that the system should verify a lock--that is, see whether a valid lock exists. LOCK.sub.-- NOQUEUE is a flag indicating that a lock should be acquired; however, the flag also indicates that if the lock cannot be granted, the request for the lock should not be queued. LOCK.sub.-- NOWAIT, in contrast, does queue the lock (but does not wait for it to be granted). LOCK.sub.-- NOQUEUE, on the other hand, indicates that the client does not want the lock if it cannot be obtained immediately.

Different types of locks are available in the system. For logical locks, seven types are provided as follows.

The first two lock types, EX.sub.-- TAB and SH.sub.-- TAB, indicate an exclusive table lock and a shared table lock, respectively. The next two lock types, EX.sub.-- INT and SH.sub.-- INT, indicate an exclusive intent lock and a shared intent lock, respectively. An "intent" lock is employed in the context of acquiring page locks. Here, the client employs the "intent" lock to make sure that the entire table is not locked. In other words, the client employs an intent lock on a table when the client is holding page locks in that table. The page-level locks, EX.sub.-- PAGE, SH.sub.-- PAGE, and UP.sub.-- PAGE, represent an exclusive page lock, a shared page lock, and an update page lock, respectively.

For address locks, the following types are provided.

As shown, two types of locks are provided: an exclusive address lock (EX.sub.-- ADDR) and a shared address lock (SH.sub.-- ADDR). The shared address lock is provided so that multiple readers of an object, such as multiple readers scanning the pages of an index, can do so in a shared fashion, thereby avoiding the need for the readers to serialize one after another.

The actual lock is represented by a lock record, LOCKREC. In an exemplary embodiment, it may be constructed as follows.

As shown, the lock record includes a "previous" pointer (lrprprev) and a "next" pointer (lrprnext), for establishing a linked list of lock records--the "context chain". The context chain exists on a per task basis: given a task, the chain indicates the locks which the task holds. The next set of pointers, lrprev and lrnext, link the lock record to the log manager data structures (i.e., a global representation of the lock). A spin lock for the hash bucket is provided by lrspinlock. This is a new data member which is added for supporting parallel lock management. An identifier representing the task holding or waiting for the lock is stored by lrspid. The next data member, lrtype, stores a lock type for logical locks (e.g., EX.sub.-- TAB, SH.sub.-- TAB, EX.sub.-- INT, SH.sub.-- INT, and the like).

The lrstatus data member stores status flags for the lock. Exemplary flags include the following.

The LR.sub.-- NOTWAITING flag indicates that the caller is not waiting (e.g., called with LOCK.sub.-- NOWAIT). The LR.sub.-- GRANTED flag indicates that the lock has been granted--the lock record is (or was) at the head of the semaphore queue. The LR.sub.-- MOVED flag indicates that the lock record (request) was moved (i.e., to another semawait). This indicates that a task went to sleep on a particular semawait but some other task requeued the lock record (request), moving from one semawait to another. Similarly, LR.sub.-- REQUEUE indicates that a lock record (request) went to sleep on a particular semawait but awoke on another. Here, the "semawait" indicates the position in the queue or line (for granting the lock request). LR.sub.-- UPGRADE indicates an upgrade of the lock request (to a different level of granularity). The LR.sub.-- UPGRDDLK flag indicates that the upgrade caused a deadlock.

The next data member of the lock record, lrsuffclass, stores information about the sufficiency of the lock, that is, whether future lock requests for the same task could be covered by the current locks. In other words, this information indicates whether the locks currently held cover the incoming lock request. The lrmagic data member serves as an integrity check for the record. The system can test this value for determining whether the lock record has been corrupted.

The lrsemawait data member stores a pointer to the semawait which can hold multiple lock requests. Recall from the lrprev and lrnext pointers that a lock record can participate on a semawait chain (of lock requests).

C. Lock Manager operation

Operation of the Lock Manager is perhaps best illustrated by example, such as processing of a client request for an address lock. The following example will focus on a single client which takes out a lock on an index page in memory (i.e., an address lock), with particular emphasis on modifications made to the Lock Manager for implementing parallel lock management. Here, one or more index pages had been read from disk into system memory. In order to gain access to one of those pages in memory, the client takes out an address lock.

For this example, the caller or "client" is getindexpage, a routine for locking an index page. The caller, shown in skeletonized form (to focus on the Lock Manager API call), is as follows.

At line 72, the routine performs general setup and initialization steps. Then, at line 74, it checks the lock mode, which specifies how a lock is released when traversing from parent to child page. At lines 76-83, the actual page is retrieved in memory, by a call to getpage. At lines 85-91, the Lock Manager is invoked for obtaining an appropriate address lock on the page (either shared or exclusive).

As shown at line 89, the actual call to the Lock Manager is made through a macro, RLOCK.sub.-- EXCLUSIVE, for ladder locking; otherwise, the call to the Lock Manager is made through the RLOCK.sub.-- SHARE macro at line 91 (for timestamp locking). These macros, in turn, expand out into calls to the Lock Manager's lock.sub.-- address API function, as shown by the following macro definitions.

# define RLOCK.sub.-- EXCLUSIVE (bp, sdes, lockrecp).backslash.lock.sub.-- address (LOCK.sub.-- ACQUIRE, EX.sub.-- ADDR, (char *) bp, &sdes.fwdarw.slocks, lockrecp)

# define RLOCK.sub.-- SHARE (bp, sdes, lockrecp).backslash.lock.sub.-- address (LOCK.sub.-- ACQUIRE, SH.sub.-- ADDR, (char *) bp, &sdes.fwdarw.slocks, lockrecp)

For a ladder locking traversal of the index pages, therefore, an exclusive lock is requested by the getindexpage function as follows:

lock.sub.-- address (LOCK.sub.-- ACQUIRE, EX.sub.-- ADDR, (char *) bp, &sdes.fwdarw.slocks, lockrecp)

As shown, the first parameter to the lock.sub.-- address call specifies a LOCK.sub.-- ACQUIRE operation. The second parameter indicates the type of lock required, here, an exclusive address lock (EX.sub.-- ADDR). The address for which the lock is required, the third parameter, is simply the address in memory (i.e., pointer to the index page; here, bp--a buffer). The fourth parameter, slocks, specifies a context chain which the client provides (via the session descriptor, sdes). Here, the session descriptor or sdes includes a slocks member, for storing the address of the lock context chain (i.e., the linked list of lock records).

The lock.sub.-- address function serves to acquire a lock on a data server address. Typically, the address will correspond to a data structure associated with an object, such as a buffer header. Address locks can be requested in shared or exclusive lock types. Compatibility for these lock types is represented by the following table.

As shown, the only compatibility which exists is between two shared address locks. Address locks are granted in the order that they are requested, thereby avoiding "starvation" of exclusive address requests. If there exists multiple readers, for instance, no reader bypasses an exclusive access. This approach leads to increased efficiency of the code (which itself is executed frequently).

In an exemplary embodiment, the lock.sub.-- address function may be constructed as follows.

The steps of the function are as follows. Local (stack) variables are declared initially, at lines 80-86. At lines 89-96, the function hashes the passed-in address into an address lock hash table. This yields a particular "bucket." Here, the bucket is protected by a spinlock; at line 96, this spinlock is grabbed. At lines 98-106, the function checks to make sure that the current task has enough locks cached. If not, more locks will be obtained from a shared/global freelist of locks.

At lines 106-114, the spinlock is asserted, thereby assuring exclusive access to the hash bucket (for guaranteeing contents and integrity of the data structures). The spinlock will be held until termination of the routine. At lines 116-125, the function looks for the object(s) which hang off the hash bucket (i.e., hash overflow chain). If the address (for the address lock) already exists in the hash bucket, an address lock has already been taken out for that object. If the address is not found there, then the current request is the first lock request for the bucket, for that particular address. At lines 127-142, a lock object is allocated (if one does not already exist in the hash table) and is linked into the hash chain. This provides a head (semaphore) in which "waiters" (i.e., those waiting for lock requests to be granted) can be chained from. The locked object is linked to the hash table using a macro, as shown specifically at line 141.

At lines 144-184, the function allocates a semawait, initializes it, and links it to the tail of the semaphore queue. Allocation of the new semawait occurs when:

(1) Request is for an exclusive address lock;

(2) Request is for a shared address lock but the semawait queue for the lock object is empty; or

(3) Request is for a shared address lock but the last semawait in the semawait queue for the lock object is for an exclusive address lock.

These conditions are specifically tested at lines 161-163.

An exclusive address lock has the property that there will exist only one lock record per semawait. In other words, a semawait will be allocated and an address lock will be allocated. If, on the other hand, the lock type is shared, multiple lock records or objects can be hanging off one semawait. Lines 161-163 specifically test if the locktype is an "exclusive address" type, or there exists no SEMAWAIT in the object (i.e., the object is linked to itself--no other SEMAWAIT is hanging off), or the head is equal to EX.sub.-- ADDR. If any of these conditions hold true, then a new SEMAWAIT is allocated (line 165) and linked in (line 168). Otherwise, the function uses the tail semawait. Here, the tail semawait already has a shared address lock and the incoming lock is a shared address lock, which can be queued to the tail.

At lines 168-192, a lock record or object is initialized and linked to the semawait. Additionally, the status flag is cleared (line 189); the lock type is set equal to the requested locktype (line 190); and the sufficiency is set equal to none (line 191). Here, only logical locks have a sufficiency class; accordingly, address locks set the sufficiency class variable to none.

At lines 194-204, the lock record is linked into the context chain. However if no context chain exists (tested at line 200), a new context chain is allocated (line 201). At lines 211-219, the lock is granted immediately if the function detects that the lock is at the head of the queue. The status flag is upgraded to "granted," at line 216. The spinlock is released at line 217, and the method returns, at line 218, with the result of LOCK.sub.-- GRANTED. If the lock is not granted at this point (i.e., the test at line 212 reveals that the request is not at the head of the queue), then the lock request must wait.

How the method terminates at this point depends on whether the caller, when invoking the function, indicated that it wanted to wait for the lock request to be granted. If the caller does not want to wait (i.e., operation is LOCK.sub.-- NOWAIT), then the lock record is marked (line 225), the status flag is set to "not waiting" (line 230), the spinlock is released (line 231), and the function returns a result of LOCK.sub.-- DIDNTWAIT (line 232). Marking the lock record allows the task to later call lock.sub.13 wait, to wait for the lock.

If the caller did not specify a "no wait" operation, then the function will wait for the lock by calling lock.sub.-- semawait, at line 238. This represents a common case. At this point, the task sleeps on the lock. When the call to lock.sub.-- semawait returns, the return result is stored in a local variable (ret), at line 238. In turn, the result is returned to the caller to lock.sub.-- address at line 243, whereupon the function is done.

Deadlock searching

A. Overview

Deadlock search can be initiated either at the time of waiting for a lock, or can be deferred for a later time. Here, deferred deadlock detection represents an optimization in the system of the present invention. In such a case, a lock can be granted without undertaking deadlock detection. The point at which the system waits on a lock is the point where the system decides whether to undertake deadlock detection (i.e., before going to sleep on the lock) or deferred detection until a later time. If the deadlock checking is deferred for a later time then a mechanism is needed to initialize the search at the later time. This is initiated by an alarm handler routine. The frequency of deadlock checking is configurable by adjusting a user-settable deadlock checking period configuration parameter.

The search method detects deadlocks by detecting cycles in a directed dependency graph amongst the tasks waiting for locks. In this graph there would be a directed edge from task A to task B if task A was waiting for a lock that task B owns. The dependency graph is not explicitly created by the method. The method actually represents only the nodes in the graph in a list called "sleeping owners list." The edges are implicitly represented through recursion of the method.

The deadlock search method employs a global sequence number and a queue. The global sequence number is called a "lock wait sequence number." This sequence number is initialized at server start-up time and incremented whenever a task has to wait for a lock. The sequence number is incremented under LOCK.sub.-- SLEEPTASK.sub.-- SPIN spinlock by the task which has to wait for its lock request. The queue, on the other hand, is called a "lock.sub.-- sleeptask queue." Each task which has to wait for a lock adds an entry to lock.sub.-- sleeptask.sub.-- queue. Once the lock is granted, the task will remove its entry from this queue. The queue comprises one or more "sleeptask" records. Each record describes the sleeping task. It stores the semawait on which the task is sleeping along with the lock wait sequence number at the time it went to sleep. Lock wait sequence number will change when the task initiates a deadlock search.

The access to this queue is serialized by LOCK.sub.-- SLEEPTASK.sub.-- SPIN spinlock. Each entry in the lock.sub.-- sleeptask.sub.-- queue has a sequence number field. When a task adds an entry to the sleeptask queue, it stores the current value of the global lock wait sequence number in the sequence number field of the entry. The task then increments the global lock wait sequence number while holding the LOCK.sub.-- SLEEPTASK.sub.-- SPIN spinlock. An array called dlscurrent.sub.-- path is used to record tasks visited in the path from the initiator of the search to the current task.

Deadlock search is initiated by the task which has to wait for a lock. The search method proceeds by creating a list of tasks which own this lock and which are waiting for some other lock. This list is the "sleeping owners list." The search method repeats recursively for each task in the sleeping owners list. A deadlock is detected when the method encounters the initiator of the search as a sleeping owner (at some level of recursion).

Spin locks are held only while creating the sleeping owners list. The relevant bucket spinlock is held while traversing the list of granted lockrecs on the head semawait to record all the sleeping owners of the lock. Then LOCK.sub.-- SLEEPTASK.sub.-- SPIN (spin lock) is held while ascertaining that the recorded owners are indeed sleeping even after the release of the bucket spinlock.

Since the deadlock search holds only the spinlock corresponding to one hash bucket at a time, lock operations can proceed on other hash buckets. In other words, the method allows the dependency graph to change while the deadlock search is in progress. As a result, new dependency edges might form and old edges might be deleted as the search is traversing the dependency graph. For correctness of the search, the search method restricts the traversal to dependency edges that were formed since the search started. Any cycles formed because of new edges are detected by later searches initiated by the tasks which created the edges. The sequence number on the lock.sub.-- sleeptask.sub.-- queue is used to detect and discard edges that were formed after the search started. Any entry added to the queue after the search started has a sequence number greater than the sequence number when the deadlock search started.

The deadlock search method does not resolve deadlocks which do not involve the initiator of the search. In the currently preferred embodiment, the method detects up to two cycles involving the initiator. The search is stopped after determining that the initiator is involved in two deadlocks. This is primarily to limit the cost of search.

B. Detailed operation of deadlock searching

During system operation, a queue of tasks exists which are sleeping on locks. Deadlocks can only happen among tasks which are sleeping. Thus, these tasks are the only candidates for performing deadlock searching. Accordingly, the deadlock search method of the present invention exploits this feature for implementing its approach.

At a high level, a given task invokes the lock.sub.-- semawait function for waiting until either a semaphore (semawait) is granted or until the task is chosen as a deadlock victim. In an exemplary embodiment, the lock.sub.-- semawait function may be constructed as follows.

Before calling the lock.sub.-- semawait function, the caller has determined that the semawait is not at the head of its semaphore queue (otherwise, the lock is granted). As shown, the function is invoked with the semaphore to wait for and the lock record to wait for. As shown at lines 22-28, the function can return a result value or flag of LOCK.sub.-- WAITED, LOCK.sub.-- DEADLOCK, or LOCK.sub.-- INTERRUPTED. LOCK.sub.-- WAITED indicates that the lock which the task had to wait for was granted. LOCK.sub.-- DEADLOCK indicates that the caller (process) was selected as a deadlock victim. LOCK.sub.-- INTERRUPTED indicates that the lock was not granted and that the task was "interrupted" while waiting for the lock. In such a case, the caller must return at some later point in time for the lock, or it can relinquish its request for the lock altogether.

The steps of the function are as follows. At line 57, the spinlock stored by the semawait is copied to a local variable, spinlock. At line 58, the function tests whether the spinlock is held (since the caller is expected to invoke this function with the spinlock held). At line 65, the function tests whether the semawait is at the head of the queue. Here, the task will only wait on the semaphore if it is not at the head of the semawait queue. As previously described, if it is at the head, then the lock has been granted (i.e., it does not need to wait). If the condition does not hold true (i.e., the semaphore is not at the head), the function knows that it has to sleep on the semaphore. Accordingly, the spinlock is released, at lines 69-70. After it has decided that it is going to sleep, the function adds an entry to the lock sleep task queue--a representation of all the tasks that are sleeping in the system for some lock, at lines 73-84. Specifically, the function grabs a sequence number (line 82) and initializes the sleep task structure (line 83).

The sleep task structure itself is constructed as follows.

Use of the structure is as follows. Each task is associated with one instance of the sleep task structure or record. Specifically, a task can only sleep on one lock at a time. In essence, the sleep task structure serves as a descriptor for a particular sleep on a lock. The sleep task structure or record is inserted into the sleep task queue, at line 84.

Once the sleep task record structure is inserted into the sleep task queue, the function determines whether to perform deferred or non-deferred deadlock detection. If the detection can be deferred (tested at line 90), the function releases the sleep task spinlock (line 96) and then goes to sleep. In a preferred embodiment, deferred detection is the default mode. Otherwise (i.e., "false" at line 90), the function proceeds to perform deadlock detection.

Before actually undertaking deadlock detection, the function must first ascertain whether another task is currently performing deadlock detection. In the preferred embodiment, only one task at a time can do deadlock detection. If another task is doing deadlock detection, the current task falls back to the deferred mode of deadlock detection. The specific check for whether deadlock detection is currently in progress is performed at line 1 12. The fall back to deferred mode occurs in the "else" statement at lines 155-163. If deadlock searching is not in progress (i.e., "true" at line 112), then the function proceeds to line 114. Now, the function can initiate deadlock searching. After initial housekeeping (e.g., setting the "in progress" flag at line 120), the function calls a high-level deadlock search routine--lock.sub.-- perform.sub.-- deadlock.sub.-- search--at line 151. If a deadlock is in fact detected, the call will return a result of LOCK.sub.-- DEADLOCK, at line 153.

With deferred mode deadlock detection, the task initially sleeps before undertaking deadlock detection. When it awakens, it determines the "reason" why it woke up. The task may awaken for one of the following reasons:

(1) The lock was granted;

(2) The task was interrupted (i.e., because of another matter requiring "attention");

(3) The task was awakened to initiate a deadlock search; or

(4) The task was selected as a deadlock victim.

Accordingly, the function will test for these conditions.

At line 237, the function tests whether the lock was granted, by testing the status flag for LR.sub.-- GRANTED. If the condition holds "true," the function releases the spinlock (line 240) and goes to the "gotlock" label at line 256, thereby bypassing the other tests. The function tests at line 262 whether the task was awakened because of an interrupt or "attention" condition. Here, the lock has not been granted. Therefore, the function performs cleanup, including releasing the spinlock (275) and removing the sleep task structure (line 286), before returning LOCK.sub.-- INTERRUPTED, at line 301.

At lines 305-306, the function tests whether the task was awakened to perform deadlock search. In this case, the task has deferred undertaking the search until it is awakened. Recall for the non-deferred deadlock search, on the other hand, the task undertakes deadlock search before sleeping or waiting. When a task is awakened from its sleep to undertake deadlock searching (i.e., "true" at lines 305-306), deadlock searching is initiated as follows. At lines 308-313, the function releases the bucket spinlock. A "deadlock" status flag is set at line 319. Then, after further initialization/housekeeping, the function invokes the deadlock search subroutine, lock.sub.-- perform.sub.-- deadlock.sub.-- search, at line 364. If a deadlock is detected, LOCK.sub.-- DEADLOCK is returned by the routine and is, in turn, returned by the lock.sub.-- semawait function, at line 366. Otherwise (i.e., no deadlock detected), the task goes back to waiting or sleeping on the lock, as indicated by line 370.

At line 375, the function tests for the fourth condition--the task is a deadlock victim. When this condition holds true (i.e., "true" at line 375), the function performs lock cleanup (line 377) and returns LOCK.sub.-- DEADLOCK, at line 378.

In the event that the task got a lock (e.g., as was shown for the "lock granted case," lines 263-257), the function proceeds to the gotlock label, shown at line 385. Here, the function "passes the baton" from one task to another. Recall that only one task at any given time can perform deadlock searching. The sleep task spinlock is released, at lines 398-399. Finally, the function returns LOCK.sub.-- WAITED, at line 407, since this represents a case where the lock was granted after waiting.

In an exemplary embodiment, the lock.sub.-- perform.sub.-- deadlock.sub.-- search function may be constructed as follows.

The function largely serves as a wrapper, performing certain initialization and housekeeping chores, before invoking the "real" deadlock workhorse routine, lock.sub.-- check.sub.-- deadlock (at line 90). The call to lock.sub.-- check.sub.-- deadlock returns status information, via deadlock.sub.-- tab. If multiple deadlocks are detected (tested at line 97), the function victimizes the initiator at line 111.

If the current task is not the victim (tested at line 123), then the sleep task entry or record is moved from head to tail, as the deadlock search has completed and the current task is not the victim. At lines 136-151, the function performs cleanup of any victim found in the deadlock search. Specifically, this is done by a call to a cleanup subroutine, at line 149. In the event that the current task is the victim, the function returns LOCK.sub.-- DEADLOCK, at line 168. Otherwise, it returns a result value of zero.

Actual deadlock checking is performed by the lock.sub.-- check.sub.-- deadlock function. In an exemplary embodiment, the function may be constructed as follows.

The function operates by performing a depth-first search of a tree of dependencies among tasks waiting for locks. The tree or graph would have a "directed edge" from task A to task B if task A is waiting for a lock that task B owns. The dependency graph is not explicitly created but is, instead, represented by recursion which occurs in the function (at lines 326-329). For instance, if task B is waiting on task A, then the function will invoke itself recursively for the task which task A is waiting on. In order to prevent stack overflow, the depth of recursion cannot exceed a maximum number of levels (here, SEMA.sub.-- MAX.sub.-- RECURSION number of levels). The recursion at a particular level stops when the function detects that one of the sleeping tasks is itself the initiator of a deadlock. Here, a deadlock is detected and a victim is selected to break the deadlock. As shown, the currently preferred embodiment does not employ any spin locks and, thus, avoids "freezing" the system while deadlock search is being performed.

The specific steps of the function are as follows. First, at lines 134-139, the function checks for stack overflow, since this is a recursive routine. At line 147, the function checks its time slice, for determining whether it needs to yield. At line 165, the function tests whether the current level has reached the maximum number of recursions (i.e., equal to SEMA.sub.-- MAX.sub.-- RECURSION). Here, an excess recursion flag is set to "true," at line 173, and a deadlock count is incremented, at line 174. Next, at lines 176-177, the requester is victimized. However, if a task is a "backout" task, a special case, then it is not victimized. Instead, the first non-backout task in the path is selected, as shown at lines 178-196. Here, the "backout" task is one which is backing out of a transaction. In order to leave the system in a consistent state, therefore, a backout task is preferably not victimized (unless there are no non-backout tasks). Finally, the "if" statement initiated at line 165 (i.e., for the case of maximum recursion) is concluded by a "return" statement, at line 197.

Ordinarily, maximum recursion has not been reached and the function proceeds to lines 200-201 to record the current path in a path array (i.e., from task A to task B to task C, and so forth and so on). The path is recorded by storing the task ID (spid) in the path array. At lines 202-211, the function creates the previously-described "sleeping owners list"--that is, the owners currently sleeping on the lock. At line 216, a "for" loop is established for examining each sleeping owner. At line 227, the function makes a last check for seeing whether the task is still sleeping. If the task is no longer sleeping, then it does not need to recurse on this entry in the sleeping owners list. In such a case, it executes the "continue" statement, at line 229.

At line 223, the function tests whether a cycle exists--that is, the sleeping owner is encountered again. In such a case, the function has found a new deadlock and, thus, increments a deadlock cycle count, at line 249. After a maximum number of search cycles has been reached (tested at line 252), the function stops looping and proceeds to choose the initiator as the victim, at line 255. However, as before, if the initiator is a "backout" task, the function instead selects the first non-backout task in the path, as shown at lines 256-277. For such a case, the method returns at line 278.

If the cycle count does not reach the limit, the function proceeds to lines 280-286, to select a deadlock victim for the current chain, by calling lock.sub.-- select.sub.-- deadlock.sub.-- victim. This is followed by clearing a "visited" bit for all tasks involved in the cycle (so that other cycles involving the same tasks can be caught). The "if" statement initiated at line 252 concludes with a "return" statement at line 323.

Otherwise (i.e., maximum cycle count has not been reached), the function or method proceeds to lines 326-329, for invoking itself recursively with the current sleeping owner. Upon returning from the recursion, the function tests whether a "victim" exists, at line 332. If one or more victims exist, the victim information is added to the deadlock chain. As the function is still at this point executing within the "for" loop established at line 216, the function will continue to loop for other deadlock candidates. In the event that the cycle count has reached a maximum limit, the function returns at line 351. Otherwise, the "for" loop loops through remaining sleeping owners. At the conclusion of the "for" loop, the function returns, at line 353.

While the invention is described in some detail with specific reference to a single preferred embodiment and certain alternatives, there is no intent to limit the invention to that particular embodiment or those specific alternatives. For example, while locks and many data structures associated with locks have been described as accessible through hash tables, those skilled in the art, enabled by the teachings of the present invention, will appreciate that other efficient-indexing access mechanisms may be employed. Further, although the discussion of the preferred embodiment focuses on exclusive and non-exclusive locks, those skilled in the art will appreciate that the teachings of the present invention may be applied to other types of locks (e.g., "intent" locks), such as the varying degrees of lock exclusivity and granularity commonly provided by database systems. In such a case, compatibility between locks can be determined by providing a lock compatibility table. Thus, the true scope of the present invention is not limited to any one of the foregoing exemplary embodiments but is instead defined by the appended claims.