Key value store by sinbad · Pull Request #1694 · git-lfs/git-lfs

sinbad · 2016-11-21T16:57:30Z

This PR adds an in-memory, optimistically locked key-value store. It's basically a replacement for Boltdb for caching active locks locally as requested in the lock PR.

Submitted separately because it's generic and hopefully easy to review. Rewrite of lock PR is still ongoing but will use this.

sinbad · 2016-11-21T17:02:01Z

Hold off a minute, I think there may be an issue with writing a DB that's truncated smaller, need to add a test for that.

sinbad · 2016-11-21T17:15:49Z

OK, handled that case now; actually still worked (gob protocol is pretty robust) but shouldn't leave old data lying around.

ttaylorr

Digging this. Left a few comments for you to 💭 about.

ttaylorr · 2016-11-21T17:44:45Z

+	}
+
+	// firstly peek at version; open read/write to keep lock between check & write
+	f, err := os.OpenFile(k.filename, os.O_RDWR|os.O_CREATE, 0664)


Thinking that we could do this eagerly and maintain a handle on the *os.File from the instance, instead of this method.

Since I assume that we Save() more than once, only having to do this somewhat expensive operation once would be a win for me.

No, this is completely deliberate, and key to the optimistic locking technique. If you hold on to the handle, it will mean that parallel instances of git-lfs will block each other, which is limiting. The whole point of the optimistic locking system is to allow multiple instances of git-lfs to operate on shared key value stores and not end up locking each other out, while also resolving any parallel update issues.

Opening a file isn't that expensive and not unexpected on a Save() call. I doubt we'll be calling it very often; optimally you only call it once just before exit because it's an in-memory store. Conflicts are resolved at save time to avoid having to maintain stronger locks (this is a common DB trick).

Got it, thanks for explaining.

ttaylorr · 2016-11-21T17:45:11Z

+
+	// Short-circuit if we have no changes
+	if len(k.log) == 0 {
+		return nil


Does k.mu lock k.log?

Implicitly yes; it's a requirement that mu is always locked in the body of functions, either read-only or a full lock on mutating functions.

ttaylorr · 2016-11-21T17:46:15Z

+
+	k.version++
+
+	enc := gob.NewEncoder(f)


Actually, we may want to just hold onto this instance instead of the file. Perhaps both, since we need to f.Seek and f.Truncate.

No, see comments above. Being able to let go of the file handle is a deliberate feature :)

ttaylorr · 2016-11-21T17:46:54Z

