{"action":"created","comment":{"url":"https://api.github.com/repos/neo4j/neo4j/pulls/comments/94600180","pull_request_review_id":15109651,"id":94600180,"diff_hunk":"@@ -498,6 +498,196 @@ else if ( lastSeenKey > nextToSee )\n     }\n \n     @Test\n+    public void shouldReadCorrectlyWhenConcurrentlyInsertingOutOfOrderAndSeekingBackwards() throws Throwable\n+    {\n+        // Checkpoint config\n+        int minCheckpointInterval = 10;\n+        int maxCheckpointInterval = 20;\n+\n+        // Write group config\n+        int nbrOfGroups = 10;\n+        int wantedRangeWidth = 1_000;\n+        int rangeWidth = wantedRangeWidth - wantedRangeWidth % nbrOfGroups;\n+        int wantedNbrOfReads = 10_000;\n+\n+        // Readers config\n+        int readers = max( 1, Runtime.getRuntime().availableProcessors() - 1 );\n+\n+        // Thread communication\n+        AtomicInteger currentWriteIteration = new AtomicInteger( 0 );\n+        AtomicLong lastWrittenKey = new AtomicLong( -1 );\n+        CountDownLatch readerReadySignal = new CountDownLatch( readers );\n+        CountDownLatch startSignal = new CountDownLatch( 1 );\n+        AtomicBoolean endSignal = new AtomicBoolean();\n+        AtomicBoolean failHalt = new AtomicBoolean(); // Readers signal to writer that there is a failure\n+        AtomicReference<Throwable> readerError = new AtomicReference<>();\n+        AtomicInteger numberOfReads = new AtomicInteger();\n+\n+        // given\n+        index = createIndex( 256 );\n+\n+        Runnable reader = () -> {\n+            int numberOfLocalReads = 0;\n+            try\n+            {\n+                readerReadySignal.countDown();\n+                while ( currentWriteIteration.get() < 1 )","path":"community/index/src/test/java/org/neo4j/index/gbptree/GBPTreeIT.java","position":37,"original_position":37,"commit_id":"e06f1c43bc7900b1467c207faa3420a39ac6ce62","original_commit_id":"de721baaa8ae4046fd9c37f04cdd42a3c3ac3aa8","user":{"login":"MishaDemianenko","id":12656787,"avatar_url":"https://avatars.githubusercontent.com/u/12656787?v=3","gravatar_id":"","url":"https://api.github.com/users/MishaDemianenko","html_url":"https://github.com/MishaDemianenko","followers_url":"https://api.github.com/users/MishaDemianenko/followers","following_url":"https://api.github.com/users/MishaDemianenko/following{/other_user}","gists_url":"https://api.github.com/users/MishaDemianenko/gists{/gist_id}","starred_url":"https://api.github.com/users/MishaDemianenko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MishaDemianenko/subscriptions","organizations_url":"https://api.github.com/users/MishaDemianenko/orgs","repos_url":"https://api.github.com/users/MishaDemianenko/repos","events_url":"https://api.github.com/users/MishaDemianenko/events{/privacy}","received_events_url":"https://api.github.com/users/MishaDemianenko/received_events","type":"User","site_admin":false},"body":"not sure i see a reason for this loop","created_at":"2017-01-04T15:15:47Z","updated_at":"2017-01-04T15:33:02Z","html_url":"https://github.com/neo4j/neo4j/pull/8571#discussion_r94600180","pull_request_url":"https://api.github.com/repos/neo4j/neo4j/pulls/8571","_links":{"self":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/comments/94600180"},"html":{"href":"https://github.com/neo4j/neo4j/pull/8571#discussion_r94600180"},"pull_request":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/8571"}}},"pull_request":{"url":"https://api.github.com/repos/neo4j/neo4j/pulls/8571","id":99963285,"html_url":"https://github.com/neo4j/neo4j/pull/8571","diff_url":"https://github.com/neo4j/neo4j/pull/8571.diff","patch_url":"https://github.com/neo4j/neo4j/pull/8571.patch","issue_url":"https://api.github.com/repos/neo4j/neo4j/issues/8571","number":8571,"state":"open","locked":false,"title":"GBPTree - Backwards seek for SeekCursor","user":{"login":"burqen","id":5220077,"avatar_url":"https://avatars.githubusercontent.com/u/5220077?v=3","gravatar_id":"","url":"https://api.github.com/users/burqen","html_url":"https://github.com/burqen","followers_url":"https://api.github.com/users/burqen/followers","following_url":"https://api.github.com/users/burqen/following{/other_user}","gists_url":"https://api.github.com/users/burqen/gists{/gist_id}","starred_url":"https://api.github.com/users/burqen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/burqen/subscriptions","organizations_url":"https://api.github.com/users/burqen/orgs","repos_url":"https://api.github.com/users/burqen/repos","events_url":"https://api.github.com/users/burqen/events{/privacy}","received_events_url":"https://api.github.com/users/burqen/received_events","type":"User","site_admin":false},"body":"Introduce backwards seek in SeekCursor. This makes it possible to scan index built on top of GBPTree in descending order.\r\n\r\n**Why is this so complicated?**\r\n\r\n*General*\r\nTo allow for lock free concurrency control the GBPTree agree to only move keys between nodes in 'forward' direction, from left to right. This means when we do normal forward seek we never risk having keys moved 'passed' us and therefore we can always be sure that we never miss any keys when traversing the leaf nodes or end up in the middle of the range when traversing down the internal nodes.\r\nThis assumption, of course, does not hold when seeking backwards.\r\n\r\nThere are two complicated cases where we risk missing keys.\r\nCase 1 - Split in current node\r\nCase 2 - Split in next node while seeker is moving to that node\r\n\r\n**Case 1 - Split in current node**\r\n*Forward seek*\r\nHere, the seeker is seeking forward and has read `K0, K1, K2` and is about to read `K3`.\r\nThen `K4` is suddenly inserted and a split happens.\r\nSeeker will now wake up and find that he is now outside the range of `(previously returned key, end of range)`. But he knows that he can continue to read forward until he hits the previously returned key, which is `K2` and then continue to return the next key, `K3`.\r\n```\r\nFORWARD\r\n    Seeker->\r\n       v  \r\n[K0 K1 K2 K3]\r\n\r\n    Seeker->\r\n       v  \r\n[K0 K1 __ __]<->[K2 K3 K4 __]\r\n```\r\n\r\n*Backward seek*\r\nHere, the seeking is seeking backwards and has only read `K3` and is about to read `K2`.\r\nAgain, `K4` is inserted, causing the same split as above.\r\nSeeker now wakes up and find that the next key he can return is `K1`. What he do not see is that `K2` has been moved to the previous sibling and so, because he can not find the previously returned key, `K3`, in the current node and because the next to return, `K1`, is located to the far right in the current node he need to jump back to the previous sibling to find where to start again.\r\n```\r\nBACKWARD\r\n     <-Seeker\r\n          v  \r\n[K0 K1 K2 K3]\r\n\r\n     <-Seeker (WRONG)\r\n          v  \r\n[K0 K1 __ __]<->[K2 K3 K4 __]\r\n\r\n               <-Seeker (RIGHT)\r\n                    v  \r\n[K0 K1 __ __]<->[K2 K3 K4 __]\r\n```\r\n\r\n**Case 2 - Split in next node while seeker is moving to that node**\r\n*Forward seek*\r\nSeeker has read `K0, K1` on node 1  and has just moved to right sibling, node 2.\r\nNow, `K6` is inserted and a split  happens in node 2, right sibling of node 1.\r\nSeeker wakes up and continues to read on node 2. Everything is fine.\r\n```\r\nFORWARD\r\n                  Seeker->\r\n                     v  \r\n1:[K0 K1 __ __]<->2:[K2 K3 K4 K5]\r\n\r\n                  Seeker->\r\n                     v  \r\n1:[K0 K1 __ __]<->2:[K2 K3 __ __]<->3:[K4 K5 K6 __]\r\n```\r\n*Backward seek*\r\nSeeker has read `K4, K5` and has just moved to left sibling, node 1.\r\nInsert `K6`, split in node 2. Note that keys are move to node 3, passed our seeker.\r\nSeeker wakes up and see `K1` as next key but misses `K3` and `K2`.\r\n```\r\nBACKWARD\r\n                      <--Seeker\r\n                            v  \r\n                1:[K0 K1 K2 K3]<->2:[K4 K5 __ __]\r\n\r\n       <-Seeker\r\n            v  \r\n1:[K0 K1 __ __]<->3:[K2 K3 K4 __]<->2:[K5 K6 __ __]\r\n```\r\nTo guard for this, seeker 'scout' next sibling before moving there and read first key that he expect to see, `K3` in this case. By using a linked cursor to 'scout' we create a consistent read over the node gap. If there us suddenly another key when he goes there he knows that he could have missed some keys and he needs to go back until he find the place where he left off, `K4`.","created_at":"2017-01-03T14:36:08Z","updated_at":"2017-01-04T15:33:02Z","closed_at":null,"merged_at":null,"merge_commit_sha":"8724fb3ec23cc889086258fe61b7fbdce9f35da9","assignee":{"login":"MishaDemianenko","id":12656787,"avatar_url":"https://avatars.githubusercontent.com/u/12656787?v=3","gravatar_id":"","url":"https://api.github.com/users/MishaDemianenko","html_url":"https://github.com/MishaDemianenko","followers_url":"https://api.github.com/users/MishaDemianenko/followers","following_url":"https://api.github.com/users/MishaDemianenko/following{/other_user}","gists_url":"https://api.github.com/users/MishaDemianenko/gists{/gist_id}","starred_url":"https://api.github.com/users/MishaDemianenko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MishaDemianenko/subscriptions","organizations_url":"https://api.github.com/users/MishaDemianenko/orgs","repos_url":"https://api.github.com/users/MishaDemianenko/repos","events_url":"https://api.github.com/users/MishaDemianenko/events{/privacy}","received_events_url":"https://api.github.com/users/MishaDemianenko/received_events","type":"User","site_admin":false},"assignees":[{"login":"MishaDemianenko","id":12656787,"avatar_url":"https://avatars.githubusercontent.com/u/12656787?v=3","gravatar_id":"","url":"https://api.github.com/users/MishaDemianenko","html_url":"https://github.com/MishaDemianenko","followers_url":"https://api.github.com/users/MishaDemianenko/followers","following_url":"https://api.github.com/users/MishaDemianenko/following{/other_user}","gists_url":"https://api.github.com/users/MishaDemianenko/gists{/gist_id}","starred_url":"https://api.github.com/users/MishaDemianenko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MishaDemianenko/subscriptions","organizations_url":"https://api.github.com/users/MishaDemianenko/orgs","repos_url":"https://api.github.com/users/MishaDemianenko/repos","events_url":"https://api.github.com/users/MishaDemianenko/events{/privacy}","received_events_url":"https://api.github.com/users/MishaDemianenko/received_events","type":"User","site_admin":false}],"milestone":null,"commits_url":"https://api.github.com/repos/neo4j/neo4j/pulls/8571/commits","review_comments_url":"https://api.github.com/repos/neo4j/neo4j/pulls/8571/comments","review_comment_url":"https://api.github.com/repos/neo4j/neo4j/pulls/comments{/number}","comments_url":"https://api.github.com/repos/neo4j/neo4j/issues/8571/comments","statuses_url":"https://api.github.com/repos/neo4j/neo4j/statuses/e06f1c43bc7900b1467c207faa3420a39ac6ce62","head":{"label":"burqen:3.2-refactored-seek-cursor--seek-backwards","ref":"3.2-refactored-seek-cursor--seek-backwards","sha":"e06f1c43bc7900b1467c207faa3420a39ac6ce62","user":{"login":"burqen","id":5220077,"avatar_url":"https://avatars.githubusercontent.com/u/5220077?v=3","gravatar_id":"","url":"https://api.github.com/users/burqen","html_url":"https://github.com/burqen","followers_url":"https://api.github.com/users/burqen/followers","following_url":"https://api.github.com/users/burqen/following{/other_user}","gists_url":"https://api.github.com/users/burqen/gists{/gist_id}","starred_url":"https://api.github.com/users/burqen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/burqen/subscriptions","organizations_url":"https://api.github.com/users/burqen/orgs","repos_url":"https://api.github.com/users/burqen/repos","events_url":"https://api.github.com/users/burqen/events{/privacy}","received_events_url":"https://api.github.com/users/burqen/received_events","type":"User","site_admin":false},"repo":{"id":34265921,"name":"neo4j","full_name":"burqen/neo4j","owner":{"login":"burqen","id":5220077,"avatar_url":"https://avatars.githubusercontent.com/u/5220077?v=3","gravatar_id":"","url":"https://api.github.com/users/burqen","html_url":"https://github.com/burqen","followers_url":"https://api.github.com/users/burqen/followers","following_url":"https://api.github.com/users/burqen/following{/other_user}","gists_url":"https://api.github.com/users/burqen/gists{/gist_id}","starred_url":"https://api.github.com/users/burqen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/burqen/subscriptions","organizations_url":"https://api.github.com/users/burqen/orgs","repos_url":"https://api.github.com/users/burqen/repos","events_url":"https://api.github.com/users/burqen/events{/privacy}","received_events_url":"https://api.github.com/users/burqen/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/burqen/neo4j","description":"Graphs for Everyone","fork":true,"url":"https://api.github.com/repos/burqen/neo4j","forks_url":"https://api.github.com/repos/burqen/neo4j/forks","keys_url":"https://api.github.com/repos/burqen/neo4j/keys{/key_id}","collaborators_url":"https://api.github.com/repos/burqen/neo4j/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/burqen/neo4j/teams","hooks_url":"https://api.github.com/repos/burqen/neo4j/hooks","issue_events_url":"https://api.github.com/repos/burqen/neo4j/issues/events{/number}","events_url":"https://api.github.com/repos/burqen/neo4j/events","assignees_url":"https://api.github.com/repos/burqen/neo4j/assignees{/user}","branches_url":"https://api.github.com/repos/burqen/neo4j/branches{/branch}","tags_url":"https://api.github.com/repos/burqen/neo4j/tags","blobs_url":"https://api.github.com/repos/burqen/neo4j/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/burqen/neo4j/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/burqen/neo4j/git/refs{/sha}","trees_url":"https://api.github.com/repos/burqen/neo4j/git/trees{/sha}","statuses_url":"https://api.github.com/repos/burqen/neo4j/statuses/{sha}","languages_url":"https://api.github.com/repos/burqen/neo4j/languages","stargazers_url":"https://api.github.com/repos/burqen/neo4j/stargazers","contributors_url":"https://api.github.com/repos/burqen/neo4j/contributors","subscribers_url":"https://api.github.com/repos/burqen/neo4j/subscribers","subscription_url":"https://api.github.com/repos/burqen/neo4j/subscription","commits_url":"https://api.github.com/repos/burqen/neo4j/commits{/sha}","git_commits_url":"https://api.github.com/repos/burqen/neo4j/git/commits{/sha}","comments_url":"https://api.github.com/repos/burqen/neo4j/comments{/number}","issue_comment_url":"https://api.github.com/repos/burqen/neo4j/issues/comments{/number}","contents_url":"https://api.github.com/repos/burqen/neo4j/contents/{+path}","compare_url":"https://api.github.com/repos/burqen/neo4j/compare/{base}...{head}","merges_url":"https://api.github.com/repos/burqen/neo4j/merges","archive_url":"https://api.github.com/repos/burqen/neo4j/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/burqen/neo4j/downloads","issues_url":"https://api.github.com/repos/burqen/neo4j/issues{/number}","pulls_url":"https://api.github.com/repos/burqen/neo4j/pulls{/number}","milestones_url":"https://api.github.com/repos/burqen/neo4j/milestones{/number}","notifications_url":"https://api.github.com/repos/burqen/neo4j/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/burqen/neo4j/labels{/name}","releases_url":"https://api.github.com/repos/burqen/neo4j/releases{/id}","deployments_url":"https://api.github.com/repos/burqen/neo4j/deployments","created_at":"2015-04-20T14:38:51Z","updated_at":"2015-04-20T14:39:14Z","pushed_at":"2017-01-04T14:45:38Z","git_url":"git://github.com/burqen/neo4j.git","ssh_url":"git@github.com:burqen/neo4j.git","clone_url":"https://github.com/burqen/neo4j.git","svn_url":"https://github.com/burqen/neo4j","homepage":"http://neo4j.com","size":354493,"stargazers_count":0,"watchers_count":0,"language":"Java","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":"2.3"}},"base":{"label":"neo4j:3.2","ref":"3.2","sha":"e11d8bbecddec7abfebcd27b429d0623c596ab76","user":{"login":"neo4j","id":201120,"avatar_url":"https://avatars.githubusercontent.com/u/201120?v=3","gravatar_id":"","url":"https://api.github.com/users/neo4j","html_url":"https://github.com/neo4j","followers_url":"https://api.github.com/users/neo4j/followers","following_url":"https://api.github.com/users/neo4j/following{/other_user}","gists_url":"https://api.github.com/users/neo4j/gists{/gist_id}","starred_url":"https://api.github.com/users/neo4j/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/neo4j/subscriptions","organizations_url":"https://api.github.com/users/neo4j/orgs","repos_url":"https://api.github.com/users/neo4j/repos","events_url":"https://api.github.com/users/neo4j/events{/privacy}","received_events_url":"https://api.github.com/users/neo4j/received_events","type":"Organization","site_admin":false},"repo":{"id":6650539,"name":"neo4j","full_name":"neo4j/neo4j","owner":{"login":"neo4j","id":201120,"avatar_url":"https://avatars.githubusercontent.com/u/201120?v=3","gravatar_id":"","url":"https://api.github.com/users/neo4j","html_url":"https://github.com/neo4j","followers_url":"https://api.github.com/users/neo4j/followers","following_url":"https://api.github.com/users/neo4j/following{/other_user}","gists_url":"https://api.github.com/users/neo4j/gists{/gist_id}","starred_url":"https://api.github.com/users/neo4j/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/neo4j/subscriptions","organizations_url":"https://api.github.com/users/neo4j/orgs","repos_url":"https://api.github.com/users/neo4j/repos","events_url":"https://api.github.com/users/neo4j/events{/privacy}","received_events_url":"https://api.github.com/users/neo4j/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/neo4j/neo4j","description":"Graphs for Everyone","fork":false,"url":"https://api.github.com/repos/neo4j/neo4j","forks_url":"https://api.github.com/repos/neo4j/neo4j/forks","keys_url":"https://api.github.com/repos/neo4j/neo4j/keys{/key_id}","collaborators_url":"https://api.github.com/repos/neo4j/neo4j/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/neo4j/neo4j/teams","hooks_url":"https://api.github.com/repos/neo4j/neo4j/hooks","issue_events_url":"https://api.github.com/repos/neo4j/neo4j/issues/events{/number}","events_url":"https://api.github.com/repos/neo4j/neo4j/events","assignees_url":"https://api.github.com/repos/neo4j/neo4j/assignees{/user}","branches_url":"https://api.github.com/repos/neo4j/neo4j/branches{/branch}","tags_url":"https://api.github.com/repos/neo4j/neo4j/tags","blobs_url":"https://api.github.com/repos/neo4j/neo4j/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/neo4j/neo4j/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/neo4j/neo4j/git/refs{/sha}","trees_url":"https://api.github.com/repos/neo4j/neo4j/git/trees{/sha}","statuses_url":"https://api.github.com/repos/neo4j/neo4j/statuses/{sha}","languages_url":"https://api.github.com/repos/neo4j/neo4j/languages","stargazers_url":"https://api.github.com/repos/neo4j/neo4j/stargazers","contributors_url":"https://api.github.com/repos/neo4j/neo4j/contributors","subscribers_url":"https://api.github.com/repos/neo4j/neo4j/subscribers","subscription_url":"https://api.github.com/repos/neo4j/neo4j/subscription","commits_url":"https://api.github.com/repos/neo4j/neo4j/commits{/sha}","git_commits_url":"https://api.github.com/repos/neo4j/neo4j/git/commits{/sha}","comments_url":"https://api.github.com/repos/neo4j/neo4j/comments{/number}","issue_comment_url":"https://api.github.com/repos/neo4j/neo4j/issues/comments{/number}","contents_url":"https://api.github.com/repos/neo4j/neo4j/contents/{+path}","compare_url":"https://api.github.com/repos/neo4j/neo4j/compare/{base}...{head}","merges_url":"https://api.github.com/repos/neo4j/neo4j/merges","archive_url":"https://api.github.com/repos/neo4j/neo4j/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/neo4j/neo4j/downloads","issues_url":"https://api.github.com/repos/neo4j/neo4j/issues{/number}","pulls_url":"https://api.github.com/repos/neo4j/neo4j/pulls{/number}","milestones_url":"https://api.github.com/repos/neo4j/neo4j/milestones{/number}","notifications_url":"https://api.github.com/repos/neo4j/neo4j/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/neo4j/neo4j/labels{/name}","releases_url":"https://api.github.com/repos/neo4j/neo4j/releases{/id}","deployments_url":"https://api.github.com/repos/neo4j/neo4j/deployments","created_at":"2012-11-12T08:46:15Z","updated_at":"2017-01-04T12:31:28Z","pushed_at":"2017-01-04T15:11:49Z","git_url":"git://github.com/neo4j/neo4j.git","ssh_url":"git@github.com:neo4j/neo4j.git","clone_url":"https://github.com/neo4j/neo4j.git","svn_url":"https://github.com/neo4j/neo4j","homepage":"http://neo4j.com","size":325899,"stargazers_count":3351,"watchers_count":3351,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1047,"mirror_url":null,"open_issues_count":401,"forks":1047,"open_issues":401,"watchers":3351,"default_branch":"3.2"}},"_links":{"self":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/8571"},"html":{"href":"https://github.com/neo4j/neo4j/pull/8571"},"issue":{"href":"https://api.github.com/repos/neo4j/neo4j/issues/8571"},"comments":{"href":"https://api.github.com/repos/neo4j/neo4j/issues/8571/comments"},"review_comments":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/8571/comments"},"review_comment":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/8571/commits"},"statuses":{"href":"https://api.github.com/repos/neo4j/neo4j/statuses/e06f1c43bc7900b1467c207faa3420a39ac6ce62"}}}}
{"actor":{"display_login":"MishaDemianenko"}}