ARK-Builders / ARK-Builders/Navigator
Composite identifiers
- Dominant language
- Kotlin
- Stars
- 16
- Forks
- 14
- PR merge metrics
- No merged PRs in 30d
Description
Right now, during indexing _ids_ are assigned to each _resource_ (initially known only by path). Tags, in its turn, are assigned to resources using these ids in order to be path-independent. We can't use random ids (like [UUID](https://en.wikipedia.org/wiki/Universally_unique_identifier)) since for any resource it's id must be computable on other devices (see [content-addressing](https://docs.ipfs.io/concepts/content-addressing)).
Unfortunately, cryptographic hash functions consume significantly more resources than [CRC32](https://en.wikipedia.org/wiki/Cyclic_redundancy_check), which we are using at the moment due to performance reasons. Using weak hash functions can lead to potential _conflicts of identifiers_ (situation when several resources have the same id). Probability of it is open question, but in practice I suspect that several resources out of 5K+ files collection do conflict by id.
These _collisions_ aren't harmful so far. Even in case of destructive operations being applied to an id which has several resources attached to it, only one of them is deleted (the resource which is visible to the user, see #140). This state of things can change in future.
One of potential solutions would be usage of _composite identifiers_: a stack of functions, where every next function is used when previous function produces a conflict in some given collection. This way, we could use our CRC32 for fast indexing and, in case of detected conflicts, falling back to a stronger function like [SHA256](https://en.wikipedia.org/wiki/SHA-2) or [MD5](https://en.wikipedia.org/wiki/MD5) applying it only for particular resources involved in the conflict.
Example:
* Resource _A_ has id `crc32: 1`.
* Resource _B_ has id `crc32: 2`.
* Resource _C_ has id `crc32: 1`.
Now we index _A_ and _B_ additionally with SHA-256.
Resource _C_ isn't needed to re-index here (but after implementation of #23 we might put such a task into the queue).
Result:
* Resource _A_ has id `crc32: 1, sha256: 17`.
* Resource _B_ has id `crc32: 2, sha256: 5`.
* Resource _C_ has id `crc32: 1`.
Maybe we can replace old id with the newer one, but for this we need to update tags storage with newer id.
If such feature is possible, we can go further and also **significantly increase indexing speed** by using file size as first (the weakest) hash function in the stack and calculating CRC-32 only for resources of the same size.
Contributor guide
Research direction
No files or tests are named. Start by tracing where resources are indexed and where tags store resource IDs, then determine how collisions and ID changes are represented. Done means conflicting resources can receive composite IDs without breaking tag references, with any indexing-speed change separately validated.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- kotlin
- Domain
- data, mobile-dev
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100