Scalable range locks

One or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more processors implementing a plurality of threads cause the one or more processors to perform a lock acquisition operation on a first range of elements of a shared resource, comprising:

• verifying that no currently locked ranges of elements of the shared resource overlap the first range, the first range comprising a plurality of elements, and the verifying comprising:
• scanning a linked list of descriptors of currently locked ranges to identify locked ranges of elements overlapping the first range comprising the plurality of elements, wherein the descriptors for the currently locked ranges each comprise a link to a next descriptor;
• and
• waiting for each of the identified overlapping locked ranges of elements to be released;
• and
• executing, subsequent to the verifying, an atomic operation to insert a descriptor for the first range into the linked list of descriptors of currently locked ranges to acquire a lock for the plurality of elements of the first range of elements of the shared resource, wherein the atomic operation comprises determining that no ranges overlapping the first range have been added to the linked list of descriptors;
• wherein the lock acquisition operation executes on a particular thread of the plurality of threads, and wherein the performing of the lock acquisition operation does not exclude access to the linked list of descriptors by other threads of the plurality of threads.

A system, comprising:

• one or more processors implementing a plurality of threads and a memory, the memory comprising program instructions executable by the one or more processors to perform a lock acquisition operation on a first range of elements of a shared resource, the first range comprising a plurality of elements, and the lock acquisition operation on the first range of elements configured to:
• scan a linked list of descriptors of currently locked ranges to identify locked ranges of elements overlapping the first range comprising the plurality of elements, wherein the descriptors for the currently locked ranges each comprise a link to a next descriptor;
• wait for each of the identified overlapping locked ranges of elements to be released;
• and
• execute, subsequent to waiting for each of the identified overlapping locked ranges of elements to be released, an atomic operation to insert a descriptor for the first range into the linked list of descriptors of currently locked ranges to lock the plurality of elements of the first range of elements of the shared resource, wherein the atomic operation comprises determining that no ranges overlapping the first range have been added to the linked list of descriptors;
• wherein the lock acquisition operation executes on a particular thread of the plurality of threads, and wherein the performing of the lock acquisition operation does not exclude access to the linked list of descriptors by other threads of the plurality of threads.