I am the author and would like to point out that this mechanism is not new, since Kleppmann uses a similar approach with fencing tokens in his article "How to do distributed locking". The alternative I mention is also commonly employed. What interests me is examining the specific question each method addresses.
The situation in which things go wrong is this: a worker has been given a grant, becomes stuck on a slow call, loses the lease, and then carries out the commit. If no other writer has accessed that record during the period of stagnation, the version remains unchanged, and a simple CAS operation still functions, with the late write proceeding as before. This does not constitute a contention bug, so making the lock stricter helps little; that is usually what confuses. Although there is only one writer, its actions are divided between the stall and the reclaim.
A per-record generation number is used, incremented each time ownership changes, and this generation number is verified with the version when a commit is made. Two points I would have overlooked without guidance are these: if the generation number is only incremented during reclamation, then there is a gap. Since a clean release followed by a new claim keeps the same generation number, a late duplicate commit could still match both numbers. Also, the check has to happen at the same time as the write; otherwise you'd merely shift the race condition rather than eliminate it.
A frequent objection I respond to directly is to replace the version stored on reclaim with an empty write. In this case, a basic CAS will detect it without a second counter, and this method works. The drawback is that one counter then has to answer two different questions. As a result, every reader's cache is invalidated by a write that didn't actually change anything, and a writer whose request is rejected sees only a general version conflict rather than a clear indication that their grant has expired. This matters because the recovery procedures are different.
As for scope, since this group will examine it, there is one coordinator and one host, along with the writers who commit through it. I prefer to make my own concessions regarding vocabulary rather than have them made for me. When the grant authority and the commit path are in the same place, an equality check on a generation is simply the degenerate case of a fencing token. Fencing tokens exist exactly because the store is generally unable to ask the lock service anything. The case involving multiple hosts, where the check becomes the highest token seen at a store that is not the grant authority, is precisely the part that has not yet been shipped.
The protocol, not the actual code, is modeled using TLA+. I employ bounded model checking, and for each specification that should fail, I create a documented mutant. I never state that anything has been 'proved'.
I would like to know what failure modes in worker pools this method might miss.
1 comment
[ 6.4 ms ] story [ 13.4 ms ] threadThe situation in which things go wrong is this: a worker has been given a grant, becomes stuck on a slow call, loses the lease, and then carries out the commit. If no other writer has accessed that record during the period of stagnation, the version remains unchanged, and a simple CAS operation still functions, with the late write proceeding as before. This does not constitute a contention bug, so making the lock stricter helps little; that is usually what confuses. Although there is only one writer, its actions are divided between the stall and the reclaim.
A per-record generation number is used, incremented each time ownership changes, and this generation number is verified with the version when a commit is made. Two points I would have overlooked without guidance are these: if the generation number is only incremented during reclamation, then there is a gap. Since a clean release followed by a new claim keeps the same generation number, a late duplicate commit could still match both numbers. Also, the check has to happen at the same time as the write; otherwise you'd merely shift the race condition rather than eliminate it.
A frequent objection I respond to directly is to replace the version stored on reclaim with an empty write. In this case, a basic CAS will detect it without a second counter, and this method works. The drawback is that one counter then has to answer two different questions. As a result, every reader's cache is invalidated by a write that didn't actually change anything, and a writer whose request is rejected sees only a general version conflict rather than a clear indication that their grant has expired. This matters because the recovery procedures are different.
As for scope, since this group will examine it, there is one coordinator and one host, along with the writers who commit through it. I prefer to make my own concessions regarding vocabulary rather than have them made for me. When the grant authority and the commit path are in the same place, an equality check on a generation is simply the degenerate case of a fencing token. Fencing tokens exist exactly because the store is generally unable to ask the lock service anything. The case involving multiple hosts, where the check becomes the highest token seen at a store that is not the grant authority, is precisely the part that has not yet been shipped.
The protocol, not the actual code, is modeled using TLA+. I employ bounded model checking, and for each specification that should fail, I create a documented mutant. I never state that anything has been 'proved'.
I would like to know what failure modes in worker pools this method might miss.