Support for Read Locks

[simlu]

How would we best go about supporting read locks (multiple read locks can be acquired at the same time)?

I'll be doing some digging and hopefully update this in a bit.

[simlu]

I did this, but it obviously won't work (since we overwrite the existing lock).
https://github.com/tristanls/dynamodb-lock-client/pull/15/files

Any idea how we would best support this?

[tristanls]

Howdy,

Been thinking about this off and on for a bit.

One issue with read locks is that it introduces the issue of priority, which rapidly increases complexity of implementation. I'm still not sure how to accomplish this.

Here's an example history:

1. Reader A acquires read lock
2. Reader B acquires read lock
3. Writer A attempts lock, fails, backs off
4. Reader A releases lock
5. Writer A attempts lock, fails (B has lock), backs off
6. Reader C acquires read lock
7. Reader B releases lock
8. Writer A attempts lock, fails (C has lock), backs off
9. .. and so on, where Writer A is starved

Now, granted, there is no fairness in the current implementation either, i.e. any process can be starved. But it seems that multiple-readers stack the deck for writers to be starved more.

Maybe that's ok?

If we did want writers to have priority... Within the constraints of storing state atomically in DynamoDB, to implement writer being able to have priority, we'd need to store some sort of an intent by a writer that a lock is being attempted, which would then have to prevent new readers from acquiring a lock. In that case, should a reader lock heartbeat fail?

I'd say that to safely implement reader locks, I'd want a TLA+ or some other formal model to gain confidence that the implementation guarantees some invariants.

What invariants would you like to guarantee for a read lock?

I assume we'd want to guarantee that a write lock can be held by only one process and no read locks can be held or acquired during that time.
Do we want to guarantee that a write lock will eventually succeed? Or we ok with write starvation? Is that a configuration parameter?