[kudu-CR] KUDU-1317. Spread creation of new tablets more randomly

["Todd Lipcon (Code Review)" <ge...@ip-10-146-233-104.ec2.internal>]

Hello Binglin Chang, Internal Jenkins, Kudu Jenkins,

I'd like you to reexamine a change.  Please visit

    http://gerrit.cloudera.org:8080/1654

to look at the new patch set (#5).

Change subject: KUDU-1317. Spread creation of new tablets more randomly
......................................................................

KUDU-1317. Spread creation of new tablets more randomly

This switches the assignment of new tablets on the cluster from being a pure
round-robin to instead use the "power-of-two-choices" algorithm. In this
algorithm, each time we need to select a replica location, we sample a random
two nodes in the cluster, and choose whichever of those has fewer tablets
already on it. Per a simple Python script simulation (attached to the JIRA),
this does a much better job of even distribution than pure random selection,
but also avoids completely overloading a reformatted node with all replicas
of a new table.

This patch aims to solve a problem we're seeing with the round-robin
strategy where recovery is not well parallelized. Because of round-robin,
each tablet server only shares replicas with its "adjacent" nodes in the
round robin ring. So, if a server crashes, at most 4 other servers can
participate in recovery.

To check that the new test isn't flaky, I looped it 1000 times:
http://dist-test.cloudera.org/job?job_id=todd.1453857519.32553

Change-Id: I8a27c2ed52b49baeffb309ebecd3d58192eaeec6
---
M src/kudu/integration-tests/create-table-itest.cc
M src/kudu/master/catalog_manager.cc
M src/kudu/master/catalog_manager.h
M src/kudu/master/master.proto
M src/kudu/master/master_service.cc
M src/kudu/master/ts_descriptor.cc
M src/kudu/master/ts_descriptor.h
M src/kudu/tserver/ts_tablet_manager.cc
M src/kudu/tserver/ts_tablet_manager.h
M src/kudu/util/random-test.cc
M src/kudu/util/random.h
11 files changed, 358 insertions(+), 12 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/54/1654/5
-- 
To view, visit http://gerrit.cloudera.org:8080/1654
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I8a27c2ed52b49baeffb309ebecd3d58192eaeec6
Gerrit-PatchSet: 5
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Binglin Chang <de...@gmail.com>
Gerrit-Reviewer: Internal Jenkins
Gerrit-Reviewer: Jean-Daniel Cryans
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>