impl/memory: Replace gkvlite with "treapstore".

impl/memory: Replace gkvlite with "treapstore".

gkvlite is the treap (tree + heap)-based key/value store used by
"impl/memory"'s backend. While it is very powerful package, its
complexity and ensuing requirements make it a somewhat-imperfect fit.
Specifically, "gkvlite" is built around resources that must be
explicitly allocated and free'd. While this makes a lot of sense for its
on-disk storage functionality, we don't use that functionality, and
integrating snapshot closing into every layer of "impl/memory" is
non-trivial.

Enter "treapstore", a treap-based storage implementation that closesly
mirrors the functionality in "gkvlite" that "impl/memory" uses, but
specifically focuses the in-memory use case. Because "treapstore"
foregoes node reuse and snapshot cleanup, we can rely entirely on Go's
memory manager to clean things up, removing the need to close things.

"treapstore" builds on an extended version of "gkvlite"'s underlying
"gtreap" package which introduces an iterator. This iterator removes the
need for the goroutine- and callback-based iteration implementations
that "impl/memory" used to interface with gkvlite (and "gtreap")'s
VisitItemsAscend method, resulting in signifcantly cleaner and likely
higher perfomant code. "treapstore" iterators don't have any cleanup
requirements. Consqeuently, explicit resource management via "stop" is
no longer necessary to perform iteration.

BUG=chromium:675485
TEST=unit

Review-Url: https://codereview.chromium.org/2604943002
Committed: https://github.com/luci/gae/commit/951a9bd6e11300d097436f797c397d42334c742e

[dnj, 2016-12-27 23:50:57]

dnj@chromium.org changed reviewers:
+ hinoka@chromium.org, iannucci@chromium.org, vadimsh@chromium.org

[dnj, 2016-12-27 23:50:58]

PTAL.

This is part of a series of patches that I created today. For context and
motivation, see https://codereview.chromium.org/2601513007

Basically, there is no good way in "gkvlite" to not lose memory for the lifetime
of the impl/memory store when taking snapshots, making it defective by design
for our purposes. I'm proposing replacing it with a lightweight in-memory
"treapstore".

https://codereview.chromium.org/2604933002 (treap iterator)
https://codereview.chromium.org/2607663002 (treapstore)
https://codereview.chromium.org/2604943002 (replace gkvlite with treapstore)

[Vadim Sh., 2016-12-28 01:57:06]

lgtm, but wait for Robbie's review too

https://codereview.chromium.org/2604943002/diff/20001/impl/memory/memstore.go
File impl/memory/memstore.go (right):

https://codereview.chromium.org/2604943002/diff/20001/impl/memory/memstore.go...
impl/memory/memstore.go:53: f(r.key, nil, r.value)
nit: this can be micro optimized by avoiding calls to oldIter.Next() and
unnecessary comparisons:

case l == nil:
  for r != nil  {
    f(r.key, nil, r.value)
    r = newIter.Next()
  }
  return

(and same for r == nil, and case l == nil && r == nil can be removed). 

IMHO, it also makes the intent cleaner.

