Duplicate entries returned by .list()

[jimpick]

Here is a hyperdrive / hyperdb (from my shopping list demo) that is showing duplicate nodes returned from .list() - it appears to be iterating incorrectly.

I don't yet have a smaller example, so here's a capture of the storage that exhibits the problem:

hyperdrive-95fe65d1af31a38b22a31ab31bc7862e80071f8482e17c8aacd18e02842b3f55-multiple-entries.zip

Test case:

var test = require('tape')
var hyperdb = require('hyperdb')

test('no duplicates', function (t) {
  var db = hyperdb('./db')
  db.list('/shopping-list', (err, list) => {
    t.error(err)
    var keys = list.map(function (node) { return node[0].key })
    t.equal(keys.length, new Set(keys).size)
    t.end()
  })
})

Result:

TAP version 13
# no duplicates
not ok 1 test exited without ending
  ---
    operator: fail
    at: process.<anonymous> (/Users/jim/backblend-jpimac/clients/research-team-tool/hyperdb-tests/hyperdb-inspector-scripts/node_modules/tape/index.js:90:19)
    stack: |-
      Error: test exited without ending
          at Test.assert [as _assert] (/Users/jim/backblend-jpimac/clients/research-team-tool/hyperdb-tests/hyperdb-inspector-scripts/node_modules/tape/lib/test.js:225:54)
          at Test.bound [as _assert] (/Users/jim/backblend-jpimac/clients/research-team-tool/hyperdb-tests/hyperdb-inspector-scripts/node_modules/tape/lib/test.js:77:32)
          at Test.fail (/Users/jim/backblend-jpimac/clients/research-team-tool/hyperdb-tests/hyperdb-inspector-scripts/node_modules/tape/lib/test.js:318:10)
          at Test.bound [as fail] (/Users/jim/backblend-jpimac/clients/research-team-tool/hyperdb-tests/hyperdb-inspector-scripts/node_modules/tape/lib/test.js:77:32)
          at Test._exit (/Users/jim/backblend-jpimac/clients/research-team-tool/hyperdb-tests/hyperdb-inspector-scripts/node_modules/tape/lib/test.js:191:14)
          at Test.bound [as _exit] (/Users/jim/backblend-jpimac/clients/research-team-tool/hyperdb-tests/hyperdb-inspector-scripts/node_modules/tape/lib/test.js:77:32)
          at process.<anonymous> (/Users/jim/backblend-jpimac/clients/research-team-tool/hyperdb-tests/hyperdb-inspector-scripts/node_modules/tape/index.js:90:19)
          at process.emit (events.js:159:13)
  ...

1..1
# tests 1
# pass  0
# fail  1

The keys returned look like this:

shopping-list/0jg9vpsbh.json
shopping-list/0jg9vmbpt.json
shopping-list/0jg9w75z8.json
shopping-list/0jg9vqekg.json
shopping-list/0jg9w1lpn.json
shopping-list/0jg9vpnui.json
shopping-list/0jg9vq1ne.json
shopping-list/0jg9vmbpt.json
shopping-list/0jg9w75z8.json
shopping-list/0jg9vqekg.json
shopping-list/0jg9vpsbh.json
shopping-list/0jg9vm64y.json
shopping-list/0jge8lsbt.json
shopping-list/0jg9w75z8.json
shopping-list/0jge8lkht.json
shopping-list/0jg9w1lpn.json
shopping-list/0jg9vpnui.json
shopping-list/0jg9vq1ne.json
shopping-list/0jg9vmbpt.json
shopping-list/0jg9w75z8.json
shopping-list/0jg9vqekg.json
shopping-list/0jg9x2tzm.json
shopping-list/0jg9vmvt2.json
shopping-list/0jge1r7el.json
shopping-list/0jg9w4278.json
shopping-list/0jg9vgul6.json
shopping-list/0jg9vn1oy.json
shopping-list/0jge1topc.json
shopping-list/0jg9w7g9y.json
shopping-list/0jg9vnmi3.json
shopping-list/0jge8m3w0.json
shopping-list/0jg9vrrxu.json
shopping-list/0jg9vlzoz.json
shopping-list/0jg9x27ew.json
shopping-list/0jge1rx18.json
shopping-list/0jg9w70rj.json

Notice that shopping-list/0jg9vmbpt.json is returned 3 times.

[jimpick]

It's highly likely that this particular database was corrupted due to a bug I introduced in an earlier PR.

[jimpick]

Confirmed that this is due to corruption in some of the feeds.

In particular:

Key dca2d360e3b7f7a09511d211ebcd28da3c8c0c4ee485700041c906c2cee63405
Ready 18
0 { key: 'shopping-list/0jg9vgul6.json',
  value: <Buffer 08 a4 83 02 20 38 28 01 30 00 38 00 40 a5 ab 8d c8 af 2c 48 a5 ab 8d c8 af 2c>,
  trie: <Buffer 00 14 00 00 0a 00 20 0b 0c 00 06 1f 06 1d 21 0b 06 12 06 0c 06 10 22 01 00 0a>,
  clock: [ 21, 1, 0, 33, 6, 1, 1 ],
  inflate: 0,
  feeds:
   [ { key: <Buffer 95 fe 65 d1 af 31 a3 8b 22 a3 1a b3 1b c7 86 2e 80 07 1f 84 82 e1 7c 8a ac d1 8e 02 84 2b 3f 55> },
     { key: <Buffer dc a2 d3 60 e3 b7 f7 a0 95 11 d2 11 eb cd 28 da 3c 8c 0c 4e e4 85 70 00 41 c9 06 c2 ce e6 34 05> },
     { key: <Buffer 40 ec e4 af 40 c7 53 2c bf 36 69 45 be 7f f6 2e 14 66 de ca 52 aa 5b 5f c5 1e 0d 79 a9 5b d0 50> },
     { key: <Buffer 57 74 83 88 ba 6f 47 1f 11 51 b7 51 27 14 bc 28 de c7 8c e2 19 bf d0 58 0f ce 26 f4 f4 fc 87 ce> },
     { key: <Buffer 0c ab f5 21 4f 09 52 1f 11 f2 5e 87 9c 42 c1 1a b4 ce 0f 7d 23 23 9c 00 7c 03 72 fc f5 fe 59 67> },
     { key: <Buffer 5c e7 d4 ab 50 70 84 d1 8a 93 57 f9 46 f5 db dd f9 45 ae 01 ce ef a3 95 f1 51 68 aa e9 02 cc 3a> },
     { key: <Buffer 45 3e ce 3f ef 95 83 90 b6 8d bc ab 88 a9 5d 8f 52 50 be 91 96 24 36 49 8a 39 87 82 21 71 b9 96> } ],
  contentFeed: <Buffer 82 36 b4 42 10 47 9c 1b 58 77 38 58 cf 7c 3b 26 82 9e 83 33 3f e6 0d 0a 86 8f 5d 27 7c d1 fd b6> }
1 { key: 'shopping-list/0jg9vgul6.json',
  value: <Buffer 08 a4 83 02 20 39 28 01 30 01 38 38 40 da b4 8d c8 af 2c 48 da b4 8d c8 af 2c>,
  trie: <Buffer 00 14 00 00 0a 00 20 0b 0c 00 06 1f 06 1d 21 0b 06 12 06 0c 06 10 22 01 00 0a>,
  clock: [ 21, 2, 0, 33, 6, 1, 1 ],
  inflate: 0 }
2 { key: '',
  value: null,
  trie: <Buffer 00 06 03 01 0c 00 00 00>,
  clock: [ 21, 3, 0, 33, 7, 1, 1, 0 ],
  inflate: 2,
  feeds:
   [ { key: <Buffer 95 fe 65 d1 af 31 a3 8b 22 a3 1a b3 1b c7 86 2e 80 07 1f 84 82 e1 7c 8a ac d1 8e 02 84 2b 3f 55> },
     { key: <Buffer dc a2 d3 60 e3 b7 f7 a0 95 11 d2 11 eb cd 28 da 3c 8c 0c 4e e4 85 70 00 41 c9 06 c2 ce e6 34 05> },
     { key: <Buffer 40 ec e4 af 40 c7 53 2c bf 36 69 45 be 7f f6 2e 14 66 de ca 52 aa 5b 5f c5 1e 0d 79 a9 5b d0 50> },
     { key: <Buffer 57 74 83 88 ba 6f 47 1f 11 51 b7 51 27 14 bc 28 de c7 8c e2 19 bf d0 58 0f ce 26 f4 f4 fc 87 ce> },
     { key: <Buffer 0c ab f5 21 4f 09 52 1f 11 f2 5e 87 9c 42 c1 1a b4 ce 0f 7d 23 23 9c 00 7c 03 72 fc f5 fe 59 67> },
     { key: <Buffer 5c e7 d4 ab 50 70 84 d1 8a 93 57 f9 46 f5 db dd f9 45 ae 01 ce ef a3 95 f1 51 68 aa e9 02 cc 3a> },
     { key: <Buffer 45 3e ce 3f ef 95 83 90 b6 8d bc ab 88 a9 5d 8f 52 50 be 91 96 24 36 49 8a 39 87 82 21 71 b9 96> },
     { key: <Buffer c7 80 79 9b 5e 27 ef bb 71 52 65 de 61 9b 88 01 04 06 73 6b 37 11 59 f5 94 8e 82 e5 52 12 dc d3> } ],
  contentFeed: <Buffer 82 36 b4 42 10 47 9c 1b 58 77 38 58 cf 7c 3b 26 82 9e 83 33 3f e6 0d 0a 86 8f 5d 27 7c d1 fd b6> }
