Graph Key Builder

Paste a list of links and see the keys the graph takes in an ordered key-value store, such as RocksDB, LMDB, Badger or etcd. Then follow the links from any node, hop by hop, and see each prefix scan a graph layer would run, with the keys it reads.

On a wide screen you can open it full screen.

How to Use It

  1. Paste your links, one a line: web calls auth, or team one,owns,web when a name has a space. Two names make a link of type link.
  2. Read the keys. Every node gets a record under n/, and every link is stored twice, under o/ with the node it leaves and under i/ with the node it reaches. The list is in the order the store keeps them.
  3. Follow the links. Pick a node, a direction, a link type and how many hops. Each hop shows the prefixes scanned, how many keys each scan read and where they lead.

Why the Layout Works

An ordered store keeps its keys sorted, so all the links filed under one node sit side by side. Following them is one prefix scan: seek to o/web/, read until the keys stop starting with it. A walk costs one scan for every node reached on the hop before, plus the keys those scans read, so a node with a million links costs a million keys to walk through. Storing each link twice lets you follow it backwards too, at the price of two writes per link. Many graph engines run on this kind of layout underneath, Dgraph on Badger and NebulaGraph on RocksDB among them.

How It Was Tested

The keys of a test graph went into SQLite 3.45.1 as BLOB keys, which SQLite compares byte by byte, the order RocksDB, LMDB and etcd keep by default. The names had a slash, a percent sign, a space, capitals, a hyphen and letters outside ASCII. SQLite gave back all 51 keys in the tool’s order, and the same keys as the tool for all 150 prefix scans a walk of that graph could make.

The Code

The tool’s logic is one JavaScript file with no dependencies, open source under the Apache License 2.0. It runs as this page, as a command line in Node.js, and inside your own code:

node graph/cli.js walk links.txt --from web --hops 2

The full manual and the tests are in the graph folder on GitHub. The other tools work the same way.