{"action":"created","comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments/37533374","id":37533374,"diff_hunk":"@@ -0,0 +1,232 @@\n+- Feature Name: Stateless Replica Relocation\n+- Status: draft\n+- Start Date: 2015-08-19\n+- RFC PR:\n+- Cockroach Issue: #620\n+\n+# Summary\n+A relocation is, conceptually, the transfer of a single replica from one store to\n+another. However, the implementation is necessarily the combination of two operations:\n+\n+1. Creating a new replica for a range on a new store.\n+2. Removing a replica of the same range from a different store.\n+\n+For example, by creating a replica on store Y and then removing a replica from\n+store X, you have in effect moved the replica from X to Y.\n+\n+This PR is suggesting an overall architectural design goal: that the decision to\n+make any individual operation (either a create or a remove) should be **stateless**.\n+In other words, the second operation in a replica relocation should not depend on a\n+specific invocation of the first operation.\n+\n+# Motivation\n+For an assortment of reasons, Cockroach will often need to relocate the replicas\n+of a range. Most immediately, this is needed for repair (when a store dies and\n+its replicas are no longer usable) and rebalance (relocating replicas on\n+overloaded stores to stores with excess capacity).\n+\n+In order to retain the integrity of a range's raft consensus group, a relocation\n+must be expressed as a combination of two operations:\n+\n+1. Creating a new replica for a range on a new store.\n+2. Removing a replica of the same range from a different store.\n+\n+These operations can happen in either order as long as quorum is maintained in\n+the range's raft group after each individual operation, although one ordering may be\n+preferred over another.\n+\n+Expressing a specific relocation (i.e. \"move replica from store X to store Y\")\n+would require maintaining some persistent state to link the two operations\n+involved.  Storing that state presents a number of issues: where is it stored,\n+in memory or on disk? If it's in memory, does it have to be replicated through\n+raft or is it local to one node?  If on disk, can the persistent state become\n+stale? How do you detect conflicts between two relocation operations initiated\n+from different places?\n+\n+This RFC suggests that no such relocation state should be persisted. Instead, a\n+system that wants to initiate a relocation will perform only the first\n+operation, and a different system will detect the need for a complementary\n+operation and perform it. A relocation is thus completed without any state being\n+exchanged between those two systems.\n+\n+By eliminating the need to persist any data about in-progress relocation\n+operations, the overall system is dramatically simplified.\n+\n+# Detailed design\n+The implementation involves a few pieces:\n+\n+1. Each range must have a persisted target replication state. This does not\n+   prescribe specific replica locations; it suggests only a desired number of\n+   replicas and some desired attributes of the stores they are placed on.\n+2. The core mechanic is a stateless function which can compare the immediate\n+   replication state of a range to its target replication state; if the desired\n+   state is different, this function will either create or remove replicas until\n+   the target state is matched.\n+3. Finally, any operations that wish to relocate a replica need only perform the\n+   first operation of the relocation (either a create or a remove). This will\n+   perturb the range's replication state away from its target; the core function\n+   will later detect the mismatch, and correct it by performing the\n+   complementary operation of the relocation (a remove or a create).\n+\n+The first piece is already present: each range has a zone configuration\n+which determines the target replication state for the range.\n+\n+The second piece, the core mechanic, will be performed by the replicate\n+queue. This queue is already used to add replicas to ranges which are\n+under-replicated; it can be enhanced to remove replicas from over-replicated\n+ranges, thus satisfying the basic requirements of the core mechanic. Detailed\n+design for these changes are in a [separate RFC (#2153)](https://github.com/cockroachdb/cockroach/pull/2153).\n+\n+The third piece simply informs the design of systems performing relocations:\n+most immediately, these will be the rebalance system and the repair system.\n+These systems, when identifying a relocation opportunity, will simply perform\n+the first operation of the relocation, and the replicate queue will perform the\n+complementary operation. \n+\n+RFCs for these operations are forthcoming.","path":"docs/RFCS/stateless_replica_relocation.md","position":86,"original_position":86,"commit_id":"848c3a4dc0f6a61c6e07476369c01e9b0bc7d202","original_commit_id":"848c3a4dc0f6a61c6e07476369c01e9b0bc7d202","user":{"login":"vivekmenezes","id":11774212,"avatar_url":"https://avatars.githubusercontent.com/u/11774212?v=3","gravatar_id":"","url":"https://api.github.com/users/vivekmenezes","html_url":"https://github.com/vivekmenezes","followers_url":"https://api.github.com/users/vivekmenezes/followers","following_url":"https://api.github.com/users/vivekmenezes/following{/other_user}","gists_url":"https://api.github.com/users/vivekmenezes/gists{/gist_id}","starred_url":"https://api.github.com/users/vivekmenezes/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vivekmenezes/subscriptions","organizations_url":"https://api.github.com/users/vivekmenezes/orgs","repos_url":"https://api.github.com/users/vivekmenezes/repos","events_url":"https://api.github.com/users/vivekmenezes/events{/privacy}","received_events_url":"https://api.github.com/users/vivekmenezes/received_events","type":"User","site_admin":false},"body":"I'd also add a section in that design doc about the replication queue.","created_at":"2015-08-20T14:13:17Z","updated_at":"2015-08-20T14:13:17Z","html_url":"https://github.com/cockroachdb/cockroach/pull/2171#discussion_r37533374","pull_request_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2171","_links":{"self":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments/37533374"},"html":{"href":"https://github.com/cockroachdb/cockroach/pull/2171#discussion_r37533374"},"pull_request":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2171"}}},"pull_request":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2171","id":42869719,"html_url":"https://github.com/cockroachdb/cockroach/pull/2171","diff_url":"https://github.com/cockroachdb/cockroach/pull/2171.diff","patch_url":"https://github.com/cockroachdb/cockroach/pull/2171.patch","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/2171","number":2171,"state":"open","locked":false,"title":"RFC for stateless replica relocation.","user":{"login":"mrtracy","id":6969858,"avatar_url":"https://avatars.githubusercontent.com/u/6969858?v=3","gravatar_id":"","url":"https://api.github.com/users/mrtracy","html_url":"https://github.com/mrtracy","followers_url":"https://api.github.com/users/mrtracy/followers","following_url":"https://api.github.com/users/mrtracy/following{/other_user}","gists_url":"https://api.github.com/users/mrtracy/gists{/gist_id}","starred_url":"https://api.github.com/users/mrtracy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mrtracy/subscriptions","organizations_url":"https://api.github.com/users/mrtracy/orgs","repos_url":"https://api.github.com/users/mrtracy/repos","events_url":"https://api.github.com/users/mrtracy/events{/privacy}","received_events_url":"https://api.github.com/users/mrtracy/received_events","type":"User","site_admin":false},"body":"","created_at":"2015-08-19T22:03:24Z","updated_at":"2015-08-20T14:13:17Z","closed_at":null,"merged_at":null,"merge_commit_sha":"aec3ec0f6478edf88b5fb7f58a9c459978dc3ed1","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2171/commits","review_comments_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2171/comments","review_comment_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments{/number}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/2171/comments","statuses_url":"https://api.github.com/repos/cockroachdb/cockroach/statuses/848c3a4dc0f6a61c6e07476369c01e9b0bc7d202","head":{"label":"mrtracy:mtracy-rfcs-stateless-relocate","ref":"mtracy-rfcs-stateless-relocate","sha":"848c3a4dc0f6a61c6e07476369c01e9b0bc7d202","user":{"login":"mrtracy","id":6969858,"avatar_url":"https://avatars.githubusercontent.com/u/6969858?v=3","gravatar_id":"","url":"https://api.github.com/users/mrtracy","html_url":"https://github.com/mrtracy","followers_url":"https://api.github.com/users/mrtracy/followers","following_url":"https://api.github.com/users/mrtracy/following{/other_user}","gists_url":"https://api.github.com/users/mrtracy/gists{/gist_id}","starred_url":"https://api.github.com/users/mrtracy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mrtracy/subscriptions","organizations_url":"https://api.github.com/users/mrtracy/orgs","repos_url":"https://api.github.com/users/mrtracy/repos","events_url":"https://api.github.com/users/mrtracy/events{/privacy}","received_events_url":"https://api.github.com/users/mrtracy/received_events","type":"User","site_admin":false},"repo":{"id":39856388,"name":"cockroach","full_name":"mrtracy/cockroach","owner":{"login":"mrtracy","id":6969858,"avatar_url":"https://avatars.githubusercontent.com/u/6969858?v=3","gravatar_id":"","url":"https://api.github.com/users/mrtracy","html_url":"https://github.com/mrtracy","followers_url":"https://api.github.com/users/mrtracy/followers","following_url":"https://api.github.com/users/mrtracy/following{/other_user}","gists_url":"https://api.github.com/users/mrtracy/gists{/gist_id}","starred_url":"https://api.github.com/users/mrtracy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mrtracy/subscriptions","organizations_url":"https://api.github.com/users/mrtracy/orgs","repos_url":"https://api.github.com/users/mrtracy/repos","events_url":"https://api.github.com/users/mrtracy/events{/privacy}","received_events_url":"https://api.github.com/users/mrtracy/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/mrtracy/cockroach","description":"A Scalable, Geo-Replicated, Transactional Datastore","fork":true,"url":"https://api.github.com/repos/mrtracy/cockroach","forks_url":"https://api.github.com/repos/mrtracy/cockroach/forks","keys_url":"https://api.github.com/repos/mrtracy/cockroach/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mrtracy/cockroach/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mrtracy/cockroach/teams","hooks_url":"https://api.github.com/repos/mrtracy/cockroach/hooks","issue_events_url":"https://api.github.com/repos/mrtracy/cockroach/issues/events{/number}","events_url":"https://api.github.com/repos/mrtracy/cockroach/events","assignees_url":"https://api.github.com/repos/mrtracy/cockroach/assignees{/user}","branches_url":"https://api.github.com/repos/mrtracy/cockroach/branches{/branch}","tags_url":"https://api.github.com/repos/mrtracy/cockroach/tags","blobs_url":"https://api.github.com/repos/mrtracy/cockroach/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mrtracy/cockroach/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mrtracy/cockroach/git/refs{/sha}","trees_url":"https://api.github.com/repos/mrtracy/cockroach/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mrtracy/cockroach/statuses/{sha}","languages_url":"https://api.github.com/repos/mrtracy/cockroach/languages","stargazers_url":"https://api.github.com/repos/mrtracy/cockroach/stargazers","contributors_url":"https://api.github.com/repos/mrtracy/cockroach/contributors","subscribers_url":"https://api.github.com/repos/mrtracy/cockroach/subscribers","subscription_url":"https://api.github.com/repos/mrtracy/cockroach/subscription","commits_url":"https://api.github.com/repos/mrtracy/cockroach/commits{/sha}","git_commits_url":"https://api.github.com/repos/mrtracy/cockroach/git/commits{/sha}","comments_url":"https://api.github.com/repos/mrtracy/cockroach/comments{/number}","issue_comment_url":"https://api.github.com/repos/mrtracy/cockroach/issues/comments{/number}","contents_url":"https://api.github.com/repos/mrtracy/cockroach/contents/{+path}","compare_url":"https://api.github.com/repos/mrtracy/cockroach/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mrtracy/cockroach/merges","archive_url":"https://api.github.com/repos/mrtracy/cockroach/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mrtracy/cockroach/downloads","issues_url":"https://api.github.com/repos/mrtracy/cockroach/issues{/number}","pulls_url":"https://api.github.com/repos/mrtracy/cockroach/pulls{/number}","milestones_url":"https://api.github.com/repos/mrtracy/cockroach/milestones{/number}","notifications_url":"https://api.github.com/repos/mrtracy/cockroach/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mrtracy/cockroach/labels{/name}","releases_url":"https://api.github.com/repos/mrtracy/cockroach/releases{/id}","created_at":"2015-07-28T20:33:41Z","updated_at":"2015-07-28T20:33:42Z","pushed_at":"2015-08-19T22:02:44Z","git_url":"git://github.com/mrtracy/cockroach.git","ssh_url":"git@github.com:mrtracy/cockroach.git","clone_url":"https://github.com/mrtracy/cockroach.git","svn_url":"https://github.com/mrtracy/cockroach","homepage":null,"size":27909,"stargazers_count":0,"watchers_count":0,"language":"Go","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"cockroachdb:master","ref":"master","sha":"d8144731e146f52943562cb2bb6e4d0d12cfba6b","user":{"login":"cockroachdb","id":6748139,"avatar_url":"https://avatars.githubusercontent.com/u/6748139?v=3","gravatar_id":"","url":"https://api.github.com/users/cockroachdb","html_url":"https://github.com/cockroachdb","followers_url":"https://api.github.com/users/cockroachdb/followers","following_url":"https://api.github.com/users/cockroachdb/following{/other_user}","gists_url":"https://api.github.com/users/cockroachdb/gists{/gist_id}","starred_url":"https://api.github.com/users/cockroachdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cockroachdb/subscriptions","organizations_url":"https://api.github.com/users/cockroachdb/orgs","repos_url":"https://api.github.com/users/cockroachdb/repos","events_url":"https://api.github.com/users/cockroachdb/events{/privacy}","received_events_url":"https://api.github.com/users/cockroachdb/received_events","type":"Organization","site_admin":false},"repo":{"id":16563587,"name":"cockroach","full_name":"cockroachdb/cockroach","owner":{"login":"cockroachdb","id":6748139,"avatar_url":"https://avatars.githubusercontent.com/u/6748139?v=3","gravatar_id":"","url":"https://api.github.com/users/cockroachdb","html_url":"https://github.com/cockroachdb","followers_url":"https://api.github.com/users/cockroachdb/followers","following_url":"https://api.github.com/users/cockroachdb/following{/other_user}","gists_url":"https://api.github.com/users/cockroachdb/gists{/gist_id}","starred_url":"https://api.github.com/users/cockroachdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cockroachdb/subscriptions","organizations_url":"https://api.github.com/users/cockroachdb/orgs","repos_url":"https://api.github.com/users/cockroachdb/repos","events_url":"https://api.github.com/users/cockroachdb/events{/privacy}","received_events_url":"https://api.github.com/users/cockroachdb/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/cockroachdb/cockroach","description":"A Scalable, Geo-Replicated, Transactional Datastore","fork":false,"url":"https://api.github.com/repos/cockroachdb/cockroach","forks_url":"https://api.github.com/repos/cockroachdb/cockroach/forks","keys_url":"https://api.github.com/repos/cockroachdb/cockroach/keys{/key_id}","collaborators_url":"https://api.github.com/repos/cockroachdb/cockroach/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/cockroachdb/cockroach/teams","hooks_url":"https://api.github.com/repos/cockroachdb/cockroach/hooks","issue_events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/events{/number}","events_url":"https://api.github.com/repos/cockroachdb/cockroach/events","assignees_url":"https://api.github.com/repos/cockroachdb/cockroach/assignees{/user}","branches_url":"https://api.github.com/repos/cockroachdb/cockroach/branches{/branch}","tags_url":"https://api.github.com/repos/cockroachdb/cockroach/tags","blobs_url":"https://api.github.com/repos/cockroachdb/cockroach/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/cockroachdb/cockroach/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/cockroachdb/cockroach/git/refs{/sha}","trees_url":"https://api.github.com/repos/cockroachdb/cockroach/git/trees{/sha}","statuses_url":"https://api.github.com/repos/cockroachdb/cockroach/statuses/{sha}","languages_url":"https://api.github.com/repos/cockroachdb/cockroach/languages","stargazers_url":"https://api.github.com/repos/cockroachdb/cockroach/stargazers","contributors_url":"https://api.github.com/repos/cockroachdb/cockroach/contributors","subscribers_url":"https://api.github.com/repos/cockroachdb/cockroach/subscribers","subscription_url":"https://api.github.com/repos/cockroachdb/cockroach/subscription","commits_url":"https://api.github.com/repos/cockroachdb/cockroach/commits{/sha}","git_commits_url":"https://api.github.com/repos/cockroachdb/cockroach/git/commits{/sha}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/comments{/number}","issue_comment_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments{/number}","contents_url":"https://api.github.com/repos/cockroachdb/cockroach/contents/{+path}","compare_url":"https://api.github.com/repos/cockroachdb/cockroach/compare/{base}...{head}","merges_url":"https://api.github.com/repos/cockroachdb/cockroach/merges","archive_url":"https://api.github.com/repos/cockroachdb/cockroach/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/cockroachdb/cockroach/downloads","issues_url":"https://api.github.com/repos/cockroachdb/cockroach/issues{/number}","pulls_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls{/number}","milestones_url":"https://api.github.com/repos/cockroachdb/cockroach/milestones{/number}","notifications_url":"https://api.github.com/repos/cockroachdb/cockroach/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/labels{/name}","releases_url":"https://api.github.com/repos/cockroachdb/cockroach/releases{/id}","created_at":"2014-02-06T00:18:47Z","updated_at":"2015-08-20T06:56:13Z","pushed_at":"2015-08-20T13:45:41Z","git_url":"git://github.com/cockroachdb/cockroach.git","ssh_url":"git@github.com:cockroachdb/cockroach.git","clone_url":"https://github.com/cockroachdb/cockroach.git","svn_url":"https://github.com/cockroachdb/cockroach","homepage":null,"size":49419,"stargazers_count":5016,"watchers_count":5016,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":398,"mirror_url":null,"open_issues_count":149,"forks":398,"open_issues":149,"watchers":5016,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2171"},"html":{"href":"https://github.com/cockroachdb/cockroach/pull/2171"},"issue":{"href":"https://api.github.com/repos/cockroachdb/cockroach/issues/2171"},"comments":{"href":"https://api.github.com/repos/cockroachdb/cockroach/issues/2171/comments"},"review_comments":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2171/comments"},"review_comment":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2171/commits"},"statuses":{"href":"https://api.github.com/repos/cockroachdb/cockroach/statuses/848c3a4dc0f6a61c6e07476369c01e9b0bc7d202"}}}}