3 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3a 28 01 30 02 38 71 40 9c f8 d7 cd af 2c 48 9c f8 d7 cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 16 00 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 4, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 3,
  feeds:
   [ { key: <Buffer 95 fe 65 d1 af 31 a3 8b 22 a3 1a b3 1b c7 86 2e 80 07 1f 84 82 e1 7c 8a ac d1 8e 02 84 2b 3f 55> },
     { key: <Buffer dc a2 d3 60 e3 b7 f7 a0 95 11 d2 11 eb cd 28 da 3c 8c 0c 4e e4 85 70 00 41 c9 06 c2 ce e6 34 05> },
     { key: <Buffer 40 ec e4 af 40 c7 53 2c bf 36 69 45 be 7f f6 2e 14 66 de ca 52 aa 5b 5f c5 1e 0d 79 a9 5b d0 50> },
     { key: <Buffer 57 74 83 88 ba 6f 47 1f 11 51 b7 51 27 14 bc 28 de c7 8c e2 19 bf d0 58 0f ce 26 f4 f4 fc 87 ce> },
     { key: <Buffer 0c ab f5 21 4f 09 52 1f 11 f2 5e 87 9c 42 c1 1a b4 ce 0f 7d 23 23 9c 00 7c 03 72 fc f5 fe 59 67> },
     { key: <Buffer 5c e7 d4 ab 50 70 84 d1 8a 93 57 f9 46 f5 db dd f9 45 ae 01 ce ef a3 95 f1 51 68 aa e9 02 cc 3a> },
     { key: <Buffer 45 3e ce 3f ef 95 83 90 b6 8d bc ab 88 a9 5d 8f 52 50 be 91 96 24 36 49 8a 39 87 82 21 71 b9 96> },
     { key: <Buffer c7 80 79 9b 5e 27 ef bb 71 52 65 de 61 9b 88 01 04 06 73 6b 37 11 59 f5 94 8e 82 e5 52 12 dc d3> },
     { key: <Buffer 23 f8 5e b2 46 50 02 f6 b7 b3 29 b5 a4 4d 1b 9f 17 bc 3b 41 c3 04 c1 a6 09 e6 3d 6d 14 5d 75 97> },
     { key: <Buffer e0 5c 55 40 f5 ad 80 81 23 87 e7 80 e1 4a 83 33 fe ac 07 94 dd f7 e2 d6 a8 58 aa 3f 68 5c c3 c2> },
     { key: <Buffer 08 cb 0b 23 05 ae 16 d7 ae 67 39 cf ad 0b 07 d1 55 5b c2 fe 60 b8 01 5a 9b bc c3 20 5a 8f 19 32> },
     { key: <Buffer 03 56 af d1 c0 be 98 6e f6 18 35 ce 97 52 61 25 52 ab 6e 72 ea b1 ce ae 24 91 df 71 ce c6 bb c6> } ],
  contentFeed: <Buffer 82 36 b4 42 10 47 9c 1b 58 77 38 58 cf 7c 3b 26 82 9e 83 33 3f e6 0d 0a 86 8f 5d 27 7c d1 fd b6> }
