Add initial Query generation, correctness checking and index generation.

go/src/infra/gae/libs/wrapper/memory/README.md

 In-memory appengine wrapper
 ===========================
 
 
 Notes on the internal encodings
 -------------------------------
 
 All datatypes inside of the index Collections of the gkvlite Store are stored
 in a manner which allows them to be compared entirely via bytes.Compare. All
 types are prefixed by a sortable type byte which encodes the sort-order of types
@@ skipping 69 matching lines @@
 
 The end-result is semantically equivalent, with the exception that Query Cursors
 on the real datastore will potentially return the same Key in the first Cursor
 use as well as on the 2nd (or Nth) cursor use, where this method will not.
 
     collections
       ents:ns                    -> key -> value
                                     (rootkind, rootid, __entity_group__,1) -> {__version__: int}
                                     (rootkind, rootid, __entity_group_ids__,1) -> {__version__: int}
                                     (__entity_group_ids__,1) -> {__version__: int}
+      // TODO(iannucci): Journal every entity write in a log with a globally
+      // increasing version number (aka "timestamp").

[M-A Ruel, 2015/05/31 23:03:15]

http://googlecloudplatform.blogspot.ca/2015/05/Got-a-second-A-leap-second-tha...

and NTP in general. In swarming, what happens in these cases is slight
reordering of the task priority. In Swarming explicitly doesn't do explicit FIFO
under millisecond level by injecting random bits in the ordering.

[iannucci, 2015/05/31 23:31:33]

Yeah, that's not what I'm referring to at all :). The entity group
metadataversion is a UTC timestamp on appspot.com (go load the entity group
version on any appspot instance and then interpret the number as a unix
timestamp). Presumably, it's synchronized by something other than NTP. I'll let
you guess how.

For our purposes here, it would just be an incrementing number because this
isn't a distributed system.

+      //
+      // TODO(iannucci): Use the value in idx collection to indicate the last
+      // global log version reflected in this index. Then index updates can happen
+      // in parallel, in a truly eventually-consistent fashion (and completely
+      // avoid holding the DB writelock while calculating index entries).
+      // Unfortunately, copying new records (and removing old ones) into the DB
+      // would still require holding global writelock.
+      //
+      // TODO(iannucci): how do we garbage-collect the journal?
+      //
+      // TODO(iannucci): add the ability in gkvlite to 'swap' a collection with
+      // another one, transactionally? Not sure if this is possible to do easily.
+      // If we had this, then we could do all the index writes for a given index
+      // on the side, and then do a quick swap into place with a writelock. As
+      // long as every index only has a single goroutine writing it, then this
+      // would enable maximum concurrency, since all indexes could update in
+      // parallel and only synchronize for the duration of a single pointer swap.
+      idx                        -> kind|A?|[-?prop]* = nil
       idx:ns:kind                -> key = nil
       idx:ns:kind|prop           -> propval|key = [prev val]
       idx:ns:kind|-prop          -> -propval|key = [next val]
       idx:ns:kind|A|?prop|?prop  -> A|propval|propval|key = [prev/next val]|[prev/next val]
       idx:ns:kind|?prop|?prop    -> propval|propval|key = [prev/next val]|[prev/next val]
-
-      // to add persistence later
-      idx:                       -> kind,A?,[-?prop]*