`NonBlockingHashSet` retains deleted values

[ikhoon]

`NonBlockingHashSet` retains deleted values

[ikhoon]

As NonBlockingHashSet delegates to NonBlockingHashMap, the problem is also reproduced in NonBlockingHashMap

NonBlockingHashMap<MyEntry, String> map = new NonBlockingHashMap<>();
map.put(entry1, "a");
map.remove(entry1);
map.put(entry2, "a");
// entry1 is revived.
assert map.keySet().toArray()[0] == entry1;

[nitsanw]

The issue here is that:

1. NBHM retains deleted keys (values in the set). This is a potential GC issue, but is inherent to the implementation.
2. MyEntry is not a good key

Your code asserts that 2 entries are equal if the value is the same, ignoring updatedAt. NBHM therefore treats them as such and will not replace the reference to the first key with the second.

[nitsanw]

I'm closing, please comment if you feel this is breaking the Map API somehow.

[ikhoon]

please comment if you feel this is breaking the Map API somehow.

Yes, I think so. It is unexpected behavior and causes bugs in our project.

• Background
  MyEntry is an intentional example to reproduce the problem. We provide Endpoint that represents a remote host and port. In addition to host and port, Endpoint also has weight property for client-side load balancing.
  Endpoint excludes the additional property - weight from equals and hashCode for better comparison of remote peers.
  https://github.com/line/armeria/blob/bcb621e46c26f0ac84b4b820687383a99b509019/core/src/main/java/com/linecorp/armeria/client/Endpoint.java#L666-L668

• Problem
  We used NonBlockingHashSet for maintaining healthy endpoints. When a weight of a endpoint is changed, we need to remove the old endpoint and add the new endpoint.
  However, NonBlockingHashSet does not replace the old endpoint with the new endpoint even though I called remove and put explicitly.
  https://github.com/line/armeria/pull/3927/files#diff-4229d073a6969fa85c1d6fe69c6c3d1c957a6a240dd77e3e397b3bf4c96792f0
  As a workaround, I decided to use ConcurrentHashMap.

- final Set<Endpoint> healthyEndpoints = new NonBlockingHashSet<>();
+ final Set<Endpoint> healthyEndpoints = ConcurrentHashMap.newKeySet();

[nitsanw]

@ikhoon I understand your frustration. I don't think this is an issue that we can easily fix within the confines of the current implementation however.

• NBHM hangs on to deleted keys until resize.
• NBHM will not overwrite key (deleted or otherwise) with a new key which is equal to it on put.

Changing this latter behaviour will slow down all operations on map by adding more code to a critical path which is already crowded. It can be done (by specialising behaviour on previous value being TOMBSTONE and key being equal), but I would need a strong argument from Map/Set documentation which clearly shows this behaviour to be wrong.

[ikhoon]

Thanks for your consideration. As I knew the expected behavior of NBHM, I can carefully use it. Mentioning this behavior in Javadoc would be super helpful for users. 🙇‍♂️