google/cayley — pull request #113 by barakmich (2014-08-11 02:34:18+00:00)
Title: Convert Cayley indexing to an append-only log

Fixes #70

In order to provide for replication, graph history and other neat clustering features, I created the interface `QuadWriter` which can take care of all the replication logic; TripleStore (soon, QuadStore, I'm guessing) should store the things that have been accepted. Further, it should be kept as a log -- a follow-up CL which adds `GetRange(from, to int64) []*graph.Delta` to the TripleStore interface is forthcoming.

Some question of moving, renaming and ownership is certainly valid.

This also turns Cayley into a full quadstore for all backends, which it was heading toward anyway. This PR finalizes that.

Anyway, this means that nothing really gets deleted, but that indexed quads get extra data about when they're valid, and the triplestore^Hquadstore iterators should check the validity. This adds some amount of slowdown for Next(), but how much?

```
$ benchcmp nolog.txt prelog.txt
benchmark old ns/op new ns/op delta
BenchmarkNamePredicate 1075967 1144500 +6.37%
BenchmarkLargeSetsNoIntersection 48881903 56925194 +16.45%
BenchmarkVeryLargeSetsSmallIntersection 509579408 757046655 +48.56%
BenchmarkHelplessContainsChecker 26454974514 27333222110 +3.32%
BenchmarkNetAndSpeed 15422744 16408261 +6.39%
BenchmarkKeanuAndNet 12878175 13006483 +1.00%
BenchmarkKeanuAndSpeed 14542854 14950108 +2.80%
BenchmarkKeanuOther 61897336 76940891 +24.30%
BenchmarkKeanuBullockOther 78667479 81221650 +3.25%
```

A couple percent, but not noise. Incidentally, this is exacerbated by the Materialize iterator that recently went in; it does a lot of Next()ing, so on things where it aborts (HelplessContainsChecker) it doesn't have as problematic an impact. So, the wins from Materialize are still large, just less so now.

So what's the overhead on queries going through the addition/deletion/readdition cycle, other than using more persistence space? This now gets tested.

The answer to that, at least with the memstore is:
```
$ benchcmp prelog.txt postlog.txt
benchmark old ns/op new ns/op delta
BenchmarkNamePredicate 1144500 1108439 -3.15%
BenchmarkLargeSetsNoIntersection 56925194 57843995 +1.61%
BenchmarkVeryLargeSetsSmallIntersection 757046655 747045447 -1.32%
BenchmarkHelplessContainsChecker 27333222110 28253011444 +3.37%
BenchmarkNetAndSpeed 16408261 17083855 +4.12%
BenchmarkKeanuAndNet 13006483 13495442 +3.76%
BenchmarkKeanuAndSpeed 14950108 15693748 +4.97%
BenchmarkKeanuOther 76940891 68439409 -11.05%
BenchmarkKeanuBullockOther 81221650 74245237 -8.59%
```

Meh. Not too much.

Obviously it'll be a bit slower for larger backends, but it'll still be fairly small because it fails fairly fast; we don't have to go through the whole tree for things that are invalid, we just go to the next thing in the underlying persistence iterator.

A migration tool to collapse the history (ie, only keep additions of things that are valid) might make sense in the future, but should be a separate tool.

/cc @kortschak @pbnjay