Remove dependency on unused ARC algorithm from hashicorp/golang-lru

[AkihiroSuda]

arc_cache.go seems modified to avoid hitting the patent (ipfs/go-ipfs-blockstore#20) of ARC algorithm, but I was confused as the code comments still state that it uses the ARC algorithm.

https://github.com/ipfs/go-ipfs-blockstore/blob/03acccfc7eae2b977b3ec49663b6e23b6a1bdf9e/arc_cache.go#L16-L29

Could you add code comments to clarify the patent status of this file?

[welcome]

Thank you for submitting your first issue to this repository! A maintainer will be here shortly to triage and review.
In the meantime, please double-check that you have provided all the necessary information to make this process easy! Any information that can help save additional round trips is useful! We currently aim to give initial feedback within two business days. If this does not happen, feel free to leave a comment.
Please keep an eye on how this issue will be labeled, as labels give an overview of priorities, assignments and additional actions requested by the maintainers:

• "Priority" labels will show how urgent this is for the team.
• "Status" labels will show if this is ready to be worked on, blocked, or in progress.
• "Need" labels will indicate if additional input or analysis is required.

Finally, remember to use https://discuss.ipfs.io if you just need general support.

[AkihiroSuda]

It would be also nice if go-ipfs-blockstore could avoid importing hashicorp/golang-lru which still contains ARC codes (hashicorp/golang-lru#73) , or switch to an ARC-free fork.

https://github.com/ipfs/go-ipfs-blockstore/blob/8aad3d8b2d942b8cf8fd90ee9b6dc958935bfe05/go.mod#L4

[AkihiroSuda]

@Stebalien could you take a look? 🙏

[AkihiroSuda]

@guseggert @Stebalien

Would it be possible to replace github.com/hashicorp/golang-lru with @ktock 's ARC-free fork?
ktock/golang-lru@ec551be

We (the containerd project) are already using his fork: https://github.com/containerd/nerdctl/blob/9efa1234350bab9a5150fbb5b7f3655aa24f82e1/go.mod#L172-L173

[Stebalien]

I'm happy to accept a patch with the comment requested in the original issue, but I'd rather not switch to a random fork (especially when upstream is active as we're likely going to switch to their new generic version sooner rather than later).

Patents aren't like copyright. Has a lawyer told you you can't import that library? Patents are all about using patented technologies.

[BigLep]

Given we haven't heard back more on this, it's not clear the priority of this right now.

[AkihiroSuda]

patch

I'm not feeling that I'm the right person to submit this patch, as I don't have good understanding of the code and the patent.

I'd appreciate if we can get the patch from the maintainers or at least somebody who has better understanding than me.

Has a lawyer told you you can't import that library?

No, importing the library is probably okay as long as it is not used, but it is slightly hard to attest that the patented code is not actually used, when it is imported.
( So, in our project we run go tool nm | grep NewARC in the CI: https://github.com/containerd/nerdctl/blob/v1.1.0/hack/verify-no-patent.sh )

[lidel]

It seems the problem was resolved in the upstream library – ARC code was moved to separate package:

• Release Notes: https://github.com/hashicorp/golang-lru/releases/tag/v2.0.3

So the remaining work here is to:

• switch boxo to hashicorp/golang-lru v2.0.3 or later
• remove mentions of arccache and ARC, as we've switched to TwoQueueCache long time ago, but comments and names are still here

PR: #367