{"push_id":994140050,"size":1,"distinct_size":1,"ref":"refs/heads/tschottdorf/consistency","head":"c04350ac445e6e2555e289b80014e2aa9582ab16","before":"34affedacba70d0051ce35c73093e9dd81d36491","commits":[{"sha":"c04350ac445e6e2555e289b80014e2aa9582ab16","author":{"email":"25fad7a39062a81fcaf88abd782f9f69679c0bdf@gmail.com","name":"Tobias Schottdorf"},"message":"Fix an anomaly caused by command queue\n\nFixes #4607, Fixes #4560.\n\nA recent change the command queue came with an innocuous-looking optimization:\nIf a new read entered the command queue, it would not wait for previous reads\nto overlapping key ranges.\n\nUnfortunately, this introduced the anomaly explained below. Three transactions\nA, B and C overlap on a single range, with increasing timestamps. Reads touch\nall keys. A only reads; B and C try to read a maximum `m` and then write `m+1`\nto their own keys.\nThe anomaly is that sometimes, B and C can commit with the same new maximum,\nwhich is clearly not linearizable, with the history explained below. The\ncrux is (***): when B goes in for its write, it doesn't wait for C's read,\nwhich sees the same maximum B read, and should get a chance to update the\ntimestamp cache. The reason C doesn't wait for B's read is that A went in for\nits read after C started, but did not incur a dependency on A (due to the\nread-read optimization).\n\n```\n+--------------+-----------------------------+\n|      A       |       B      |       C      |\n---------------+-----------------------------+\n|              | enter CQ (r) |              |\n|              | read max = 1 |              |\n|              | leave CQ (r) |              |\n|              |              | enter CQ(r)  |\n|              |              | read max = 1 |\n| enter CQ (r) |              |              |\n|              | enter CQ (w) |              |\n|              | wait: A ***  |              |\n| read         |              |              |\n| leave CQ (r) |              |              |\n|              | write 2      |              |\n|              | commit       |              |\n|              | leave CQ (w) |              |\n|              |              | leave CQ (r) |\n|              |              | enter CQ (w) |\n|              |              | write 2      |\n|              |              | commit       |\n|              |              | leave CQ (w) |\n+--------------+--------------+--------------+\n```\n\nThe fix is easy: Have write commands wait for all underlying reads, even when\nthey are already covered.\n\n`Benchmark(Insert|Update|Delete|Scan).*Cockroach` are identical. Ditto for the\nPgbench suite, which had a tiny amount more allocs:\n\n```\nname                              old alloc/op   new alloc/op\nPgbenchExec_Cockroach-8              152kB ± 0%     153kB ± 0%\nPgbenchQuery_Cockroach-8             197kB ± 0%     197kB ± 0%\nParallelPgbenchQuery_Cockroach-8     659kB ± 0%     752kB ± 0%\n\nname                              old allocs/op  new allocs/op\nPgbenchExec_Cockroach-8              2.87k ± 0%     2.89k ± 0%\nPgbenchQuery_Cockroach-8             3.58k ± 0%     3.57k ± 0%\nParallelPgbenchQuery_Cockroach-8     9.79k ± 0%    10.79k ± 0%\n```","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach/commits/c04350ac445e6e2555e289b80014e2aa9582ab16"}]}