Switch `net::LruCache` to not use `LinkedHashSet`

[Rjected]

Right now the LruCache data structure uses a LinkedHashSet. This data structure is responsible for a large number of allocations. We don't strictly need to use this dependency, and there may be related memory leaks, re: https://github.com/paradigmxyz/reth/issues/6765#issuecomment-1966558358

[PanGan21]

Hi @Rjected , what would you suggest to use instead of LinkedHashSet ?

[mattsse]

essentially schnellru::LruMap::new(ByLength::new(max_length))

but there's one problem:

https://github.com/paradigmxyz/reth/blob/6725d43f053d3eba66c0a516af041c5018452bd9/crates/net/network/src/cache.rs#L39-L39

I don't think the api supports this, but we currently rely on this for some cleanup:

https://github.com/paradigmxyz/reth/blob/6725d43f053d3eba66c0a516af041c5018452bd9/crates/net/network/src/transactions/fetcher.rs#L407-L410

so unclear if we can easily do this

[AbnerZheng]

Will give it a try, since LruMap support pop_oldest, which is the same as LinkedHashSet::pop_front https://docs.rs/schnellru/latest/schnellru/struct.LruMap.html#method.pop_oldest

[mattsse]

this is unfortunately not equivalent because this forcefully pops, so we'd always need to check limits first

[AbnerZheng]

We can create a LRUMap with len = limit + 1, then the code of insert_and_get_evicted would keep the same except replacing LinkedHashSet::pop_front with LruMap::pop_oldest.

[Rjected]

We can create a LRUMap with len = limit + 1, then the code of insert_and_get_evicted would keep the same except replacing LinkedHashSet::pop_front with LruMap::pop_oldest.

this would impact the ordering though, right?

[AbnerZheng]

In my opinion, they are both following the same logic, remove the least recently used entry and return it.

[mattsse]

remove the least recently used entry and return it.

but that's all it does, no insert, so this needs to be done manually, so I guess we need the wrapper type and implement insert_and_get_evicted manually

[AbnerZheng]

Ah, I got it. You want to find a LRU library that is able to support insert_and_get_evicted natively, even though the current implementation of LRUCache implemented the logic manually.

[ghost]

@Rjected I just go through the implementation of the LinkedHashSet and it's not optimal, and at the same time the way we use the unlimited memory for LRU can cause crash. If everyone is busy with other issues, then I can take this one.

[onbjerg]

@0xJepsen can you type a short msg here so I can assign you?

[github-actions[bot]]

This issue is stale because it has been open for 21 days with no activity.