# -*- org -*-

client-side cache object
* pinSet - the cumulative set of pins at which this transaction is
  valid
* rootInterval - the transaction window, or root of the interval
  hierarchy
* *interval - pointer to the innermost interval
* activePin - none or the pin of the underlying transaction
* desiredPin - none of the pin at which the next underlying
  transaction should start

per-cluster pinCushion object
* pinTable - table of pairs of pin numbers and pin timestamps
* referencedPins - priority queue of the oldest pin used by each
  outstanding transaction


cache.beginRO(freshness)
* pins = pinCushion.request(freshness)
** I believe this can be done asynchronously, which might help absorb
   this round trip.  OTOH, maybe we'll just always need the result of
   this immediately anyways.
* if no pin returned
** this.pinSet = {*}
* else
** this.pinSet = pins + {*}
* this.activePin = none
* this.rootInterval = [0, inf)
* this.interval = &this.rootInterval

pinCushion.request(freshness)
* timestamp = now() - freshness
* pins = set of pins with timestamps greater than timestamp
* if no pins found
** add newest pin to this.referencedPins
** return no pins
* add oldest returned pin to this.referencedPins
* return pins

pinCushion.insertPin(timestamp, pin)
* add pin to this.pinTable

cache.commit()
* if this.activePin is not none
** (We could actually be lazier about this and possibly reuse the same
   underlying transaction in the next cache transaction.  However, if
   we do this, we have to leave things referenced in the pin cushion
   (though we could potentially move our reference) and we have to
   ensure our freshness requirement is still satisfied on the next
   begin.)
** commit underlying transaction
* pinCushion.releasePin()
** We don't have to wait on the response to this
* this.interval = null

pinCushion.releasePin()
* remove the calling host's pin from this.referencedPins
* for otherPin in this.pinTable
** if otherPin.pin < min(this.referencedPins) and
   otherPin.timestamp < now() - maxStaleness
*** remove otherPin from this.pinTable


cache.exec(stmt)
* if this.interval is null
** return execute stmt
* pin = policy.choosePin(this.pinSet)
* if pin != this.activePin
** Assert pin is in this.pinSet
** if this.activePin is not none
*** commit underlying transaction
** begin underlying transaction at pin (may be *)
** if pin is *
*** pin, timestamp = Pin the database transaction
*** this.pinSet = {pin}
*** Put pin, timestamp to the pin cushion
** this.activePin = pin
* result = execute stmt
** (The commit, begin, and query should be done in one round trip)
* localInterval = get validity interval from DB
* Assert localInterval overlaps with at least one pin in this.pinSet
* Assert localInterval overlaps with *this.interval
* this.pinSet = intersect(this.pinSet, localInterval)
* *this.interval = intersect(*this.interval, localInterval)
* return result

cache.wrapper(f, args...)
* key = (f, args...)
* if this.pinSet == {*}
** cacheResult = none
* else
** node = lookupNode(key)
** cacheResult = node.lookup(boundsWithoutStar(this.pinSet), key)
*** How do we decide which possible result in the interval to return?
*** Alternatively, if pinSet contains *, we could pass an unbounded
    interval.  If we did this, the cache would have to be able to
    return at least one pin number along with the result, in case the
    returned interval did not contain any pins in pinSet.  Each
    insertion into the cache would have to include at least one pin
    number in the inserted interval.
* if cacheResult is none
** (Note that we start a transaction lazily in cache.exec.  This is
   particularly useful if our pin set shrinks by calls to other
   cacheable functions before we actually make a query from this one.)
** (Push our frame)
** localInterval = [0, inf)
** parentInterval = this.interval
** this.interval = &localInterval
** result = f(args...)
** (Pop our frame)
** this.interval = parentInterval
** node.put(localInterval, key, result)
*** We could optimize network traffic by keeping a stack of keys for
    each connection in the cache node itself so we don't have to
    retransmit it.
* else
** result, localInterval = cacheResult
* Assert localInterval overlaps with at least one pin in this.pinSet
* Assert localInterval overlaps with *this.interval
* this.pinSet = intersect(this.pinSet, localInterval)
** (Only necessary if it was a cache hit?)
* *this.interval = intersect(*this.interval, localInterval)
* return result


node.lookup(interval, key)
* Use policy to determine which value to return, if any


node.put(interval, key, value)


Interval properties
* The pin that you choose must be in the intersection of all enclosing
  intervals
** No, wait, we have to prevent one side of the tree from going down
   one side of the interval while the other goes down the other side
   of the interval.  The pin must be chosen from the intersection of
   _all_ intervals leading up to this point in the cache transaction.
* The interval of a cache transaction or cachable function is the
  intersection of the intervals of all queries performed by that
  transaction or cachable function and all of its children