Make sure elapsed time is not negative

System.nanoTime() can sometimes go backwards as it relies on
performance counters. This commit fixes exceptions that can
surface due to requestTime being negative. See github issue:
https://github.com/voldemort/voldemort/issues/139
Small bug fixes and cleanup in R2Store
Add MANIFEST.MF to git ignore

Manifest.mf is an autogenerated file. Adding it to the ignore list.
Fixes to KeySampler/KeyVersionFetcher

-- Handle larger fetches without OOME
-- Adding support to use query-keys on hexstring keys, so as to be compatible with the keySampler/keyVersionFetcher
Dropped META-INF/MANIFEST.MF
Partition balance analysis tool for more than two zones.

- Started a directory for all of our tools (src/java/voldemort/tools)

- PartitionBalance :
  - broke this util out of ClusterInstance to make it more self-contained
  - this changed the declaration of a lot of the methods that invoked analyzeBalance and analyzeBalanceVerbose

- ClusterInstanceTest  :  Added a bunch of tests to confirm that partition balance can be constructed (or not) for combinations of 2 & 3 zones
Added RepartitionCLI. It is the subset of the RebalanceCLI that does repartitioning.
Initial version of repartitioning tool 'RepartitionCLI'.

RebalanceCLI
- removed all "generate" options and code from this tool (now tools/RepartitionCLI)
- removed "analysis" option from this tool (now tools/PartitionAnalysisCLI)
- Fixed errors in help/usage docs

RepartitionCLI
- Removed unnecessary options that restricted partition movement to be 'within a zone'. This decouples the repartition tool from the planning tool. This also assumes that optimizations can be done at plan time to keep all movement within a zone (when possible).
- cleaned up option names to be more concise
- Added options for target cluster/stores to allow zone expansion to be fully specified

PartitionBalance
- New class extracted from ClusterInstance
- Made all partition analysis zone-aware. This prevents zones with fewer nodes, or partitions, from skewing any analysis. I.e., each zone's balance analysis is now correctly normalized to be comparable with other zones' balance analyses.
- added inner ZoneBalanceStats class that makes stats tracking clearer
- added getUtility methods to hide the exact utiliyt method from the interfaces
- Changed utility methods to sum over all zones and to combine zone primary analysis with nary analysis.

RebalanceClusterUtils.java
- changed/extended balancePrimaryPartitions to handle zone expansion
- Stripped out a bunch of unnecessary options/code. I.e., options/code that tried to minimize cross zone moves during repartitioning (rather than during planning!)
- Added some helper methods to clean up repeated code.

RebalanceUtilsTest
- test new helper methods
Refactoring. Renamed RebalanceClusterUtils->RepartitionUtils and moved some tests into new file RepartitionUtilsTest.
Added tests of repartitioning algorithms.

RepartitionCLI
- added arg for greedy zone IDs; not bothering exposing it via CLI though

ClusterUtils.java
- split method that identifies contiguous partition ID runs into two, better tested and now correct, methods

PartitionBalance
- fix div by zero error

RepartitionUtils
- Documented the repartition method
- Reused the internal balancePrimaryPartitions method in the method that breaks apart contiguous partitoin runs
- dropped unused methods
- switched greedy algorithms to do either zone-by-zone or cluster as a whole. unless we find cluster-as-a-whole leads to too much data movement, is the behavior that we want.

ClusterInstanceTest
- made all the get*Cluster and get*StoreDefs methods static and added some more. These are generally useful for tests beyond ClusterInstance.

RepartitionUtilsTest
- Actually test all of hte repartitioning algorithms!
copyright fix
Initial work on RebalancePlanCLI.

Extracted the planning logic out of RebalanceController. This will reduce cut-and-paste coding, clarify which arguments are needed to tune planning (versus execution of a plan), and isolate rebalance planning logic from execution logic. There are a ton of TODOs added in this commit. As the refactoring continues, and the controller is changed to use the new RebalancePlan, these TODOs will be addressed. This commit has a working RebalancePlanCLI that handles the use cases rebalance planning has historically handled (rebalance in place and cluster expansion). This commit does not address zone expanison. The output of plan statistics is much richer and includes detailed statistics on cross zone moves (from which zone to which zone) and nodes (how much in and how much out). All these statistics are at the partition-store level which should be more informative than prior statistics. Finally, these statistics include an estimation of storage overhead per-node which can be used to assess how much free disk space is required to execute a plan safely.

OrderedClusterTransition
- TODOs to deprecate this. This logic belongs in the plan, not the execution.

RebalanceClusterPlan
- TODOs for refactoring
- Has logic for doing things "the old way" and the "new way". The new way has simpler data structures nad better encapsulation.
- Many more getters for detailed plan stats

RebalanceNodePlan
- Minor TODOs and some renaming of varaibles

RebalancePartitionsInfo
- A ton of refactoring TODOs
- Fixed all move counting getters to count partition-stores

Node
- getStateString method to pretty print ID, host name and ports.

RepartitionCLI
- more argument handling

PartitionBalance
- getters for partition-store accounting of current cluster+store defs

RebalanceUtils
- Some methods to deprecate
- validation methods for cluster arguments

RebalancePlan
- New class to encapsulate all rebalancing planning

RebalanceTypedBatchPlan
RebalanceDonorBasedBatchPlan
RebalanceStealerBasedBatchPlan
- Sub-classes of RebalancePlan that are needed for converting static plan into executable plan

RebalancePlanCLI
- CLI for generating a plan

MoveMap & MoveMapTest
- 2-d map counter used in partitoin-store accounting
I mangled the merge after a rebase. This commit manually fixes the errors I introduced. Mea culpa.
RebalancePlanCLI working for 2-to-3 zone expansion

