A transparent cache for datastore, backed by memcache.

filter/dscache/doc.go

Index: filter/dscache/doc.go
diff --git a/filter/dscache/doc.go b/filter/dscache/doc.go
new file mode 100644
index 0000000000000000000000000000000000000000..51e00c8c8e16e4346168d1576e5af5d5e682a9d7
--- /dev/null
+++ b/filter/dscache/doc.go
@@ -0,0 +1,160 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Package dscache provides a transparent cache for RawDatastore which is
+// backed by Memcache.
+//
+// Inspiration
+//
+// Although this is not a port of any particular implementation, it takes
+// inspiration from these fine libraries:
+//   - https://cloud.google.com/appengine/docs/python/ndb/
+//   - https://github.com/qedus/nds
+//   - https://github.com/mjibson/goon
+//
+// Algorithm
+//
+// Memcache contains cache entries for single datastore entities. The memcache
+// key looks like
+//
+//   "gae:" | vers | ":" | shard | ":" | Base64_std_nopad(SHA1(datastore.Key))
+//
+// Where:
+//   - vers is an ascii-hex-encoded number (currently 1).
+//   - shard is a zero-based ascii-hex-encoded number (depends on shardsForKey).
+//   - SHA1 has been chosen as unlikely (p == 1e-18) to collide, given dedicated
+//     memcache sizes of up to 170 Exabytes (assuming an average entry size of
+//     100KB including the memcache key). This is clearly overkill, but MD5
+//     could start showing collisions at this probability in as small as a 26GB
+//     cache (and also MD5 sucks).
+//
+// The memcache value is a compression byte, indicating the scheme (See
+// CompressionType), followed by the encoded (and possibly compressed) value.
+// Encoding is done with datastore.PropertyMap.Write(). The memcache value
+// may also be the empty byte sequence, indicating that this entity is deleted.
+//
+// The memcache entry may also have a 'flags' value set to one of the following:
+//   - 0 "entity" (cached value)
+//   - 1 "lock"   (someone is mutating this entry)
+//
+// Algorithm - Put and Delete
+//
+// On a Put (or Delete), an empty value is unconditionally written to
+// memcache with a LockTimeSeconds expiration (default 31 seconds), and
+// a memcache flag value of 0x1 (indicating that it's a put-locked key). The
+// random value is to preclude Get operations from believing that they possess
+// the lock.
+//
+// NOTE: If this memcache Set fails, it's a HARD ERROR. See DANGER ZONE.
+//
+// The datastore operation will then occur. Assuming success, Put will then
+// unconditionally delete all of the memcache locks. At some point later, a
+// Get will write its own lock, get the value from datastore, and compare and
+// swap to populate the value (detailed below).
+//
+// Algorithm - Get
+//
+// On a Get, "Add" a lock for it (which only does something if there's no entry
+// in memcache yet) with a nonce value. We immediately Get the memcache entries
+// back (for CAS purposes later).
+//
+// If it doesn't exist (unlikely since we just Add'd it) or if its flag is
+// "lock" and the Value != the nonce we put there, go hit the datastore without
+// trying to update memcache.
+//
+// If its flag is "entity", decode the object and return it. If the Value is
+// the empty byte sequence, return ErrNoSuchEntity.
+//
+// If its flag is "lock" and the Value equals the nonce, go get it from the
+// datastore. If that's successful, then encode the value to bytes, and CAS
+// the object to memcache. The CAS will succeed if nothing else touched the
+// memcache in the meantime (like a Put, a memcache expiration/eviction, etc.).
+//
+// Algorithm - Transactions
+//
+// In a transaction, all Put memcache operations are held until the very end of
+// the transaction. Right before the transaction is committed, all accumulated
+// Put memcache items are unconditionally set into memcache.
+//
+// NOTE: If this memcache Set fails, it's a HARD ERROR. See DANGER ZONE.
+//
+// If the transaction is sucessfully committed (err == nil), then all the locks
+// will be deleted.
+//
+// The assumption here is that get operations apply all outstanding
+// transactions before they return data (https://cloud.google.com/appengine/docs/go/datastore/#Go_Datastore_writes_and_data_visibility),
+// and so it is safe to purge all the locks if the transaction is known-good.
+//
+// If the transaction succeeds, but RunInTransaction returns an error (which can
+// happen), or if the transaction fails, then the lock entries time out
+// naturally. This will mean 31-ish seconds of direct datastore access, but it's
+// the more-correct thing to do.
+//
+// Gets and Queries in a transaction pass right through without reading or
+// writing memcache.
+//
+// Cache control
+//
+// An entity may expose the following metadata (see
+// datastore.PropertyLoadSaver.GetMeta) to control the behavior of its cache.
+//
+//   - `gae:"$dscache.enable,<true|false>"` - whether or not this entity should
+//      be cached at all. If ommitted, dscache defaults to true.
+//   - `gae:"$dscache.expiration,#seconds"` - the number of seconds of
+//     persistance to use when this item is cached. 0 is infinite. If omitted,
+//     defaults to 0.
+//
+// In addition, the application may set a function shardsForKey(key) which
+// returns the number of shards to use for a given datastore key. This function
+// is set with the invocation of FilterRDS.
+//
+// Shards have the effect that all write (Put/Delete) operations clear all
+// memcache entries for the given datastore entry, and all reads read (and
+// possibly populate) one of the memcache entries. So if an entity has 4 shards,
+// a datastore Get for it will pull from one of the 4 possible memcache keys
+// at random. This is good for heavily-read, but infrequently updated, entities.

