BaseKV Internals: A RedisGraph Subset on a KV Engine

You are reading part 7, the final part, of a seven-part series taking apart the internals of BaseKV, a single-binary, disk-based key-value engine written in Go. The previous six parts built up a picture of a database that is, at its core, one ordered B+tree in one file with one write loop. This part is the one that surprised us most while building it: on top of that same B+tree, with no new storage engine and no new concurrency model, we layered a property graph and a usable subset of Cypher, and exposed it through the GRAPH.* commands that legacy RedisGraph clients already speak.

This is the last article in the series, so here is the full map one more time, with this part marked:

1. The bet on a disk-based Redis
2. Fitting Redis data types into a B+tree
3. Sorted sets on disk, an honest trade-off
4. SCAN cursors over a live B+tree
5. Three protocols, one file
6. Durability, the write loop, and TTL
7. A RedisGraph subset on a KV engine (this one)

Why a graph subset exists at all

The honest reason this feature exists is migration pressure, not graph-database ambition. RedisGraph reached end of life and was wound down by Redis, and the open-source line continues as a separate project, FalkorDB. That leaves a population of applications that still issue GRAPH.QUERY against a GRAPH.* endpoint and just need that endpoint to keep answering. We wrote about the migration landscape in RedisGraph deprecated, now what and the trade-offs against a real graph database in Neo4j vs a disk-based RedisGraph-style subset. The short version: if your workload is a handful of labels, exact-match lookups, single-hop traversals, and the occasional aggregate, you do not need a dedicated graph engine, and you certainly do not need to rewrite the call sites. You need something that speaks the protocol and stores the data durably. That is the niche BaseKV fills here. It is a migration cushion, not a Neo4j competitor, and we want to be clear about that before showing any code.

The stored model

A graph is just another key. When you run a query against a graph named social, the engine stores everything for that graph inside the graph sub-bucket, under keys composed from the graph's name. There are three record kinds, all msgpack-encoded.

Metadata lives at one key per graph. It holds the auto-incrementing ID counters and the list of declared secondary indexes:

type graphMeta struct {
	NextNodeID int64        `msgpack:"next_node_id"`
	NextEdgeID int64        `msgpack:"next_edge_id"`
	Indexes    []graphIndex `msgpack:"indexes,omitempty"`
}

Nodes and edges are the two record types that make it a property graph. A node carries its ID, zero or more labels, and a free-form property map. An edge is directional: it has a type, a source node ID, a destination node ID, and its own properties.

type graphNode struct {
	ID         int64                  `msgpack:"id"`
	Labels     []string               `msgpack:"labels,omitempty"`
	Properties map[string]interface{} `msgpack:"properties,omitempty"`
}

type graphEdge struct {
	ID         int64                  `msgpack:"id"`
	Type       string                 `msgpack:"type,omitempty"`
	Src        int64                  `msgpack:"src"`
	Dst        int64                  `msgpack:"dst"`
	Properties map[string]interface{} `msgpack:"properties,omitempty"`
}

The key layout is where the B+tree earns its keep. Conceptually each graph owns a slice of the keyspace and every record sits at a key prefixed by the graph name: the meta record under an m: prefix, every node under n:<id>, every edge under e:<id>. In the code the prefixing is done by encodeCompositeKey, which writes a 4-byte big-endian length of the graph name, then the name, then the member. That length prefix is deliberate. It guarantees that all of one graph's records sort together and that no graph's keyspace can bleed into another's, even if one graph name happens to be a prefix of another. The IDs in the member portion are zero-padded to twenty digits (n:%020d), which is the trick from Part 3 reused here: zero-padding makes lexicographic byte order agree with numeric order, so a cursor walking the bucket hands back nodes already sorted by ID, with no sort step in our code.

That single decision pays for several others. Listing a graph's nodes is a prefix scan. Deleting a graph is a prefix scan plus a delete of each key under it, which is exactly what GRAPH.DELETE does. Because the same ordered cursor that powers SCAN and sorted sets is what we iterate here, the graph feature inherited the engine's read concurrency and crash safety for free. There is no separate graph store to keep consistent with the KV store; it is the KV store.

Secondary structures, also just keys

A naive scan-and-filter is fine for tiny graphs and miserable for anything larger, so alongside each node we write small index keys, again under the same graph prefix. A label index entry (l:<label>:<id>) lets MATCH (n:Person) seek straight to the nodes carrying that label instead of reading every node in the graph. An adjacency entry (adj:<srcid>:<edgeid>) lets a traversal find a node's outgoing edges by prefix seek rather than scanning all edges. And if you declare an index with CREATE INDEX ON :Person(email), we write a property index entry (i:person:email:<value>:<id>) so that an equality filter on that property becomes a seek. These are not a separate index structure; they are more keys in the same bucket, with empty values, exploiting the same ordering. When a node is rewritten, putGraphNode cleans up the stale label and property index entries for the old version before writing the new ones, so the indexes never drift from the data.

The query path

The command surface mirrors RedisGraph. GRAPH.QUERY runs a query, GRAPH.RO_QUERY runs one but rejects anything that writes, GRAPH.LIST enumerates the graphs that exist, GRAPH.DELETE removes a graph and all its records, and GRAPH.EXPLAIN and GRAPH.PROFILE return plan-shaped output. Read-write routing is decided up front by a cheap textual check: if the query begins with CREATE or MERGE, or contains a SET or DELETE clause, it is a write and runs inside an Update transaction; otherwise it runs inside a View. That is the same single-writer discipline the rest of the engine lives by, applied here so a graph mutation takes the one write transaction and graph reads scale out across read transactions.

