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..aafe22156ed6fe67fa3fa24298997f2ed7a8b291
--- /dev/null
+++ b/filter/dscache/doc.go
@@ -0,0 +1,110 @@
+// 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 dscache.shards).
+//   - SHA1 has been chosen as unlikely (p == 1e-18) to collide, given dedicated

[Vadim Sh., 2015/08/05 17:09:31]

just curious: why not use the key directly? Too long?

[iannucci, 2015/08/06 01:54:01]

Yeah, there's a limit of 250 bytes for the memcache key (and it also may not
contain null bytes, so I can't just gzip some encoding of it). Additionally,
long keys eat into the available space for a memcache row (overhead + key +
value). I figured this was a pretty good compromise.

+//     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).

[Vadim Sh., 2015/08/05 17:09:31]

that's a good argument :D

+//
+// 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:

[Vadim Sh., 2015/08/05 17:09:31]

where 'flags' value is stored?

[iannucci, 2015/08/06 01:54:00]

It's 4 of the bytes in the 'overhead' of the memcache implementation. It's
SetFlags(uint32) on memcache.Item.

+//   - 0 "entity" (cached value)
+//   - 1 "lock"   (someone is mutating this entry)
+//
+// Algorithm - Put and Delete
+//
+// On a Put (or Delete), the memcache value written with a LockTimeSeconds

[Vadim Sh., 2015/08/05 17:09:31]

unconditionally written? Overriding any existing stuff?

[iannucci, 2015/08/06 01:54:00]

Yeah, it writes a lock (blank value + 30 second timeout) to exclude any Gets
from trying to populate the memcache entry while the put is doing it's thing.
Afterwards it's deleted. The 30s expiration is in the event of a crash.

+// expiration (default 31 seconds), and a memcache flag value of 0x1 (indicating
+// that it's a put-locked key).
+//
+// The datastore operation will then occur. Assuming success, Put will then
+// delete all of the memcache locks (Not using CompareAndSwap).

[Vadim Sh., 2015/08/05 17:09:31]

what are "memcache locks"?

[iannucci, 2015/08/06 01:54:00]

Hopefully clarified this section

+//
+// 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 it's flag is

[Vadim Sh., 2015/08/05 17:09:31]

typo: its (not it's)

[iannucci, 2015/08/06 01:54:01]

Done.

+// "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

[Vadim Sh., 2015/08/05 17:09:31]

What about Gets in transaction?

DS transactions use snapshot isolation (or whatever it is called).

[iannucci, 2015/08/06 01:54:01]

Gets pass through without any memcache interaction (reads or writes)

+//
+// 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 keys are locked. 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.
+//
+// Cache control
+//
+// An entity may expose the following metadata (see
+// datastore.PropertyLoadSaver.GetMeta) to control the behavior of its cache.
+//
+//   - "dscache.enable,<true|false>" - whether or not this entity should be

[Vadim Sh., 2015/08/05 17:09:31]

isn't it $dscache.enable?

[iannucci, 2015/08/06 01:54:01]

clarified

+//     cached at all. If ommitted, dscache defaults to true.
+//   - "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.

[Vadim Sh., 2015/08/05 17:09:31]

what does it mean to use sharding for a single datastore key?

[iannucci, 2015/08/06 01:54:00]

clarified

+//
+// 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.

[Vadim Sh., 2015/08/05 17:09:31]

good :)

+//   - It's tolerant of memcache failures (but will give potentially
+//     inconsistent results if memcache is non-operational). Using a transaction
+//     bypasses the cache logic, which will present a consistent view of the data.
+//   - 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 .
+package dscache