A transparent cache for datastore, backed by memcache.

filter/dscache/support.go

Index: filter/dscache/support.go
diff --git a/filter/dscache/support.go b/filter/dscache/support.go
new file mode 100644
index 0000000000000000000000000000000000000000..027e73699517b2d3b634b3960ed1358d4e97b898
--- /dev/null
+++ b/filter/dscache/support.go
@@ -0,0 +1,150 @@
+// 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
+
+import (
+	"fmt"
+	"math/rand"
+	"time"
+
+	ds "github.com/luci/gae/service/datastore"
+	"github.com/luci/gae/service/memcache"
+	"github.com/luci/luci-go/common/logging"
+)
+
+type supportContext struct {
+	aid string
+	ns  string
+
+	log          logging.Logger
+	mc           memcache.Interface
+	mr           *rand.Rand
+	shardsForKey func(ds.Key) int
+}
+
+func (s *supportContext) numShards(k ds.Key) int {
+	ret := DefaultShards
+	if s.shardsForKey != nil {
+		ret = s.shardsForKey(k)
+	}
+	if ret < 1 {
+		return 0 // disable caching entirely
+	}
+	if ret > MaxShards {
+		ret = MaxShards
+	}
+	return ret
+}
+
+func (s *supportContext) mkRandKeys(keys []ds.Key, metas ds.MultiMetaGetter) []string {
+	ret := []string(nil)
+	for i, key := range keys {
+		if !metas.GetMetaDefault(i, CacheEnableMeta, true).(bool) {
+			continue
+		}
+		shards := s.numShards(key)
+		if shards == 0 {
+			continue
+		}
+		if ret == nil {
+			ret = make([]string, len(keys))
+		}
+		ret[i] = MakeMemcacheKey(s.mr.Intn(shards), key)

[Vadim Sh., 2015/08/06 01:23:34]

so shards reduce contention on reads by making writes more expensive ('put' must
invalidate all shards)?

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

Right

+	}
+	if len(ret) == 0 {

[dnj, 2015/08/05 18:32:18]

Is this necessary? Either it is allocated and gets populated, or it is still nil
from not being populated. If len(keys) == 0, the "for" will not be entered, so
no grow.

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

o rite

+		ret = nil
+	}
+	return ret
+}
+
+func (s *supportContext) mkAllKeys(keys []ds.Key) []string {
+	size := 0
+	nums := make([]int, len(keys))
+	for i, k := range keys {
+		shards := s.numShards(k)
+		nums[i] = shards
+		size += shards
+	}
+	if size == 0 {
+		return nil
+	}
+	ret := make([]string, 0, size)
+	for i, key := range keys {
+		keySuffix := HashKey(key)
+		for shard := 0; shard < nums[i]; shard++ {
+			ret = append(ret, fmt.Sprintf(KeyFormat, shard, keySuffix))
+		}
+	}
+	return ret
+}
+
+// crappyNonce creates a really crappy nonce using math/rand. This is generally

[Vadim Sh., 2015/08/06 01:23:34]

lol

+// unacceptable for cryptographic purposes, but since mathrand is the only
+// mocked randomness source, we use that.

[dnj, 2015/08/05 18:32:18]

Worth mentioning that we're using it for sharding, not crypto, and it should be
just fine for that purpose. IMO remove the TODO.

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

ya, did

+//
+// Do not use this function for anything other than mkRandLockItems or your hair
+// will fall out. You've been warned.
+//
+// TODO(riannucci): make this use crypto/rand instead

[Vadim Sh., 2015/08/06 01:23:34]

do you see any exploitation possibilities? Not all random must be secure random.
math/rand is good enough IMHO.

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

Yeah it's actually fine... just felt dirty extracting []byte from math/rand.
Update comment.

+func (s *supportContext) crappyNonce() []byte {
+	ret := make([]byte, NonceUint32s*4)
+	for w := uint(0); w < NonceUint32s; w++ {
+		word := s.mr.Uint32()
+		for i := uint(0); i < 4; i++ {
+			ret[(w*4)+i] = byte(word >> (8 * i))
+		}
+	}
+	return ret
+}
+
+func (s *supportContext) mutation(keys []ds.Key, f func() error) error {
+	lockItems, lockKeys := s.mkAllLockItems(keys)
+	if lockItems == nil {
+		return f()
+	}
+	if err := s.mc.SetMulti(lockItems); err != nil {
+		s.log.Errorf("dscache: mc.SetMulti: %s", err)

[dnj, 2015/08/05 18:32:18]

This could be a lot of logging if memcache is not working. Since it's allowed to
fail, IMO make this "Debugf".

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

changed to a hard failz

+	}
+	err := f()

[dnj, 2015/08/05 18:32:18]

if err := f(); err == nil {
...
}

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

Nah, I return it in the else case.

+	if err == nil {
+		if err := s.mc.DeleteMulti(lockKeys); err != nil {
+			s.log.Errorf("dscache: mc.DeleteMulti: %s", err)

[dnj, 2015/08/05 18:32:18]

(same)

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

a warning now

+		}
+	}
+	return err
+}
+
+func (s *supportContext) mkRandLockItems(keys []ds.Key, metas ds.MultiMetaGetter) ([]memcache.Item, []byte) {
+	mcKeys := s.mkRandKeys(keys, metas)
+	if len(mcKeys) == 0 {
+		return nil, nil
+	}
+	nonce := s.crappyNonce()
+	ret := make([]memcache.Item, len(mcKeys))
+	for i, k := range mcKeys {
+		if k == "" {

[Vadim Sh., 2015/08/06 01:23:34]

is it possible?

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

Yeah. This is done if mkRandKeys detects that some of the keys have caching
disabled. I have tests that cover this, FWIW.

+			continue
+		}
+		ret[i] = (s.mc.NewItem(k).
+			SetFlags(uint32(ItemHasLock)).

[Vadim Sh., 2015/08/06 01:23:34]

ah, I didn't know about flags. Cool.

+			SetExpiration(time.Second * time.Duration(LockTimeSeconds)).

[Vadim Sh., 2015/08/06 01:23:34]

why not define LockTimeSeconds to be of type time.Duration?

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

Because SetExpiration truncates anything shorter than seconds. Didn't want to
give false hope if someone set it to a millisecond (and then memcache treats it
as infinite :D).

+			SetValue(nonce))
+	}
+	return ret, nonce
+}
+
+func (s *supportContext) mkAllLockItems(keys []ds.Key) ([]memcache.Item, []string) {
+	mcKeys := s.mkAllKeys(keys)
+	if mcKeys == nil {
+		return nil, nil
+	}
+	ret := make([]memcache.Item, len(mcKeys))
+	for i := range ret {
+		ret[i] = (s.mc.NewItem(mcKeys[i]).
+			SetFlags(uint32(ItemHasLock)).
+			SetExpiration(time.Second * time.Duration(LockTimeSeconds)))
+	}
+	return ret, mcKeys
+}