4 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3b 28 01 30 03 38 ab 01 40 8c 9d d8 cd af 2c 48 8c 9d d8 cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 16 00 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 5, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 3 }
5 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3a 28 01 30 04 38 e6 01 40 ce a3 d8 cd af 2c 48 ce a3 d8 cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 16 00 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 6, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 3 }
6 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3b 28 01 30 05 38 a0 02 40 fc e1 d9 cd af 2c 48 fc e1 d9 cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 16 00 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 7, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 3 }
7 { key: 'shopping-list/0jg9w7g9y.json',
  value: <Buffer 08 a4 83 02 20 42 28 01 30 06 38 db 02 40 bd e7 e2 cd af 2c 48 bd e7 e2 cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0b 0e 0c 02 06 10 02 21 07 16 00 0e 0d 03 01 06 1e 22 02 06 04 23 04 14 00>,
  clock: [ 21, 8, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 3 }
8 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3a 28 01 30 07 38 9d 03 40 bb d7 ed cd af 2c 48 bb d7 ed cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 02 07 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 9, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 3 }
9 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3b 28 01 30 08 38 d7 03 40 e5 e2 ed cd af 2c 48 e5 e2 ed cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 02 07 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 10, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 3 }
10 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3a 28 01 30 09 38 92 04 40 af ed ed cd af 2c 48 af ed ed cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 02 07 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 11, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 3 }
11 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3b 28 01 30 0a 38 cc 04 40 97 ae ef cd af 2c 48 97 ae ef cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 02 07 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 12, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 0 }
12 { key: 'shopping-list/0jg9w75z8.json',
  value: <Buffer 08 a4 83 02 20 3a 28 01 30 0b 38 87 05 40 c5 c8 ef cd af 2c 48 c5 c8 ef cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 02 07 10 02 21 07 06 07 0e 08 06 0b 22 08 06 09 23 04 09 01 06 02>,
  clock: [ 21, 13, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 0 }
13 { key: 'shopping-list/0jg9x27ew.json',
  value: <Buffer 08 a4 83 02 20 36 28 01 30 0c 38 c1 05 40 f5 fd ef cd af 2c 48 f5 fd ef cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 07 0e 0c 02 0c 02 07 21 0b 10 02 06 1d 06 0e 23 04 0e 0e>,
  clock: [ 21, 14, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 0 }
14 { key: 'shopping-list/0jg9x27ew.json',
  value: <Buffer 08 a4 83 02 20 37 28 01 30 0d 38 f7 05 40 b3 85 f0 cd af 2c 48 b3 85 f0 cd af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 07 0e 0c 02 0c 02 07 21 0b 10 02 06 1d 06 0e 23 04 0e 0e>,
  clock: [ 21, 15, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 0 }
15 { key: 'shopping-list/0jge8lkht.json',
  value: <Buffer 08 a4 83 02 20 48 28 01 30 0e 38 ae 06 40 81 b6 84 ce af 2c 48 81 b6 84 ce af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 02 07 02 0e 21 0d 06 07 06 0b 02 0c 22 03 06 1f 0e 08>,
  clock: [ 21, 16, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 0 }
16 { key: 'shopping-list/0jge8lsbt.json',
  value: <Buffer 08 a4 83 02 20 47 28 01 30 0f 38 f6 06 40 a9 85 85 ce af 2c 48 a9 85 85 ce af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 0d 0e 0c 02 07 02 0e 21 0d 06 07 06 0b 02 0c 22 09 06 1f 02 0f 23 02 0e 08>,
  clock: [ 21, 17, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 0 }
17 { key: 'shopping-list/0jge8m3w0.json',
  value: <Buffer 08 a4 83 02 20 55 28 01 30 10 38 bd 07 40 b0 fa 85 ce af 2c 48 b0 fa 85 ce af 2c>,
  trie: <Buffer 00 14 00 00 0e 10 20 07 0e 0c 02 10 02 07 21 0d 10 02 02 0e 06 0e 22 04 00 0f 23 08 06 1d 24 08 06 0a>,
  clock: [ 21, 18, 0, 33, 7, 1, 4, 17, 3, 0, 1, 1 ],
  inflate: 0 }

At entry 11, the inflate pointer resets to '0'. So when hyperdb runs _mapList() to remap the feeds, it's using the oldest list of feeds, which doesn't have enough feeds to map properly. Perhaps _mapList() should throw an exception if it doesn't having enough mappings?

I'll close this. We can use the zip in the future to test a tool that detects corruption.