Hi Benedict, Thank you for offering. It would be very helpful to try it out indeed, if it isn’t too much hassle to set it up. Would the ordered list be singly linked? I’m hoping so because of cycles.
The Trie memtables did indeed work out very well, after a minor tweak. Thanks, /Erik On 27 Jul 2026, at 12:22, Benedict Elliott Smith <[email protected]> wrote: This Message Is From an External Sender This message came from outside your organization. <https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op2yXeLH-cgOf_AgNzK--MM6SvdmzeSBbLXoROvTgptQGdDGwfUKdAktnYG2qvQcq9L6KUaPETz4eMU375Ut0VhHiRpeOW-8nS06Y6Q3S4GIbXx1TqPm0LnZcV_awH8$> Report Suspicious CASSANDRA-7282 is pretty much a complete implementation, and should be easily rebased. I wouldn't mind doing it if it helped test out such an interesting GC improvement, it is anyway a shame it has languished for so long. Trie memtables seem like they're already well placed for this experiment. On 2026/07/27 10:09:00 Dmitry Konstantinov wrote: > Hi Erik, > Thanks for the email! We're always happy to welcome JVM developers here. > We also have Trie memtable implementation for memtable <partition key ---> > partition data> map - [1],[2],[5] > It can keep some portion of data off-heap also but the underlying objects > are still in heap: > > [image: image.png] > > There is an idea about extending Trie implementation and moving more parts > of it to off-heap - [3]. > There is also another idea for the map but it has not been implemented so > far: [4] > > [1] > https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW-9xcjyrA$ > > [2] > https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW8x7ctJIw$ > [3] > https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW-71YRlTg$ > > [4] > https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW-07j5veQ$ > [5] > https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW_72alOLg$ > > Regards, > Dmitry > > On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev < > [email protected]<mailto:[email protected]>> wrote: > > > Hi, > > > > I’m one of the ZGC devs. Have been playing around a bit with an > > interesting algorithmic extension of generational ZGC using a form of > > reference counting in the old generation. This allows us to essentially > > have young generation collections reclaim zero reference count old objects, > > and free up acyclic garbage in the old generation as well, just before it > > promotes objects from the young generation to the old generation. The > > consequence is that as long as long-lived garbage is acyclic, we pretty > > much don’t need to do major collections other than to defragment memory > > every now and then. But the actual pressure to reclaim old garbage vanishes > > and is handled from the young collections. > > > > One quirk is that in this scheme, we can reclaim objects that never have > > an in-degree higher than 6, because then accounting isn’t free any longer > > (we are using available object header bits). > > > > I was delighted to find that cassandra memtables using skip lists are > > acyclic. But unfortunately I think the base nodes of the skip lists get too > > high in-degree and ultimately end up spoiling eager reclamation. > > > > So I’m wondering, how annoying would it be to change this map > > implementation to something that is both acyclic and has ref counts lower > > than 7 for any internal nodes? If that’s not too tricky to do, I suspect we > > could collapse the GC overheads related to having memtables in-heap. Maybe > > a tree structure or something? What do you guys think? If it’s too annoying > > that’s good feedback too. > > > > Please let me know if this is the wrong place for this kind of discussion. > > > > Thanks, > > /Erik > > > > -- > Dmitry Konstantinov >
