cipd: Implement local cache for ResolveVersion(...) call with tags.

go/src/infra/tools/cipd/internal/tagcache.go

Index: go/src/infra/tools/cipd/internal/tagcache.go
diff --git a/go/src/infra/tools/cipd/internal/tagcache.go b/go/src/infra/tools/cipd/internal/tagcache.go
new file mode 100644
index 0000000000000000000000000000000000000000..b588d0a78d3c321f43fae8293f618d79da100c83
--- /dev/null
+++ b/go/src/infra/tools/cipd/internal/tagcache.go
@@ -0,0 +1,174 @@
+// 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 internal
+
+import (
+	"io/ioutil"
+	"os"
+	"sync"
+
+	"infra/tools/cipd/common"
+	"infra/tools/cipd/internal/messages"
+)
+
+// MaxTagCacheSize is how many entries to keep in TagCache database.
+const MaxTagCacheSize = 300
+
+// TagCache provides a thread safe mapping (package name, tag) -> instance ID.
+// This mapping is safe to cache because tags are not detachable: once a tag is
+// successfully resolved to an instance ID it is guaranteed to resolve to same
+// instance ID later or not resolve at all (e.g. if one tag is attached to
+// multiple instances, in which case the tag is misused anyway). In any case,

[tandrii(chromium), 2015/09/30 18:11:15]

Maybe warn the misuse info to the set-tag and register commands?

[nodir, 2015/09/30 19:08:23]

We should prevent this from happening on the server

[Vadim Sh., 2015/09/30 22:50:59]

Applying same tag to multiple packages is not forbidden operation. It's
perfectly reasonable in some workflows. Such tags just should not be used to
name versions. (They still can be used as, well.. tags). For example imagine you
have some release pipeline and you want to mark packages that passed (or failed)
canary stage. You can use 'canary_passed:true' or 'canary_passed:false' tags on
them. Then all packages that passed canary can be fetched via search for
'canary_passed:true' tag.

I'm considering making stronger distinction between two kinds of tags (see
https://chromium.googlesource.com/infra/infra/+/master/appengine/chrome_infra...),
but it's not of a very high priority and I prefer to add features only if
absolutely necessary.

[tandrii_google, 2015/09/30 23:11:00]

FTR, that's exactly what I intended to do with CQ package, actually.

[nodir, 2015/10/01 23:24:04]

Looked up the server code: if there is >1 instance with a tag, server will
respond with AMBIGUOUS_VERSION status [1]. Client handles that. Someone may
abuse non-unique tags for versions, but that won't be subtle: they will quickly
discover that nothing is updated (as long as there is monitoring for cipd
deployment (?))

[1]:
https://chromium.googlesource.com/infra/infra/+/master/appengine/chrome_infra...

