The SHA1 hash of maps should not depend on the key ordering

[asciiansi]

(original question below)

Currently, the content/value hashes for a map depend on the key ordering - with different orders (possibly arising from different concrete map implementations), we generate different content/value hashes for the 'same' map, which means:

• Entities with a map key (useful, but so far undocumented) aren't always returned/joined correctly.
• (Lesser impact, but) some documents that are essentially the same (varying only in key order) are stored under multiple content-hashes (sub-optimal, but no undesired behaviour)

---

(old proposed solution, for posterity, see #474 for what I ended up doing):

• The SHA1 hashes of maps should not depend on the key ordering - we'll take inspiration from java.util.Map's hashcodes here.
• Users that want to can preserve the old behaviour for document content-hashes
• Users that want to can preserve the old behaviour for map-keys (independently from the previous content-hash behaviour)
• Users that want to can migrate their Kafka streams via a tool.

---

(original question)

Is it intended that map keys for a crux.db/id always must be in the same order, despite having the same content/hash? Querying for an entity using (crux/entity db {:a 1 :b 1}) is not the same as (crux/entity db {:b 1 :a 1}) for example. The query only seems to work for me using the same key order as the transacted entity.

I can semi-understand why this is case but nonetheless it's a bit surprising for keys and lead to some brief debugging. Specifically, it seems a bit strange as maps are by definition unordered and often manipulating programatically.

Moreover, it's typical in a larger system when dealing with dynamically constructed keys to make use of assoc, update, etc. which becomes very dangerous and instead requires construction of a new map, creating even more garbage. I currently work around this simply by using a function every time I create keys dynamically, but there are a few cases where this is a bit annoying.

I find maps in general useful as keys since they allow a composite and additionally remove some overhead for reaching into an entity via a query using crux/q. I would prefer other options for key and would love to discuss further if you are willing along with use-cases and reasoning. For now, I'm mostly using maps to workaround dissatisfaction with other key types which aren't really suitable for my apps.

For context, I am using 100% RocksDB on both ends (though I prefer/will eventually switch to LMDB). Here are my deps:

juxt/crux-core                      {:mvn/version "19.09-1.5.0-alpha"}
juxt/crux-rocksdb                   {:mvn/version "19.09-1.5.0-alpha"}

At the very least, this should be documented given I found it surprising if it's not considered a bug. Thanks.

[refset]

Thanks for reporting this @asciiansi - I hope you find the fix satisfactory. We will be releasing imminently.

[adam0z]

As mentioned in docs, maps are allowed as valid :crux.db/id. Do I understand it properly that there is no difference in performance using maps as _id?
I would like to create my own _id like:

#crux/id {:type :person :source_id 42 :key "age"}

instead of uuid, or string like "person_42_age"
and use it also as a foreign key in relations.

[jarohen]

Yep, that's correct - we convert entity ids, attributes and values to content hashes early on and then use those content hashes throughout the query engine.

[adam0z]

Do you use SHA1 hashes and if so do you have any collision handle?
https://pthree.org/2014/03/06/the-reality-of-sha1/
Or is there an assumption that collisions would not become likely?

[jarohen]

Yes - we currently use SHA1 without a collision handle, with the assumption that collisions are sufficiently unlikely.