Stealers steal from first donor with desired partition-store. This currently biases all work towards donors with lowest node IDs. This is truly imbalanced plan!

RebalanceClusterPlan
- Decorated with more TODOs...
- Changed stealer to pick first donor with desired partition-store
- Added commented-out code section that outlines next step for better planning

RebalancePartitionsInfo
- Decorated with more TODOs

RebalancePlan
- Much clean up refactoring. Construction now generates plan.
- Methods added to get the plan (getPlan) and to print the plan (toString)

RebalanceUtils
- Helper method that derives targetCluster from initialCluster and finalCluster.
RebalancePlan de-insanification

This is a messy commit:

1) There are a ton of TODOs, a ton of code marked to be deprecated, and a lot of gymnastics to continue using data structures that ought to be simplified or removed. All of this is necessary until the RebalanceController is switched to use the RebalancePlan, and until the abortable rebalance work and this work are merged to master. Cleaning up shared data structures is too high risk while on separate branches.

2) Some of the RebalanceTest tests are currently failing. Going to debug and fix in next commit.

Commit notes:

RebalanceClusterPlan
- renamed cluster members to be target & final rather than current & target
- determines batch plan at construction time
- added batchPlan() method that
  - is more clear than prior planning method
  - optimized to do n-ary to n-ary migration within a cluster so that only new zones require cross zone moves

RebalancePlan
- minor change for method name change

StoreRoutingPlan
- added internal member & method to track all nary-partition-stores per node
- get zone replica type methods that take partition id as input

RebalanceUtils
- added / refactored suite of methods that validate pairs of clusters (current&target, current&final, target&final)

There are tests missing at this point in development:
- simple & basic tests of RebalancePlan
- test StoreRoutingPlan.getNaryPartitionIds (and possibly other methods too)
- tests for RebalanceUtils.validate.* methods
Fixed broken junit tests. Documented and commented out other parts of unit tests that rely on donor-based rebalancing or that rely on partition-stores being deleted during rebalance. Both features are currently (necessarily) broken.

AdminClient
- Fix latent bug that treated node ids as dense/contiguous

RebalanceclusterPlan
- minor refactor

RebalanceController
- handle the case of an "empty" plan differently. Because unneccessary moves are optimized out at plan time, some of the small tests now yield plans with no data movement. I.e., primary partition IDs move among nodes, but data does not because all nodes already host all data. This exposed a corner case in which rebalance was successful, but servers never updated their cluster xml with new partitoin ID mapping.
- Removed random/unnecessary 10s sleep from control path. Annotated with a TODO for discussion to confirm this is right thing to do.

DonorBasedRebalanceAsyncOperation
- minor code clarification

DonorBasedRebalancePusherSlave
- Fixed latent bug (wrong value passed to sleep). Added TODO wondering why this sleep is here in the first place.

StorageEngine
- How are isPartitoinScanSupported() and isPartitionAware() related?

PartitionPrefixedBdbStorageEngine
- add isPartitionAware that returns true. Is this correct!?

AdminRebalanceTest
- Commented out asserts that test deletion during rebalancing

ZonedRebalanceTest
- Removed donor-based rebalancing tests from this test suite.
Added unit tests for RebalancePlan and for cluster xform & verification methods in RebalanceUtils

RebalancePlanTest
- Test the core use cases for rebalance planning:
  - no-op,
  - rebalance (zone/node topology same, but partition id layout changed),
  - cluster expansion (zone topology same, but new nodes added & partitions moved to them),
  - zone expansion (zone topoloigy changes with partitions moved to new zone).

RebalanceController
- rename method

RebalancePlan
- added getters for aggregate plan statistics

ServerTestUtils
- Changed getLocalZonedCluster to accept array of node IDs. Necessary to generalize other test methods.

ClusterInstanceTest
- pass storage type into helper methods that construct store defs
- chnagned all get???Cluster.*() methods to use new getLocalZonedCluster interface. Also added more such helper methods.

RebalanceUtilsTest
- Test the cluster transformation & verification methods

RepartitionUtilsTest
- simple clean up
copyright updates.
Addressing reviews of balance analysis & repartitionerCLI

RebalancePlan
- print out invalid metadata rate analysis

Cluster
- added members that allow reverse lookup of partitionID to either ZoneId or NodeId

StoreRoutingPlan
- Added reverse lookup of nodeID to Zone Primaries hosted.

RepartitionCLI
- moved constants into RepartitionUtils
- Added validation of clusters & storedefs passed in.

ClusterUtils
- use lookup from Cluster object
- changed all contig partition ID methods to call the one method that does all the complicated work.

PartitionBalance
- Added constants for use in the utility function
- Broke the core, complicated method into small, reasonably-sized pieces.
- Added verbose print out of ZoneReplicaTypes (to complement old "replica type" print out)

RepartitionUtils
- Document the recommend default constants for repartitioning
- Dump invalid metadata rate
- Clean up comments and java doc
- dumpInvalidMetadataRate analyzes and pretty-prints how many pseudo-masters per-zone per-unique-store-def lead to invalid metadata exception.
Refactoring: cleaned up util methods and moved them to appropriate util classes

RebalanceUtils
- all dump cluster methods are now here with more consistent interfaces
- analyzeInvalidMetadataRate is here (for lack of better place to put it)

RepartitionUtils
- moved all helper/util methods out of this class

Utils
- added removeItemsToSplitListEvenly, distributeEvenlyIntoList, and distributeEvenlyIntoMap

Moved test methods around to match new locations of util methods.