+
+	enc := gob.NewEncoder(f)
+	err = enc.Encode(k.version)
+	if err != nil {


Nit: inline this:

if err = enc.Encode(k.Version); err != nil { // ... }

ttaylorr · 2016-11-21T17:47:00Z

+		return fmt.Errorf("Error while writing version data to %v: %v", k.filename, err)
+	}
+	err = enc.Encode(k.db)
+	if err != nil {


ttaylorr · 2016-11-21T17:51:55Z

+	db      map[string]interface{}
+}
+
+type keyValueOperation int


Possible to use a byte, since it's smaller than an int?

Yeah, although because of data alignment, in practice you don't actually save anything unless you have an array of them :)

ttaylorr · 2016-11-21T17:52:59Z

@@ -0,0 +1,201 @@
+package tools


I think this would be appropriate to put in a sub-package of tools: github.com/git-lfs/git-lfs/tools/kv, which would allow us to get rid of a lot of KeyValue* prefixes.

OK, can I call it 'keyvalue' for clarity? I even considered the option of making it a separate top-level package since it's not even specific to git-lfs...

Let's stick with tools/kv since kv is a common abbreviation.

I'm 👍 on kv because it's a common abbreviation, and go packages tend to prefer that (such as io). I'm totally fine with leaving it if you have strong feelings about it though.

ttaylorr · 2016-11-21T17:54:56Z

+func NewKeyValueStore(filepath string) (*KeyValueStore, error) {
+	kv := &KeyValueStore{filename: filepath, db: make(map[string]interface{})}
+	err := kv.loadAndMergeIfNeeded()
+	return kv, err


Nit: since you can return non-nil values for both, this could be simplified to:

return kv, kv.loadAndMergeIfNeeded()

ttaylorr · 2016-11-21T17:56:59Z

+	defer k.mu.Unlock()
+
+	delete(k.db, key)
+	k.log = append(k.log, keyValueChange{keyValueRemoveOperation, key, nil})


Looks like these transactional methods are pretty similar. What do you think about teaching the keyValueChange type how to perform these operations?

ttaylorr · 2016-11-21T17:57:26Z

+	if err == nil {
+		defer f.Close()
+		return k.loadAndMergeReaderIfNeeded(f)
+	} else if !os.IsNotExist(err) {


Is this possible given the above?

Not any more 👍

technoweenie

Made a few code style improvements, but nothing crucial. Thanks for doing this!

technoweenie · 2016-11-22T21:07:51Z

+	if err != nil {
+		return err
+	}
+	stat, _ := os.Stat(k.filename)


Small nit, but you can call f.Stat() here.

technoweenie · 2016-11-22T21:20:51Z

+		case setOperation:
+			baseDb[change.key] = change.value
+		case removeOperation:
+			delete(baseDb, change.key)


There's a bit of duplication here with Set() and Remove(). Though since this is just a wrapper around a map, it's probably fine for now. One way to solve it is to turn change into an interface, and calling Apply() on *setKey or *removeKey implementations in reapplyChanges() and logChange().

It looks like a mutex is needed here, but I think it's fine this code path is only called on Save() (which has a mutex) and NewStore() (which shouldn't need one).

It's only one line of duplication in practice since at this point we're replaying the change and don't want to re-record it in the log; I think a function or interface for 1 line is probably overkill.

The pattern I've used for the mutex is that externally visible functions lock it and internal functions rely on it already being locked. This distinction is required because Go's mutexes aren't recursive, so locks have to be at the edge of the interface and not re-locked inside that.

ttaylorr · 2016-11-23T18:08:32Z

Hmm.. I think we have a new intermittent failure:

test: clone in current directory ...                               FAILED

I've seen this one pop up a few times here and there, and only on Windows. Haven't done any investigation, so I'm not sure what's going on 😭

I'm going to re-run the tests for now, since your PR didn't introduce the transient failure.

sinbad · 2016-11-24T10:43:11Z

Gah, yeah I saw this a couple of weeks ago in an unrelated PR. Only seems to affect AppVeyor and I can't reproduce it on Windows :/

Could do this automatically using reflection? This is faster for now.

Some refactoring to make it cleaner when doing this

This actually didn’t cause any decoding issues to leave old data at the end, but we should be efficient with on-disk data.

sinbad · 2016-11-28T15:44:07Z

Re-targetted this at locking-master which will be my integration point for locking stuff from now on, so I can submit incrementally without the overhead of needing APIs to be final at every point. Appveyor problems went away again after I rebased.

sinbad added the review label Nov 21, 2016

ttaylorr reviewed Nov 21, 2016

View reviewed changes

ttaylorr approved these changes Nov 22, 2016

View reviewed changes

technoweenie approved these changes Nov 22, 2016

View reviewed changes

sinbad changed the base branch from master to locking-master November 28, 2016 15:05

sinbad added 12 commits November 28, 2016 15:12

First pass at an in-memory, optimistically locked key/value store

83828f6

Don’t try to decode a 0-byte key value store file, just ignore

49444ee

Need to export KV data members

28163b8

Need to allow registration of custom structs for storage

5a4f853

Could do this automatically using reflection? This is faster for now.

Initial key value store test

1dce30d

Manually serialize version & db in order so we can decode separately

5a6caff

Some refactoring to make it cleaner when doing this

Must update version loaded from disk

931caaa

Test for merge behaviour on optimistic lock conflict

ff247d5

Truncate file when we re-write in case it gets smaller

eb908d7

This actually didn’t cause any decoding issues to leave old data at the end, but we should be efficient with on-disk data.

PR feedback

c24b647

Move KeyValueStore into tools/kv and shorten naming

a372626

PR review; tidy stat

a047f0a

sinbad force-pushed the key-value-store branch from 79824bb to a047f0a Compare November 28, 2016 15:13

sinbad merged commit ab48ceb into locking-master Nov 28, 2016

sinbad deleted the key-value-store branch November 28, 2016 15:42

sinbad mentioned this pull request Dec 14, 2016

Mid-stage locking support #1769

Merged

Conversation

sinbad commented Nov 21, 2016

Uh oh!

sinbad commented Nov 21, 2016

Uh oh!

sinbad commented Nov 21, 2016

Uh oh!

ttaylorr left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

technoweenie left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ttaylorr commented Nov 23, 2016

Uh oh!

sinbad commented Nov 24, 2016

Uh oh!

sinbad commented Nov 28, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants