You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@cassandra.apache.org by Erik Osterlund via dev <de...@cassandra.apache.org> on 2026/07/27 12:30:48 UTC

Re: [External] : Re: MemTables and ZGC old gen reference counting

Hi Dmitry,

Thanks for the reply and the pointers, it’s very helpful. As a GC developer, I naturally get interested when people are moving data off-heap because of GC issues.

I tried out the Trie memtable data structure. Unfortunately, it looks like there is a cycle caused by InMemoryTrie.ApplyState which has an implicit this$0 field due to being an internal class. I tried patching it up a bit locally to pass that around as an argument instead. Still some slab allocator (not sure what it’s fore) seemingly causing in-degree > 6 which the algorithm is a bit sensitive to right now. But with the patched Trie and unslabbed_heap_buffers it works beautifully well and I see several GB reclaimed old gen memory in young collections, without having to trace the old generation. It’s CPU spending is now invariant of the old gen live set size, as long as we can stick to these rules I mentioned.

This feels rather encouraging IMO. :-)

Thanks,
/Erik

On 27 Jul 2026, at 12:09, Dmitry Konstantinov <ne...@gmail.com> wrote:

This Message Is From a New Sender
You have not previously corresponded with the sender of this message.
<https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op20OCZG1EegmzBtO1N5l_0NlI-ToMvOCf6nTg_MDwHHjAYeHpOwVpF74U5Z9U9hvMImUXCmFpRqWmpISVsORhymuGGN-sm7Tr4G63oCvH3p-fuixd7qWTAOw5ah2Ug$>
Report Suspicious

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.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://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html<https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w58ED4ei$>
[2] https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf<https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6wwydJXc_$>
[3] https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57+Flat+keys+and+trie+interfaces<https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3z0dj6w$>
[4] https://issues.apache.org/jira/browse/CASSANDRA-7282<https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w33qzYRA$>
[5] https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java<https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3Jt98gW$>

Regards,
Dmitry

On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev <de...@cassandra.apache.org>> 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

Re: [External] : Re: MemTables and ZGC old gen reference counting

Posted by Erik Osterlund via dev <de...@cassandra.apache.org>.

So I’m trying out a sort of reference count coalescing technique that has good synergies with the current generational ZGC design. The idea is that between two young collection starts, for each reference field, only the first and the last store matters; all other ref counting involving that reference field cancel each other out.

The first store is already detected by our store barriers, and the last store is lazily processed by either the first store of the next young collection epoch, or its remembered set scanning. The first store of an epoch can peek at our precise remembered set (that we already have) to assess whether there was a store in the previous epoch, which means there should have been a last increment.

The algorithm only tracks old-to-old references, and old generation roots (including young-to-old edges), are accounted separately.

The main reason for the signedness is that if you remove an edge in a new epoch but added an edge to the same object the previous epoch, the accounting for the decrement might happen before the increment. After young generation marking terminates, the reference counts get ripe and stabilize so they can be used to make decisions about what should be freed.

Other than that, when objects move in the old generation, we can temporarily slip into negative territory because the application thread doesn’t understand there is a from-space object with pending last increments from the previous epoch. Then, the GC will apply reference counts later on that stabilize the counters before young generation marking terminates.

While a major collection is going on, I’m currently unable to perform eager reclamation, but the ability heals after the major collection finishes. The reference counts are kept track of throughout, and as objects are promoted during old gen marking, the newly promoted objects may get eagerly reclaimed. But the oldest garbage has to wait until major collection finishes, currently. And I don’t yet prune the dead-to-live reference counts found by the major collections. Might want to iron some of that out when I get time.

Hope this helps.

/Erik

On 28 Jul 2026, at 15:45, Benedict Elliott Smith <be...@apache.org> 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-cikv1DqfbnUOO1r6Y_GKhbW4G1_v8_E4yh4z7O20I7abz8KKFmvyQLB-Razq-v5yMcf9_nOivia_cSncVJaj13MuXbk8_GVENtki_WXRjw10JSMrF35cBQ$>
Report Suspicious

