this is getting too bad. It can't wait go rewrite

The following revision refers to this bug:
  https://chromium.googlesource.com/infra/infra/+/c602c7f72b528058a6b92e780721367ee7e1d901

commit c602c7f72b528058a6b92e780721367ee7e1d901
Author: Nodir Turakulov <nodir@google.com>
Date: Sat Jun 16 00:31:56 2018

[buildbucket] Remove tag index order requirement

TagIndex entires are currently guaranteed to be sorted.

One TagIndex entity does not scale to the QPS we have today for a same
buildset. It needs to be sharded. To continue benefiting from tag index entry
ordering, we'd need to implement merging of sorted arrays.
It is not worth it. We have up to 1000 entries. It takes <1ms to sort them
on macbookpro

R=vadimsh@chromium.org

Bug:  838318 
Change-Id: I4362a420b730d1e8d12252677f5fb3b81554c3cd
Reviewed-on: https://chromium-review.googlesource.com/1102564
Commit-Queue: Nodir Turakulov <nodir@chromium.org>
Reviewed-by: Vadim Shtayura <vadimsh@chromium.org>

[modify] https://crrev.com/c602c7f72b528058a6b92e780721367ee7e1d901/appengine/cr-buildbucket/service.py
[modify] https://crrev.com/c602c7f72b528058a6b92e780721367ee7e1d901/appengine/cr-buildbucket/test/service_test.py
[modify] https://crrev.com/c602c7f72b528058a6b92e780721367ee7e1d901/appengine/cr-buildbucket/errors.py
[modify] https://crrev.com/c602c7f72b528058a6b92e780721367ee7e1d901/appengine/cr-buildbucket/model.py

The following revision refers to this bug:
  https://chromium.googlesource.com/infra/infra/+/121069bd76a02b5d3958ef9c6b3cf395718153f9

commit 121069bd76a02b5d3958ef9c6b3cf395718153f9
Author: Nodir Turakulov <nodir@google.com>
Date: Wed Jun 20 05:27:33 2018

[buildbucket] Shard TagIndex entries.

One TagIndex entity does not scale to the QPS we have today for a same
buildset. Shard them.

Current TagIndex id format is "<key>:<value>". Add a new format
":<shard_index>:<key>:<value>" for positive shard indexes.
The zeroth entity remains "<key>:<value>".

When adding entries, pick a random entity. When searching, load them all.
Start with 16 shards. This number can be safely increased later.

Do not change max entry count per shard, which is 1000 now. Its purpose is to
handle datastore entity size limit. Entire shard set is marked permanently
incomplete if any of them reaches 1001 entries.

When searching, we used to sort entries of TagIndex. Now we have multiple TagIndexes.
Instead of sorting all their entries, filter out ones by build id low/high (including
cursor), and put the rest to a min-heap.
This is O(N) where N is number of entries in all shards.
Then pop P items from the heap, where P is the page size. This is O(P * log(N)).
P is capped at 100, so overall the function is linear.
Incidentally, this gets rid of entry_index variable and simplifies id low/high filtering.

Bug:  838318 
Change-Id: I42f5de1cb6c673a9f0d767af36cd6647bd3db19d
Reviewed-on: https://chromium-review.googlesource.com/1104703
Reviewed-by: Vadim Shtayura <vadimsh@chromium.org>
Commit-Queue: Nodir Turakulov <nodir@chromium.org>

[modify] https://crrev.com/121069bd76a02b5d3958ef9c6b3cf395718153f9/appengine/cr-buildbucket/handlers.py
[modify] https://crrev.com/121069bd76a02b5d3958ef9c6b3cf395718153f9/appengine/cr-buildbucket/test/handlers_test.py
[modify] https://crrev.com/121069bd76a02b5d3958ef9c6b3cf395718153f9/appengine/cr-buildbucket/model.py
[modify] https://crrev.com/121069bd76a02b5d3958ef9c6b3cf395718153f9/appengine/cr-buildbucket/service.py
[modify] https://crrev.com/121069bd76a02b5d3958ef9c6b3cf395718153f9/appengine/cr-buildbucket/test/model_test.py
[modify] https://crrev.com/121069bd76a02b5d3958ef9c6b3cf395718153f9/appengine/cr-buildbucket/test/service_test.py

beautiful graph http://shortn/_GROssxN8aI