Basis Token Consistency (BTC)

This page is a work-in-progress.

Basis Token Consistency (BTC) is a simple HTTP extension. BTC uses a clock-vector model to annotate all consistency-related HTTP responses such that any participating cache can identify when contents it holds are rendered obsolete by a newly-observed response.

How it Works

HTTP responses generated by BTC-implementing servers include the new Cache-Consistent header. An example of this header produced by the server www.cs.bu.edu might look something like this:

Cache-Consistent: studentdb;4e9, db2row@bu.edu;7a, form01@cs.bu.edu;2

The intuitive meaning of this header is "This response was produced using data from three data sources with the opaque identifiers `studentdb@www.cs.bu.edu', `db2row@bu.edu', and `form01@cs.bu.edu'; the current revision numbers of these data sources are (in hexadecimal) 4e9, 7a, and 2, respectively."

Formally, the Cache-Consistent header is specified with the following ABNF:

CacheConsistent = ``Cache-Consistent'' ``:'' #cctokengeneration

cctokengeneration = cctoken ``;'' ccgeneration [ ccdoesnot ] [ ccwillnot ]

cctoken = cctokenid [ cctokenscope ]

cctokenscope = ``@'' host

cctokenid = token

ccgeneration = 1*HEX

ccdoesnot = ``-'' ccmargin

ccwillnot = ``+'' ccmargin

ccmargin = 1*HEX

The cctokenscope value allows a token to be explicitly shared among all hosts of a given DNS domain; any server responding to a Host string of which a cctokenscope is a suffix is allows to provide tokens using that cctokenscope value. The implied cctokenscope value if none is specified is the Host string the server is responding to.

BTC-implementing caches maintain an index of their contents on cctoken values, along with a "watermark" value for each cctoken representing the highest ccgeneration seen so far for that cctoken. When a response arrives at the cache, the cache examines each cctokengeneration attached to that response; if the ccgeneration number is greater than the cache's current watermark value, it invalidates all of its currently cached responses which correspond to that cctoken; if the ccgeneration number is less than the current watermark, the cache recognizes the new response as stale/inconsistent (probably produced by an inconsistent upstream cache) and can repeat the request using an end-to-end reload; if the ccgeneration matches, then no action is taken. (These rules are relaxed by the margin consistency extension.)

Why it Works

Consider the world as having an infinitely long logical clock vector (the set of all possible cctoken values), each response annotates itself by marking a salient subset of the clock vector and the logical clock values used to produce it. Assuming the server is consistent and produces non-decreasing logical clock values, this is sufficient to infer happens-before and happens-after causal relationships, which is sufficient to identify deviation from a non-decreasing view of the server's state (that is, a view consistent response stream).

More intuitively speaking, the consistency-relationship of any set of documents is represented by the set of cctokens they share. Two unrelated documents will have no shared tokens, and thus changes in one will have no impact upon whether the other should be considered stale or not (i.e., neither will ever contradict the other in terms of any ordering of events or data); Similarly, once either of two documents which do share a data source has been seen reflecting a new revision t+1 of that data source, all documents which reflect the previous state t of that data source would, if viewed, cause the user to perceive a server state older than what they had previously seen (state t+1).

Features

  • Strong Point-to-Point Consistency
  • Invalidations are Automatically Aggregated
  • Aggregation is Independent of HTTP Namespaces
  • Invalidation is Driven by the Application
  • Lazy Delivery
  • Data Pertains to Entities it Annotates
  • No Per-Client State at Server or Cache

Extensions

  • BTC-based Coherence
  • Strong End-to-End Consistency
  • Minimal View Consistency
  • Relaxing Consistency Demands (δ Consistency)
  • Nesting Consistency Issues

Specification

BTC is roughly specified in the GI 2002 paper and the WC3 paper; the Technical Report is also useful, but contains one minor error. Basic BTC extensions are discussed in the WC3 paper. A formal internet-draft-style specification is forthcoming.

Publications