Could I ask why you need negative numbers? And is there any reason this couldn't be reset by an Old Gen GC, or is that too onerous? Intuitively, it seems likely that the counter could be reset and incremented once for each incoming reference encountered during GC, so that this feature is disabled across an Old Gen GC, but potentially of wider impact between GCs?

I'll admit, it's unclear how much benefit this refinement would have even if it were possible. I'm simply interested in the shape of the problem at this point. The idea of a hybrid refcount/tracing GC makes a lot of sense for memtables, and no doubt other workloads with skewed lifetimes that distort GC. A little over a decade ago I implemented a hybrid refcount+RCU/epoch scheme for Memtable slab management, so that slabs could be compacted and reclaimed, although it was not adopted. It would be neat for the native GC to support a similar capability.

On 2026/07/28 11:24:14 Erik Osterlund via dev wrote:
> Absolutely. In the current prototype, I’m using 4 object header word bits to track reference counts. It needs to be signed because of arcane reasons. So I can track a range from -7 to 7, and occasionally there will be one ref count stale that is artificial. When there is either overflow or underflow, the ”uncertain” reference count with a value of -8 is installed, meaning that we have lost track and must conservatively assume for the rest of the object life time that it might have a positive reference count. We just don’t know.
>
> I know this is a bit annoying to deal with so I’ll see if I can make this a me problem instead. I think I can.
>
> Having said that, I don’t have a good intuition for the trade-off of using slabs or not. Sounds like there will be per-object overhead without slabs, but with slavs we will be storing more garbage, compared to doing more fine grained eager reclamation. Will be interesting to evaluate that trade-off more, given this new eager reclamation ability.
>
> Thanks,
> /Erik
>
> On 28 Jul 2026, at 11:37, Benedict Elliott Smith <be...@apache.org>> wrote:
>
> 
> Could I ask how the high in-degree to slabs affects GC? The references to the slab are acyclic, and so I would expect the incoming references to be collected directly, eventually reducing the in-degree? I suppose the in-degree counter saturating
>
>
> Could I ask how the high in-degree to slabs affects GC? The references to the slab are acyclic, and so I would expect the incoming references to be collected directly, eventually reducing the in-degree? I suppose the in-degree counter saturating once disables the feature for the object entirely?
>
> One other significant problem with unslabbed buffers is that the _object_ overhead is higher; offheap_objects was introduced in large part to address this problem (there remains significant object overhead, but a small fraction). However, every mode besides unslabbed_buffers has a problem with overwrite workloads, since you cannot reclaim any released space until the memtable is flushed. For these workloads the object overhead might be a price worth paying if you can flush less often.
>
> On 2026/07/28 07:12:42 Branimir Lambov wrote:
> > Hi Erik,
> >
> > The slabs will always have a high in-degree because we allocate space for
> > data inside them. We generally don't use unslabbed because of the high GC
> > overhead; it would be interesting to see what kind of performance one gets
> > with unslabbed compared to heap buffers with this GC improvement and
> > whether it makes unslabbed a realistic option to use.
> >
> > The other way to avoid the high in-degree of slabs is to use the
> > offheap_objects option. This choice is used very often in production
> > systems. It takes the trie buffers and cell data off-heap, but still has
> > quite a bit of ordering structure on the heap.
> >
> > The above applies to all memtable implementations in Cassandra; they share
> > the same cell data management logic.
> >
> > I will take removing the cycle in ApplyState into account for the next
> > stages of trie memtable development.
> >
> > Regards,
> > Branimir
> >
> > On Mon, Jul 27, 2026 at 3:32 PM Erik Osterlund via dev <
> > dev@cassandra.apache.org<ma...@cassandra.apache.org>> wrote:
> >
> > > Hi Dmitry,
> > >
> > > Thanks for the reply and the pointers, it’s very helpful. As a GC
> > > developer, I naturally get interested when people are moving data off-heap
> > > because of GC issues.
> > >
> > > I tried out the Trie memtable data structure. Unfortunately, it looks like
> > > there is a cycle caused by InMemoryTrie.ApplyState which has an implicit
> > > this$0 field due to being an internal class. I tried patching it up a bit
> > > locally to pass that around as an argument instead. Still some slab
> > > allocator (not sure what it’s fore) seemingly causing in-degree > 6 which
> > > the algorithm is a bit sensitive to right now. But with the patched Trie
> > > and unslabbed_heap_buffers it works beautifully well and I see several GB
> > > reclaimed old gen memory in young collections, without having to trace the
> > > old generation. It’s CPU spending is now invariant of the old gen live set
> > > size, as long as we can stick to these rules I mentioned.
> > >
> > > This feels rather encouraging IMO. :-)
> > >
> > > Thanks,
> > > /Erik
> > >
> > >
> > > On 27 Jul 2026, at 12:09, Dmitry Konstantinov <ne...@gmail.com>> wrote:
> > >
> > > This Message Is From a New Sender
> > > You have not previously corresponded with the sender of this message.
> > > Report Suspicious
> > >
> > > <https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op20OCZG1EegmzBtO1N5l_0NlI-ToMvOCf6nTg_MDwHHjAYeHpOwVpF74U5Z9U9hvMImUXCmFpRqWmpISVsORhymuGGN-sm7Tr4G63oCvH3p-fuixd7qWTAOw5ah2Ug$  >
> > >
> > > 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.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!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnFKWf9IaA$
><https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnFKWf9IaA$%3E>> > <https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w58ED4ei$>
><https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w58ED4ei$%3E%3E>>>
> > > [2] https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnGP2Tgbfw$
><https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnGP2Tgbfw$%3E>> > <https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6wwydJXc_$>
><https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6wwydJXc_$%3E%3E>>>
> > > [3]
> > > https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnEhc2vqyA$
><https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnEhc2vqyA$%3E>> > <https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3z0dj6w$>
><https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3z0dj6w$%3E%3E>>>
> > > [4] https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnE5Cnkryg$
><https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnE5Cnkryg$%3E>> > <https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w33qzYRA$>
><https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w33qzYRA$%3E%3E>>> [5]
> > > https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnGdQs3SOQ$
><https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnGdQs3SOQ$%3E>> > <https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3Jt98gW$>
><https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3Jt98gW$%3E%3E>>>
> > > Regards,
> > > Dmitry
> > >
> > > On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev <
> > > dev@cassandra.apache.org<ma...@cassandra.apache.org>> 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
> > >
> > >
> > >
> >
>
>

