You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@jena.apache.org by GitBox <gi...@apache.org> on 2020/01/17 19:50:36 UTC
[GitHub] [jena] afs opened a new pull request #673: JENA-1812: Switch to
Murmur3 for blank node allocation
afs opened a new pull request #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673
Use Murmur3-128bit for blank node label allocation. This code is called when a blank node appears in RDF syntax.
This is an alternative to #667 as discussed at [JENA-1812](https://issues.apache.org/jira/browse/JENA-1812).
Murmur3-128 retain the length of blank node labels while not triggering security scans.
The murmurs implementation is the one from Apache Commons Codec. The differences between it and the Guava implementation are, for this usage, slight. For reference, the Guava version is includes in the source but the compiler does not generate any bytecode.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
[GitHub] [jena] afs merged pull request #673: JENA-1812: Switch to Murmur3
for blank node allocation
Posted by GitBox <gi...@apache.org>.
afs merged pull request #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
[GitHub] [jena] afs commented on a change in pull request #673: JENA-1812:
Switch to Murmur3 for blank node allocation
Posted by GitBox <gi...@apache.org>.
afs commented on a change in pull request #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673#discussion_r368726668
##########
File path: jena-arq/src/main/java/org/apache/jena/riot/lang/BlankNodeAllocatorHash.java
##########
@@ -90,6 +80,12 @@ protected UUID freshSeed() {
@Override
public void reset() {
UUID seed = this.freshSeed();
+ long mostSigBits = seed.getMostSignificantBits();
+ long leastSigBits = seed.getLeastSignificantBits();
+ // Stamp on version and variant. Makes it an illegal UUID (unless all the bits are zero!)
Review comment:
TBH it is not needed, it's being a little tidy saying "this is not being used as a UUID". We are using a UUID but only as convenient way to get a quality random number so large it is unique for practical purposes. Version and variant are together 6 bits (fixed), leaving 122 bits of input. 122 bits is a very large number. IIRC (e.g. 3Store paper) a few bits more that 64 is enough. 58 bits more is a lot more.
> The “Birthday Paradox”1 gives the probability of an accidental hash collision
> occurring anywhere in a knowledge base of 10^9 distinct nodes to be around
> 1 : 10^−10 when using an effective 63 bit hash.
(more details in the paper)
The requirements are uniqueness for any bnodes that are ever going to meet (assumed "global"), speed and not requiring keeping the seen labels over the life of a parser run. Prior to using the hash allocator, Jena kept labels it had seen and very occasionally a user would run out of heap due to the footprint.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
[GitHub] [jena] afs commented on issue #673: JENA-1812: Switch to Murmur3
for blank node allocation
Posted by GitBox <gi...@apache.org>.
afs commented on issue #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673#issuecomment-576032364
Both the Apache Commons and Google Guava impls are translations of the C++ code. I think (maybe Claude can confirm) that the "x86" in the method names is because Java uses the same endian-ness as x86. But maybe the int->long conversions are different - one of the two fixes in codec 1.14 is about int to long which in Java (signed numbers) does a sign extension.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
[GitHub] [jena] rvesse commented on a change in pull request #673:
JENA-1812: Switch to Murmur3 for blank node allocation
Posted by GitBox <gi...@apache.org>.
rvesse commented on a change in pull request #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673#discussion_r368429994
##########
File path: jena-arq/src/main/java/org/apache/jena/riot/lang/BlankNodeAllocatorHash.java
##########
@@ -90,6 +80,12 @@ protected UUID freshSeed() {
@Override
public void reset() {
UUID seed = this.freshSeed();
+ long mostSigBits = seed.getMostSignificantBits();
+ long leastSigBits = seed.getLeastSignificantBits();
+ // Stamp on version and variant. Makes it an illegal UUID (unless all the bits are zero!)
Review comment:
I assume this is needed because otherwise the version and variant segments of the UUID would always be the same leading to some predictability in the hashing?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
[GitHub] [jena] rvesse commented on a change in pull request #673:
JENA-1812: Switch to Murmur3 for blank node allocation
Posted by GitBox <gi...@apache.org>.
rvesse commented on a change in pull request #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673#discussion_r368888535
##########
File path: jena-arq/src/main/java/org/apache/jena/riot/lang/BlankNodeAllocatorHash.java
##########
@@ -90,6 +80,12 @@ protected UUID freshSeed() {
@Override
public void reset() {
UUID seed = this.freshSeed();
+ long mostSigBits = seed.getMostSignificantBits();
+ long leastSigBits = seed.getLeastSignificantBits();
+ // Stamp on version and variant. Makes it an illegal UUID (unless all the bits are zero!)
Review comment:
Sure I'm well aware of the birthday paradox and the parsing concerns and overheads involved, just wanted to clarify the intent of the code
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
[GitHub] [jena] afs commented on a change in pull request #673: JENA-1812:
Switch to Murmur3 for blank node allocation
Posted by GitBox <gi...@apache.org>.
afs commented on a change in pull request #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673#discussion_r368163841
##########
File path: jena-arq/src/main/java/org/apache/jena/riot/lang/BlankNodeAllocatorHash.java
##########
@@ -113,20 +104,67 @@ public Node call() {
public Node create() {
counter++;
// Make illegal string bytes so can't clash with alloc(String).
- // It is different because it has zeros in it.
+ // It is different because it has a zero (illegal in a Java string) in it.
counterBytes[0] = 0;
counterBytes[1] = 0;
Bytes.setLong(counter, counterBytes, 2);
return alloc(counterBytes);
}
+ /** Given the per-run seed and label bytes, make a blank node. */
private Node alloc(byte[] labelBytes) {
- // UUID.nameUUIDFromBytes(seedBytes+labelBytes) uses MD5 but creates the digester
- // each time. It also stamps in the UUID version/variant bits.
- mDigest.update(seedBytes);
- mDigest.update(labelBytes);
- byte[] bytes = mDigest.digest(); // resets
- String hexString = Bytes.asHexLC(bytes);
+ byte[] input = new byte[seedBytes.length+labelBytes.length];
+ System.arraycopy(seedBytes, 0, input, 0, seedBytes.length);
+ System.arraycopy(labelBytes, 0, input, seedBytes.length, labelBytes.length);
+
+ // Apache Common Codec or Guava.
+ // The 2 versions of the code below should produce the same hex strings.
+ //
+ // The main difference from our perspective is that the Guava version
+ // returns a byte[]. Hashes are not "large numbers" - they are bit patterns --
+ // but it does create and use internal Java objects.
+ //
+ // We need to be careful about byte order. The long[] returned by
+ // MurmurHash3 (Apache Commons) needs to be stringified as "low bytes first"
+ // which is the reverse of %d-formatting for a long which is
+ // "high byte first" (in a left-to-right writing system).
+ //
+ // For byte output compatibility with byte[] from Guava,
+ // need to reverse the bytes of the longs so that it prints "low to high"
+ // Java works in big-endian -- high bytes first.
+
+ String hexString;
+ if ( true ) {
+ long[] x = MurmurHash3.hash128(input);
Review comment:
Thanks for the heads-up. It is also good to see the Murmur3 no longer uses `String.getBytes()`.
Changed to jena dependency to codec 1.14 and now calling `MurmurHash3.hash128x86(x)`
In fact, v1.14 has made a change unintentionally: it does apply the mask. I'll take this to the CODEC ticket.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
[GitHub] [jena] Claudenw commented on issue #673: JENA-1812: Switch to
Murmur3 for blank node allocation
Posted by GitBox <gi...@apache.org>.
Claudenw commented on issue #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673#issuecomment-576153847
There are 4 implementations of Murmur3: There are 32 and 128 bit implementations both available in x86 and x64 variants. The x86 and x64 variants are turned for different platforms but return different values. The version available in commons-codec is murmur3-x86-128.
The recent fix in commons-codec was a sign extension bug in seeds wherein if the seed was negative the conversion from int to long was not masked allowing the sign to extend across the upper bytes and changing the result with respect to the "C" code. The name was also changed to reflect the actual hashing method being implemented.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
[GitHub] [jena] Claudenw commented on a change in pull request #673:
JENA-1812: Switch to Murmur3 for blank node allocation
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #673: JENA-1812: Switch to Murmur3 for blank node allocation
URL: https://github.com/apache/jena/pull/673#discussion_r368123823
##########
File path: jena-arq/src/main/java/org/apache/jena/riot/lang/BlankNodeAllocatorHash.java
##########
@@ -113,20 +104,67 @@ public Node call() {
public Node create() {
counter++;
// Make illegal string bytes so can't clash with alloc(String).
- // It is different because it has zeros in it.
+ // It is different because it has a zero (illegal in a Java string) in it.
counterBytes[0] = 0;
counterBytes[1] = 0;
Bytes.setLong(counter, counterBytes, 2);
return alloc(counterBytes);
}
+ /** Given the per-run seed and label bytes, make a blank node. */
private Node alloc(byte[] labelBytes) {
- // UUID.nameUUIDFromBytes(seedBytes+labelBytes) uses MD5 but creates the digester
- // each time. It also stamps in the UUID version/variant bits.
- mDigest.update(seedBytes);
- mDigest.update(labelBytes);
- byte[] bytes = mDigest.digest(); // resets
- String hexString = Bytes.asHexLC(bytes);
+ byte[] input = new byte[seedBytes.length+labelBytes.length];
+ System.arraycopy(seedBytes, 0, input, 0, seedBytes.length);
+ System.arraycopy(labelBytes, 0, input, seedBytes.length, labelBytes.length);
+
+ // Apache Common Codec or Guava.
+ // The 2 versions of the code below should produce the same hex strings.
+ //
+ // The main difference from our perspective is that the Guava version
+ // returns a byte[]. Hashes are not "large numbers" - they are bit patterns --
+ // but it does create and use internal Java objects.
+ //
+ // We need to be careful about byte order. The long[] returned by
+ // MurmurHash3 (Apache Commons) needs to be stringified as "low bytes first"
+ // which is the reverse of %d-formatting for a long which is
+ // "high byte first" (in a left-to-right writing system).
+ //
+ // For byte output compatibility with byte[] from Guava,
+ // need to reverse the bytes of the longs so that it prints "low to high"
+ // Java works in big-endian -- high bytes first.
+
+ String hexString;
+ if ( true ) {
+ long[] x = MurmurHash3.hash128(input);
Review comment:
The original commons-codec `MurmurHash3.hash128` (like the Guava code) has a sign extension issue with the seed value. Since the seed is 104729 (for some reason) the hashes will work correctly. However a fair amount of work has gone into commons-codec recently and v 1.14 fixes the issue. Because of the change several of the `MurmurHash3.hash128(x)` methods have been deprecated. It is probably cleaner to call `MurmurHash3.hash128x86( input, 0, input.length, MurmurHash3.DEFAULT_SEED)` or `MurmurHash3.hash128x86( input, 0, input.length, 104729L)`
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org