Graph-Native Data Structures in C#, Part 3: Linked Lists and Sequences as Edges

When Order Is the Data

Relational tables store facts. Graph edges store relationships. Sequences sit awkwardly between the two. An audit log, a document version chain, a workflow step list, an activity feed: in all of them the order is the data, not just a sort key.

SQL works around this with ORDER BY created_at, which ties ordering to the clock and falls apart the moment two events land in the same millisecond. A graph solves it directly. Model each item as a vertex, connect items with directed next edges, and hang head_of and current pointers on a stream vertex. You get a singly linked list that lives in the graph, walkable in both directions, sliceable by step count, and usable with everything else in your schema.

This is Part 3 of the series. Part 1 has the schema and VID conventions everything here builds on. The running example is an append only audit stream. Version history for a document is the same structure with different names.

Schema: Stream and Event Vertices Connected by Edges

Two tags and three edge types:

CREATE TAG event(eid STRING, type STRING, payload STRING, ts INT);
CREATE TAG stream(name STRING);
CREATE EDGE next();          // event -> next event
CREATE EDGE head_of();       // stream -> first event
CREATE EDGE current();       // stream -> latest event

Vertex IDs follow the deterministic pattern from Part 1:

• Events: evt: plus a content addressable or monotonic identifier, for example evt: plus the first 16 hex characters of a SHA-256 over the payload and timestamp.
• Streams: stream: plus the stream name, for example stream:orders-svc.

Deterministic VIDs are what make appends idempotent. In NebulaGraph, INSERT VERTEX is an upsert by VID. Inserting a vertex with a VID that already exists overwrites its properties instead of creating a second one. A replayed event with the same content produces the same VID, lands on the same vertex, writes the same data, and nothing is duplicated.

Edge identity is (src VID, dst VID, edge type, rank). For a singly linked list always use rank=0. If you insert two next edges from the same source with the same rank and different destinations, NebulaGraph overwrites the first with the second without an error, and your chain is broken with nothing to tell you.

Walking the Chain in C#

GO does most of the work. The M TO N STEPS form walks a bounded number of hops:

GO 1 TO 50 STEPS FROM 'evt:abc' OVER next YIELD dst(edge) AS eid

That returns up to 50 successors of evt:abc, ordered by depth. One thing to know: GO uses walk semantics, so a vertex or edge can be visited more than once. A cycle in a damaged chain will not loop forever, it stops at N steps, but it will quietly return nonsense. Check for cycles in C# before you trust the result.

For the latest N events, start at the stream's current pointer and walk backwards:

GO 1 FROM 'stream:orders-svc' OVER current YIELD dst(edge) AS tail
| GO 1 TO 10 STEPS FROM $-.tail OVER next REVERSELY YIELD dst(edge) AS eid
| LIMIT 0, 5

REVERSELY traverses the edge in the other direction. It is native nGQL only, it has no openCypher equivalent. Before 3.0 there was a bug that let expired edges leak into REVERSELY results. It was fixed in v3.0.0, so on 3.8.x you are fine.

Here is a C# helper for both operations using NebulaNet (NuGet package NebulaNet, currently 3.0.0, check the GitHub tag against your server version before you ship):

public class EventStreamReader
{
    private readonly NebulaPool _pool;
 
    public EventStreamReader(NebulaPool pool) => _pool = pool;
 
    // Walk forward from a known event vertex, up to maxSteps hops.
    public async Task<List<string>> WalkForwardAsync(
        string startEventVid,
        int maxSteps = 50)
    {
        var session = await _pool.GetSessionAsync("root", "nebula");
        try
        {
            string nGql = $"""
                GO 1 TO {maxSteps} STEPS FROM '{startEventVid}'
                OVER next
                YIELD dst(edge) AS eid
                """;
 
            var result = await session.ExecuteAsync(nGql);
            return result.AsVertexIdList("eid"); // extension from nebula-net
        }
        finally
        {
            session.Release();
        }
    }
 
    // Return the latest N event VIDs by walking backwards from the stream's current pointer.
    public async Task<List<string>> TakeLatestAsync(string streamName, int n)
    {
        var session = await _pool.GetSessionAsync("root", "nebula");
        try
        {
            string nGql = $"""
                GO 1 FROM 'stream:{streamName}' OVER current YIELD dst(edge) AS tail
                | GO 1 TO {n} STEPS FROM $-.tail OVER next REVERSELY
                  YIELD dst(edge) AS eid
                | LIMIT 0, {n}
                """;
 
            var result = await session.ExecuteAsync(nGql);
            return result.AsVertexIdList("eid");
        }
        finally
        {
            session.Release();
        }
    }
}

YIELD supports src(edge), dst(edge), type(edge) and rank(edge). Nesting them, such as dst(src(edge)), is not supported.

