Add treapstore, a treap-based in-memory data store

Add treapstore, a treap-based in-memory data store

Add treapstore, which leverages gtreap implementation at
"github.com/luci/gtreap" to build a store.

This is intended as a lightweight and dedicated replacement for gkvlite
in "github.com/luci/gae/impl/memory".

BUG=chromium:675485
TEST=unit

Review-Url: https://codereview.chromium.org/2607663002
Committed: https://github.com/luci/luci-go/commit/aa8118f9689dceeb722b56a74dc40c05945d380d

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

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

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

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:33:40]

mostly lg

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
File common/data/treapstore/store.go (right):

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:18: "github.com/luci/gtreap"
do we need to fork it? IIRC, we forked gkvlite to fix some bugs that upstream
ignored. luci/gtreap looks to be identical to steveyen/gtreap.

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:54: // Snapshot creates a snapshot of the Store
and all of its Collection instances.
nit: "Snapshot creates a read-only copy of the Store ..."

This is more informative.

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:151: s    *Store
nit: this is unnecessary, just use 'putLock == nil' as a check for the read-only
bit, as in Store.

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:154: root    *atomic.Value
I'm not sure atomic.Value is necessary since you use putLock too. Is there a
reason to use atomic.Value in addition to the lock?

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:182: c.setRoot(c.currentRoot().Upsert(i,
rand.Int()))
nit: do rand.Int() outside the lock

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

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
File common/data/treapstore/store.go (right):

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:18: "github.com/luci/gtreap"
On 2016/12/28 01:33:40, Vadim Sh. wrote:
> do we need to fork it? IIRC, we forked gkvlite to fix some bugs that upstream
> ignored. luci/gtreap looks to be identical to steveyen/gtreap.

nvm, saw another CL :)

[dnj, 2016-12-28 03:01:06]

Thanks! Made those changes.

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
File common/data/treapstore/store.go (right):

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:18: "github.com/luci/gtreap"
On 2016/12/28 01:34:27, Vadim Sh. wrote:
> On 2016/12/28 01:33:40, Vadim Sh. wrote:
> > do we need to fork it? IIRC, we forked gkvlite to fix some bugs that
upstream
> > ignored. luci/gtreap looks to be identical to steveyen/gtreap.
> 
> nvm, saw another CL :)

Acknowledged. Yeah will actually put that forward as a pull request post-review
and if steveyen merges it back in will un-fork.

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:54: // Snapshot creates a snapshot of the Store
and all of its Collection instances.
On 2016/12/28 01:33:40, Vadim Sh. wrote:
> nit: "Snapshot creates a read-only copy of the Store ..."
> 
> This is more informative.

Done.

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:151: s    *Store
On 2016/12/28 01:33:39, Vadim Sh. wrote:
> nit: this is unnecessary, just use 'putLock == nil' as a check for the
read-only
> bit, as in Store.

Done.

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:154: root    *atomic.Value
On 2016/12/28 01:33:39, Vadim Sh. wrote:
> I'm not sure atomic.Value is necessary since you use putLock too. Is there a
> reason to use atomic.Value in addition to the lock?

Readers will grab this value w/out taking out a lock. I suppose I could use
RWLock. Probably cleaner, better performance. I'll do that.

https://codereview.chromium.org/2607663002/diff/20001/common/data/treapstore/...
common/data/treapstore/store.go:182: c.setRoot(c.currentRoot().Upsert(i,
rand.Int()))
On 2016/12/28 01:33:40, Vadim Sh. wrote:
> nit: do rand.Int() outside the lock

um ... yes done. /ashamed

[dnj, 2016-12-28 03:01:43]

BTW I intend to 100% coverage test this before commit. I didn't want to
overinvest in case Robbie had some objections to this approach.

[dnj, 2016-12-28 21:52:04]

The CQ bit was checked by dnj@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-12-28 21:52:07]

Dry run: 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, 2016-12-28 21:58:17]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-12-28 21:58:18]

Dry run: This issue passed the CQ dry run.

[dnj, 2016-12-28 23:23:56]

(ping) Got 100% test coverage, things looking good, and deps (gtreap) are all
set up. Any objection to committing this?

[Vadim Sh., 2016-12-28 23:48:28]

lgtm

[dnj, 2016-12-28 23:58:08]

The CQ bit was checked by dnj@chromium.org

[commit-bot: I haz the power, 2016-12-28 23:58:19]

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, 2016-12-29 00:03:45]

CQ is committing da patch.

Bot data: {"patchset_id": 120001, "attempt_start_ts": 1482969488082350,
"parent_rev": "cc2b303de7a9dd94840f1f0c161093bad0b77196", "commit_rev":
"aa8118f9689dceeb722b56a74dc40c05945d380d"}

[commit-bot: I haz the power, 2016-12-29 00:03:48]

Description was changed from

==========
Add treapstore, a treap-based in-memory data store

Add treapstore, which leverages gtreap implementation at
"github.com/luci/gtreap" to build a store.

This is intended as a lightweight and dedicated replacement for gkvlite
in "github.com/luci/gae/impl/memory".

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

to

==========
Add treapstore, a treap-based in-memory data store

Add treapstore, which leverages gtreap implementation at
"github.com/luci/gtreap" to build a store.

This is intended as a lightweight and dedicated replacement for gkvlite
in "github.com/luci/gae/impl/memory".

BUG=chromium:675485
TEST=unit

Review-Url: https://codereview.chromium.org/2607663002
Committed:
https://github.com/luci/luci-go/commit/aa8118f9689dceeb722b56a74dc40c05945d380d
==========

[commit-bot: I haz the power, 2016-12-29 00:03:50]

Committed patchset #7 (id:120001) as
https://github.com/luci/luci-go/commit/aa8118f9689dceeb722b56a74dc40c05945d380d