Skip to content

PATTERN Cited by 1 source

Lex-sorted concatenated edge ID

Lex-sorted concatenated edge ID is a deterministic edge- identifier construction: given a pair of endpoint node IDs, sort them lexicographically, then concatenate. The result is a unique- and-stable identifier per edge-pair regardless of which direction the caller specified.

edge_id(A, B) = lex_sort([A, B]).concat()
            ≡ edge_id(B, A)

Why a deterministic edge-pair ID

In a graph storage layout that stores edge links under direction-specific keys (forward + reverse adjacency indexes, patterns/forward-and-reverse-adjacency-index) but edge properties in their own namespace (patterns/separate-edge-links-from-properties), the property namespace must have a single canonical record per edge pair — otherwise:

  • Storing properties twice (under both natural orderings) doubles storage and forces atomic two-record writes per update.
  • Storing them under one canonical ordering forces callers to know which ordering before issuing a property request.

The lex-sort-then-concat construction makes the canonical ordering a function of the values, computable independently by any client or server, and bidirectional-equivalent by construction.

Disclosed in Netflix Graph Abstraction

Verbatim from Part-I:

"To ensure consistent record identifiers when updating edge properties in either direction, the Abstraction lexicographically sorts and concatenates the source and destination node IDs to create a direction-agnostic identifier for property storage. This ensures that properties can be accessed or mutated in a single database call regardless of the direction specified in the request."

Construction

For Netflix's (profile-A, device-X) example:

Caller view Lex-sort Concat ID
device-X → profile-A [device-X, profile-A] device-X\|profile-A
profile-A → device-X [device-X, profile-A] device-X\|profile-A

Both directions land at the same partition; both updates respect LWW against a consistent identifier.

Where to apply

This is a property-namespace-only construction. The link namespaces continue to use the natural endpoint-keyed clustering (forward index keyed by source, reverse index keyed by target) because traversals fundamentally need to find neighbours of a specific node. The lex-sorted concat ID lives only in the edge-property namespace.

Namespace Identifier strategy
Forward link namespace partition = source, clustering = target
Reverse link namespace partition = target, clustering = source
Edge property namespace lex-sorted-concat of (source, target)

Trade-offs

  • Opacity to humans / clients. The ID is opaque; clients cannot retrieve a property by directly using (source, target) — they must apply the same sort + concat transformation. Server-side helpers usually hide this from callers.
  • Self-loop edge case. A self-loop edge (A, A) has the trivial lex-sort [A, A] → concat A||A. No collision risk since all other edges have two distinct endpoint values (assuming node IDs are unique within the graph, which is a property-graph invariant).
  • Cross-edge-type collision. If multiple edge types can exist between the same pair of nodes (e.g., friend AND colleague between two profiles), the property namespace must include the edge type as part of the partitioning to avoid collision. Netflix Graph Abstraction has per-edge-type property namespaces, so the lex-sort-concat ID is unique within a namespace.

Composition

The pattern is the third structural piece of Netflix Graph Abstraction's edge storage layout:

  1. patterns/separate-edge-links-from-properties — split into 2 namespaces.
  2. patterns/forward-and-reverse-adjacency-index — link namespace materialised in both directions.
  3. Lex-sorted concat ID — property namespace uses one canonical record per edge pair.

Together: any edge-property update touches one record; either- direction traversal is O(neighbours); multi-namespace consistency handled by Kafka entropy repair.

Seen in

Last updated · 542 distilled / 1,571 read