[Vadim Sh., 2015/08/07 17:30:47]

nit: mention that it's needed to avoid having hot keys in memcached, e.g. the
contention happens in memcached guts, not in our code. You sort of mention this
below, but it would be clearer here.

[iannucci, 2015/08/07 19:41:00]

Done.

+//
+// Caveats
+//
+// A couple things to note that may differ from other appengine datastore
+// caching libraries (like goon, nds, or ndb).
+//
+//   - It does NOT provide in-memory ("per-request") caching.
+//   - It's INtolerant of some memcache failures, but in exchange will not return
+//     inconsistent results. See DANGER ZONE for details.
+//   - Queries do not interact with the cache at all.
+//   - Negative lookups (e.g. ErrNoSuchEntity) are cached.
+//   - Allows sharding hot memcache entries as recommended by
+//     https://cloud.google.com/appengine/articles/best-practices-for-app-engine-memcache#distribute-load .
+//
+// DANGER ZONE
+//
+// As mentioned in the Put/Delete/Transactions sections above, if the memcache
+// Set fails, that's a HARD ERROR. The reason for this is that otherwise in the
+// event of transient memcache failures, the memcache may be permanently left in
+// an inconsistent state, since there will be nothing to actually ensure that
+// the bad value is flushed from memcache. As long as the Put is allowed to
+// write the lock, then all will be (eventually) well, and so all other memcache
+// operations are best effort.
+//
+// So, if memcache is DOWN, you will effectively see tons of errors in the logs,
+// and all cached datastore access will be essentially degraded to a slow
+// read-only state. At this point, you have essentially 3 mitigration
+// strategies:
+//   - wait for memcache to come back up.
+//   - dynamically disable all memcache access by writing the datastore entry:
+//       /dscache,1 = {"Enable": false}
+//     in the default namespace. This can be done by invoking the
+//     SetDynamicGlobalEnable method. This can take up to 5 minutes to take
+//     effect. If you have very long-running backend requests, you may need to
+//     cycle them to have it take effect. This dynamic bit is read essentially
+//     once per http request (when FilteRDS is called on the context).
+//   - push a new version of the application disabling the cache filter
+//     by setting InstanceEnabledStatic to false in an init() function.
+//
+// On every dscache.FilterRDS invocation, it takes the opportunity to fetch this
+// datastore value, if it hasn't been fetched in the last
+// GlobalEnabledCheckInterval time (5 minutes). This equates to essentially once
+// per http request, per 5 minutes, per instance.
+package dscache