clustering

package
v0.1.0-alpha.4 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 11, 2026 License: MIT Imports: 14 Imported by: 0

README

graph/clustering

Groups the graph's entities by the prefix of their IDs and keeps one small record per group in the COMMUNITY_INDEX bucket. A caller feeds the package entity changes; the package publishes only the groups that changed. It reads no graph data itself, starts no goroutine and opens no ENTITY_STATES watch.

What a community is

An entity ID has six parts, org.platform.system.domain.type.instance (ADR-102). A community here is every entity whose ID starts with the same first parts. The level is how many parts:

Level Prefix Example
0 org.platform.system.domain acme.dep1.gcs1.robotics
1 org.platform.system (the source) acme.dep1.gcs1
2 org.platform (the deployment) acme.dep1

So one entity is in three communities, and the levels never overlap in name. Nothing is detected: the groups follow from the IDs, which is the decision of ADR-099. The pin's label propagation is not carried.

The record for a group is a Community: its ID (the prefix), Level, MemberCount, TypeCounts (members by the ID's fifth part, the 10 most common), Keywords (the 10 most frequent words in members' string values), a one-line StatisticalSummary built from those counts, and RepEntities (up to 5 member IDs, the lexically smallest among members that have words). It never lists the members, so its size does not grow with the group: every field is capped, and the encoded record stays under MaxRecordBytes (8 KiB). The key is {level}.{prefix}, for example 1.acme.dep1.gcs1.

A record also carries EntityRevision (entity_revision), the latest entity write it reflects: the highest ENTITY_STATES revision among the Upsert and Delete calls the maintainer applied for entities whose IDs fall in the group. That counts every applied call: a delete of an entity the maintainer never held (such as a delete marker replayed after a restart) and a refused value both raise it. A delivery at or below the revision already applied for its key is not applied and does not raise it. The mark ends with the group: when the last member goes, the records go, and the entity that recreates the group gives it that entity's revision. A raised record differs from the one last written, so the next tick writes it. What it promises, and only when the caller feeds revisions in ascending order across keys (below): every ENTITY_STATES write at or below entity_revision is reflected in the record. A written record never carries 0.

To read one record, a reader finds its key with GroupKey(entityID, level), which refuses a level outside 0 to 2 and an ID the canonical parser refuses, and checks the value with DecodeCommunity(key, value), which refuses a value that is not JSON, a record whose level is not 0, 1 or 2, a record whose level and ID do not give that key, and entity_revision 0. GetAllCommunities checks each entry the same way. To read every record at one level, a reader lists the keys that start with LevelPrefix(level), the level and a dot, which refuses a level outside 0 to 2.

A word is a run of 3 to MaxWordBytes (32) ASCII letters and digits in a string value, ignoring case and a short list of stop words. A longer run is not a word, and nothing is cut. IDs, predicate names and the objects of relationships (other entity IDs) add no words. Each entity adds at most its MaxEntityTerms (32) most frequent words to each of its groups, so a word that is outside the top 32 of every member cannot become a keyword.

Basic use

You give the maintainer each change to an entity and say when the first read of the bucket is complete. Then you call Tick on an interval.

// kv is the COMMUNITY_INDEX bucket, from kvcatalog.EnsureCatalogBucket(ctx, client, graph.BucketCommunityIndex).
storage, err := clustering.NewNATSCommunityStorage(client.NewKVStore(kv))
if err != nil {
    return err
}
m, err := clustering.NewMaintainer(storage)
if err != nil {
    return err
}

// For each delivery of your ENTITY_STATES watch: the revision is that of the value you decoded.
if err := m.Upsert(entityID, revision, state); err != nil {
    // a refused entity: see "Failure signals"
}
// For a delete or purge of a key:
_ = m.Delete(entityID, revision)

// After the watch's initial replay has been applied. With a raw WatchAll that is the nil entry on its
// updates channel, the marker graph/follower already relies on (graph/follower/follower.go:227).
m.BootstrapDone()

// On an interval, from any goroutine:
err = m.Tick(ctx)

graph/clustering/maintainer_product_integration_test.go (TestMaintainerAsAProduct) runs exactly this against a real NATS server and reads the records back with storage.GetAllCommunities(ctx).

