Kythe Storage Model

As viewed from the storage layer, a ‘node’ in a Kythe graph is essentially a bag of string-valued key/value properties associated with a unique name. In order for this representation to make sense, each node must have a unique name, to distinguish it from all the other nodes in the graph.

To solve this naming problem, Kythe adopts the view that a node is a d-dimensional ‘vector’, where each dimension represents some scalar fact about the node: The “dimensions” in this case are not numbers, but arbitrary semantic categories, e.g., kind, identifier, snippet, location, corpus, language. A particular node is defined by fixing its values in each dimension (where “empty” is also an option).

In practice it is not necessary to model nodes as explicit vectors, but the ability to do so is very convenient for computation. In particular, searching, clustering, indexing, and other related machine-learning tasks are simple to express in this model: Node-vectors can be projected into weight vectors for computing similarities or identifying clusters, or subjected to principal components analysis to identify relevant features, and so on.

Taking the view that a node is essentially a vector of its properties leads to the naming scheme Kythe uses for nodes in its graph:

A node N can be uniquely identified relative to a universe U of nodes by fixing any v-dimensional projection of the node’s attributes that differs from all U \ {N} under the same projection. In other words, we can choose a name for N by picking a small basis of facts about a node, and use the node’s projection into the basis as its “name”. This works as long as the facts we pick are sufficient to distinguish all the nodes in our set U.

We call a name constructed using this approach a “Vector-Name” or VName for the node. A VName is the primary unit of naming in the Kythe graph store.

One important property of a VName is that it is extensible: As a collection of nodes grows, new nodes may arrive that differ from the existing nodes, but have the same VName. To maintain uniqueness, it is only necessary to add one or more additional dimensions to the VName projection to account for the new data. Updating existing VNames to a new projection is a trivial mechanical rewriting process, particularly when the new projection is an extension of the old one.

See also Kythe URI Specification, which is essentially the same, except that a VName uses UTF-8 and a URI uses pct-encoded values.

The initial definition of a VName includes the following 5 fields:

Other fields can be added as necessary—for example, if a Branch or Client label becomes necessary. As a rule, we try to keep the number of essential VName dimensions as small as possible.

A ticket is defined as a canonical, invertible, textual (and, if practical, human-readable) string encoding of a VName (or a projection of a VName). A ticket encoding is a rule for rendering a (partial) VName into a string such as a URI, JSON or similar. We have the option to define as many such encodings as we may need, subject to the following restrictions:

A ticket should be easy to copy and paste and send around in e-mail or as a URI or JSON string. A ticket doesn’t necessarily have to make sense to a human reader, though to the extent it is possible and practical, it should.

Any encoding that satisfies the above requirements can be used as a ticket; the Kythe open-source tools will use the Kythe URI encoding to create tickets.

A fact is a pair (name, value) of strings, with the constraints that the fact name (fact label) must be non-empty and conform to the following EBNF grammar:

In other words, a fact name is a simple, path-structured label. This construction makes it easy to encode an extensible schema for fact names—the first path component can be used as a schema label, e.g., /kythe for facts defined by the Kythe schema. Other schemata or extensions are free to define different naming conventions within their own namespace. Fact names must be encoded as UTF-8 strings.

In The Unicode Standard 6.3, Section 4.5 "General Category" defines a set of character categories. In the grammar above, LETTER corresponds to characters in categories Lu, Ll, Lt, Lm, or Lo, and DIGIT corresponds to those in category Nd.

Values are stored as strings of uninterpreted bytes—it is up to the schema to define what values are legal for a given fact name, and how to encode them. Importantly, however, the graph store considers values atomic, and does not interpret any structure that may be stored inside them. Set- or sequence-valued data can be stored as multiple facts with a common prefix, e.g.,

The graph store does not interpret fact names; the schema must define the specific rules that apply to their construction and relationships.

An entry is a data structure that associates a single fact with a graph object (a node or an edge). An entry is the primary unit of encoding in the graph store, and each has the following components:

where

If Kind and Target are set, the entry denotes a fact about an edge in the graph; otherwise the entry denotes a fact about a node in the graph. To be valid, an entry must satisfy this constraint:

Implementations of specific services (e.g., cross-references) may define their own specific node and edge representations as needed. The primitive graph store records only entries. A "node" or "edge" in the graph store is simply the collection of entries in the store that share a source, kind, and target.

Given a particular ticket encoding, the standard entry order is defined by lexicographic comparison of the fields of the entry, with ties broken in left-to-right order: Source, Kind, Target, Fact, Value. An empty string (ø) is considered to precede any non-empty string. The VName valued fields Source and Target are compared according to the VName ordering rule.

For example, the following entries are in standard (nondecreasing) entry order; the underlined element in each row denotes the field that “causes” the row to be ordered after the previous row.

Conceptually, each field is compared in isolation; in practice this can be implemented by a flat string comparison separating adjacent fields as if they by an out-of-band delimiter such as NUL.

All edges in a Kythe graph are labelled and directional. The schema defines which edge labels are expected for various purposes, and more can be added.

To support efficient queries, services based on Kythe data will often find it useful to denormalize the Kythe data, to make it easy to traverse the edges of the graph in either direction. For example, if the schema defines a calls edge that connects a function call site with the function it invokes, a user may be interested in two obvious questions:

