apache / apache/datasketches-java
Non-deterministic result when merging an empty KllFloatsSketch with two others
- 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