{"action":"created","issue":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/1644","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/1644/labels{/name}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/1644/comments","events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/1644/events","html_url":"https://github.com/cockroachdb/cockroach/issues/1644","id":93549136,"number":1644,"title":"Range created by Split may conflict with Range created by multiraft","user":{"login":"es-chow","id":11871102,"avatar_url":"https://avatars.githubusercontent.com/u/11871102?v=3","gravatar_id":"","url":"https://api.github.com/users/es-chow","html_url":"https://github.com/es-chow","followers_url":"https://api.github.com/users/es-chow/followers","following_url":"https://api.github.com/users/es-chow/following{/other_user}","gists_url":"https://api.github.com/users/es-chow/gists{/gist_id}","starred_url":"https://api.github.com/users/es-chow/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/es-chow/subscriptions","organizations_url":"https://api.github.com/users/es-chow/orgs","repos_url":"https://api.github.com/users/es-chow/repos","events_url":"https://api.github.com/users/es-chow/events{/privacy}","received_events_url":"https://api.github.com/users/es-chow/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":10,"created_at":"2015-07-07T14:51:27Z","updated_at":"2015-07-13T23:19:39Z","closed_at":null,"body":"For a normal range split, Range struct in memory created by Split will be created first before a Raft message is received.\r\n<img width=\"689\" alt=\"2015-07-07 10 20 35\" src=\"https://cloud.githubusercontent.com/assets/11871102/8548325/c514a074-24f6-11e5-80dd-e560a7fa2046.png\">\r\nBut there are some corner cases Range created by Split may conflict with Range created by multiraft when receiving a Raft message.\r\n1. Before A EndTransactionRequest(split_trigger) is applied, a Raft message from other node had been received, then a Range struct will be created by multiraft calling Store.GroupStorage such as the node 3 in the following picture.\r\n<img width=\"787\" alt=\"2015-07-07 10 22 18\" src=\"https://cloud.githubusercontent.com/assets/11871102/8548519/c01d0042-24f7-11e5-82cc-eafc0ed80061.png\">\r\n2. Before a EndTransactionRequest(split_trigger) is applied, multiple Raft message include MsgSnap from other node had been received, then this Range will failed in Range.ApplySnapshot as the key space is conflict with existing key space in the store such as the node 3 in the following picture.\r\n<img width=\"805\" alt=\"2015-07-07 10 22 27\" src=\"https://cloud.githubusercontent.com/assets/11871102/8548573/188e29e0-24f8-11e5-8782-fa47ebebb07f.png\">\r\n3. As the Applying Raft command is asynchorous with writing into storage, so some Raft messages may delayed in applying even it's a Raft leader. This also cause key space conflicting such as the node 3.\r\n<img width=\"814\" alt=\"2015-07-07 10 22 38\" src=\"https://cloud.githubusercontent.com/assets/11871102/8548705/f543771e-24f8-11e5-8d02-fb1e5ecb3d2c.png\">\r\n\r\nOne way to resolve case 1 and 2 is intercepting the MsgVote, MsgApp message if a multiraft group cannot be found in multiraft and delay the group and range creating until a MsgSnap is received and the RangeDescriptor inside is not conflict the key space in the store, if conflict, then a multiraft group and range will not be created to wait the EndTransaction(split_trigger) to finish. But this is not work with   case 3.  "},"comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments/121088463","html_url":"https://github.com/cockroachdb/cockroach/issues/1644#issuecomment-121088463","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/1644","id":121088463,"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},"created_at":"2015-07-13T23:19:39Z","updated_at":"2015-07-13T23:19:39Z","body":"@es-chow: @bdarnell and I have been discussing a more radical restructuring of things in order to eliminate the confusion we're currently dealing with in splitting and also in change replica updates. The idea is to create a new `storage.StorageKey` which would look like:\r\n\r\n```go\r\ntype StorageKey struct {\r\n  groupID proto.RaftID\r\n  replicaLogIndex uint64\r\n  key proto.Key\r\n}```\r\n\r\nThis composite key struct would be passed into the various storage/engine methods in place of `proto.Key` and would be used to provide absolute certainty about which data belongs to which range. The `groupID` and the `replicaLogIndex` would be prepended as part of `proto.EncodedKey` MVCC key values. It would mean that on splits and merges, we'd need to rewrite the data in the second half of the range to include the new `groupID` and `replicaLogIndex`. The `replicaLogIndex` for each replica would be stored in the RangeDescriptor; the `replicaLogIndex` is set to the Raft log index at which a replica was first added to the Raft group. This provides crucial support when avoiding situations where old data for a range which was rebalanced in the past conflicts with new data for a range rebalanced back to the same store at a future point in time.\r\n\r\nThoughts?"}}