2b:null 2c:["$","title",null,{"children":"Inside Hypercore | Jim Pick | Observable"}] 31:T4d2,md`## "SLEEP" files Hypercore presents an "append-only" log abstraction to the world. But internally, it builds a simple database so that data can be stored to places to such as disks, or easily replicated over point-to-point or peer-to-peer networks -- it is particularly good at doing "sparse" replication, where only a subset of the data is synchronized between peers (for example, when Beaker Browser loads assets for a web page from a hyper:// URL). Internally, the data and indexes for the database are mapped into a series of "SLEEP" files (see the [Dat Paper](https://github.com/datprotocol/whitepaper/blob/master/dat-paper.pdf) for details). Depending on which storage library is used, the files might be stored as actual files in a filesystem, or they might be stored in-memory, or in IndexedDB in a web browser. We will first focus on two of the SLEEP files used by the database: * **data** - stored the raw binary data for the records * **tree** - a binary tree data structure that stores alternating "leaves" and "roots". Each "leaf" corresponds to a data record, with just the length of the data in bytes, and a hash of the content. Each "root" is a "Merkle Root" combining the hashes of all the subtrees under it. `32:T4af,{ for await (const treeData of onTreeIterator()) { await Promises.delay(100) const nodes = getNodes(feed.length) const printTree = printFlatTree(nodes).split('\n') const lines = [] let index = 0 for (let i = 0; i < printTree.length - 1; i++) { let dataIndex = '' let data = '' if (i % 2 == 0) { dataIndex = `${i / 2}` data = String(await feedGet(feed, i / 2)) } lines.push( dataIndex.padEnd(3) + data.padEnd(12) + printTree[i] ) } const width = lines.reduce((acc, line) => Math.max(acc, line.length), 0) const lines2 = [] for (let i = 0; i < printTree.length - 1; i++) { let dataIndex = '' let size = '' let hash = '' if (i % 2 == 0) { dataIndex = `${i / 2}` // size = 'Size: ' + String(await feedGet(feed, i / 2)).length } if (treeData[i]) { size = 'Size: ' + treeData[i].size hash = 'Hash: ' + treeData[i].hash } lines2.push( lines[i].padEnd(width + 1) + size.padEnd(10) + hash ) } yield html`

${lines2.join('\n')}

` } }33:Tea7,shimAndIterators = { class Target extends EventTarget {} const target = new Target() const dataRecords = [] const dataSubState = { listener: null, pending: false } target.addEventListener('data', evt => { dataRecords.push(evt.detail) if (dataSubState.handler) { dataSubState.handler() dataSubState.handler = null } else { dataSubState.Pending = true } }) function onDataIterator () { return { [Symbol.asyncIterator]: () => ({ next: () => new Promise(resolve => { if (dataSubState.pending) { dataSubState.pending = false resolve({ value: dataRecords, done: false }) } else { dataSubState.handler = () => { resolve({ value: dataRecords, done: false }) } } }) }) } } const treeRecords = [] const treeSubState = { handlers: [], pending: false } target.addEventListener('tree', evt => { console.log('Jim evt tree', evt.detail) const { name, offset, hash, size } = evt.detail treeRecords[(offset - 32) / 40] = { hash, size } if (treeSubState.handlers.length > 0) { while (treeSubState.handlers.length > 0) { const handler = treeSubState.handlers.pop() handler() } } else { treeSubState.pending = true } }) function onTreeIterator () { return { [Symbol.asyncIterator]: () => ({ next: () => new Promise(resolve => { if (treeSubState.pending) { treeSubState.pending = false console.log('Jim tree pending', treeRecords) resolve({ value: treeRecords, done: false }) } else { console.log('Jim register tree listener') treeSubState.handlers.push(() => { console.log('Jim tree handler', treeRecords) resolve({ value: treeRecords, done: false }) }) } }) }) } } function storageShim (name) { const ramFile = ram(name) return randomAccess({ open: function (req) { ramFile.open(err => { req.callback(err) }) }, read: function (req) { const {offset, size} = req ramFile.read(offset, size, (err, buffer) => { // console.log('_read:', name, offset, size, '=>', buffer) req.callback(err, buffer) }) }, write: function (req) { const {offset, data} = req if ( name !== 'bitfield' && name !== 'signatures' && name !== 'key' && name !== 'secret_key' && !(name === 'tree' && offset === 0) ) { if (name === 'tree') { const hash = data.slice(0, 32).toString('hex') const size = uint64be.decode(data, 32) console.log('_write:', name, offset, '<=', 'Hash:', hash, 'Size:', size) target.dispatchEvent( new CustomEvent('tree', { detail: { offset, hash, size } }) ) } else if (name === 'data') { console.log('_write:', name, offset, '<=', `"${data.toString()}"`) target.dispatchEvent( new CustomEvent('data', { detail: { offset, data } }) ) } else { console.log('_write:', name, offset, '<=', data) } } ramFile.write(offset, data, err => { req.callback(err) }) }, close: function (req) { req.callback(null) } }) } return { storageShim, onDataIterator, onTreeIterator } }34:[] 2f:{"id":"1119be5116fcdc56","slug":"inside-hypercore","title":"Inside Hypercore","thumbnail":"6364f5f620c0c71aae44e51639189c492a312b50dec61ba740b44e801d82e4ef","access_level":"public","create_time":"$D2020-07-27T02:45:01.835Z","update_time":"$D2020-07-31T14:45:16.533Z","view_time":null,"first_public_time":"$D2020-07-27T06:42:08.981Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"5252cea433451319","login":"jimpick","name":"Jim Pick","avatar_url":"https://avatars-next.observableusercontent.com/e8813527082139d5411445010e72fd85f99b04a26355e795d0ea26765425d0cd","tier":"starter_2024"},"version":355,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"bda4505ba9a55ac8","login":"jimpick","name":"Jim Pick","avatar_url":"https://avatars-next.observableusercontent.com/e8813527082139d5411445010e72fd85f99b04a26355e795d0ea26765425d0cd","tier":null}],"members":[{"type":"individual","id":"bda4505ba9a55ac8","login":"jimpick","name":"Jim Pick","avatar_url":"https://avatars-next.observableusercontent.com/e8813527082139d5411445010e72fd85f99b04a26355e795d0ea26765425d0cd","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":1,"collection":{"id":"c273e1e644de46b3","slug":"hypercore-ipld","title":"hypercore-ipld","owner":{"id":"5252cea433451319","login":"jimpick","name":"Jim Pick"}},"type":"notebook","body":{"title":"Inside Hypercore","cells":[{"id":0,"value":"md`# Inside Hypercore\n\nThis information is based on Hypercore version 7 -- newer versions of Hypercore have more features and the internal data structures will be different.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"md`## \"data\"\n\nThe \"data\" SLEEP file simply is a concatenation of all the binary data written to the append-only log, ordered in the sequence it was written in. So it is just the bytes for record 0 + the bytes for record 1 + the bytes for record 2 and so on...`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"md`Here's the hypercore demo from the previous notebook:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":165,"value":"viewof b1 = appendButton()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"{\n let table = '| index | value |\\n'\n table += '| --- | --- |\\n'\n for (let i = 0; i < length; i++) {\n table += `| ${i} | ${await feedGet(feed, i)} |\\n`\n }\n return md`${table}`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"md`In this notebook, we are using a \"shimmed\" storage function (below) so that we can spy on the various SLEEP file contents.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"{\n for await (const dataRecords of onDataIterator()) {\n let table = '| Index | Offset | Data (bin => hex) | Data (bin => string) |\\n'\n table += '| --- | --- | --- | --- |\\n'\n let index = 0\n for (const { offset, data } of dataRecords) {\n const binData = [...data].map(b => b.toString(16).padStart(2, \"0\")).join(' ')\n table += `| ${index++} | ${offset} | ${binData} | ${data.toString()} |\\n`\n }\n yield md`${table}`\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"md`Only the binary \\`data\\` shown above is stored in the file. The offsets are not stored, but can be derived from the information stored in the \\`tree\\` file.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"md`## \"tree\"\n\nThe \\`tree\\` SLEEP file is a binary tree data structure. It stores extra metadata (size, content hashes) that the \\`data\\` SLEEP file does not store.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":195,"value":"viewof b2 = appendButton()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":133,"value":"nodes = flatTree.fullRoots(length * 2).map(root => flatTree.spans(root)).map(([first, last]) => {\n const nodes = []\n for (let i = first; i <= last; i++) nodes.push(i)\n return nodes\n}).flat()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"html`

${printFlatTree(nodes)}

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"md`Each \"leaf\" (nodes on the far left) correspond to a data record. Notice that the indexes of the leafs are all even numbers. Multiply the index of the record by \"2\" to get the matching leaf record in the \\`tree\\` data structure.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":"md`Let's see the data for the leaves alongside the tree.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":206,"value":"{\n const printTree = printFlatTree(nodes).split('\\n')\n const lines = []\n let index = 0\n for (let i = 0; i < printTree.length - 1; i++) {\n let dataIndex = ''\n let data = ''\n if (i % 2 == 0) {\n dataIndex = `${i / 2}`\n data = String(await feedGet(feed, i / 2))\n }\n lines.push(\n dataIndex.padEnd(3) +\n data.padEnd(12) +\n printTree[i]\n )\n }\n return html`

${lines.join('\\n')}

`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":220,"value":"viewof b3 = appendButton()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":234,"value":"md`Everything shown above isn't actually stored in the \\`tree\\` file. Because it is a binary tree, the index of a node in the tree is enough to determine it's parents, children and siblings.\n\nEach entry in the \\`tree\\` file is a fixed number of bytes. Only 2 pieces of information are stored in each entry: the \\`size\\` of the content and the \\`hash\\` of the content.\n\nFor leaf nodes that correspond to record entries, the \\`size\\` is just the size of the record in bytes. The \\`hash\\` is a [BLAKE2b](https://en.wikipedia.org/wiki/BLAKE_%28hash_function%29) hash of the bytes in the records + a small prefix. The hash is used to verify that synchronized data is correct.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":241,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":346,"value":"viewof b4 = appendButton()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":337,"value":"md`Each merkle parent node has the size of each of it's children added together. The hash of each merkle parent node is a hash that involves combining the hashes of both children and hashing that.\n\nDepending on the number of records, there may be multiple \"roots\" to the graph.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":340,"value":"roots = flatTree.fullRoots(length * 2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"md`## Imports and demo helpers`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"import {button} from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"import {hypercore, ram, onAppendAsyncIterator, feedGet, appendRandomFruit} from '@jimpick/hypercore-intro'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"feed = hypercore(storageShim)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"length = {\n yield feed.length\n for await (const v of onAppendAsyncIterator(feed)) {\n yield feed.length\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"randomAccess = require('https://bundle.run/random-access-storage@1.4.1')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"uint64be = require('https://bundle.run/uint64be@3.0.0')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"storageShim = shimAndIterators.storageShim","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"onDataIterator = shimAndIterators.onDataIterator","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"onTreeIterator = shimAndIterators.onTreeIterator","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"printFlatTree = require('https://bundle.run/print-flat-tree@2.2.0')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"flatTree = require('https://bundle.run/flat-tree@1.6.0')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":188,"value":"function appendButton () {\n const div = html`\n

\n \n \n

\n `\n const button = div.querySelector('button')\n const span = div.querySelector('span')\n \n button.onclick = () => {\n const fruit = appendRandomFruit(feed)\n span.innerText = `Appended: ${fruit}`\n }\n return div\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":281,"value":"{\n await Promises.delay(1000)\n appendRandomFruit(feed);\n return \"init with random fruit\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":312,"value":"function getNodes (length) {\n const nodes = flatTree.fullRoots(length * 2)\n .map(root => flatTree.spans(root))\n .map(([first, last]) => {\n const nodes = []\n for (let i = first; i <= last; i++) nodes.push(i)\n return nodes\n })\n .flat()\n return nodes\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 30:"$2f:body"