Reader bias based locking technique enabling high read concurrency for read-mostly workloads
A data object has a lock and a condition indicator associated with it. Based at least partly on detecting a first setting of the condition indicator, a reader stores an indication that the reader has obtained read access to the data object in an element of a readers structure and reads the data object without acquiring the lock. A writer detects the first setting and replaces it with a second setting, indicating that the lock is to be acquired by readers before reading the data object. Prior to performing a write on the data object, the writer verifies that one or more elements of the readers structure have been cleared.
1. A computer-implemented method, comprising:
determining, by a first writer of a plurality of data accessors which includes at least the first writer and at least one reader, that a flag associated with a data object on which a write operation is to be performed by the first writer is set to a first value, wherein the first value indicates that a read operation on the data object can be performed without acquiring a lock associated with the data object;
computing, by the first writer based on one or more metrics associated with the write operation, a duration during which readers are to be prevented from performing read operations on the data object without acquiring the lock; and
causing, by the first writer, the flag to be set to a second value for at least the duration, wherein the second value indicates that the lock has to be acquired to perform a read operation on the data object.
2. The computer-implemented method as recited in claim 1 , wherein the one or more metrics includes a time for which the first writer has to wait for one or more readers to complete in-progress read operations on the data object before the first writer can initiate the write operation.
3. The computer-implemented method as recited in claim 1 , wherein the one or more metrics includes a time taken by the writer to examine a readers data structure which includes entries representing in-progress read operations on at least the data object.
4. The computer-implemented method as recited in claim 1 , wherein said causing, by the first writer, the flag to be set to the second value for at least the second duration comprises:
setting a timeout associated with the second value, such that readers are prevented from re-setting the flag to the first value until the timeout expires.
5. The computer-implemented method as recited in claim 1 , further comprising:
determining, by a first reader of the plurality of data accessors, that the flag is set to the second value;
acquiring, by the first reader, in accordance with the second value, the lock associated with the data object; and
subsequent to verifying, by the first reader, that the first reader is permitted to re-set the flag, re-setting the flag to the first value by the first reader.
6. The computer-implemented method as recited in claim 1 , further comprising:
acquiring, by the first writer, the lock on the data object prior to determining that the flag is set to the first value.
7. The computer-implemented method as recited in claim 1 , further comprising:
analyzing performance of read or write operations directed to at least the data object during an observation period; and
modifying, based at least in part on a result of said analyzing, a tuning parameter used to compute the duration during which readers are to be prevented from performing read operations on the data object without acquiring the lock.
8. A system, comprising:
one or more computing devices;
wherein the one or more computing devices include instructions that upon execution on or across the one or more computing devices:
determine, by a first writer of a plurality of data accessors which includes at least the first writer and at least one reader, that a flag associated with a data object on which a write operation is to be performed by the first writer is set to a first value, wherein the first value indicates that a read operation on the data object can be performed without acquiring a lock associated with the data object;
compute, by the first writer based on one or more metrics associated with the write operation, a duration during which readers are to be prevented from performing read operations on the data object without acquiring the lock; and
cause, by the first writer, the flag to be set to a second value for at least the duration, wherein the second value indicates that the lock has to be acquired to perform a read operation on the data object.
9. The system as recited in claim 8 , wherein the one or more metrics includes a time for which the first writer has to wait for one or more readers to complete in-progress read operations on the data object before the first writer can initiate the write operation.
10. The system as recited in claim 8 , wherein the one or more metrics includes a time taken by the writer to examine a readers data structure which includes entries representing in-progress read operations on at least the data object.
11. The system as recited in claim 8 , wherein to cause, by the first writer, the flag to be set to the second value for at least the second duration, the one or more computing devices include further instructions that upon execution on or across the one or more computing devices:
set a timeout associated with the second value, such that readers are prevented from re-setting the flag to the first value until the timeout expires.
12. The system as recited in claim 8 , wherein the one or more computing devices include further instructions that upon execution on or across the one or more computing devices:
determine, by a first reader of the plurality of data accessors, that the flag is set to the second value;
acquire, by the first reader, in accordance with the second value, the lock associated with the data object; and
subsequent to verifying, by the first reader, that the first reader is permitted to re-set the flag, re-set the flag to the first value by the first reader.
13. The system as recited in claim 8 , wherein the one or more computing devices include further instructions that upon execution on or across the one or more computing devices:
acquire, by the first writer, the lock on the data object prior to determining that the flag is set to the first value.
14. The system as recited in claim 8 , wherein the one or more computing devices include further instructions that upon execution on or across the one or more computing devices:
analyze performance of read or write operations directed to at least the data object during an observation period; and
modify, based at least in part on a result of analysis of the performance, a tuning parameter used to compute the duration during which readers are to be prevented from performing read operations on the data object without acquiring the lock.
15. A computer-implemented method, comprising:
obtaining, by one or more readers of a plurality of data accessors, read access to a first data object without acquiring a first lock on the first data object;
determining, by a writer of the plurality of data accessors, whose write is directed to the first data object, that the write is to be deferred until the one or more readers have completed respective read operations on the first data object; and
causing, by the writer, based at least in part on said determining, another reader of the plurality of data accessors to acquire the first lock to obtain read access to the first data object.
16. The computer-implemented method as recited in claim 15 , further comprising:
determining, by a first reader of the one or more readers prior to obtaining read access to the first data object, based at least in part on a first value of a flag associated with the first data object, that read access to the first data object can be obtained without acquiring the first lock; and
wherein said causing, by the writer, the other reader to acquire the first lock comprises:
setting, by the first writer, the flag to a second value.
17. The computer-implemented method as recited in claim 16 , further comprising:
re-setting the flag to the first value by the other reader after the other reader has acquired the first lock to obtain read access to the first data object.
18. The computer-implemented method as recited in claim 15 , further comprising:
setting, by the writer, a timeout such that prior to expiration of the timeout, readers are required to acquire the first lock to obtain read access to the first data object.
19. The computer-implemented method as recited in claim 18 , further comprising:
computing, by the writer, the timeout based on one or more metrics, including a metric indicating a period for which the write is deferred.
20. The computer-implemented method as recited in claim 15 , wherein said determining, by the writer of the plurality of data accessors that the write is to be deferred comprises:
examining, by the writer, contents of a data structure which contains one or more entries representing in-progress read operations on the first data object, wherein individual ones of the entries are generated by respective readers.