The interesting decision is the parser. We did not write a Cypher compiler. Early versions matched whole statements with regular expressions, and you can still see those patterns in the source. What ships now is a small hand-written lexer and recursive-descent parser: it tokenizes the query into identifiers, punctuation, strings, and operators, then parses node patterns (v:Label {k: val}), edge patterns [r:TYPE], and the clause sequence WHERE ... RETURN ... SET ... DELETE ... LIMIT. The WHERE grammar has real precedence, with OR over AND over primary comparisons, and supports =, !=, <>, the ordering operators, plus IN, STARTS WITH, ENDS WITH, CONTAINS, and IS NULL. It parses, it is not a toy, but it is a deliberately bounded grammar, not the full language.

Execution is a hand-written evaluator, not a planner. For a node match it picks the cheapest available entry point in this order: if the WHERE clause has an equality on an indexed property, it seeks the property index; otherwise if there is a label it seeks the label index; otherwise it falls back to scanning every node. Then it filters each candidate against the inline property pattern and the WHERE expression, and projects the requested RETURN columns. Edge matches start from the left-hand nodes and walk adjacency entries. The result is assembled into the three-part array shape RedisGraph clients expect, a header row of column names, the data rows, and a stats row, built from this struct:

type graphQueryResponse struct {
	header []interface{}
	rows   []interface{}
	stats  []interface{}
}

The stats strings ("Nodes created: 1", "Records produced: 4", "Query internal execution time: ...") are formatted to look like RedisGraph's so existing client libraries parse them without complaint. When a write produces no rows, only the stats array comes back, which is also what callers expect.

Honest scope

This is where we have to be careful, because the gap between "speaks the protocol" and "is a graph database" is exactly where a migration goes wrong if nobody told you. The original plan document scoped Phase 1 to create, merge, single-pattern match, and basic where filters, and explicitly put aggregations, path expansion, variable-length edges, and planner parity out of scope. The shipping code has actually grown past that plan in a few places, and we would rather tell you precisely where it stands than point you at a stale spec.

What works today: CREATE of nodes and single-edge patterns; MERGE of a node by label and exact property set; MATCH with optional label, inline property filters, and a WHERE clause; RETURN of variables, var.property projections, and id(n); SET to update properties; DELETE of matched nodes (with their incident edges) and of matched relationships; and LIMIT. Beyond the original plan, the evaluator also implements the aggregates count, sum, min, max, avg, and collect with implicit grouping on the non-aggregate columns, variable-length relationship patterns like [*1..3] via a bounded breadth-first walk over adjacency keys, and user-declared property indexes through CREATE INDEX and DROP INDEX.

What still does not work, and is not pretended to: there is no query planner, so GRAPH.EXPLAIN and GRAPH.PROFILE are compatibility stubs that emit plausible operator names and fixed timings rather than a measured plan; multi-pattern MATCH and longer chained patterns beyond the single (a)-[r]->(b) form are not supported; OPTIONAL MATCH, WITH, UNWIND, ORDER BY, SKIP, named-path semantics, query parameters ($param), and the long tail of Cypher functions are absent; and the comparison operators coerce types pragmatically rather than implementing Cypher's full type system and precedence. The execution model is scan-and-filter accelerated by simple secondary indexes, which is fine for modest graphs and exact-match access patterns and gets slower, linearly, as a query touches more of the graph. If your workload needs real planning, deep multi-hop traversal at scale, or full language coverage, that is a dedicated graph engine's job, and we say so directly in Neo4j vs a disk-based RedisGraph-style subset and in our notes on migrating legacy graph query workloads.

Graph keys are first-class keys

One thing we did insist on: a graph is not a second-class citizen bolted onto the side. Because the graph's metadata key lives in a known bucket under a known prefix, the engine's keyspace commands recognize it. TYPE social returns graph. EXISTS social and DEL social work, with DEL delegating to the same prefix-delete that GRAPH.DELETE uses. KEYS * and SCAN include graph names alongside strings, hashes, sets, sorted sets, and streams, by checking the graph bucket for meta keys during their walk. TTL applies too: you can set an expiry on a graph key and the background sweeper from Part 6 will remove it like any other. From the keyspace's point of view a graph is one named thing that happens to expand into many internal records, and every general-purpose key command treats it that way. That consistency is the difference between a feature and a bolt-on, and it falls out naturally because the graph never left the one bucket-and-key model the rest of the engine uses.

Closing the series

Step back from this part and the whole series resolves into a single claim, which we set out to demonstrate rather than assert. One byte-ordered B+tree in one file, plus composite keys that lay out structured data so that lexicographic order is the order you want, plus one serialized write loop for durability, is enough to host a remarkable amount of surface area. Part 2 fit the Redis string, list, hash, and set types into that tree. Part 3 reproduced sorted sets by encoding both orderings as keys. Part 4 walked a live tree with stateful SCAN cursors. Part 5 served three wire protocols against the one file. Part 6 explained how a single write loop and a TTL sweeper give crash-safe durability. And this part showed that the very same primitives, with nothing new underneath, carry a property graph and a Cypher subset that legacy RedisGraph clients can talk to unchanged.

The through-line is restraint. At no point did a new capability require a new storage engine, a new cache, or a new concurrency model. Each feature is composite keys and ordered iteration in a fresh arrangement. That is the bet BaseKV makes, and the reason we wrote the series: the interesting engineering was never in raw speed, it was in how much you can build honestly on a small, well-chosen foundation, and in being straight about where that foundation stops. If this is the first part you have read, start at the beginning and watch the same idea get reused six times.

---

This concludes the series. Series index: part 1, the design bet, part 2, encoding Redis types, part 3, sorted sets on disk, part 4, SCAN over a live B+tree, part 5, three protocols one file, part 6, durability and TTL. Related reading: RedisGraph deprecated, now what, Neo4j vs a disk-based RedisGraph-style subset, migrating legacy graph query workloads.