Enrich Routing Table API

[lthibault]

On several occasions, we have found ourselves wishing to query a host's routing table for peer metadata (as opposed to simply querying for the list of peer IDs). At present, this is an O(n) operation that requires us to stream the entire routing table to the client, for subsequent filtering. The present issue proposes to extend the RoutingTable API to support basic query and filter operations that are implemented on the server-side.

I have labeled this issue as a question to encourage feedback.

Objectives

The API should embody the following properties:

1. Simplicity. We should deliberately refrain from supporting complex queries, so as to keep the wire payloads simple and predictable. The smallest API providing (1) indexed lookups (2) filtering (3) result ordering (4) limits. We should not hesitate to limit the expressiveness of filtering semantics in pursuit of simplicity at both the design and implementation level.
2. Abstraction over Storage. The query API should minimize assumptions about the storage backend, which I expect will evolve substantially between now and our first stable release. It should be straightforward to develop reasonably-performant implementations using popular in-memory, SQL, filesystem or NoSQL backends.
3. Single-Writer, Multiple-Reader Semantics. A node's routing table is updated only by the node itself, on the basis of heartbeats received from peers, and so the query API should be read-only. Moreover, we should assume that reads are at least 10x more frequent than writes. As cluster sizes grow, we should not hesitate to batch writes of incoming heartbeats together so that this assumption remains true. A consequence of this assumption is that implementations ought to support optimistic concurrency, which I informally define as "writers do not block readers".
4. Performant Encoding/Decoding of Queries. Converting queries to and from from their wire formats should require few CPU cycles and little memory. Wire formats should be densely packed and common queries should be further compressed using predetermined lookup tables.

The existing design principles of eventual-consistency and high-availability remain in place.

API Design

MemDB: an Ideal Starting Point?

MemDB offers a good starting point for the design of a query API that satisfies the above requirements. To wit:

• Simplicity is trivially achieved insofar as the MemDB API supports exactly the lookup/filter/order/limit semantics required, and presents no barriers to restricting the filtering API.
• Abstraction over storage is already present in both CASM and Wetware through the RoutingTable interfaces. These need only be updated to reflect the enriched API.
• Single-writer, multiple-reader semantics are provided by MemDB itself. A mutex enforces a single concurrent write-transaction, which operates on an immutable snapshot of table state. Changes are applied atomically using CAS. Read-transactions similarly operate on immutable snapshots.

Modeling the query API after MemDB would limit the scope of de novo development work to:

1. Defining the new RoutingTable interfaces, which can be modeled upon the MemDB API.
2. Implementing the performant encoding and decoding of queries, which should be straightforward with capnp.

Datastore: an Alternative Approach

An alternative approach is to model the query API on IPFS' Go Datastore. Instead of defining our own query API, we might consider building the routing table as a specific implementation of datastore.Read. Analyzing this option in the context of our design goals, as above, we find:

1. Simplicity is compromised by the expressiveness of its query API. Operations like ReturnSizes and Offset are irrelevant to routing table operations, and others like KeysOnly are implementation-oriented interfaces that do not explicitly map onto domain logic.
2. As noted in the query.Query docstring, the storage backend must be carefully selected to correspond to the kinds of queries it will service, which breaks abstraction over storage.
3. Certain storage backends exhibit single-writer, multiple-reader semantics, while others do not. Most implementations use pessimistic lock-based concurrency. Satisfying these constraints requires us to either (a) employ a full-fledged SQL database, (b) employ SQLite, which in turn introduces CGO and its drawbacks; or (c) implement a wrapper around MemDB to fit the datastore.Read interface.
4. We must still implement the performant encoding and decoding of queries. Note that the Order and Filter types remain to be defunctionalized.

More generally, the goal of the RoutingTable API is to allow CASM/Wetware developers to flexibly evolve the routing-table implementation, not to provide a general-purpose database. Indeed, we are developing a specialized system with stronger assumptions that provide opportunities to simplify implementation and improve runtime performance. As such, it is unlikely that users should ever benefit from replacing the storage backend, other than perhaps to toggle between in-memory and persistent storage, which is best provided as a boolean configuration option. We should expose a specialized interface for querying routing information, not a general interface for querying databases.

Package-Level API Design

Regardless of the query API itself, an important consideration is whether to extend CASM's pulse.RoutingTable interface directly, or whether to define the extended interface in Wetware and employ type-assertion. I am currently leaning towards the former on the basis that:

1. Query semantics are likely to be required in a wide range of distributed applications, consistent with CASM's mission to be a "universal middleware for distributed computing".
2. Complexity in Wetware is growing at a rate that far exceeds that of CASM, so it seems appropriate to push some of this complexity down the stack. It feels especially appropriate in the present case since routing table queries are incidental, rather than central, to Wetware's core mission
3. A general-purpose STM system, with a small API and minimal guarantees, seems like a valuable primitive for building distributed systems, and would make a valuable addition to CASM's feature-set.

The main factor in this decision is that directly extending the pulse.RoutingTable API effectively forces us to migrate the stm package from Wetware to CASM. This having been said, I think it is worth the trouble because:

1. The migration is simple enough. The pkg/stm package is quite self-contained, having only an internal dependency on internal/bounded (which can be trivially duplicated to -- or even exported from -- CASM).
2. Package pkg/stm is already designed with third-party consumption in mind, in particular where security is concerned. It exports a capability-oriented API with strong isolation at both the table level and the "database" (collection of tables) level. Migrating the package to CASM does not increase the attack surface.

Implementation

I will now share some thoughts about how we might approach the implementation of a MemDB-based routing-table and its API, beginning with the latter.

A guiding principle in the following draft is to both (1) closely follow the structure of the pkg/stm API, in order to preserve mechanical sympathy; and (2) to abstract, where appropriate, the details of capability-based security and MemDB. An instructive example is to be found in the suppression of the read-vs-write distinction from the API. The RoutingTable defines only read-operations, and is itself an object capability conferring the ability to query the routing table. Thus, we expose only one method, Query, which returns a RecordSet that wraps a stm.Txn and its corresponding stm.TableRef.

The RecordSet provides the classic Lookup and Iter methods, which are applied to the subset of records it describes. Simple ordering is provided by the Reverse method, which returns a reverse-iterator, along with the First and Last methods, which directly return their corresponding routing records. Additional methods are exported that have the effect of restricting the set of records indexed by Lookup and Iter to a subset of the current query. The initial query indexes the entire routing table.

type RoutingTable interface {
    Query(context.Context) RecordSet
}

type Indexer interface {
	Index() uint16   // enum value to be set in capnp
	String() string  // index name consumed by memdb.Txn
}

type RecordSet interface {
	Iter() routing.Iterator
	Reverse() routing.Iterator

	// Lookup returns the record matching Arg exactly.  It returns ErrNotFound if
	// such a record does not exist.
	Lookup(Indexer, Arg) (routing.Record, error)

	// First and Last correspondingly return the first and last record matching the
	// constraints specified by the supplied arguments.
	First(Indexer, ...Arg) (routing.Record, error)
	Last(Indexer, ...Arg) (routing.Record, error)

	// Filter returns the subset of the current RecordSet specified by the supplied
	// arguments.
	Filter(Indexer, ...Arg) RecordSet
}