{"action":"created","comment":{"url":"https://api.github.com/repos/neo4j/neo4j/pulls/comments/89322397","pull_request_review_id":9867858,"id":89322397,"diff_hunk":"@@ -0,0 +1,167 @@\n+/*\n+ * Copyright (c) 2002-2016 \"Neo Technology,\"\n+ * Network Engine for Objects in Lund AB [http://neotechnology.com]\n+ *\n+ * This file is part of Neo4j.\n+ *\n+ * Neo4j is free software: you can redistribute it and/or modify\n+ * it under the terms of the GNU General Public License as published by\n+ * the Free Software Foundation, either version 3 of the License, or\n+ * (at your option) any later version.\n+ *\n+ * This program is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n+ * GNU General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU General Public License\n+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.\n+ */\n+package org.neo4j.index.gbptree;\n+\n+import java.util.Comparator;\n+\n+import org.neo4j.io.pagecache.PageCursor;\n+\n+/**\n+ * Main point of interaction for customizing a {@link GBPTree}, how its keys and values are represented\n+ * as bytes and what keys and values contains.\n+ * <p>\n+ * Additionally custom meta data can be supplied, which will be persisted in {@link GBPTree}.\n+ *\n+ * @param <KEY> type of key\n+ * @param <VALUE> type of value\n+ */\n+public interface Layout<KEY,VALUE> extends Comparator<KEY>\n+{\n+    /**\n+     * @return new key instances.\n+     */\n+    KEY newKey();\n+\n+    /**\n+     * Populates {@code into} with minimum key that can ever exist in a tree with this layout.\n+     *\n+     * @param into instance to write minimum key into.\n+     * @return the provided {@code into} instance for convenience.\n+     */\n+    KEY minKey( KEY into );\n+\n+    /**\n+     * Populates {@code into} with maximum key that can ever exist in a tree with this layout.\n+     *\n+     * @param into instance to write maximum key into.\n+     * @return the provided {@code into} instance for convenience.\n+     */\n+    KEY maxKey( KEY into );\n+\n+    /**\n+     * Copies contents of {@code key} to {@code into}.\n+     *\n+     * @param key key (left unchanged as part of this call) to copy contents from.\n+     * @param into key (changed as part of this call) to copy contents into.\n+     */\n+    void copyKey( KEY key, KEY into );","path":"community/index/src/main/java/org/neo4j/index/gbptree/Layout.java","position":64,"original_position":64,"commit_id":"ca95fb7c9f23522ddecd8d991b56e02d3fe83927","original_commit_id":"95517dfbd7071260357f737d14f48e8b6aebbeaf","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":"waaait, should key itself knew that?","created_at":"2016-11-23T14:10:05Z","updated_at":"2016-11-23T14:10:05Z","html_url":"https://github.com/neo4j/neo4j/pull/8408#discussion_r89322397","pull_request_url":"https://api.github.com/repos/neo4j/neo4j/pulls/8408","_links":{"self":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/comments/89322397"},"html":{"href":"https://github.com/neo4j/neo4j/pull/8408#discussion_r89322397"},"pull_request":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/8408"}}},"pull_request":{"url":"https://api.github.com/repos/neo4j/neo4j/pulls/8408","id":94587799,"html_url":"https://github.com/neo4j/neo4j/pull/8408","diff_url":"https://github.com/neo4j/neo4j/pull/8408.diff","patch_url":"https://github.com/neo4j/neo4j/pull/8408.patch","issue_url":"https://api.github.com/repos/neo4j/neo4j/issues/8408","number":8408,"state":"open","locked":false,"title":"Introducting GBPTree, initial step for native indexing","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":"**WHAT?**\r\nThis is the first step in building a generation-aware B+tree (GB+Tree) implementation directly atop a PageCache with no caching in between. Additionally internal and leaf nodes on same level are linked both left and right with sibling pointers, this to provide correct reading when concurrently modifying the tree.\r\n\r\n**WHY?**\r\nInitial prototyping has shown great performance improvement on label scan store writes compared to lucene.\r\n\r\nA GB+Tree could potentially be used for a lot of different types of indexes, path index for example.\r\n\r\n**DETAILS ON IMPLEMENTATION**\r\n*Non blocking*\r\nTree is modified by a single writer, multiple concurrent readers are allowed. Both reading and writing is non blocking.\r\n\r\n*Garbage*\r\nImplementation aim to make reading and writing garbage free.\r\n\r\n*Build order*\r\nThe 'index' module is built directly before 'kernel' module, see community package pom.\r\n\r\n**GENERATION**\r\nEvery node and child/sibling pointer has a generation indicating when it first evolved (was created). During recovery, pointers and nodes can have been flushed to disk or lost from memory. To determine if a pointer or node can be 'trusted' to be stable on disk there is a global STABLE generation of the tree. This generation and every generation before it has been checkpointed (flushed to disk) and can therefore be trusted, even after a crash.\r\n\r\nThe generation currently under evolution is considered to be UNSTABLE. Data belonging to or pointing to UNSTABLE generation can not be trusted after a crash and must be overwritten during recovery. Note that this is not implemented yet. After checkpoint the STABLE generation will be set to the UNSTABLE generation and UNSTABLE generation will be incremented.\r\n\r\n*GenSafePointer, GSP*\r\nBy guarding the pointer fields, generation and address, with a checksum we can determine if a pointer is BROKEN (wrong checksum). A pointer can be broken if the page is flushed while writing the pointer and then crash before that page is flushed again.\r\n\r\nA pointer with generation and checksum is called a GenSafePointer, GSP.\r\n\r\n*GenSafePointerPair, GSPP*\r\nWe always want to keep a stable version of every pointer. Therefore all pointers are in fact two GSPs, a GSPP. So when we read or write a child pointer for example, we look at the pair for pointers as a whole and determine which one to read from or write to, look at GenSafePointerPair class.\r\n\r\n**LabelScanStore**\r\nThere is an implementation of a label scan store built on top of this that will be introduced in a separate PR.\r\n\r\n**Note**\r\nThis is minimal feature set and among the things missing (but in pipeline) are:\r\n- Implement recovery\r\n- Implement freelist\r\n- Rebalance and merge when removing from tree","created_at":"2016-11-21T10:24:21Z","updated_at":"2016-11-23T14:10:05Z","closed_at":null,"merged_at":null,"merge_commit_sha":"06fb186582b8d4044c5ca4d7792793d96118bdb8","assignee":{"login":"chrisvest","id":7993,"avatar_url":"https://avatars.githubusercontent.com/u/7993?v=3","gravatar_id":"","url":"https://api.github.com/users/chrisvest","html_url":"https://github.com/chrisvest","followers_url":"https://api.github.com/users/chrisvest/followers","following_url":"https://api.github.com/users/chrisvest/following{/other_user}","gists_url":"https://api.github.com/users/chrisvest/gists{/gist_id}","starred_url":"https://api.github.com/users/chrisvest/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chrisvest/subscriptions","organizations_url":"https://api.github.com/users/chrisvest/orgs","repos_url":"https://api.github.com/users/chrisvest/repos","events_url":"https://api.github.com/users/chrisvest/events{/privacy}","received_events_url":"https://api.github.com/users/chrisvest/received_events","type":"User","site_admin":false},"assignees":[{"login":"chrisvest","id":7993,"avatar_url":"https://avatars.githubusercontent.com/u/7993?v=3","gravatar_id":"","url":"https://api.github.com/users/chrisvest","html_url":"https://github.com/chrisvest","followers_url":"https://api.github.com/users/chrisvest/followers","following_url":"https://api.github.com/users/chrisvest/following{/other_user}","gists_url":"https://api.github.com/users/chrisvest/gists{/gist_id}","starred_url":"https://api.github.com/users/chrisvest/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chrisvest/subscriptions","organizations_url":"https://api.github.com/users/chrisvest/orgs","repos_url":"https://api.github.com/users/chrisvest/repos","events_url":"https://api.github.com/users/chrisvest/events{/privacy}","received_events_url":"https://api.github.com/users/chrisvest/received_events","type":"User","site_admin":false},{"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/8408/commits","review_comments_url":"https://api.github.com/repos/neo4j/neo4j/pulls/8408/comments","review_comment_url":"https://api.github.com/repos/neo4j/neo4j/pulls/comments{/number}","comments_url":"https://api.github.com/repos/neo4j/neo4j/issues/8408/comments","statuses_url":"https://api.github.com/repos/neo4j/neo4j/statuses/ca95fb7c9f23522ddecd8d991b56e02d3fe83927","head":{"label":"burqen:3.2-native-index","ref":"3.2-native-index","sha":"ca95fb7c9f23522ddecd8d991b56e02d3fe83927","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":"2016-11-23T12:22:01Z","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":345654,"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":"20504b1ee8e06fff5a040a2965ec23d9bde593a4","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":"2016-11-23T13:14:24Z","pushed_at":"2016-11-23T13:27:53Z","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":387378,"stargazers_count":3225,"watchers_count":3225,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1026,"mirror_url":null,"open_issues_count":403,"forks":1026,"open_issues":403,"watchers":3225,"default_branch":"3.1"}},"_links":{"self":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/8408"},"html":{"href":"https://github.com/neo4j/neo4j/pull/8408"},"issue":{"href":"https://api.github.com/repos/neo4j/neo4j/issues/8408"},"comments":{"href":"https://api.github.com/repos/neo4j/neo4j/issues/8408/comments"},"review_comments":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/8408/comments"},"review_comment":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/neo4j/neo4j/pulls/8408/commits"},"statuses":{"href":"https://api.github.com/repos/neo4j/neo4j/statuses/ca95fb7c9f23522ddecd8d991b56e02d3fe83927"}}}}
{"actor":{"display_login":"MishaDemianenko"}}