tools

Graph Key Builder Shows the Keys a Graph Takes in RocksDB, LMDB or etcd, and What Each Hop Costs

Sometimes a few links have to sit next to your records: which service calls which, who follows whom, what an AI agent remembers about what. A graph database is one more system to run for that. If you already run an ordered key-value store, the graph can live there, as long as the keys are laid out well.

The Graph Key Builder shows how. Paste a list of links and you get every key the graph takes, in the order the store keeps them. Then pick a node and follow its links hop by hop, with each prefix scan listed and the keys it read counted.

The Graph Key Builder walking two hops out from web in an example service graph: 7 nodes reached with 4 prefix scans, reading 7 keys.

Every node gets a record of its own, n/web, where its fields go. Every link is stored twice: as o/web/calls/auth under the node it leaves, and as i/auth/calls/web under the node it reaches. Two writes per link is the price of following links both ways, and they belong in one transaction.

An ordered store keeps keys sorted, so all of a node’s links sit side by side. Reading them is one prefix scan: seek to o/web/ and read until the keys stop matching. Dgraph and NebulaGraph keep their graphs in Badger and RocksDB on much the same idea.

What a Walk Costs

Each hop scans once for every node the hop before it reached. In the example, walking two hops out from web takes 4 scans and reads 7 keys. That’s cheap for a small graph and a short walk. It grows with every node the walk reaches, and a node with a million links reads a million keys when a walk passes through it.

Checked Against SQLite

Byte order is where a quick script goes wrong. Stores compare keys byte by byte in UTF-8, and JavaScript’s own sort puts 😀 before ～ where a store puts it after. The tool sorts by bytes. With a test graph full of awkward names, SQLite 3.45.1 kept all 51 keys in the tool’s order and returned the same keys as the tool for all 150 prefix scans a walk could make.

The tool’s logic is one JavaScript file with no dependencies, open source under the Apache License 2.0. The manual and the tests are in the graph folder on GitHub.