Mutations: Append and Splice

AppendAsync, an Idempotent Tail Insert

Appending takes three steps. Insert the new event vertex, insert a next edge from the old tail, then move the stream's current edge. The idempotency you get from a deterministic VID covers the vertex only. Moving the pointer is last write wins and it is not atomic. If two writers race to move current, one overwrites the other, and an event ends up orphaned from the current chain even though its vertex is there. The practical fix at this layer is to serialise writes in the application, with a distributed lock or a single writer per stream.

public async Task AppendAsync(
    string streamName,
    string newEventVid,
    string oldTailVid,
    string eventType,
    string payload,
    long ts)
{
    var session = await _pool.GetSessionAsync("root", "nebula");
    try
    {
        // Step 1: upsert the event vertex (idempotent by deterministic VID)
        string insertEvent = $"""
            INSERT VERTEX event(eid, type, payload, ts)
            VALUES '{newEventVid}':('{newEventVid}', '{eventType}', '{payload}', {ts});
            """;
 
        // Step 2: link old tail to new event
        string insertNext = $"""
            INSERT EDGE next() VALUES '{oldTailVid}'->'{newEventVid}'@0:();
            """;
 
        // Step 3: move the stream's current edge.
        // Delete the old one and insert a new one. UPDATE EDGE can only change
        // properties, and we need to change dst, so delete plus insert it is.
        string deleteOldCurrent = $"""
            DELETE EDGE current 'stream:{streamName}'->'{oldTailVid}'@0;
            """;
        string insertNewCurrent = $"""
            INSERT EDGE current() VALUES 'stream:{streamName}'->'{newEventVid}'@0:();
            """;
 
        await session.ExecuteAsync(insertEvent);
        await session.ExecuteAsync(insertNext);
        await session.ExecuteAsync(deleteOldCurrent);
        await session.ExecuteAsync(insertNewCurrent);
    }
    finally
    {
        session.Release();
    }
}

SpliceAsync, a Mid Chain Insert

Splicing is where it gets risky. To put newVid between prevVid and nextVid:

1. Insert the new event vertex.
2. Insert the next edge prevVid -> newVid.
3. Insert the next edge newVid -> nextVid.
4. Delete the old next edge prevVid -> nextVid.

Do step 4 last. If the process dies between steps 2 and 3 and step 4, the chain has a fork, two next edges out of prevVid, but both paths still reach nextVid. That is recoverable, a later cleanup can drop the direct edge. If you delete the old edge first and then crash, the chain is broken and nextVid is orphaned. Always remove the bypassed edge after the new path is confirmed.

Versioned and Temporal Data

Document version history maps onto this exactly. Each commit is an event vertex whose payload holds the diff or a snapshot. The head_of edge points at the oldest version, the root of the history. current points at HEAD. Walking forward from head_of gives you history in order. Walking backward from current gives you the N most recent revisions without loading the whole chain.

Keep the chain immutable. Never change an event vertex after it is written. If you need to annotate a past event, for example to mark it reviewed, add a separate review vertex and connect it with a reviewed edge. The audit chain stays clean and the annotations sit beside it.

Pitfalls Checklist

Accidental cycles. A next edge pointing the wrong way creates a cycle that GO will walk quietly up to the step cap, returning the same VIDs more than once. Check the returned list for duplicates before you process it.

Orphaned nodes after a bad splice. Delete the bypassed edge last, as above. If you need strict consistency, keep a compensating transaction table in a relational sidecar.

Concurrent append races. Idempotent VIDs protect the vertex, not the pointer edges. Serialise writes per stream with a distributed lock, Redis or an Azure Blob lease for example, or send every append for a stream through one actor.

Rank collisions. Always use rank 0 for singly linked list edges. The moment a second next edge from the same source is inserted at rank 0, it silently replaces the first. If you genuinely need parallel edges, merge commits with two parents for example, assign explicit stable ranks and write down why.

NuGet version lag. NebulaNet 3.0.0 on NuGet is from March 2022, while the server is on 3.8.x. Some nGQL syntax added in later server releases may behave oddly or fail. Pin your integration tests to the real server version and check the nebula-contrib/nebula-net repository for unreleased fixes before you assume the package is current.

nGQL is not openCypher. Everything here, GO ... OVER ... REVERSELY, INSERT VERTEX, DELETE EDGE, is native nGQL and does not work in the openCypher dialect. If your codebase uses both, keep the chain walking queries in service classes that are clearly marked as native nGQL.

Where to Go Next

Part 4 covers trees and hierarchical data: parent and child edges, subtree queries with GET SUBGRAPH, and storing materialised paths as edge properties so you can avoid deep recursive walks. The linked list here composes naturally with that, because a sequence of tree mutation events is a linked list, and replaying it rebuilds the tree as it was at any point in its history.