{"action":"created","comment":{"url":"https://api.github.com/repos/google/trillian/pulls/comments/91546393","pull_request_review_id":12051139,"id":91546393,"diff_hunk":"@@ -0,0 +1,186 @@\n+# Storage Design Notes\n+## Status: (Very very)^N Draft\n+### Author: Martin Smith\n+\n+## Tree Node Storage\n+\n+The node level of storage provides a fairly abstract tree model that is used to implement\n+verifiable logs and maps. Most users will not need this level but it is important to know the\n+concepts involved. The API for this is defined in `storage/tree_storage.go`. Related protos are in\n+the `storage/storagepb` package.\n+\n+The model provides a versioned view of the tree. Revision numbers increase monotonically as the\n+tree is mutated.\n+\n+### NodeIDs\n+\n+Nodes in storage are uniquely identified by a `NodeID`. This combines a tree path with\n+a revision number. The path is effectively used as a bitwise subtree prefix in the tree. \n+\n+The same `NodeID` objects are used by both logs and maps but they are interpreted differently.\n+There are API functions that create them for each case. Mixing node ID types in API calls will\n+give incorrect results.\n+\n+### Subtree Compaction\n+\n+As an optimization the tree is not stored as a set of raw nodes but at as a collection of subtrees.\n+\n+Currently, subtrees must be be a multiple of 8 levels deep (referred to as `strataDepth` in the\n+code). Only the bottom level nodes the \"leaves\" of the subtree are physically stored.\n+Intermediate subtree nodes are rehashed from the \"leaves\" when the subtree is loaded into memory.\n+\n+Subtrees are keyed by the `NodeID` of the root (effectively a path prefix) and contain the\n+intermediate nodes for that subtree, identified by their suffix. These are actually stored in a\n+proto map where the key is the suffix path. \n+\n+Subtrees are versioned to support the access model for nodes described above. Node addresses within\n+the model are distinct because the path to a subtree must be unique.\n+\n+When node updates are applied they will affect one or more subtrees and caching is used to increase\n+efficiency. After all updates have been done in-memory the cache is flushed to storage so each\n+affected subtree is only written once.\n+\n+Subtrees are helpful for reads because it is likely that many of the nodes traversed in\n+Merkle paths for proofs are part of the same subtree. The number of subtrees involved in a path\n+through a large tree from the leaves to the root is also bounded. For writes the subtree update\n+batches what would be many smaller writes into one larger but manageable one.\n+\n+We gain space efficiency by not storing intermediate nodes. This is a big saving as it avoids\n+storing entire tree levels, which get very large as the tree grows. This is magnified further as we\n+store many versions of the tree.\n+\n+#### Subtree Diagrams\n+\n+This diagram shows a tree as it might actually be stored by our code using subtrees of depth 8.\n+\n+Each subtree does not include its \"root\" node, though this counts as part of the depth. There are\n+additional subtrees below and to the right of the child subtree shown, they can't easily be shown\n+in the diagram. Obviously, there could be less than 256 \"leaf\" nodes in the subtrees if they are not\n+yet fully populated.\n+\n+![strata depth 8 tree](StratumDepth8.png, \"Stratum Depth 8\")\n+\n+As it's hard to visualize the structure at scale with stratum depth 8 some examples of smaller\n+depths might make things clearer, though these are not supported by the code the diagrams are\n+much simpler.\n+\n+This diagram shows a tree with strata depth 2. It is a somewhat special case as all the levels are\n+stored. Note that the root node is never stored and is always recalculated.\n+\n+![strata depth 2 tree diagram](StratumDepth2.png, \"Stratum Depth 2\")\n+\n+This diagram shows a tree with strata depth 3. Note that only the bottom level of each subtree is\n+stored and how the binary path is used as a subtree prefix to identify subtrees.\n+\n+![strata depth 3 tree diagram](StratumDepth3.png, \"Stratum Depth 3\")\n+\n+### Consistency and Other Requirements\n+\n+Storage implementations must provide strongly consistent updates to the tree data. Some users may\n+see an earlier view than others if updates have not been fully propagated yet but they must not see\n+partial updates or inconsistent views.\n+\n+It is not a requirement that the underlying storage is relational. Our initial implementation uses\n+an RDBMS and has this [database schema diagram](database-diagram.pdf, \"Trillian DB Schema\")\n+\n+## Map Storage\n+\n+Need stuff here.\n+\n+## Log Storage\n+\n+### The Log Tree\n+\n+The node tree built for a log is a representation of a Merkle Tree, which starts out empty and grows\n+as leaves are added. A Merkle Tree of a specific size is a fixed and well-defined shape.\n+                     \n+Leaves are never removed and a completely filled in left subtree of the tree\n+structure is never further mutated. \n+\n+The log stores two hashes per leaf, a raw SHA256 hash of the leaf data used for deduplication and\n+the Merkle Leaf Hash of the data, which becomes part of the tree.\n+\n+### Log NodeIDs / Tree Coordinates\n+\n+Log nodes are notionally addressed using a three dimensional coordinate tuple (level in tree, index\n+in level, revision number).\n+\n+Level zero is always the leaf level and additional intermediate levels are added above this as the\n+tree grows. Levels are only created when they are used.","path":"docs/storage/storage.md","position":109,"original_position":109,"commit_id":"8d672f6f94383306cc1460a68c59d5b63899f960","original_commit_id":"8d672f6f94383306cc1460a68c59d5b63899f960","user":{"login":"phad","id":874173,"avatar_url":"https://avatars.githubusercontent.com/u/874173?v=3","gravatar_id":"","url":"https://api.github.com/users/phad","html_url":"https://github.com/phad","followers_url":"https://api.github.com/users/phad/followers","following_url":"https://api.github.com/users/phad/following{/other_user}","gists_url":"https://api.github.com/users/phad/gists{/gist_id}","starred_url":"https://api.github.com/users/phad/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/phad/subscriptions","organizations_url":"https://api.github.com/users/phad/orgs","repos_url":"https://api.github.com/users/phad/repos","events_url":"https://api.github.com/users/phad/events{/privacy}","received_events_url":"https://api.github.com/users/phad/received_events","type":"User","site_admin":false},"body":"So would I be correct to conclude that as a tree grows, and new (higher level) intermediates are added, that existing nodes migrate from one stratum to new ones, to accommodate the extra level created?","created_at":"2016-12-08T16:14:17Z","updated_at":"2016-12-08T16:22:13Z","html_url":"https://github.com/google/trillian/pull/261#discussion_r91546393","pull_request_url":"https://api.github.com/repos/google/trillian/pulls/261","_links":{"self":{"href":"https://api.github.com/repos/google/trillian/pulls/comments/91546393"},"html":{"href":"https://github.com/google/trillian/pull/261#discussion_r91546393"},"pull_request":{"href":"https://api.github.com/repos/google/trillian/pulls/261"}}},"pull_request":{"url":"https://api.github.com/repos/google/trillian/pulls/261","id":97093863,"html_url":"https://github.com/google/trillian/pull/261","diff_url":"https://github.com/google/trillian/pull/261.diff","patch_url":"https://github.com/google/trillian/pull/261.patch","issue_url":"https://api.github.com/repos/google/trillian/issues/261","number":261,"state":"open","locked":false,"title":"Initial storage docs and diags","user":{"login":"Martin2112","id":13366863,"avatar_url":"https://avatars.githubusercontent.com/u/13366863?v=3","gravatar_id":"","url":"https://api.github.com/users/Martin2112","html_url":"https://github.com/Martin2112","followers_url":"https://api.github.com/users/Martin2112/followers","following_url":"https://api.github.com/users/Martin2112/following{/other_user}","gists_url":"https://api.github.com/users/Martin2112/gists{/gist_id}","starred_url":"https://api.github.com/users/Martin2112/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Martin2112/subscriptions","organizations_url":"https://api.github.com/users/Martin2112/orgs","repos_url":"https://api.github.com/users/Martin2112/repos","events_url":"https://api.github.com/users/Martin2112/events{/privacy}","received_events_url":"https://api.github.com/users/Martin2112/received_events","type":"User","site_admin":false},"body":"Will add to this as we go but I thought we should at least document stuff like how the subtree storage works because it's not obvious.","created_at":"2016-12-08T10:17:50Z","updated_at":"2016-12-08T16:22:13Z","closed_at":null,"merged_at":null,"merge_commit_sha":"7a30336e751643d47f56298b9462fb55278b7aed","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/google/trillian/pulls/261/commits","review_comments_url":"https://api.github.com/repos/google/trillian/pulls/261/comments","review_comment_url":"https://api.github.com/repos/google/trillian/pulls/comments{/number}","comments_url":"https://api.github.com/repos/google/trillian/issues/261/comments","statuses_url":"https://api.github.com/repos/google/trillian/statuses/8d672f6f94383306cc1460a68c59d5b63899f960","head":{"label":"Martin2112:storage_doc","ref":"storage_doc","sha":"8d672f6f94383306cc1460a68c59d5b63899f960","user":{"login":"Martin2112","id":13366863,"avatar_url":"https://avatars.githubusercontent.com/u/13366863?v=3","gravatar_id":"","url":"https://api.github.com/users/Martin2112","html_url":"https://github.com/Martin2112","followers_url":"https://api.github.com/users/Martin2112/followers","following_url":"https://api.github.com/users/Martin2112/following{/other_user}","gists_url":"https://api.github.com/users/Martin2112/gists{/gist_id}","starred_url":"https://api.github.com/users/Martin2112/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Martin2112/subscriptions","organizations_url":"https://api.github.com/users/Martin2112/orgs","repos_url":"https://api.github.com/users/Martin2112/repos","events_url":"https://api.github.com/users/Martin2112/events{/privacy}","received_events_url":"https://api.github.com/users/Martin2112/received_events","type":"User","site_admin":false},"repo":{"id":60082567,"name":"trillian","full_name":"Martin2112/trillian","owner":{"login":"Martin2112","id":13366863,"avatar_url":"https://avatars.githubusercontent.com/u/13366863?v=3","gravatar_id":"","url":"https://api.github.com/users/Martin2112","html_url":"https://github.com/Martin2112","followers_url":"https://api.github.com/users/Martin2112/followers","following_url":"https://api.github.com/users/Martin2112/following{/other_user}","gists_url":"https://api.github.com/users/Martin2112/gists{/gist_id}","starred_url":"https://api.github.com/users/Martin2112/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Martin2112/subscriptions","organizations_url":"https://api.github.com/users/Martin2112/orgs","repos_url":"https://api.github.com/users/Martin2112/repos","events_url":"https://api.github.com/users/Martin2112/events{/privacy}","received_events_url":"https://api.github.com/users/Martin2112/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Martin2112/trillian","description":null,"fork":true,"url":"https://api.github.com/repos/Martin2112/trillian","forks_url":"https://api.github.com/repos/Martin2112/trillian/forks","keys_url":"https://api.github.com/repos/Martin2112/trillian/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Martin2112/trillian/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Martin2112/trillian/teams","hooks_url":"https://api.github.com/repos/Martin2112/trillian/hooks","issue_events_url":"https://api.github.com/repos/Martin2112/trillian/issues/events{/number}","events_url":"https://api.github.com/repos/Martin2112/trillian/events","assignees_url":"https://api.github.com/repos/Martin2112/trillian/assignees{/user}","branches_url":"https://api.github.com/repos/Martin2112/trillian/branches{/branch}","tags_url":"https://api.github.com/repos/Martin2112/trillian/tags","blobs_url":"https://api.github.com/repos/Martin2112/trillian/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Martin2112/trillian/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Martin2112/trillian/git/refs{/sha}","trees_url":"https://api.github.com/repos/Martin2112/trillian/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Martin2112/trillian/statuses/{sha}","languages_url":"https://api.github.com/repos/Martin2112/trillian/languages","stargazers_url":"https://api.github.com/repos/Martin2112/trillian/stargazers","contributors_url":"https://api.github.com/repos/Martin2112/trillian/contributors","subscribers_url":"https://api.github.com/repos/Martin2112/trillian/subscribers","subscription_url":"https://api.github.com/repos/Martin2112/trillian/subscription","commits_url":"https://api.github.com/repos/Martin2112/trillian/commits{/sha}","git_commits_url":"https://api.github.com/repos/Martin2112/trillian/git/commits{/sha}","comments_url":"https://api.github.com/repos/Martin2112/trillian/comments{/number}","issue_comment_url":"https://api.github.com/repos/Martin2112/trillian/issues/comments{/number}","contents_url":"https://api.github.com/repos/Martin2112/trillian/contents/{+path}","compare_url":"https://api.github.com/repos/Martin2112/trillian/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Martin2112/trillian/merges","archive_url":"https://api.github.com/repos/Martin2112/trillian/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Martin2112/trillian/downloads","issues_url":"https://api.github.com/repos/Martin2112/trillian/issues{/number}","pulls_url":"https://api.github.com/repos/Martin2112/trillian/pulls{/number}","milestones_url":"https://api.github.com/repos/Martin2112/trillian/milestones{/number}","notifications_url":"https://api.github.com/repos/Martin2112/trillian/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Martin2112/trillian/labels{/name}","releases_url":"https://api.github.com/repos/Martin2112/trillian/releases{/id}","deployments_url":"https://api.github.com/repos/Martin2112/trillian/deployments","created_at":"2016-05-31T11:07:09Z","updated_at":"2016-05-31T11:07:10Z","pushed_at":"2016-12-08T16:00:50Z","git_url":"git://github.com/Martin2112/trillian.git","ssh_url":"git@github.com:Martin2112/trillian.git","clone_url":"https://github.com/Martin2112/trillian.git","svn_url":"https://github.com/Martin2112/trillian","homepage":null,"size":1621,"stargazers_count":0,"watchers_count":0,"language":"Go","has_issues":false,"has_downloads":false,"has_wiki":false,"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":"google:master","ref":"master","sha":"b8e00a510dd554732ddcfd516b3a1c52024700b7","user":{"login":"google","id":1342004,"avatar_url":"https://avatars.githubusercontent.com/u/1342004?v=3","gravatar_id":"","url":"https://api.github.com/users/google","html_url":"https://github.com/google","followers_url":"https://api.github.com/users/google/followers","following_url":"https://api.github.com/users/google/following{/other_user}","gists_url":"https://api.github.com/users/google/gists{/gist_id}","starred_url":"https://api.github.com/users/google/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/google/subscriptions","organizations_url":"https://api.github.com/users/google/orgs","repos_url":"https://api.github.com/users/google/repos","events_url":"https://api.github.com/users/google/events{/privacy}","received_events_url":"https://api.github.com/users/google/received_events","type":"Organization","site_admin":false},"repo":{"id":58654489,"name":"trillian","full_name":"google/trillian","owner":{"login":"google","id":1342004,"avatar_url":"https://avatars.githubusercontent.com/u/1342004?v=3","gravatar_id":"","url":"https://api.github.com/users/google","html_url":"https://github.com/google","followers_url":"https://api.github.com/users/google/followers","following_url":"https://api.github.com/users/google/following{/other_user}","gists_url":"https://api.github.com/users/google/gists{/gist_id}","starred_url":"https://api.github.com/users/google/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/google/subscriptions","organizations_url":"https://api.github.com/users/google/orgs","repos_url":"https://api.github.com/users/google/repos","events_url":"https://api.github.com/users/google/events{/privacy}","received_events_url":"https://api.github.com/users/google/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/google/trillian","description":null,"fork":false,"url":"https://api.github.com/repos/google/trillian","forks_url":"https://api.github.com/repos/google/trillian/forks","keys_url":"https://api.github.com/repos/google/trillian/keys{/key_id}","collaborators_url":"https://api.github.com/repos/google/trillian/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/google/trillian/teams","hooks_url":"https://api.github.com/repos/google/trillian/hooks","issue_events_url":"https://api.github.com/repos/google/trillian/issues/events{/number}","events_url":"https://api.github.com/repos/google/trillian/events","assignees_url":"https://api.github.com/repos/google/trillian/assignees{/user}","branches_url":"https://api.github.com/repos/google/trillian/branches{/branch}","tags_url":"https://api.github.com/repos/google/trillian/tags","blobs_url":"https://api.github.com/repos/google/trillian/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/google/trillian/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/google/trillian/git/refs{/sha}","trees_url":"https://api.github.com/repos/google/trillian/git/trees{/sha}","statuses_url":"https://api.github.com/repos/google/trillian/statuses/{sha}","languages_url":"https://api.github.com/repos/google/trillian/languages","stargazers_url":"https://api.github.com/repos/google/trillian/stargazers","contributors_url":"https://api.github.com/repos/google/trillian/contributors","subscribers_url":"https://api.github.com/repos/google/trillian/subscribers","subscription_url":"https://api.github.com/repos/google/trillian/subscription","commits_url":"https://api.github.com/repos/google/trillian/commits{/sha}","git_commits_url":"https://api.github.com/repos/google/trillian/git/commits{/sha}","comments_url":"https://api.github.com/repos/google/trillian/comments{/number}","issue_comment_url":"https://api.github.com/repos/google/trillian/issues/comments{/number}","contents_url":"https://api.github.com/repos/google/trillian/contents/{+path}","compare_url":"https://api.github.com/repos/google/trillian/compare/{base}...{head}","merges_url":"https://api.github.com/repos/google/trillian/merges","archive_url":"https://api.github.com/repos/google/trillian/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/google/trillian/downloads","issues_url":"https://api.github.com/repos/google/trillian/issues{/number}","pulls_url":"https://api.github.com/repos/google/trillian/pulls{/number}","milestones_url":"https://api.github.com/repos/google/trillian/milestones{/number}","notifications_url":"https://api.github.com/repos/google/trillian/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/google/trillian/labels{/name}","releases_url":"https://api.github.com/repos/google/trillian/releases{/id}","deployments_url":"https://api.github.com/repos/google/trillian/deployments","created_at":"2016-05-12T15:37:35Z","updated_at":"2016-12-08T14:52:57Z","pushed_at":"2016-12-08T16:00:51Z","git_url":"git://github.com/google/trillian.git","ssh_url":"git@github.com:google/trillian.git","clone_url":"https://github.com/google/trillian.git","svn_url":"https://github.com/google/trillian","homepage":null,"size":1916,"stargazers_count":126,"watchers_count":126,"language":"Go","has_issues":true,"has_downloads":false,"has_wiki":false,"has_pages":false,"forks_count":17,"mirror_url":null,"open_issues_count":14,"forks":17,"open_issues":14,"watchers":126,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/google/trillian/pulls/261"},"html":{"href":"https://github.com/google/trillian/pull/261"},"issue":{"href":"https://api.github.com/repos/google/trillian/issues/261"},"comments":{"href":"https://api.github.com/repos/google/trillian/issues/261/comments"},"review_comments":{"href":"https://api.github.com/repos/google/trillian/pulls/261/comments"},"review_comment":{"href":"https://api.github.com/repos/google/trillian/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/google/trillian/pulls/261/commits"},"statuses":{"href":"https://api.github.com/repos/google/trillian/statuses/8d672f6f94383306cc1460a68c59d5b63899f960"}}}}
{"actor":{"display_login":"phad"}}