Re: [External] : Re: MemTables and ZGC old gen reference counting

Posted by Benedict Elliott Smith <be...@apache.org>.

Could I ask why you need negative numbers? And is there any reason this couldn't be reset by an Old Gen GC, or is that too onerous? Intuitively, it seems likely that the counter could be reset and incremented once for each incoming reference encountered during GC, so that this feature is disabled across an Old Gen GC, but potentially of wider impact between GCs?

I'll admit, it's unclear how much benefit this refinement would have even if it were possible. I'm simply interested in the shape of the problem at this point. The idea of a hybrid refcount/tracing GC makes a lot of sense for memtables, and no doubt other workloads with skewed lifetimes that distort GC. A little over a decade ago I implemented a hybrid refcount+RCU/epoch scheme for Memtable slab management, so that slabs could be compacted and reclaimed, although it was not adopted. It would be neat for the native GC to support a similar capability.

On 2026/07/28 11:24:14 Erik Osterlund via dev wrote:
> Absolutely. In the current prototype, I’m using 4 object header word bits to track reference counts. It needs to be signed because of arcane reasons. So I can track a range from -7 to 7, and occasionally there will be one ref count stale that is artificial. When there is either overflow or underflow, the ”uncertain” reference count with a value of -8 is installed, meaning that we have lost track and must conservatively assume for the rest of the object life time that it might have a positive reference count. We just don’t know.
> 
> I know this is a bit annoying to deal with so I’ll see if I can make this a me problem instead. I think I can.
> 
> Having said that, I don’t have a good intuition for the trade-off of using slabs or not. Sounds like there will be per-object overhead without slabs, but with slavs we will be storing more garbage, compared to doing more fine grained eager reclamation. Will be interesting to evaluate that trade-off more, given this new eager reclamation ability.
> 
> Thanks,
> /Erik
> 
> On 28 Jul 2026, at 11:37, Benedict Elliott Smith <be...@apache.org> wrote:
> 
> 
> Could I ask how the high in-degree to slabs affects GC? The references to the slab are acyclic, and so I would expect the incoming references to be collected directly, eventually reducing the in-degree? I suppose the in-degree counter saturating
> 
> 
> Could I ask how the high in-degree to slabs affects GC? The references to the slab are acyclic, and so I would expect the incoming references to be collected directly, eventually reducing the in-degree? I suppose the in-degree counter saturating once disables the feature for the object entirely?
> 
> One other significant problem with unslabbed buffers is that the _object_ overhead is higher; offheap_objects was introduced in large part to address this problem (there remains significant object overhead, but a small fraction). However, every mode besides unslabbed_buffers has a problem with overwrite workloads, since you cannot reclaim any released space until the memtable is flushed. For these workloads the object overhead might be a price worth paying if you can flush less often.
> 
> On 2026/07/28 07:12:42 Branimir Lambov wrote:
> > Hi Erik,
> >
> > The slabs will always have a high in-degree because we allocate space for
> > data inside them. We generally don't use unslabbed because of the high GC
> > overhead; it would be interesting to see what kind of performance one gets
> > with unslabbed compared to heap buffers with this GC improvement and
> > whether it makes unslabbed a realistic option to use.
> >
> > The other way to avoid the high in-degree of slabs is to use the
> > offheap_objects option. This choice is used very often in production
> > systems. It takes the trie buffers and cell data off-heap, but still has
> > quite a bit of ordering structure on the heap.
> >
> > The above applies to all memtable implementations in Cassandra; they share
> > the same cell data management logic.
> >
> > I will take removing the cycle in ApplyState into account for the next
> > stages of trie memtable development.
> >
> > Regards,
> > Branimir
> >
> > On Mon, Jul 27, 2026 at 3:32 PM Erik Osterlund via dev <
> > dev@cassandra.apache.org> wrote:
> >
> > > Hi Dmitry,
> > >
> > > Thanks for the reply and the pointers, it’s very helpful. As a GC
> > > developer, I naturally get interested when people are moving data off-heap
> > > because of GC issues.
> > >
> > > I tried out the Trie memtable data structure. Unfortunately, it looks like
> > > there is a cycle caused by InMemoryTrie.ApplyState which has an implicit
> > > this$0 field due to being an internal class. I tried patching it up a bit
> > > locally to pass that around as an argument instead. Still some slab
> > > allocator (not sure what it’s fore) seemingly causing in-degree > 6 which
> > > the algorithm is a bit sensitive to right now. But with the patched Trie
> > > and unslabbed_heap_buffers it works beautifully well and I see several GB
> > > reclaimed old gen memory in young collections, without having to trace the
> > > old generation. It’s CPU spending is now invariant of the old gen live set
> > > size, as long as we can stick to these rules I mentioned.
> > >
> > > This feels rather encouraging IMO. :-)
> > >
> > > Thanks,
> > > /Erik
> > >
> > >
> > > On 27 Jul 2026, at 12:09, Dmitry Konstantinov <ne...@gmail.com> wrote:
> > >
> > > This Message Is From a New Sender
> > > You have not previously corresponded with the sender of this message.
> > > Report Suspicious
> > >
> > > <https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op20OCZG1EegmzBtO1N5l_0NlI-ToMvOCf6nTg_MDwHHjAYeHpOwVpF74U5Z9U9hvMImUXCmFpRqWmpISVsORhymuGGN-sm7Tr4G63oCvH3p-fuixd7qWTAOw5ah2Ug$ >
> > >
> > > 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.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!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnFKWf9IaA$
> > > <https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w58ED4ei$>
> >>
> > > [2] https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnGP2Tgbfw$
> > > <https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6wwydJXc_$>
> >>
> > > [3]
> > > https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnEhc2vqyA$
> > > <https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3z0dj6w$>
> >>
> > > [4] https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnE5Cnkryg$
> > > <https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w33qzYRA$>
> >> [5]
> > > https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnGdQs3SOQ$
> > > <https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3Jt98gW$>
> >>
> > > Regards,
> > > Dmitry
> > >
> > > On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev <
> > > dev@cassandra.apache.org> 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
> > >
> > >
> > >
> >
> 
>

Re: [External] : Re: MemTables and ZGC old gen reference counting

Posted by Erik Osterlund via dev <de...@cassandra.apache.org>.

Absolutely. In the current prototype, I’m using 4 object header word bits to track reference counts. It needs to be signed because of arcane reasons. So I can track a range from -7 to 7, and occasionally there will be one ref count stale that is artificial. When there is either overflow or underflow, the ”uncertain” reference count with a value of -8 is installed, meaning that we have lost track and must conservatively assume for the rest of the object life time that it might have a positive reference count. We just don’t know.

I know this is a bit annoying to deal with so I’ll see if I can make this a me problem instead. I think I can.

Having said that, I don’t have a good intuition for the trade-off of using slabs or not. Sounds like there will be per-object overhead without slabs, but with slavs we will be storing more garbage, compared to doing more fine grained eager reclamation. Will be interesting to evaluate that trade-off more, given this new eager reclamation ability.

Thanks,
/Erik

On 28 Jul 2026, at 11:37, Benedict Elliott Smith <be...@apache.org> wrote:


Could I ask how the high in-degree to slabs affects GC? The references to the slab are acyclic, and so I would expect the incoming references to be collected directly, eventually reducing the in-degree? I suppose the in-degree counter saturating


Could I ask how the high in-degree to slabs affects GC? The references to the slab are acyclic, and so I would expect the incoming references to be collected directly, eventually reducing the in-degree? I suppose the in-degree counter saturating once disables the feature for the object entirely?

One other significant problem with unslabbed buffers is that the _object_ overhead is higher; offheap_objects was introduced in large part to address this problem (there remains significant object overhead, but a small fraction). However, every mode besides unslabbed_buffers has a problem with overwrite workloads, since you cannot reclaim any released space until the memtable is flushed. For these workloads the object overhead might be a price worth paying if you can flush less often.

On 2026/07/28 07:12:42 Branimir Lambov wrote:
> Hi Erik,
>
> The slabs will always have a high in-degree because we allocate space for
> data inside them. We generally don't use unslabbed because of the high GC
> overhead; it would be interesting to see what kind of performance one gets
> with unslabbed compared to heap buffers with this GC improvement and
> whether it makes unslabbed a realistic option to use.
>
> The other way to avoid the high in-degree of slabs is to use the
> offheap_objects option. This choice is used very often in production
> systems. It takes the trie buffers and cell data off-heap, but still has
> quite a bit of ordering structure on the heap.
>
> The above applies to all memtable implementations in Cassandra; they share
> the same cell data management logic.
>
> I will take removing the cycle in ApplyState into account for the next
> stages of trie memtable development.
>
> Regards,
> Branimir
>
> On Mon, Jul 27, 2026 at 3:32 PM Erik Osterlund via dev <
> dev@cassandra.apache.org> wrote:
>
> > Hi Dmitry,
> >
> > Thanks for the reply and the pointers, it’s very helpful. As a GC
> > developer, I naturally get interested when people are moving data off-heap
> > because of GC issues.
> >
> > I tried out the Trie memtable data structure. Unfortunately, it looks like
> > there is a cycle caused by InMemoryTrie.ApplyState which has an implicit
> > this$0 field due to being an internal class. I tried patching it up a bit
> > locally to pass that around as an argument instead. Still some slab
> > allocator (not sure what it’s fore) seemingly causing in-degree > 6 which
> > the algorithm is a bit sensitive to right now. But with the patched Trie
> > and unslabbed_heap_buffers it works beautifully well and I see several GB
> > reclaimed old gen memory in young collections, without having to trace the
> > old generation. It’s CPU spending is now invariant of the old gen live set
> > size, as long as we can stick to these rules I mentioned.
> >
> > This feels rather encouraging IMO. :-)
> >
> > Thanks,
> > /Erik
> >
> >
> > On 27 Jul 2026, at 12:09, Dmitry Konstantinov <ne...@gmail.com> wrote:
> >
> > This Message Is From a New Sender
> > You have not previously corresponded with the sender of this message.
> > Report Suspicious
> >
> > <https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op20OCZG1EegmzBtO1N5l_0NlI-ToMvOCf6nTg_MDwHHjAYeHpOwVpF74U5Z9U9hvMImUXCmFpRqWmpISVsORhymuGGN-sm7Tr4G63oCvH3p-fuixd7qWTAOw5ah2Ug$ >
> >
> > 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.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!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnFKWf9IaA$
> > <https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w58ED4ei$>
>>
> > [2] https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnGP2Tgbfw$
> > <https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6wwydJXc_$>
>>
> > [3]
> > https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnEhc2vqyA$
> > <https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3z0dj6w$>
>>
> > [4] https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnE5Cnkryg$
> > <https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w33qzYRA$>
>> [5]
> > https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PMxBEtu9Z3MPIuEL5qQZnoS3GuUv1PF-NbzE56Or1vN79-0b_J4URoHRsJjxNDTSKLO7-2cZnQukAnGdQs3SOQ$
> > <https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3Jt98gW$>
>>
> > Regards,
> > Dmitry
> >
> > On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev <
> > dev@cassandra.apache.org> 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
> >
> >
> >
>

Re: [External] : Re: MemTables and ZGC old gen reference counting

Posted by Benedict Elliott Smith <be...@apache.org>.

Could I ask how the high in-degree to slabs affects GC? The references to the slab are acyclic, and so I would expect the incoming references to be collected directly, eventually reducing the in-degree? I suppose the in-degree counter saturating once disables the feature for the object entirely?

One other significant problem with unslabbed buffers is that the _object_ overhead is higher; offheap_objects was introduced in large part to address this problem (there remains significant object overhead, but a small fraction). However, every mode besides unslabbed_buffers has a problem with overwrite workloads, since you cannot reclaim any released space until the memtable is flushed. For these workloads the object overhead might be a price worth paying if you can flush less often.

On 2026/07/28 07:12:42 Branimir Lambov wrote:
> Hi Erik,
> 
> The slabs will always have a high in-degree because we allocate space for
> data inside them. We generally don't use unslabbed because of the high GC
> overhead; it would be interesting to see what kind of performance one gets
> with unslabbed compared to heap buffers with this GC improvement and
> whether it makes unslabbed a realistic option to use.
> 
> The other way to avoid the high in-degree of slabs is to use the
> offheap_objects option. This choice is used very often in production
> systems. It takes the trie buffers and cell data off-heap, but still has
> quite a bit of ordering structure on the heap.
> 
> The above applies to all memtable implementations in Cassandra; they share
> the same cell data management logic.
> 
> I will take removing the cycle in ApplyState into account for the next
> stages of trie memtable development.
> 
> Regards,
> Branimir
> 
> On Mon, Jul 27, 2026 at 3:32 PM Erik Osterlund via dev <
> dev@cassandra.apache.org> wrote:
> 
> > Hi Dmitry,
> >
> > Thanks for the reply and the pointers, it’s very helpful. As a GC
> > developer, I naturally get interested when people are moving data off-heap
> > because of GC issues.
> >
> > I tried out the Trie memtable data structure. Unfortunately, it looks like
> > there is a cycle caused by InMemoryTrie.ApplyState which has an implicit
> > this$0 field due to being an internal class. I tried patching it up a bit
> > locally to pass that around as an argument instead. Still some slab
> > allocator (not sure what it’s fore) seemingly causing in-degree > 6 which
> > the algorithm is a bit sensitive to right now. But with the patched Trie
> > and unslabbed_heap_buffers it works beautifully well and I see several GB
> > reclaimed old gen memory in young collections, without having to trace the
> > old generation. It’s CPU spending is now invariant of the old gen live set
> > size, as long as we can stick to these rules I mentioned.
> >
> > This feels rather encouraging IMO. :-)
> >
> > Thanks,
> > /Erik
> >
> >
> > On 27 Jul 2026, at 12:09, Dmitry Konstantinov <ne...@gmail.com> wrote:
> >
> > This Message Is From a New Sender
> > You have not previously corresponded with the sender of this message.
> > Report Suspicious
> >
> > <https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op20OCZG1EegmzBtO1N5l_0NlI-ToMvOCf6nTg_MDwHHjAYeHpOwVpF74U5Z9U9hvMImUXCmFpRqWmpISVsORhymuGGN-sm7Tr4G63oCvH3p-fuixd7qWTAOw5ah2Ug$>
> >
> > 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.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://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html
> > <https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w58ED4ei$>
> >
> > [2] https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf
> > <https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6wwydJXc_$>
> >
> > [3]
> > https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57+Flat+keys+and+trie+interfaces
> > <https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3z0dj6w$>
> >
> > [4] https://issues.apache.org/jira/browse/CASSANDRA-7282
> > <https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w33qzYRA$>
> > [5]
> > https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java
> > <https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3Jt98gW$>
> >
> > Regards,
> > Dmitry
> >
> > On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev <
> > dev@cassandra.apache.org> 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
> >
> >
> >
>

Re: [External] : Re: MemTables and ZGC old gen reference counting

Posted by Erik Osterlund via dev <de...@cassandra.apache.org>.

Hi Branimir,

As a GC guy, I can’t help but feel it would be nice if the simple solution of using objects works well. So it is definitely going to be interesting to see how this pans out. This is still an early prototype though so don’t hold your breath. :)

Thank you for taking care of the ApplyState cycle! That’s really helpful. Then I’ll see if I can fix the high in-degree issue.

Thanks,
/Erik

On 28 Jul 2026, at 09:12, Branimir Lambov <bl...@gmail.com> wrote:

This Message Is From a New Sender
You have not previously corresponded with the sender of this message.
<https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op20OCelNeSl_twjf9P4EOFCiXjEdjXxAEB7pdW43oxiaenzC8GoaZS_j_DCgb_kRDOkjWZSwHDvhYOny6vWKAIBmHRuVtta71LhoGba2NxUwKXoouQJ-qi7HJ1VZYw$>
Report Suspicious
Hi Erik,

The slabs will always have a high in-degree because we allocate space for data inside them. We generally don't use unslabbed because of the high GC overhead; it would be interesting to see what kind of performance one gets with unslabbed compared to heap buffers with this GC improvement and whether it makes unslabbed a realistic option to use.

The other way to avoid the high in-degree of slabs is to use the offheap_objects option. This choice is used very often in production systems. It takes the trie buffers and cell data off-heap, but still has quite a bit of ordering structure on the heap.

The above applies to all memtable implementations in Cassandra; they share the same cell data management logic.

I will take removing the cycle in ApplyState into account for the next stages of trie memtable development.

Regards,
Branimir

On Mon, Jul 27, 2026 at 3:32 PM Erik Osterlund via dev <de...@cassandra.apache.org>> wrote:
Hi Dmitry,

Thanks for the reply and the pointers, it’s very helpful. As a GC developer, I naturally get interested when people are moving data off-heap because of GC issues.

This feels rather encouraging IMO. :-)

Thanks,
/Erik

On 27 Jul 2026, at 12:09, Dmitry Konstantinov <ne...@gmail.com>> wrote:

Hi Erik,

<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]

Regards,
Dmitry

On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev <de...@cassandra.apache.org>> wrote:
Hi,

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).

Please let me know if this is the wrong place for this kind of discussion.

Thanks,
/Erik

--
Dmitry Konstantinov

Re: [External] : Re: MemTables and ZGC old gen reference counting

Posted by Branimir Lambov <bl...@gmail.com>.

Hi Erik,

The slabs will always have a high in-degree because we allocate space for
data inside them. We generally don't use unslabbed because of the high GC
overhead; it would be interesting to see what kind of performance one gets
with unslabbed compared to heap buffers with this GC improvement and
whether it makes unslabbed a realistic option to use.

The other way to avoid the high in-degree of slabs is to use the
offheap_objects option. This choice is used very often in production
systems. It takes the trie buffers and cell data off-heap, but still has
quite a bit of ordering structure on the heap.

The above applies to all memtable implementations in Cassandra; they share
the same cell data management logic.

I will take removing the cycle in ApplyState into account for the next
stages of trie memtable development.

Regards,
Branimir

On Mon, Jul 27, 2026 at 3:32 PM Erik Osterlund via dev <
dev@cassandra.apache.org> wrote:

> Hi Dmitry,
>
> Thanks for the reply and the pointers, it’s very helpful. As a GC
> developer, I naturally get interested when people are moving data off-heap
> because of GC issues.
>
> I tried out the Trie memtable data structure. Unfortunately, it looks like
> there is a cycle caused by InMemoryTrie.ApplyState which has an implicit
> this$0 field due to being an internal class. I tried patching it up a bit
> locally to pass that around as an argument instead. Still some slab
> allocator (not sure what it’s fore) seemingly causing in-degree > 6 which
> the algorithm is a bit sensitive to right now. But with the patched Trie
> and unslabbed_heap_buffers it works beautifully well and I see several GB
> reclaimed old gen memory in young collections, without having to trace the
> old generation. It’s CPU spending is now invariant of the old gen live set
> size, as long as we can stick to these rules I mentioned.
>
> This feels rather encouraging IMO. :-)
>
> Thanks,
> /Erik
>
>
> On 27 Jul 2026, at 12:09, Dmitry Konstantinov <ne...@gmail.com> wrote:
>
> This Message Is From a New Sender
> You have not previously corresponded with the sender of this message.
> Report Suspicious
>
> <https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op20OCZG1EegmzBtO1N5l_0NlI-ToMvOCf6nTg_MDwHHjAYeHpOwVpF74U5Z9U9hvMImUXCmFpRqWmpISVsORhymuGGN-sm7Tr4G63oCvH3p-fuixd7qWTAOw5ah2Ug$>
>
> 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.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://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html
> <https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w58ED4ei$>
>
> [2] https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf
> <https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6wwydJXc_$>
>
> [3]
> https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57+Flat+keys+and+trie+interfaces
> <https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3z0dj6w$>
>
> [4] https://issues.apache.org/jira/browse/CASSANDRA-7282
> <https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w33qzYRA$>
> [5]
> https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java
> <https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!PczTox7K8CxUiR-8i1oQAWeuiwNxISCGjq8moRxQRGYGjt7DVNe2Uk51DQscE8g13blXNeWAG6E6w3Jt98gW$>
>
> Regards,
> Dmitry
>
> On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev <
> dev@cassandra.apache.org> 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
>
>
>