apache / apache/datasketches-java

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

Open
#693 13 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
958
Forks
226
Avg merge
3d 9h
Merged PRs (30d)
8

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 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
```

Contributor guide

No contributing guide indexed for this repository

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.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.