ARK-Builders / ARK-Builders/Navigator

Composite identifiers

Open
#147 0 comments 0 reactions 0 assignees View on GitHub
concept performance UX
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.