What the caller owes the maintainer:

  • The revision of the exact value. Upsert(entityID, revision, state) takes the KV revision of the very value state was decoded from. Do not read the entity again and pair the new value with an older revision.
  • Increasing revisions per key. Deliveries for one key must arrive in increasing revision order, as from one ordered watch. The maintainer ignores a delivery at or below the revision it already holds for that key, and that is its only defence; it cannot reorder. This is the caller's precondition, not something the package checks across keys or tests against a real watch.
  • Ascending revisions across keys, for entity_revision to hold. entity_revision's promise needs every delivery, whatever its key, to arrive in increasing revision order. Fed out of order across keys, the records' counts and words still come out right, but a record can name a revision above a write it does not yet reflect. That a KV watch delivers this order is not promised here: ADR-066 states it without a probe. processor/graph-clustering, which wires the watch, probes it at the pinned nats.go and nats-server versions (TestWatchOrderAcrossKeys). The order it observed is recorded in that change's notes/2.3.md as an observation, not a promise (ADR-112).
  • Revision 0 is refused. A KV entry's first revision is 1 (TestKVRevisionStartsAtOne probes it on the pinned nats.go and nats-server; it is not promised beyond that), so 0 means the caller passed none.
  • BootstrapDone once, after the replay. Tick before it returns ErrBootstrapIncomplete and writes nothing, because a record built from half a replay would be published as if it were the graph.

The methods are safe to call from the watch goroutine and a ticker goroutine at once. Upsert and Delete never wait for the storage writes of a running Tick.

What a tick costs

The maintainer keeps the groups in memory and updates them as changes arrive: a changed entity subtracts its old contribution (one member, one count for its type, its words) and adds the new one. A restart rebuilds them from the watch's replay, so the first tick after a start publishes every group once.

A Tick recomputes only the groups touched since their last publication, and writes a record only when it differs from the one last written. After the first tick it reads nothing from COMMUNITY_INDEX and holds no handle on ENTITY_STATES. A write that changes no count, word or representative still raises entity_revision, so it writes its entity's three records once. The cost of a group is in proportion to its distinct words (a top-k selection, not a full sort), and it is paid while Upsert and Delete wait on the same lock. TestTickCost counts the storage calls: k changed entities cause writes only to their groups, and an unchanged graph writes nothing.

The first tick lists the bucket's keys once. After every changed record is written it removes the records of groups that no longer exist (the groups that became empty, and keys left from an earlier run). If any write fails nothing is removed, so the old records stay readable (ADR-085, decision 7: stale, never empty).

Failure signals

  • ErrBootstrapIncomplete (errors.Is): Tick before BootstrapDone.
  • A storage error from Tick: a write, a removal or the first listing failed, or the context ended before the pending work was done. The work stays pending and the next Tick retries it. A Tick with nothing pending does not look at the context.
  • *IncompleteError (errors.As): every group was published, but some entities are refused. Refused holds their IDs, sorted; Error() names the first ten. Tick returns nil only when all is published and nothing is refused.
  • A refusal from Upsert, an invalid error naming the entity: a nil state, an ID that is not a valid 6-part entity ID, or a state whose ID differs from entityID. A refused entity contributes nothing and stays in the refused set until a valid Upsert or a Delete for it.
  • GetAllCommunities fails, naming the key, on an entry it cannot read or that DecodeCommunity refuses (the pin skipped such entries), and returns the context's error if the context ends. An empty bucket is no records and no error.