https://codereview.chromium.org/2604943002/diff/20001/impl/memory/memstore.go...
impl/memory/memstore.go:80: // should occur happen with file IO on the
underlying file (which of course
the comment is probably stale. There should be no files involved anymore.
Mentioning file IO while none of the underlying libraries use files is
confusing.

[dnj, 2016-12-28 02:52:16]

Thanks! Will definitely wait for Robbie's review for all of this :)

https://codereview.chromium.org/2604943002/diff/20001/impl/memory/memstore.go
File impl/memory/memstore.go (right):

https://codereview.chromium.org/2604943002/diff/20001/impl/memory/memstore.go...
impl/memory/memstore.go:53: f(r.key, nil, r.value)
On 2016/12/28 01:57:05, Vadim Sh. wrote:
> nit: this can be micro optimized by avoiding calls to oldIter.Next() and
> unnecessary comparisons:
> 
> case l == nil:
>   for r != nil  {
>     f(r.key, nil, r.value)
>     r = newIter.Next()
>   }
>   return
> 
> (and same for r == nil, and case l == nil && r == nil can be removed). 
> 
> IMHO, it also makes the intent cleaner.

I was initially trying to stay as close to the original function as possible,
but agreed. Done.

https://codereview.chromium.org/2604943002/diff/20001/impl/memory/memstore.go...
impl/memory/memstore.go:80: // should occur happen with file IO on the
underlying file (which of course
On 2016/12/28 01:57:05, Vadim Sh. wrote:
> the comment is probably stale. There should be no files involved anymore.
> Mentioning file IO while none of the underlying libraries use files is
> confusing.

Done.

[iannucci, 2017-01-07 19:06:17]

\o/

lgtm!

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/datastore_i...
File impl/memory/datastore_index.go (right):

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/datastore_i...
impl/memory/datastore_index.go:212: forEachItem(newColl, func(k, _ []byte) bool
{
would it be worth just using for loops here now? avoid the callback?

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/datastore_i...
File impl/memory/datastore_index_test.go (right):

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/datastore_i...
impl/memory/datastore_index_test.go:256: forEachItem(coll, func(k, v []byte)
bool {
it's fine to keep it for funsies in the tests though if the syntax is annoying

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore.go
File impl/memory/memstore.go (right):

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore.go...
impl/memory/memstore.go:21: // storeEntryCompare is a gtrea.Compare function for
*storeEntry.
gtreap

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore.go...
impl/memory/memstore.go:22: func storeEntryCompare(a, b interface{}) int {
that's unfortunate :/ no way we can hack up gtreap so that keys are always
[]byte and build the comparisons in? I suppose it would be worth benching first
of course, but I suspect the casting isn't doing favors :)

Or, better, a ByteKeyer function `func(a interface{}) []byte`? Then the internal
structures could store the []byte too, which would be the same object contained
in the storeEntry. If no bytekeyer is provided, then it would fall back to the
compare function.

i.e. https://en.wikipedia.org/wiki/Schwartzian_transform

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore_it...
File impl/memory/memstore_iter.go (right):

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore_it...
impl/memory/memstore_iter.go:63: it.skip(serialize.Join(it.def.prefix[:pfxLen],
suffix))
:O

\o/

[dnj, 2017-01-08 03:38:14]

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/datastore_i...
File impl/memory/datastore_index.go (right):

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/datastore_i...
impl/memory/datastore_index.go:212: forEachItem(newColl, func(k, _ []byte) bool
{
On 2017/01/07 19:06:17, iannucci wrote:
> would it be worth just using for loops here now? avoid the callback?

Thought about it a bit. I actually added VisitAscend to treapstore:
https://codereview.chromium.org/2616303002

Reason is that the stack-based traversal is ideal when useful, and since this is
production code I think that it would be useful to keep it in here. I simplified
the memstore interface to be "ForEachItem" (period) instead of requiring the
user to provide a pivot like gkvlite does.

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/datastore_i...
File impl/memory/datastore_index_test.go (right):

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/datastore_i...
impl/memory/datastore_index_test.go:256: forEachItem(coll, func(k, v []byte)
bool {
On 2017/01/07 19:06:17, iannucci wrote:
> it's fine to keep it for funsies in the tests though if the syntax is annoying

Acknowledged.

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore.go
File impl/memory/memstore.go (right):

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore.go...
impl/memory/memstore.go:21: // storeEntryCompare is a gtrea.Compare function for
*storeEntry.
On 2017/01/07 19:06:17, iannucci wrote:
> gtreap

Done.

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore.go...
impl/memory/memstore.go:22: func storeEntryCompare(a, b interface{}) int {
On 2017/01/07 19:06:17, iannucci wrote:
> that's unfortunate :/ no way we can hack up gtreap so that keys are always
> []byte and build the comparisons in? I suppose it would be worth benching
first
> of course, but I suspect the casting isn't doing favors :)
> 
> Or, better, a ByteKeyer function `func(a interface{}) []byte`? Then the
internal
> structures could store the []byte too, which would be the same object
contained
> in the storeEntry. If no bytekeyer is provided, then it would fall back to the
> compare function.
> 
> i.e. https://en.wikipedia.org/wiki/Schwartzian_transform

Yeah we totally could do this. Might be worth determining if useful? ATM it
would require updating gtreap, treapstore, and impl/memory, so let's punt on it
for a later effort. I'll add a TODO.

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore_it...
File impl/memory/memstore_iter.go (right):

https://codereview.chromium.org/2604943002/diff/60001/impl/memory/memstore_it...
impl/memory/memstore_iter.go:63: it.skip(serialize.Join(it.def.prefix[:pfxLen],
suffix))
On 2017/01/07 19:06:17, iannucci wrote:
> :O
> 
> \o/

:D Yeah I think we both disliked the complexity of this code. While I was making
treapstore, I decided it was worth it to just bite the bullet and implement an
actual iterator.

[dnj, 2017-01-08 20:31:37]

The CQ bit was checked by dnj@chromium.org

[dnj, 2017-01-08 20:31:37]

The patchset sent to the CQ was uploaded after l-g-t-m from
vadimsh@chromium.org, iannucci@chromium.org
Link to the patchset: https://codereview.chromium.org/2604943002/#ps80001
(title: "Comments.")

[commit-bot: I haz the power, 2017-01-08 20:31:39]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-01-08 20:35:36]

CQ is committing da patch.

Bot data: {"patchset_id": 80001, "attempt_start_ts": 1483907497125500,
"parent_rev": "a05a77f8ad60158869c1dc908b16dc618a580101", "commit_rev":
"951a9bd6e11300d097436f797c397d42334c742e"}

[commit-bot: I haz the power, 2017-01-08 20:35:39]

Description was changed from

==========
impl/memory: Replace gkvlite with "treapstore".

gkvlite is the treap (tree + heap)-based key/value store used by
"impl/memory"'s backend. While it is very powerful package, its
complexity and ensuing requirements make it a somewhat-imperfect fit.
Specifically, "gkvlite" is built around resources that must be
explicitly allocated and free'd. While this makes a lot of sense for its
on-disk storage functionality, we don't use that functionality, and
integrating snapshot closing into every layer of "impl/memory" is
non-trivial.

Enter "treapstore", a treap-based storage implementation that closesly
mirrors the functionality in "gkvlite" that "impl/memory" uses, but
specifically focuses the in-memory use case. Because "treapstore"
foregoes node reuse and snapshot cleanup, we can rely entirely on Go's
memory manager to clean things up, removing the need to close things.

"treapstore" builds on an extended version of "gkvlite"'s underlying
"gtreap" package which introduces an iterator. This iterator removes the
need for the goroutine- and callback-based iteration implementations
that "impl/memory" used to interface with gkvlite (and "gtreap")'s
VisitItemsAscend method, resulting in signifcantly cleaner and likely
higher perfomant code. "treapstore" iterators don't have any cleanup
requirements. Consqeuently, explicit resource management via "stop" is
no longer necessary to perform iteration.

BUG=chromium:675485
TEST=unit
==========

to

==========
impl/memory: Replace gkvlite with "treapstore".

gkvlite is the treap (tree + heap)-based key/value store used by
"impl/memory"'s backend. While it is very powerful package, its
complexity and ensuing requirements make it a somewhat-imperfect fit.
Specifically, "gkvlite" is built around resources that must be
explicitly allocated and free'd. While this makes a lot of sense for its
on-disk storage functionality, we don't use that functionality, and
integrating snapshot closing into every layer of "impl/memory" is
non-trivial.

Enter "treapstore", a treap-based storage implementation that closesly
mirrors the functionality in "gkvlite" that "impl/memory" uses, but
specifically focuses the in-memory use case. Because "treapstore"
foregoes node reuse and snapshot cleanup, we can rely entirely on Go's
memory manager to clean things up, removing the need to close things.

"treapstore" builds on an extended version of "gkvlite"'s underlying
"gtreap" package which introduces an iterator. This iterator removes the
need for the goroutine- and callback-based iteration implementations
that "impl/memory" used to interface with gkvlite (and "gtreap")'s
VisitItemsAscend method, resulting in signifcantly cleaner and likely
higher perfomant code. "treapstore" iterators don't have any cleanup
requirements. Consqeuently, explicit resource management via "stop" is
no longer necessary to perform iteration.

BUG=chromium:675485
TEST=unit

Review-Url: https://codereview.chromium.org/2604943002
Committed:
https://github.com/luci/gae/commit/951a9bd6e11300d097436f797c397d42334c742e
==========

[commit-bot: I haz the power, 2017-01-08 20:35:40]

Committed patchset #5 (id:80001) as
https://github.com/luci/gae/commit/951a9bd6e11300d097436f797c397d42334c742e