Method and apparatus for dynamic lock granularity escalation and de-escalation in a computer system

• US 6,144,983 A
• Filed: 06/09/1998
• Issued: 11/07/2000
• Est. Priority Date: 06/09/1998
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Klots, Boris, Bamford, Roger J.
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US09/094,214
• Time in Patent Office: 882 Days
• Field of Search: 707/8, 710/200, 711/163, 709/104
• US Class Current: 718/104
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method and apparatus for dynamic lock granularity escalation and de-escalation in a computer system is provided. Upon receiving a request for a resource, a scope of a previously granted lock is modified. According to one embodiment, hash lock de-escalation is employed. In hash lock de-escalation, the scope of the previously granted lock held on a set of resources is reduced by de-escalating the previously granted lock from a coarser-grain lock to one or more finer-grain locks on members of the set. According to another embodiment, hash lock escalation is employed. In hash lock escalation, the scope of previously granted locks held on one or more members of the set of resources are released and promoted into a coarser-grain lock that covers the set of resources as well as the requested resource.

Claims

1. A method for managing access to a computer data resource, the method comprising:

assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values;

receiving a request for a resource in said plurality of resources;

in response to receiving said request, performing the steps of;

generating a hash value based on a key value of said resource;

identifying a hash bucket associated with said hash value;

detecting a granted lock covering any of said plurality of resources in said hash bucket;

modifying a lock scope associated with said granted lock; and

granting a new lock that covers said requested resource.

2. The method of claim 1, wherein said plurality of resources that are assigned to a particular hash bucket are disjoint relative to said key values.

3. The method of claim 1, wherein said step of detecting comprises:

testing to determine whether said granted lock covers said hash bucket; and

de-escalating said granted lock to cover a first subset of resources in said hash bucket, said first subset not including said requested resource, when said granted lock covers said hash bucket; and

wherein said new lock covering said requested resource includes a second subset of resources in said hash bucket, said second subset including said requested resource.

4. The method of claim 1, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.

5. The method of claim 1, wherein said request was issued by a requestor, the method further comprising:

testing to determine whether;

said requester already owns one or more locks on a subset of said resources in said hash bucket, said subset including at least one resource other than said requested resource, and

a lock on said hash bucket is not owned by any other entity; and

escalating said lock on said subset into a lock on said hash bucket, when said requestor already owns said one or more locks on said subset and said lock on said hash bucket is not owned by any other entity.

6. The method of claim 1, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.

7. The method of claim 1, further comprising the steps of:

creating a log of disk access paths over a period of time;

generating a hash function, based upon said log, that maps requests on adjacent resources into coarser-grain hash lock requests on disjoint sets of resources thereby breaking up a hot spot identified by said log.

8. A method for de-escalation of disjoint sets of computer data resources, comprising the steps of:

assigning a plurality of disjoint resources to a plurality of groups;

receiving a request for a lock on a resource in said plurality of disjoint resources; and

in response to receiving said request, performing the steps of;

identifying a group in said plurality of groups that includes said requested resource;

detecting a granted lock covering any constituent resource of said group;

modifying a lock scope associated with said granted lock; and

granting a new lock that covers said requested resource.

9. The method of claim 8, further comprising the steps of:

creating a log of disk access paths over a period of time; and

generating a hash function, based upon said log, said hash function assigning said plurality of disjoint resources into said plurality of groups thereby breaking up a hot spot identified by said log.

10. The method of claim 9, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.

11. The method of claim 9, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.

12. A computer system configured to perform the steps of:

assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values;

receiving a request for a resource in said plurality of resources;

in response to receiving said request, performing the steps of;

generating a hash value based on a key value of said resource;

identifying a hash bucket associated with said hash value;

detecting a granted lock covering any of said plurality of resources in said hash bucket;

modifying a lock scope associated with said granted lock; and

granting a new lock that covers said requested resource.

13. The computer system of claim 12, wherein said plurality of resources that are assigned to a particular hash bucket are disjoint relative to said key values.

14. The computer system of claim 12, wherein said step of detecting comprises:

testing to determine whether said previously granted lock covers said hash bucket; and

de-escalating said granted lock to cover a first subset of resources in said hash bucket, said first subset not including said requested resource, when said granted lock covers said hash bucket; and

