<div dir="ltr"><div dir="ltr">
<div>Thank you for those references! The docs by Ben Manes look like a
good starting point to learn more about implementing a concurrent cache.</div><div><br></div><div>To
elaborate on my motivation: I work as an educator explaining concepts
behind Java extensions in a corporate context.
LRU caches seemed like an interesting choice as an example demonstrating
the new interfaces for sequenced collections together with virtual
threads. But my main interest (that's why I asked here) is in
understanding design considerations for the Java core libraries so I can
explain them to others.</div><div><br></div><div>When preparing the example, I stumbled upon what I perceived as gaps in the core libraries:</div><div>- Collections.synchronizedSequencedSet and similar wrappers are not provided although Collections.synchronizedSortedSet (and others) are</div><div>- There is no sequenced collection with external ordering in java.util.concurrent</div><div><br></div><div>Here is a summary of what I infer from our interaction: </div><div>-
Synchronized wrappers are of limited use. The benefit of adding them
for sequenced collections is unclear, despite already providing them for
other interfaces extending Set and Map.</div><div>- The implementation
of concurrent versions of sequenced collections with external ordering
is non-trivial
and the benefit of adding them to the core libraries is unclear. For
specific use cases like concurrent caches there are external libraries.<br></div><div>- Although the mentioned gaps are apparent, it is unlikely that they will be filled before clarifying how that could be useful.<br></div><div><br></div><div>Assuming
that's a fair summary, I think I understand better now why the
mentioned gaps are there. So, thanks again for your input!</div>
</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Nov 14, 2023 at 8:43 PM Stuart Marks <<a href="mailto:stuart.marks@oracle.com">stuart.marks@oracle.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<p>Ah, so you want a concurrent cache! This is why it's important to
talk about use cases. Turns out there are a lot of subtle issues
here, and there has been a lot of work in this area outside the
JDK. For example, a bit of searching turned up this Stack Overflow
question [1]. The answers aren't particularly valuable, but there
is this comment [2] from Ben Manes, who knows something about this
topic:</p>
<p>
</p><blockquote type="cite">ConcurrentLinkedHashMap [3] beget Guava's
Cache [4] which beget Caffeine. [5] [6]<br>
</blockquote>
<p></p>
<p>[1]:
<a href="https://stackoverflow.com/questions/40239485/concurrent-lru-cache-implementation" target="_blank">https://stackoverflow.com/questions/40239485/concurrent-lru-cache-implementation</a></p>
<p>[2]:
<a href="https://stackoverflow.com/questions/40239485/concurrent-lru-cache-implementation#comment67809840_40239485" target="_blank">https://stackoverflow.com/questions/40239485/concurrent-lru-cache-implementation#comment67809840_40239485</a></p>
<p>[3]:
<a href="https://github.com/ben-manes/concurrentlinkedhashmap/wiki/Design" target="_blank">https://github.com/ben-manes/concurrentlinkedhashmap/wiki/Design</a></p>
<p>[4]:
<a href="https://github.com/ben-manes/concurrentlinkedhashmap/blob/wiki/ConcurrentCachingAtGoogle.pdf" target="_blank">https://github.com/ben-manes/concurrentlinkedhashmap/blob/wiki/ConcurrentCachingAtGoogle.pdf</a></p>
<p>[5]:
<a href="http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html" target="_blank">http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html</a></p>
<p>[6]: <a href="https://github.com/ben-manes/caffeine" target="_blank">https://github.com/ben-manes/caffeine</a></p>
<p>It looks like "ConcurrentLinkedHashMap" is a concurrent hash map
that maintains ordering but that doesn't actually maintain a
linked list of entries in the same way as LinkedHashMap. I haven't
looked closely at the implementation, but I'd guess that it
maintains ordering using a weakly consistent side data structure.</p>
<p>Weak consistency seems to be the flavor of most concurrent data
structures; you give up non-essential consistency in order to gain
concurrency. For example, ConcurrentHashMap's views' iterators are
"weakly consistent" which roughly means that an element reported
by the iterator was a member at one time, but elements might not
be reported by the iterator if they were added or removed sometime
during the iteration. For an LRU cache, weaker semantics might be
that you don't care about the exact ordering of recency of usage.
(Indeed, ordering of events is somewhat ill-defined in a
concurrent system.) Instead, you probably want things that were
used fairly recently to stay in the cache longer, while things
that haven't been used recently should tend to expire earlier.</p>
<p>I'd suggest looking at some of these caching libraries. Or if
you're keen to roll your own, read some of the design documents.
Which might convince you that you don't want to roll your own. :-)</p>
<p>s'marks<br>
</p>
<br>
<div>On 11/10/23 3:26 AM, Sebastian Fischer
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div dir="ltr">
<div>Hi Stuart.</div>
<div><br>
</div>
<div>Thanks, I understand now how the limited thread safety of
"synchronized" wrappers has led to not adding new ones.</div>
<div><br>
</div>
<div>My use case is an LRU-cache that is accessed by a large
number of (virtual) threads. </div>
<div><br>
</div>
<div>In my initial implementation I constructed a
LinkedHashMap passing true for the accessOrder parameter,
implemented removeEldestEntry appropriately and then wrapped
it using Collections.sequencedMap. Thanks to this interface,
I did not need a specialized wrapper supporting putLast or
pollFirstEntry to manage the capacity myself. So, wrapping a
LinkedHashMap seemed like a viable approach at first.<br>
</div>
<div><br>
</div>
<div>But, the map is being used by many threads, and a
synchronized wrapper is governed by a single exclusion lock.
I improved throughput using a concurrent map supporting
concurrent reads and (some) writes. Here is a simplified
example using a sequenced collection instead of a map.</div>
<div><br>
</div>
<div> public record RecentlyAccessed<T>(int capacity,
SequencedCollection<T> elements) {<br>
public RecentlyAccessed(int capacity) {<br>
this(capacity, new
ConcurrentLinkedDeque<>());<br>
}<br>
<br>
public void add(T elem) {<br>
elements.addLast(elem);<br>
while (capacity < elements.size()) {<br>
elements.removeFirst();<br>
}<br>
}<br>
}</div>
<div><br>
</div>
<div>As the add method is not synchronized, the real capacity
might deviate from the intended capacity. Additionally,
ConcurrentLinkedDeque can contain duplicate elements. I
could implement repositioning by removing all occurrences of
elem before calling addLast but that would introduce an
intermediate state where elem is not present (even if it was
present before) due to the lack of synchronization. </div>
<div><br>
</div>
<div>In my current implementation of the cache I use a
ConcurrentHashMap with an additional ConcurrentLinkedDeque
holding keys in access order telling me which entries to
remove from the map. But this approach is not really
thread-safe due to missing synchronization and incorrect due
to duplicate keys in the deque.<br>
</div>
<div><br>
</div>
<div>I was hoping to use a ConcurrentLinkedHashSet (or really
ConcurrentLinkedHashMap, but both seem useful), where
repositioning would presumably be implemented in a
thread-safe way. Ideally, the option to override
removeEldestEntry would allow it to also maintain the
intended capacity in a thread-safe way.</div>
<div><br>
</div>
<div>I'm not familiar enough with the implementation of
concurrent collections to judge whether my hope is
justified. But essentially, my use case would be an
LRU-cache that does not use a single exclusion lock to
improve concurrent access by a large number of (virtual)
threads.</div>
<br>
<div>Sebastian<br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Fri, Nov 10, 2023 at
1:03 AM Stuart Marks <<a href="mailto:stuart.marks@oracle.com" target="_blank">stuart.marks@oracle.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Sebastian,<br>
<br>
Regarding the lack of "synchronized" wrappers for Sequenced
Collections: the main <br>
issue is that they provide only a limited sense of "thread
safety" and as such don't <br>
add much actual value. Specifically, the synchronized
wrappers hold a lock only <br>
around invocations of individual methods. This omits a large
class of common, <br>
compound operations on collections, such as check-then-act
operations and bulk <br>
operations that involve iteration or streaming. These
operations aren't thread-safe <br>
with synchronized wrappers. To perform these operations
safely from multiple <br>
threads, the client needs to do its own locking around the
compound operation. This <br>
mostly defeats the purpose of the synchronized wrappers.<br>
<br>
If you need to use something like
LinkedHashMap/LinkedHashSet from multiple threads, <br>
my recommendation is to write your own class that exposes
exactly the set of <br>
operations you need and that does proper locking for those
operations. It can then <br>
delegate the appropriate operations to an internal
collection.<br>
<br>
Regarding concurrent collections: these are mainly intended
for operations to <br>
proceed concurrently on different parts of the collection,
such as updating <br>
different mappings in a ConcurrentHashMap simultaneously, or
having <br>
producers/consumers operating on different ends of a Queue.
I note that <br>
historically, the concurrent collections haven't included
concurrent versions of <br>
LinkedHashSet/Map or general-purpose List implementations.
(There is <br>
CopyOnWriteArrayList/Set, but they're highly specialized and
can be prohibitively <br>
expensive for use cases that involve a lot of updates.)<br>
<br>
While it looks like things are missing from the concurrent
collections, I'd have to <br>
ask what use cases would be satisfied by adding something
like a "concurrent <br>
sequenced set" (or map) that wouldn't be fulfilled with a
customized wrapper around <br>
LinkedHashSet/Map.<br>
<br>
s'marks<br>
<br>
<br>
On 11/2/23 4:56 AM, Sebastian Fischer wrote:<br>
> Hello.<br>
><br>
> I am new to this list so might have missed previous
discussion about this but <br>
> could not find what I was looking for in the archives.<br>
><br>
> The Sequenced collections JEP adds the following static
methods to <br>
> java.util.Collections.<br>
><br>
> - unmodifiableSequencedCollection<br>
> - unmodifiableSequencedSet<br>
> - unmodifiableSequencedMap<br>
><br>
> However, the set of static methods returning
thread-safe versions of their <br>
> arguments (like synchronizedCollection,
synchronizedSet, and synchronizedMap) has <br>
> not been extended.<br>
><br>
> As a consequence, I don't see a straightforward way to
create thread-safe <br>
> sequenced sets or maps where encounter-order
corresponds to insertion order (like <br>
> LinkedHashSet or LinkedHashMap) and access them as
SequencedSet or SequencedMap.<br>
><br>
> When using the available methods mentioned above, the
result is not a sequenced type.<br>
><br>
> For predefined sets and maps where encounter order
corresponds to natural order, <br>
> there are the following methods in
java.util.Collections.<br>
><br>
> - synchronizedNavigableSet<br>
> - synchronizedNavigableMap<br>
> - synchronizedSortedSet<br>
> - synchronizedSortedMap<br>
><br>
> However, these methods cannot be used with
LinkedHashSet or LinkedHashMap.<br>
><br>
> The following methods would be useful in order to
create thread-safe sequenced <br>
> collections where encounter order is insertion order,
but they are currently not <br>
> provided.<br>
><br>
> - synchronizedSequencedCollection<br>
> - synchronizedSequencedSet<br>
> - synchronizedSequencedMap<br>
><br>
> What are the reasons for or against adding these
methods?<br>
><br>
> There are also no implementations of concurrent
sequenced sets and maps where <br>
> encounter order is insertion order in
java.util.concurrent. All of the provided <br>
> concurrent sequenced sets and maps are based on natural
order, and consequently do <br>
> not support addFirst, and so on.<br>
><br>
> Are there plans to add concurrent sequenced collections
that support the whole <br>
> interface of sequenced collections?<br>
><br>
> Kind regards,<br>
> Sebastian<br>
</blockquote>
</div>
</div>
</blockquote>
</div>
</blockquote></div></div>