To answer cross-reference queries efficiently, one simple strategy is to pre-compute the “mirror” of each calls edge, that is to say, the edge with the endpoints reversed, and the relationship inverted. Notionally, this is as if we had, for each edge of the form A calls B, a “reverse” edge B called_by A.

When adding a new feature to the Kythe schema, a natural question to ask is which direction should be the canonical or ‘forward’ edge, i.e., which edge should be emitted by the indexer, and which should be derived?

In Kythe, we have adopted the convention that the “forward” edge, which is the one to be emitted by the indexer, should be the one that expresses some kind of dependency relationship between the source and the target. In the example above, A calls B expresses a dependency between the call site and the callee function. The callee, however, does not have any dependency on the call site; the call site could be deleted from the source without affecting the target function at all.

In the rare cases where no obvious dependency relationship exists, either edge may be labelled as “forward”, but we have adopted the convention that the forward direction is whichever is expected to have the lesser out-degree. As a rule of thumb, if the number of edges X foo Y is expected to be some constant multiple of the number of occurrences of X, foo is designated a forward relationship; otherwise foo is considered a reverse relationship.

By convention, Kythe tools use a fixed lexical convention for generating names for “reverse” edges — generally synthesized for serving purposes — from the edges specified in the schema (refer to the Kythe graph schema).

A graph store is any set of valid entries. A forward graph store is a graph store in which every non-empty edge label is a forward edge label as defined by the schema. Informally, forward edges are those that denote a dependency relationship of the source on the target (see above).

In this model, combining two graph stores into one is accomplished by computing the set union of the two stores. How this is implemented depends on the concrete representation, but for the simple case of a flat ordered table of entries, it can be a simple merge-and-remove-duplicates.

A Read operation should be implemented with time complexity proportional to the size of the return set. The general form of a Read query is:

This operation returns all entries with the given source ticket, subject to the following rules:

Rationale: This formulation allows a client to fetch node metadata and implement depth-first traversals over selected parts of the graph. Because nodes in a forward graph store are expected to have low out-degree for any given edge kind, this allows transitive-closure computations and other simple forward-graph explorations to be performed fairly efficiently. Any implementation that can easily locate all the entries with a given source should be able to implement this query efficiently (even a flat file of entries in standard entry order).

Write operations update the contents of the store. The general form of a write query is:

This operation atomically inserts or updates a collection of entries into the store. Each update is a tuple of the form (kind, target, fact, value). For each such update, the entry (source, kind, target, fact, value) is written into the store, replacing any existing entry (source, kind, target, fact, value') that may exist. Note that this operation cannot delete any data from the store; entries are only ever inserted or updated. Apart from acting atomically, no other constraints are placed on the implementation.

Rationale: Synthesis operations may modify existing data, or add new data, but data need not be deleted except to satisfy requirements external to the data model such as requests to obliterate sensitive data. Such cases must be handled by explicit modification of the underlying storage, and are not addressed by the tool interface.

A Scan is similar to a Read, but with no time complexity restrictions. The general form of a scan query is:

This operation returns all entries with the specified target, kind, and fact label prefix. Each of the parameters may also be empty, in which case that parameter is always considered to match. Thus, the full range of possibilities is:

As the name implies, scans are expected and allowed to be time-consuming, full-table scan operations. An implementation is of course free to construct side-indices as needed to improve performance, but this isn’t required.

A sharding is a special case of a scan that is intended to support bulk manipulation of a large, complete graph store, e.g., via tools like Hadoop or MapReduce. The two general forms of sharding query are:

These operations nominally partition the graph store into n > 0 shards by fingerprint of source | kind, and return to the caller (the count of) all the entries in shard index, where 0 ≤ index < n. Basically this operation allows a graph store to be adapted to a MapReduce or Hadoop Reader for sharded processing. A caller can invoke Count(0, 1) to obtain the total number of entries in the graph store.

Rationale: Sharding by source and kind ensures a processing tool can assemble complete nodes and edges from the entries sent to a given shard. Since a forward graph is expected to have low average out degree, we have omitted more general features like configurable hash functions.

The simplest reasonable graph store implementation is a single file of entries in standard order, such as a LevelDB file or a sequence of CSV or JSON records with a line index.

Modifications in this representation are inefficient—they are best handled by keeping a log of small append-only tables, one for each file being analyzed, say, and periodically merging the results together. Despite being unsuited for writing, However, a single-file format is a good and portable transport method for small graph stores, and has the advantage that it is easy to work with.

This format is a reasonable choice for read-only artifacts emitted from a standalone command-line analyzer, where the end results are expected to be combined with other stores to form a larger index for serving. The advantage of single-file formats is that they are easy to ship around to other tools and can be converted to more complex formats without too much overhead.

A slightly more flexible graph store implementation can be built on top of a SQLite or MySQL database. A trivial implementation can be built using a single table of entries, which is more or less a transliteration of the single-file implementation into SQL. A more sophisticated approach (and more efficient for writing) is to split the entries into three tables — this example uses the syntax supported by SQLite:

Implementing most of the service methods is fairly straightforward in this representation: Writes can be wrapped in transactions to ensure they are atomic, while reads and scans can be fairly easily turned into simple SQL queries. The map operations are harder in this format, however.