DynoBinarySearch { public T getTokenOwner(T token) { if (listEmpty.get()) { return null; } if (rangeList.size() == 1) { return rangeList.get(0).getTokenOwner(); } DynoTokenRange<T> firstRange = rangeList.get(0); DynoTokenRange<T> lastRange = rangeList.get(rangeList.size() - 1); if (firstRange.compareTo(token) == 0) { return firstRange.getTokenOwner(); } if (lastRange.compareTo(token) < 0) { return firstRange.getTokenOwner(); } int index = Collections.binarySearch(rangeList, token); if (index < 0) { throw new RuntimeException("Token not found!: " + token); } return rangeList.get(index).getTokenOwner(); } DynoBinarySearch(List<T> list); T getTokenOwner(T token); String toString();  }
@Test public void testTokenSearch() throws Exception { List<Integer> list = Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90, 100); DynoBinarySearch<Integer> search = new DynoBinarySearch<Integer>(list); for (int i = 0; i <= 133; i++) { Integer token = search.getTokenOwner(i); Integer expected = getExpectedToken(i); Assert.assertEquals(expected, token); } }
@Test public void testTokenDistribution() throws Exception { List<Long> tokens = Arrays.asList(611697721L, 2043353485L, 3475009249L); DynoBinarySearch<Long> search = new DynoBinarySearch<Long>(tokens); Map<Long, Long> tokenCount = new HashMap<Long, Long>(); tokenCount.put(611697721L, 0L); tokenCount.put(2043353485L, 0L); tokenCount.put(3475009249L, 0L); Murmur1HashPartitioner hash = new Murmur1HashPartitioner(); for (int i = 0; i < 1000000; i++) { long lHash = hash.hash("" + i); Long token = search.getTokenOwner(lHash); Long count = tokenCount.get(token); count++; tokenCount.put(token, count); } long total = 0; for (Long value : tokenCount.values()) { total += value; } for (Long token : tokenCount.keySet()) { Long value = tokenCount.get(token); Long percent = value * 100 / total; Assert.assertTrue("Percentage is off for tokenCount: " + tokenCount, percent >= 30 && percent <= 35); } }