+// returning  a cached instance ID does make sense. The primary purpose of this
+// cache is to avoid round trips to the service to increase reliability of
+// 'cipd ensure' calls that use only tags to specify versions. It happens to be
+// the most common case of 'cipd ensure' usage by far.
+type TagCache interface {

[tandrii(chromium), 2015/09/30 18:11:15]

frankly, i don't see a reason to have interface => this is internal package,
with no other implementation, so just a struct should do.
I agree with nodir@ that we do indeed overuse this pattern.

[nodir, 2015/09/30 19:08:24]

I agree (with tandrii agreeing with me)

[Vadim Sh., 2015/09/30 22:50:59]

Converted to struct, whatever. I like interfaces because docs are in single
place, and not scattered around the file.

[tandrii_google, 2015/09/30 23:11:00]

True, but godoc does look worse. So, it's a trade-off.

+	// Load loads the state from given buffer.
+	Load([]byte) error
+
+	// Save dumps state to the byte buffer. Also resets 'Dirty' flag.
+	Save() ([]byte, error)
+
+	// Dirty return true if Save() needs to be called to persist changes.
+	Dirty() bool
+
+	// ResolveTag returns cached tag or empty Pin{} if such tag is not in cache.
+	ResolveTag(packageName, tag string) common.Pin
+
+	// AddTag records that (pin.PackageName, tag) maps to pin.InstanceID.
+	AddTag(pin common.Pin, tag string)
+}
+
+// NewTagCache returns implementation of TagCache.
+func NewTagCache() TagCache {
+	return &tagCache{}
+}
+
+// LoadTagCacheFromFile reads tag cache state from given file path if it exists.
+// Returns empty cache if file doesn't exist.
+func LoadTagCacheFromFile(path string) (TagCache, error) {
+	buf, err := ioutil.ReadFile(path)
+	if os.IsNotExist(err) {
+		return NewTagCache(), nil
+	}
+	if err != nil {
+		return nil, err
+	}
+	cache := NewTagCache()
+	if err := cache.Load(buf); err != nil {
+		return nil, err
+	}
+	return cache, nil
+}
+
+type tagCache struct {
+	lock  sync.Mutex
+	cache messages.TagCache
+	dirty bool
+}
+
+func (c *tagCache) Load(buf []byte) error {
+	cache := messages.TagCache{}
+	if err := UnmarshalWithSHA1(buf, &cache); err != nil {

[nodir, 2015/09/30 19:08:23]

Why do you have to do it? A message probably won't be decoded if it is corrupted

[Vadim Sh., 2015/09/30 22:50:59]

This code will be used on thousands of bots. Some of them under stress, with bad
disks, etc. I don't like to rely on "probably" and then debug random shit.

[nodir, 2015/10/01 23:24:03]

the word "probably" meant that I don't know for sure and suggested you to check
that (apparently, not a good idea). I am not opposed to sha1 check

[Vadim Sh., 2015/10/01 23:34:07]

I'm sorry if my reply sounded harsh...

Protobufs do not have strict validation, it's very easy to "correctly" decode
corrupted proto message.

+		return err
+	}
+
+	// Validate entries. Make sure to keep only MaxTagCacheSize number of them.
+	goodOnes := make([]*messages.TagCache_Entry, 0, MaxTagCacheSize)
+	for i := 0; i < len(cache.Entries) && len(goodOnes) < MaxTagCacheSize; i++ {
+		e := cache.Entries[i]
+		valid := e != nil &&
+			common.ValidatePackageName(e.GetPackage()) == nil &&
+			common.ValidateInstanceTag(e.GetTag()) == nil &&
+			common.ValidateInstanceID(e.GetInstanceId()) == nil
+		if valid {
+			goodOnes = append(goodOnes, e)
+		}
+	}
+
+	c.lock.Lock()
+	defer c.lock.Unlock()
+	c.cache.Entries = goodOnes
+	c.dirty = false
+	return nil
+}
+
+func (c *tagCache) Save() ([]byte, error) {
+	// Remove all "holes" left from moving entries in AddTag.
+	c.lock.Lock()
+	compacted := make([]*messages.TagCache_Entry, 0, len(c.cache.Entries))
+	for _, e := range c.cache.Entries {
+		if e != nil {
+			compacted = append(compacted, e)
+		}
+	}

[tandrii(chromium), 2015/09/30 18:11:15]

didn't you mean to add:
  c.cache.Entries = compacted
?
And if so, then maybe pre-allocating len(c.cache.Entries) isn't the best
approach. Then again, it's ~300 items...

[Vadim Sh., 2015/09/30 22:50:59]

Yes, forgot.
It should be reasonably small. cipd.Client is short lived currently, it is use
for a small number of operations and the closed.

+	c.dirty = false

[nodir, 2015/09/30 19:08:23]

set it to false if MarshalWithSHA1 didn't error out

[Vadim Sh., 2015/09/30 22:50:59]

Done.

+	c.lock.Unlock()
+
+	// Keep at most MaxTagCacheSize entries. Truncate head of the slice, since
+	// it's  where old items are. All new hotness is at the tail, we need
+	// to keep it.

[tandrii(chromium), 2015/09/30 18:11:15]

but you don't move "old hot" items to the end, so tail isn't always "hot". not
critical, as just-remove-old-hot will soon become new-hot, so I guess it's OK. 
tl;dr I personally think LRU fits better this, but LRR (last R for resolved) is
also OK :)

[Vadim Sh., 2015/09/30 22:50:59]

I decided I don't want to write to disk after each cached ResolveVersion
response. That's why reads from cache do not change it (only AddTag does). It's
conscious decision ;)