wherein said new lock covering said requested resource includes a second subset of resources in said hash bucket, said second subset including said requested resource.

15. The computer system of claim 12, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.

16. The computer system of claim 12, wherein said request was issued by a requestor, the method further comprising:

testing to determine whether;

said requestor already owns one or more locks on a subset of said resources in said hash bucket, said subset including at least one resource other than said requested resource, and

a lock on said hash bucket is not owned by any other entity; and

escalating said lock on said subset into a lock on said hash bucket, when said requestor already owns said one or more locks on said subset and said lock on said hash bucket is not owned by any other entity.

17. The computer system of claim 12, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.

18. The computer system of claim 12, further configured to perform the steps of:

creating a log of disk access paths over a period of time;

generating a hash function, based upon said log, that maps requests on adjacent resources into coarser-grain hash lock requests on disjoint sets of resources thereby breaking up a hot spot identified by said log.

19. A computer system configured to perform the steps of:

assigning a plurality of disjoint resources to a plurality of groups;

receiving a request for a lock on a resource in said plurality of disjoint resources; and

in response to receiving said request, performing the steps of;

identifying a group in said plurality of groups that includes said requested resource;

detecting a granted lock covering any constituent resource said group;

modifying a lock scope associated with said granted lock when a lock is detected; and

granting a new lock that covers said requested resource.

20. The computer system of claim 19, further configured to perform the steps of:

creating a log of disk access paths over a period of time; and

generating a hash function, based upon said log, said hash function assigning said plurality of disjoint resources into said plurality of groups thereby breaking up a hot spot identified by said log.

21. The computer system of claim 20, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.

22. The computer system of claim 20, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.

23. A computer-readable medium having stored therein one or more sequences of instructions for managing access to a data resource, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values;

receiving a request for a resource in said plurality of resources;

in response to receiving said request, performing the steps of;

generating a hash value based on a key value of said resource;

identifying a hash bucket associated with said hash value;

detecting a granted lock covering any of said plurality of resources in said hash bucket;

modifying a lock scope associated with said granted lock; and

granting a new lock that covers said requested resource.

24. The computer-readable medium of claim 23, wherein said plurality of resources that are assigned to a particular hash bucket are disjoint relative to said key values.

25. The computer-readable medium of claim 23, wherein said step of detecting comprises:

testing to determine whether said previously granted lock covers said hash bucket; and

de-escalating said granted lock to cover a first subset of resources in said hash bucket, said first subset not including said requested resource, when said granted lock covers said hash bucket; and

wherein said new lock covering said requested resource includes a second subset of resources in said hash bucket, said second subset including said requested resource.

26. The computer-readable medium of claim 23, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.

27. The computer-readable medium of claim 23, wherein said request was issued by a requestor, the method further comprising:

testing to determine whether;

said requestor already owns one or more locks on a subset of said resources in said hash bucket, said subset including at least one resource other than said requested resource, and

a lock on said hash bucket is not owned by any other entity; and

escalating said lock on said subset into a lock on said hash bucket, when said requestor already owns said one or more locks on said subset and said lock on said hash bucket is not owned by any other entity.

28. The computer-readable medium of claim 23, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.

29. The computer-readable medium of claim 23, further comprising the steps of:

creating a log of disk access paths over a period of time;

generating a hash function, based upon said log, that maps requests on adjacent resources into coarser-grain hash lock requests on disjoint sets of resources thereby breaking up a hot spot identified by said log.

30. A computer-readable medium having stored therein one or more sequences of instructions for managing access to a data resource, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

assigning a plurality of disjoint resources to a plurality of groups;

receiving a request for a lock on a resource in said plurality of disjoint resources; and

in response to receiving said request, performing the steps of;

identifying a group in said plurality of groups that includes said requested resource;

detecting a granted lock covering any constituent resource in said group;

modifying a lock scope associated with said granted lock; and

granting a new lock that covers said requested resource.

31. The computer-readable medium of claim 30, further comprising the steps of:

creating a log of disk access paths over a period of time;

generating a hash function, based upon said log, said hash function assigning said plurality of disjoint resources into said plurality of groups thereby breaking up a hot spot identified by said log.

32. The computer-readable medium of claim 31, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.

33. The computer-readable medium of claim 31, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.