{"action":"created","issue":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5432","repository_url":"https://api.github.com/repos/cockroachdb/cockroach","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5432/labels{/name}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5432/comments","events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5432/events","html_url":"https://github.com/cockroachdb/cockroach/pull/5432","id":142245860,"number":5432,"title":"Always write intents on WriteTooOldError to prevent starvation","user":{"login":"spencerkimball","id":6147149,"avatar_url":"https://avatars.githubusercontent.com/u/6147149?v=3","gravatar_id":"","url":"https://api.github.com/users/spencerkimball","html_url":"https://github.com/spencerkimball","followers_url":"https://api.github.com/users/spencerkimball/followers","following_url":"https://api.github.com/users/spencerkimball/following{/other_user}","gists_url":"https://api.github.com/users/spencerkimball/gists{/gist_id}","starred_url":"https://api.github.com/users/spencerkimball/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/spencerkimball/subscriptions","organizations_url":"https://api.github.com/users/spencerkimball/orgs","repos_url":"https://api.github.com/users/spencerkimball/repos","events_url":"https://api.github.com/users/spencerkimball/events{/privacy}","received_events_url":"https://api.github.com/users/spencerkimball/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"tschottdorf","id":5076964,"avatar_url":"https://avatars.githubusercontent.com/u/5076964?v=3","gravatar_id":"","url":"https://api.github.com/users/tschottdorf","html_url":"https://github.com/tschottdorf","followers_url":"https://api.github.com/users/tschottdorf/followers","following_url":"https://api.github.com/users/tschottdorf/following{/other_user}","gists_url":"https://api.github.com/users/tschottdorf/gists{/gist_id}","starred_url":"https://api.github.com/users/tschottdorf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tschottdorf/subscriptions","organizations_url":"https://api.github.com/users/tschottdorf/orgs","repos_url":"https://api.github.com/users/tschottdorf/repos","events_url":"https://api.github.com/users/tschottdorf/events{/privacy}","received_events_url":"https://api.github.com/users/tschottdorf/received_events","type":"User","site_admin":false},"milestone":null,"comments":23,"created_at":"2016-03-21T03:41:46Z","updated_at":"2016-03-24T16:01:33Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/5432","html_url":"https://github.com/cockroachdb/cockroach/pull/5432","diff_url":"https://github.com/cockroachdb/cockroach/pull/5432.diff","patch_url":"https://github.com/cockroachdb/cockroach/pull/5432.patch"},"body":"This PR started out with an assumption that this would be easier\r\nthan it turned out to be and a lot of changes had to go into making\r\nthis a reality. Here's a summary of them.\r\n\r\n- On `WriteTooOldError`, MVCC code now writes at the next logical\r\n  timestamp but still returns the error. The error is used to update\r\n  the batch timestamp or batch txn timestamp. This means we can lay\r\n  down intents even when there are busy writes, which otherwise\r\n  were leading to starvation scenarios.\r\n- To deal with the new policy for write too old errors, changes\r\n  were necessary to increment and conditional put to avoid writing\r\n  incorrect values.\r\n- MVCC increment/cput code was NOT correct before for snapshot iso\r\n  because on these two read-then-mutate write commands, we are\r\n  doing the read and the write at the txn timestamp, not the txn\r\n  original timestamp. The conclusion I've come to is that we\r\n  were incorrectly using upgraded txn timestamp for successive\r\n  writes within an epoch of a txn when we should ALWAYS insist\r\n  only on using the `OrigTimestamp` for an epoch.\r\n- Snapshot isolation MUST restart on write too old errors (same\r\n  for serializable isolation, though the diff between timestamp\r\n  and orig timestamp subsumes this). In order to allow snapshot\r\n  isolation transactions to lay down intents, I've introduced a\r\n  new `Transaction.WriteTooOld` boolean in the proto, which is set\r\n  on any `WriteTooOldError` and then consulting during `EndTxn`\r\n  to prompt a restart if the isolation is `SNAPSHOT`.\r\n- MVCC intents are now abandoned instead of committed if they\r\n  have newer timestamp than the resolving transaction. This is an\r\n  integral component of the replay protection and in conjunction\r\n  with the timestamp cache, makes it impossible to commit abandoned\r\n  intents on adverserial replays.\r\n- Thread the txn ID through to the intent resolving so that a txn\r\n  which pushes an intent in its way can proceed without its txn\r\n  timestamp being incremented (and leading to a transaction retry\r\n  for serializable isolation).\r\n- Modify write timestamp cache to only include DeleteRange ops. This\r\n  should be a boon to performance. If we encounter a new timestamp\r\n  from the cache now, we always move the transaction timestamp\r\n  forward and set the WriteTooOld boolean, to guard against phantom\r\n  delete anomalies.\r\n- Removed the \"fiddleWithTimestamps\" kludge! This cleans up some\r\n  frightening code. Now we just execute the commands in a batch and\r\n  let the timestamp tick up on overlapping write commands. We're\r\n  careful to update the node clock from the store when the batch\r\n  is complete so that subsequent commands are guaranteed to see\r\n  the work done by the batch.\r\n\r\nWe were previously laboring under the misapprehension that on\r\n`WriteTooOldErrors` we were retrying transactions, thereby\r\nproviding replay protection after txn entries and the sequence\r\ncache were cleared. What we were actually doing was retrying\r\nimmediately from the store level (so going back through raft and\r\nthereby not avoiding the starvation issues). This also would fail\r\nto prevent bad replay scenarios (see below for what I think is\r\none which would cause problems).\r\n\r\nQuestion: what happens in the case of a rogue BeginTxn/Write for\r\na key which is then abandoned for final commit epoch, followed by\r\na rogue EndTxn, if the rogues arrive after the txn has been\r\ncommitted and cleaned up? The rogues in concert could resurrect\r\nthe abandoned intent and commit it, as these two rogue batches\r\nwould agree on epochs, and there was previously no protection at\r\nMVCC for committing intents with timestamps which are newer than\r\nthe commit timestamp.\r\n\r\nAll intent resolutions should update the read timestamp cache to\r\nthe timestamp of the txn. This guarantees that before a txn is GCd,\r\nthe timestamp caches for any of its abandoned intents will disallow\r\nreplays from timestamps earlier or equal to any possible replay of\r\nan earlier epoch's `EndTransaction` command.\r\n\r\nThe txn ID in the timestamp cache should be set to nil if a txn is\r\nresolving its own intents or else to the pusher txn ID in the event\r\nthat a push is responsible for the intent resolve. This allows the\r\npusher to proceed without increasing its commit timestamp and\r\npossibly restarting.\r\n\r\nTODO(tschottdorf): I removed the code to bail early on retry txn\r\nstatus in txn_coord_sender.go. I think what we want instead is a\r\nway to query through the SQL driver whether the txn is still\r\nexpected to be valid. We could just duplicate the logic that's in\r\n`EndTransaction`.\n\n<!-- Reviewable:start -->\n---\nThis change is [<img src=\"https://reviewable.io/review_button.svg\" height=\"35\" align=\"absmiddle\" alt=\"Reviewable\"/>](https://reviewable.io/reviews/cockroachdb/cockroach/5432)\n<!-- Reviewable:end -->\n"},"comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments/200901524","html_url":"https://github.com/cockroachdb/cockroach/pull/5432#issuecomment-200901524","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5432","id":200901524,"user":{"login":"tschottdorf","id":5076964,"avatar_url":"https://avatars.githubusercontent.com/u/5076964?v=3","gravatar_id":"","url":"https://api.github.com/users/tschottdorf","html_url":"https://github.com/tschottdorf","followers_url":"https://api.github.com/users/tschottdorf/followers","following_url":"https://api.github.com/users/tschottdorf/following{/other_user}","gists_url":"https://api.github.com/users/tschottdorf/gists{/gist_id}","starred_url":"https://api.github.com/users/tschottdorf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tschottdorf/subscriptions","organizations_url":"https://api.github.com/users/tschottdorf/orgs","repos_url":"https://api.github.com/users/tschottdorf/repos","events_url":"https://api.github.com/users/tschottdorf/events{/privacy}","received_events_url":"https://api.github.com/users/tschottdorf/received_events","type":"User","site_admin":false},"created_at":"2016-03-24T16:01:33Z","updated_at":"2016-03-24T16:01:33Z","body":"basically LGTM, with a handful of teeny weenie comments.\n\n---\n\nReviewed 33 of 33 files at r10, 29 of 29 files at r12, 4 of 13 files at r13, 6 of 12 files at r14, 14 of 14 files at r15.\nReview status: all files reviewed at latest revision, 28 unresolved discussions.\n\n---\n\n*[roachpb/data.go, line 899 \\[r8\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDZ0sSxUVyIAkRbYvYM:-KDdFC1OlmZv846q3eJY:1414672565) ([raw file](https://github.com/cockroachdb/cockroach/blob/f2b6b741bbd25fdaf1f56dd81fcec2ce579d6972/roachpb/data.go#L899)):*\n`keys.Addr`, but you don't want it here.\n\nThe code below is equivalent to `return bytes.Compare(s.EndKey, o.Key) > 0 && bytes.Compare(o.EndKey, s.Key) > 0`.\n\n---\n\n*[roachpb/data_test.go, line 657 \\[r15\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDdGqblfDIbmA4f0DfY:-KDdGqblfDIbmA4f0DfZ:-1304416019) ([raw file](https://github.com/cockroachdb/cockroach/blob/975be766384c58fbf015dcff369026f97333ed23/roachpb/data_test.go#L657)):*\ns/$/./\n\n---\n\n*[roachpb/errors.proto, line 90 \\[r15\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDdHIX5DsvJUKy8joKY:-KDdHIX6wbcTcZilE5aY:-771295487) ([raw file](https://github.com/cockroachdb/cockroach/blob/975be766384c58fbf015dcff369026f97333ed23/roachpb/errors.proto#L90)):*\nCan you add more comments on when that happens and how it's handled (I'm assuming it should never happen to users, and it's handled just like any other error that kills the transaction).\n\n---\n\n*[storage/replica.go, line 1685 \\[r8\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDZ3_YKHiL7TIGupxHV:-KDdI5MzcwruDJnFpEuC:-1598173125) ([raw file](https://github.com/cockroachdb/cockroach/blob/f2b6b741bbd25fdaf1f56dd81fcec2ce579d6972/storage/replica.go#L1685)):*\nYou have an example in the test, mention that this has limitations with a reference to that test. Also wouldn't hurt to point out that this replay protection here is best-effort, but not complete (for example, replay bursts which come out of order will probably slip through since you never see the exact timestamp twice in a row). Just to avoid a false sense of certainty around this in folks who don't know the code as well.\n\n---\n\n*[storage/replica_test.go, line 2106 \\[r3\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDU7bVgMgYG6Zqakf3v:-KDdK5eHQoXIHLu6i-nw:572619457) ([raw file](https://github.com/cockroachdb/cockroach/blob/4bf98e0b7bb0f1648b0298aa4069da1966699b8c/storage/replica_test.go#L2106)):*\nright, but `ba.Txn` is the only moving part I'm actually (legitimately, because we do change it) worried about.\n\n---\n\n*[storage/replica_test.go, line 2108 \\[r15\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDdIz2ImMzH5pGikspN:-KDdIz2ImMzH5pGikspO:-1304122883) ([raw file](https://github.com/cockroachdb/cockroach/blob/975be766384c58fbf015dcff369026f97333ed23/storage/replica_test.go#L2108)):*\ns/.*//\n\n---\n\n*[storage/replica_test.go, line 2151 \\[r15\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDdJDwrlnQ0Tjw_xkZ0:-KDdJDwrlnQ0Tjw_xkZ1:-173769222) ([raw file](https://github.com/cockroachdb/cockroach/blob/975be766384c58fbf015dcff369026f97333ed23/storage/replica_test.go#L2151)):*\nCan you add a more details here?\n\n---\n\n*[storage/store.go, line 1666 \\[r8\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDZ5wSKDWN3CUd9knd4:-KDdKQQOMrwQQT1Wff7N:1861822066) ([raw file](https://github.com/cockroachdb/cockroach/blob/f2b6b741bbd25fdaf1f56dd81fcec2ce579d6972/storage/store.go#L1666)):*\nSorry, don't meant \"mutate `ba.Txn`\", I meant \"no need for the TODO here because you're only changing the pointer `ba.Txn` and that's fine\". The new code actually does wipe over our original `*ba.Txn`, we don't want that. So `maybeUpdateTransaction` should keep returning an error, but you can assign to `ba.Txn` without a TODO.\n\n---\n\n*[storage/store.go, line 1673 \\[r15\\]](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-KDdL13Ya8jcAEK5bhts:-KDdL13Ya8jcAEK5bhtt:1437300220) ([raw file](https://github.com/cockroachdb/cockroach/blob/975be766384c58fbf015dcff369026f97333ed23/storage/store.go#L1673)):*\nbtw, couldn't this be a very expensive check to always perform on a write intent error? After all, this is a whole Raft command to a possibly remote node. Can we save it for the common case somehow?\n\n---\n\n\n*Comments from the [review on Reviewable.io](https://reviewable.io:443/reviews/cockroachdb/cockroach/5432#-:-KDdLjkw5LI12MBG7dG-:772378451)*\n<!-- Sent from Reviewable.io -->\n"}}