[tandrii_google, 2015/09/30 23:11:00]

Acknowledged.

+	if len(compacted) > MaxTagCacheSize {
+		compacted = compacted[len(compacted)-MaxTagCacheSize:]
+	}
+	return MarshalWithSHA1(&messages.TagCache{Entries: compacted})
+}
+
+func (c *tagCache) Dirty() bool {
+	c.lock.Lock()
+	defer c.lock.Unlock()
+	return c.dirty
+}
+
+func (c *tagCache) ResolveTag(pkg, tag string) common.Pin {
+	c.lock.Lock()
+	defer c.lock.Unlock()
+	for _, e := range c.cache.Entries {

[nodir, 2015/09/30 19:08:23]

shouldn't you iterate from the tail? given freshest entries are there

[Vadim Sh., 2015/09/30 22:50:59]

Done. Whatever, it is <300 items.

[nodir, 2015/10/01 23:24:03]

I thought that was the point of putting fresh items in the end.

[Vadim Sh., 2015/10/01 23:34:07]

They are in the end because that way no operation needs to "shift" array when
inserting stuff. Though it is probably an overkill too, considering it's just
300 items...

+		if e != nil && e.GetPackage() == pkg && e.GetTag() == tag {
+			return common.Pin{
+				PackageName: pkg,
+				InstanceID:  e.GetInstanceId(),
+			}
+		}
+	}
+	return common.Pin{}
+}
+
+func (c *tagCache) AddTag(pin common.Pin, tag string) {
+	// Just skip invalid data. It should not be here anyway.
+	bad := common.ValidatePackageName(pin.PackageName) != nil ||
+		common.ValidateInstanceID(pin.InstanceID) != nil ||
+		common.ValidateInstanceTag(tag) != nil
+	if bad {

[tandrii(chromium), 2015/09/30 18:11:15]

since you have comment, why not avoid `bad` var entierly?

[nodir, 2015/09/30 19:08:23]

the if statement will probably become scary

[Vadim Sh., 2015/09/30 22:50:59]

Yes, 'if' becomes uglier.

+		return
+	}
+
+	c.lock.Lock()
+	defer c.lock.Unlock()
+
+	// Try to find an existing entry in the cache. It will be moved to bottom

[tandrii(chromium), 2015/09/30 18:11:15]

this is weird. As a safety check, OK. But current usage of this cache
essentially makes sure this never happens. This is because AddTag is only called
after ResolveTag() finds nothing.

[nodir, 2015/09/30 19:08:23]

it may happen because of a race condition. State may change between ResolveTag
and AddTag

[Vadim Sh., 2015/09/30 22:50:59]

TagCache just implements some interface, regardless of how this interface is
being used. I don't want to discover some hidden "wtf" few months later when
TagCache is used in some other way.

[tandrii_google, 2015/09/30 23:11:00]

I meant it more in connection with compaction not actually happening in Save().
Since that was a bug, this is irrelevant.

+	// (thus promoted as "most recent one"). We put a "hole" (nil) in previous
+	// position to avoid shifting array for no good reason. All "holes" are
+	// compacted in Save().

[tandrii(chromium), 2015/09/30 18:11:15]

Hm, holes are compacted in what gets actually written to resulting buffer, but
actual entries stay with holes.

[nodir, 2015/09/30 19:08:23]

+1

[Vadim Sh., 2015/09/30 22:50:59]

Done.

+	var existing *messages.TagCache_Entry
+	for i, e := range c.cache.Entries {
+		if e != nil && e.GetPackage() == pin.PackageName && e.GetTag() == tag {
+			existing = e
+			c.cache.Entries[i] = nil
+			break
+		}
+	}
+	if existing == nil {
+		existing = &messages.TagCache_Entry{
+			Package: &pin.PackageName,

[Vadim Sh., 2015/09/30 03:50:00]

pointers to strings annoy me, put that's how golang protobuf work :-/

+			Tag:     &tag,
+		}
+	}
+	existing.InstanceId = &pin.InstanceID
+
+	c.dirty = true
+	c.cache.Entries = append(c.cache.Entries, existing)
+}