Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Potential patent problem with golang-lru.ARCCache #6590

Closed
MichaelMure opened this issue Aug 20, 2019 · 3 comments · Fixed by #6592
Closed

Potential patent problem with golang-lru.ARCCache #6590

MichaelMure opened this issue Aug 20, 2019 · 3 comments · Fixed by #6592
Labels
kind/bug A bug in existing code (including security flaws)

Comments

@MichaelMure
Copy link
Contributor

Version information:

go-ipfs v0.4.22

Description:

I'm obviously not a lawyer and not even really versed in those kind of things, but golang-lru state that:

ARC has been patented by IBM, so do not use it if that is problematic for your program.

https://github.com/hashicorp/golang-lru/blob/master/doc.go#L16-L17

go-ipfs does use ARC, specifically through go-ipfs-blockstore. Would that be a problem?
@MichaelMure MichaelMure added the kind/bug A bug in existing code (including security flaws) label Aug 20, 2019
@Stebalien
Copy link
Member

At the moment, this issue would only concern non-OSS forks of go-ipfs: https://www-03.ibm.com/press/us/en/pressrelease/7473.wss.

Postgres appears to have had the same issue so they just switched to a slightly different algorithm: http://www.varlena.com/GeneralBits/96.php. We can probably just switch to the 2Q cache https://github.com/hashicorp/golang-lru/blob/master/2q.go.

Stebalien added a commit to ipfs/go-ipfs-blockstore that referenced this issue Aug 20, 2019
@Stebalien
cache: switch to 2q
82da4c4 
Due to patent concerns in closed-source downstream products:
ipfs/kubo#6590
@Stebalien Stebalien mentioned this issue Aug 20, 2019
Merged
@Stebalien
Copy link
Member

Simple fix: ipfs/go-ipfs-blockstore#20

@parkan
Copy link

parkan commented Aug 20, 2019

good find @Stebalien, I was wondering whether this patent was in the OSS pool... 2Q looks nearly indistinguishable in general case performance from ARC based on the paper so this fix seems reasonable

Stebalien added a commit that referenced this issue Aug 20, 2019
@Stebalien
switch from ARC cache to a 2Q cache
055803d 
fixes #6590 (potential non-OSS patent issue)
@Stebalien Stebalien mentioned this issue Aug 20, 2019
Merged
@Stebalien Stebalien mentioned this issue Aug 23, 2019
Closed
ralendor pushed a commit to ralendor/go-ipfs that referenced this issue Jun 6, 2020
@Stebalien
switch from ARC cache to a 2Q cache
3e00c7a 
fixes ipfs#6590 (potential non-OSS patent issue)
ralendor pushed a commit to ralendor/go-ipfs that referenced this issue Jun 6, 2020
@Stebalien
switch from ARC cache to a 2Q cache
89510f7 
fixes ipfs#6590 (potential non-OSS patent issue)
ralendor pushed a commit to ralendor/go-ipfs that referenced this issue Jun 8, 2020
@Stebalien
switch from ARC cache to a 2Q cache
7542207 
fixes ipfs#6590 (potential non-OSS patent issue)
ralendor pushed a commit to ralendor/go-ipfs that referenced this issue Jun 8, 2020
@Stebalien
switch from ARC cache to a 2Q cache
63f72bb 
fixes ipfs#6590 (potential non-OSS patent issue)
ralendor pushed a commit to ralendor/go-ipfs that referenced this issue Jun 8, 2020
@Stebalien
switch from ARC cache to a 2Q cache
0c4d034 
fixes ipfs#6590 (potential non-OSS patent issue)
ralendor pushed a commit to ralendor/go-ipfs that referenced this issue Jun 8, 2020
@Stebalien
switch from ARC cache to a 2Q cache
7f62b20 
fixes ipfs#6590 (potential non-OSS patent issue)
@BrandonWeng BrandonWeng mentioned this issue Feb 3, 2023
Merged
BrandonWeng added a commit to sei-protocol/sei-cosmos that referenced this issue Feb 3, 2023
@BrandonWeng
[store] bump CommitKVStoreCache limit and switch to 2Q from arc (#152)
7333425 
## Describe your changes and provide context
IRRC we had discussions around bumping the limit for the inter-block
cache since 1k is pretty little for our volume of TXs per block. Im
setting it to 100k to be the same as the BoundedCacheKv store

While I was investigating the race condition issue in the LRU cache, I
saw that several repos brought up concerns around using ArcCache in
their code as it's been patented by IBM (and later sold to Intel)

hashicorp/golang-lru#31 
hashicorp/golang-lru#73 

ipfs/kubo#6590
ipfs/go-ipfs-blockstore#20

Postgres and IPFS replaced it with 2Q, which based on the whitepaper
should have the same performance as ARC.
## Testing performed to validate your change
Deployed a LT cluster with these changes and saw no impact to consensus
and the performance (with LT clients running) is similar

![image](https://user-images.githubusercontent.com/18161326/216499319-be5ae693-242f-453c-8073-414bf5f810bd.png)
codchen pushed a commit to sei-protocol/sei-cosmos that referenced this issue Feb 12, 2023
@BrandonWeng @codchen
[store] bump CommitKVStoreCache limit and switch to 2Q from arc (#152)
1d173a5 
## Describe your changes and provide context
IRRC we had discussions around bumping the limit for the inter-block
cache since 1k is pretty little for our volume of TXs per block. Im
setting it to 100k to be the same as the BoundedCacheKv store

While I was investigating the race condition issue in the LRU cache, I
saw that several repos brought up concerns around using ArcCache in
their code as it's been patented by IBM (and later sold to Intel)

hashicorp/golang-lru#31 
hashicorp/golang-lru#73 

ipfs/kubo#6590
ipfs/go-ipfs-blockstore#20

Postgres and IPFS replaced it with 2Q, which based on the whitepaper
should have the same performance as ARC.
## Testing performed to validate your change
Deployed a LT cluster with these changes and saw no impact to consensus
and the performance (with LT clients running) is similar

![image](https://user-images.githubusercontent.com/18161326/216499319-be5ae693-242f-453c-8073-414bf5f810bd.png)
@lidel lidel mentioned this issue Mar 15, 2023
Closed
Jorropo pushed a commit to ipfs/go-libipfs-rapide that referenced this issue Mar 23, 2023
@Stebalien
cache: switch to 2q
1c203d9 
Due to patent concerns in closed-source downstream products:
ipfs/kubo#6590


This commit was moved from ipfs/go-ipfs-blockstore@82da4c4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
kind/bug A bug in existing code (including security flaws)
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

switch from ARC cache to a 2Q cache ipfs/kubo
3 participants
@parkan @MichaelMure @Stebalien