Non-deterministic result when merging an empty KllFloatsSketch with two others

Open
#693 13 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
45/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Tech stack
java
Domain
data

Research direction

Start by reproducing the supplied test around KllFloatsSketch.newHeapInstance(), heapify(), merge(), and toByteArray(). Compare repeated serialized results when merging the sketches containing 1 and 200 items, then trace the merge and serialization behavior. Done means the repeated test produces one deterministic digest and passes consistently.

Written by the indexing model from the issue text.

Description

Merging an empty KllFloatsSketch with two KllFloatsSketch, with 1 and 200 "items" respectively, does not always produce the same result

I would have expected the following test scenario to pass:

@Test
  public void test() throws NoSuchAlgorithmException {

    KllFloatsSketch t1 = KllFloatsSketch.newHeapInstance();
    t1.update(1f);
    byte[] tb1 = t1.toByteArray();

    KllFloatsSketch t2 = KllFloatsSketch.newHeapInstance();
    for(int i=0; i<200; i++) {
      t2.update(1f*i);
    }
    byte[] tb2 = t2.toByteArray();

    HashSet<BigInteger> digests = new HashSet<>();
    for(int i=0; i<30; i++) {
      KllFloatsSketch start = KllFloatsSketch.newHeapInstance();

      byte[] h1 = Arrays.copyOf(tb1, tb1.length);
      byte[] h2 = Arrays.copyOf(tb2, tb2.length);

      KllFloatsSketch kll1 = KllFloatsSketch.heapify(MemorySegment.ofArray(h1));
      start.merge(kll1);

      KllFloatsSketch kll2 = KllFloatsSketch.heapify(MemorySegment.ofArray(h2));
      start.merge(kll2);

      MessageDigest md5 = MessageDigest.getInstance("MD5");

      BigInteger digest = new BigInteger(md5.digest(start.toByteArray()));
      digests.add(digest);
      System.out.println(digest);
    }
    assertEquals(1, digests.size());
  }

The digests are:

115710133967357289505160160937439690295
-100233422360292323003164315945381734567
-100233422360292323003164315945381734567
-100233422360292323003164315945381734567
115710133967357289505160160937439690295
115710133967357289505160160937439690295
...

And therefore the test throws:

java.lang.AssertionError:
Expected :2
Actual   :1
Dominant language
Java
Stars
958
Forks
226
Avg merge
3d 40m
Merged PRs (30d)
13

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from apache/datasketches-java

All issues in apache/datasketches-java

Similar issues

More Java issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.