Fixes bad partitioning of data in the v1 memory store (openzipkin#1843)

adriancole · web-flow · commit 0b499b89f2df · 2017-12-14T17:18:36.000+08:00
*Note* this only affects people using the v1 in-memory component. The
in-memory option of zipkin-server does not use this even if v1 format is
accepted.

This fixes a partitioning messup where all spans for the same timestamp
filed under the same key.
diff --git a/zipkin/src/main/java/zipkin/storage/InMemorySpanStore.java b/zipkin/src/main/java/zipkin/storage/InMemorySpanStore.java
@@ -330,7 +330,11 @@ static final class LinkedListSortedMultimap<K, V> extends SortedMultimap<K, V> {
     @Override public int compare(Pair<Long> left, Pair<Long> right) {
       long x = left._2, y = right._2;
       int result = (x < y) ? -1 : ((x == y) ? 0 : 1); // Long.compareTo is JRE 7+
-      return -result; // use negative as we are descending
+      if (result != 0) return -result; // use negative as we are descending
+      // secondary compare as TreeMap is in use
+      x = left._1;
+      y = right._1;
+      return (x < y) ? -1 : ((x == y) ? 0 : 1);
     }
 
     @Override public String toString() {
diff --git a/zipkin/src/test/java/zipkin/storage/InMemorySpanStoreTest.java b/zipkin/src/test/java/zipkin/storage/InMemorySpanStoreTest.java
@@ -13,6 +13,7 @@
  */
 package zipkin.storage;
 
+import java.util.Map;
 import org.junit.Before;
 import org.junit.Test;
 import zipkin.Annotation;
@@ -24,7 +25,7 @@
 import static org.assertj.core.api.Assertions.assertThat;
 import static zipkin.TestObjects.TODAY;
 
-public class InMemorySpanStoreEvictionTest {
+public class InMemorySpanStoreTest {
   InMemoryStorage storage = new InMemoryStorage.Builder().maxSpanCount(1000).build();
   InMemorySpanStore store = storage.spanStore();
   StorageAdapters.SpanConsumer consumer = store.spanConsumer;
@@ -78,6 +79,16 @@ public void clear() {
     .id(0x654)
     .annotations(asList(ann7, ann8)).build();
 
+  /** Ensures we don't overload a partition due to key equality being conflated with order */
+  @Test
+  public void differentiatesOnTraceIdWhenTimestampEqual() {
+    consumer.accept(asList(span1));
+    consumer.accept(asList(span1.toBuilder().traceId(333L).build()));
+
+    assertThat(store).extracting("spansByTraceIdTimeStamp.delegate")
+      .allSatisfy(map -> assertThat((Map) map).hasSize(2));
+  }
+
   @Test
   public void dropsLargerThanMax() {
     consumer.accept(asList(TestObjects.LOTS_OF_SPANS));
diff --git a/zipkin2/src/test/java/zipkin2/storage/InMemoryStorageTest.java b/zipkin2/src/test/java/zipkin2/storage/InMemoryStorageTest.java
@@ -16,6 +16,7 @@
 import java.io.IOException;
 import java.util.Collections;
 import java.util.List;
+import java.util.Map;
 import java.util.stream.Collectors;
 import java.util.stream.IntStream;
 import org.junit.Test;
@@ -27,6 +28,7 @@
 import static java.util.Arrays.asList;
 import static java.util.stream.Collectors.toList;
 import static org.assertj.core.api.Assertions.assertThat;
+import static zipkin2.TestObjects.CLIENT_SPAN;
 import static zipkin2.TestObjects.TODAY;
 
 public class InMemoryStorageTest {
@@ -77,6 +79,15 @@ public class InMemoryStorageTest {
       .containsExactly(earlyTraces);
   }
 
+  /** Ensures we don't overload a partition due to key equality being conflated with order */
+  @Test public void differentiatesOnTraceIdWhenTimestampEqual() {
+    storage.accept(asList(CLIENT_SPAN));
+    storage.accept(asList(CLIENT_SPAN.toBuilder().traceId("333").build()));
+
+    assertThat(storage).extracting("spansByTraceIdTimeStamp.delegate")
+      .allSatisfy(map -> assertThat((Map) map).hasSize(2));
+  }
+
   /** It should be safe to run dependency link jobs twice */
   @Test public void replayOverwrites() throws IOException {
     Span span = Span.newBuilder().traceId("10").id("10").name("receive")