What is not here

  • Language-model summaries and the summary store (the pin's CommunitySummarizer, StatisticalSummarizer, enhancement worker and COMMUNITY_SUMMARIES): tier 2, tracked in issue #485. The record's StatisticalSummary is a template over the counts.
  • Label propagation and the edge providers that fed it: removed by ADR-099. A detection overlay over chosen relationship predicates may return as a later change, off by default, in a namespace nothing reads for serving.
  • The watch and the ticker. processor/graph-clustering follows ENTITY_STATES through graph/follower, whose entries carry the delivered value and its revision, calls Upsert and Delete with them, and runs Tick every detection_interval once the replay is applied. It does not read records back: GetAllCommunities served the pin's anomaly lane, which is never ported, and has no caller in this tree.
  • A reader's consistency rule. Which generation of the bucket a reader sees during a tick is for the processor/graph-query item, not decided here.
  • A per-group member list and a membership hash. Members are found through the prefix queries of the graph's query lane.

The decoder in semboids reads a member list from a record; it does not read these bounded records.

Documentation

Overview

Package clustering groups entities by entity-ID prefix and publishes one bounded record per group to the COMMUNITY_INDEX bucket.

A group (a "community" in the record) is every entity whose ID shares one prefix: level 0 is org.platform.system.domain, level 1 is org.platform.system and level 2 is org.platform (ADR-099, with the levels ADR-102 gives). Nothing is detected: an entity's groups follow from its ID alone.

A Maintainer keeps the groups current from entity changes. The caller feeds it one ordered watch of ENTITY_STATES: Upsert or Delete for each delivery, with the revision of the exact value decoded, then BootstrapDone when the watch's initial replay ends. Tick, called on an interval, writes the record of each group that changed since its last publication (Community) through a NATSCommunityStorage, and removes nothing until every write of that tick has succeeded. GetAllCommunities reads every record back.

The package starts no goroutine and holds no ENTITY_STATES handle; the watch and the ticker belong to the caller (processor/graph-clustering). Records are bounded by construction (MaxRecordBytes) and hold counts and samples, never a member list. The README lists what is not here: label propagation, and the language-model summaries.

Index

Constants

View Source
const (
	// MaxRepEntities is the most representative entity IDs a record holds.
	MaxRepEntities = 5
	// MaxKeywords is the most keywords, and the most entity types, a record holds.
	MaxKeywords = 10
	// MaxEntityTerms is the most words one entity contributes to each of its groups.
	MaxEntityTerms = 32
	// MaxWordBytes is the longest word. A longer run of letters and digits is not a word.
	MaxWordBytes = 32
	// MaxRecordBytes bounds a record's JSON encoding whatever its members' values: a
	// 256-byte ID, MaxKeywords types of at most 246 bytes, MaxKeywords words,
	// MaxRepEntities 256-byte IDs and a summary naming three types and five keywords
	// encode to under 6 KiB (TestRecordIsBounded).
	MaxRecordBytes = 8 << 10
)

The bounds of a published group record (design D4). Each holds by construction, so a record is never truncated at run time.

Variables

View Source
var ErrBootstrapIncomplete = errors.New("clustering: bootstrap incomplete")

ErrBootstrapIncomplete is returned by Tick before BootstrapDone: a record built from a partial replay would be published as if it were the graph.

Functions

func GroupKey

func GroupKey(entityID string, level int) (string, error)

GroupKey returns the COMMUNITY_INDEX key of entityID's group at level: the level, a dot, and the ID's first four (level 0), three (1) or two (2) positions. It refuses, with an invalid error, a level outside 0 to 2 and an ID the canonical parser refuses.

func LevelPrefix

func LevelPrefix(level int) (string, error)

LevelPrefix returns the prefix every COMMUNITY_INDEX key at level starts with: the level and a dot. It refuses, with an invalid error, a level outside 0 to 2.

Types

type Community

type Community struct {
	// ID is the group's entity-ID prefix.
	ID string `json:"id"`

	// Level is the group's level: 0, 1 or 2.
	Level int `json:"level"`

	// MemberCount is the number of entities in the group.
	MemberCount int `json:"member_count"`

	// EntityRevision is the highest ENTITY_STATES revision among the Upsert and Delete
	// calls the maintainer applied for entities whose IDs parse into the group, held,
	// refused or not; a delivery at or below an entity's last-applied revision is not
	// applied. The mark ends with the group: a recreated group starts at the write that
	// recreated it. With the caller feeding ascending revisions across keys, every write at
	// or below it is reflected in the record. It is never 0 (DecodeCommunity).
	EntityRevision uint64 `json:"entity_revision"`

	// TypeCounts counts members by entity type (the ID's fifth position), for the
	// MaxKeywords most common types, ties broken lexically.
	TypeCounts map[string]int `json:"type_counts"`

	// Keywords are the group's MaxKeywords most frequent words, most frequent first,
	// ties broken lexically. Words come only from members' string values.
	Keywords []string `json:"keywords,omitempty"`

	// StatisticalSummary is a one-line text built from the counts, three types and five
	// keywords.
	StatisticalSummary string `json:"statistical_summary,omitempty"`

	// RepEntities are the lexically smallest IDs of members with words, at most
	// MaxRepEntities.
	RepEntities []string `json:"rep_entities,omitempty"`
}

Community is the published record of one group: every entity whose ID shares one prefix. Level 0 groups by org.platform.system.domain, level 1 by the source org.platform.system, level 2 by the deployment org.platform (ADR-102 d6); ID is that prefix. The record holds counts and samples, never the member list, so its size does not grow with the group.

func DecodeCommunity

func DecodeCommunity(key string, value []byte) (*Community, error)

DecodeCommunity decodes value, the COMMUNITY_INDEX entry at key, as storage does. It refuses, with an invalid error naming key, a value that is not JSON, a record whose level is not 0, 1 or 2, a record whose level and ID do not give key, and a record whose EntityRevision is 0, which no maintainer writes.

type IncompleteError

type IncompleteError struct {
	// Refused are the refused entity IDs, sorted.
	Refused []string
}

IncompleteError is returned by a Tick that published every group while some entities stay refused: the records leave those entities out.

func (*IncompleteError) Error

func (e *IncompleteError) Error() string

type Maintainer

type Maintainer struct {
	// contains filtered or unexported fields
}

Maintainer keeps one group per entity-ID prefix at each level current from entity changes, and publishes the changed groups' records on each Tick. A caller feeds it one ordered watch of the entity bucket: Upsert and Delete for each delivery, in increasing revision order per key, then BootstrapDone when the initial replay ends. Its methods may be called from the watch goroutine and a ticker goroutine at once.

func NewMaintainer

func NewMaintainer(storage *NATSCommunityStorage) (*Maintainer, error)

NewMaintainer returns a Maintainer publishing to storage. It refuses a nil storage.

func (*Maintainer) BootstrapDone

func (m *Maintainer) BootstrapDone()

BootstrapDone records that the initial replay has been applied; Tick publishes only after it.

func (*Maintainer) Delete

func (m *Maintainer) Delete(entityID string, revision uint64) error

Delete removes entityID's contribution at revision. A revision at or below the one last applied changes nothing. An entity it does not hold has nothing to remove, but the Delete is applied all the same: like any applied Delete it raises its groups' Community.EntityRevision to revision. Revision 0 is refused, as in Upsert.

func (*Maintainer) Tick

func (m *Maintainer) Tick(ctx context.Context) error

Tick publishes every group changed since its last successful publication: it writes each record that differs from the one last written and, only after every write succeeded, removes the records of groups that became empty and, after the first tick's one key listing, the keys of groups that do not exist. A failure, or the context ending before the pending work is done, returns an error and leaves the work pending for the next Tick; with nothing pending, an ended context is not consulted. It returns ErrBootstrapIncomplete before BootstrapDone, an *IncompleteError when all is published but some entities are refused, and nil otherwise.

func (*Maintainer) Upsert

func (m *Maintainer) Upsert(entityID string, revision uint64, state *graph.EntityState) error

Upsert applies entityID's value at revision, the revision of the exact value state was decoded from. A revision at or below the one last applied for entityID changes nothing. Revision 0 is refused and changes nothing: a KV entry's revision is its stream sequence, which starts at 1 (TestKVRevisionStartsAtOne), so 0 is a caller that passed no revision. It refuses, with an invalid error naming the entity, a nil state, an ID the canonical parser refuses, or a state whose ID is not entityID; a refused entity contributes nothing until a valid Upsert or a Delete for it. An applied Upsert, refused or not, raises its groups' Community.EntityRevision to revision.

type NATSCommunityStorage

type NATSCommunityStorage struct {
	// contains filtered or unexported fields
}

NATSCommunityStorage reads and writes group records in the COMMUNITY_INDEX bucket (graph.BucketCommunityIndex), one key per group: {level}.{group ID}.

func NewNATSCommunityStorage

func NewNATSCommunityStorage(kv *natsclient.KVStore) (*NATSCommunityStorage, error)

NewNATSCommunityStorage returns a storage over kv, the COMMUNITY_INDEX bucket. It refuses a nil kv.

func (*NATSCommunityStorage) GetAllCommunities

func (s *NATSCommunityStorage) GetAllCommunities(ctx context.Context) ([]*Community, error)

GetAllCommunities returns every record in the bucket, in key order. An entry that cannot be read, or is not the record of the group its key names, fails the call with an error naming the key; an ended context returns its error. An empty bucket gives no records and no error.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL