[
https://issues.apache.org/jira/browse/CASSANDRA-20280?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18118358#comment-18118358
]
Dmitry Konstantinov edited comment on CASSANDRA-20280 at 9/23/26 1:14 PM:
--------------------------------------------------------------------------
A draft version for more compact off-heap cell layout (I have a prototype and
trying now to make an access logic for cell data fast enough):
{code:java}
[ flags ][ timestamp ][ value length ][ path length ][ ttl ][ local deletion ][
value ][ path ]
[ 1b ][ 8b ][ 0b / 4b ][ 0b / 4b ][0b/4b][ 0b / 4b ][
arb ][ arb ]
{code}
Only the flags and the timestamp are always present.
The flags byte carries the value length in its low bits, so we can read a short
length + flags using a single load, length is placed to lower bits to extract
it faster (it is frequently accessed by different logic).
{code:java}
bits 0-4 the value length, or {@link #LENGTH_EXTENDED} when it does not fit in
five bits, in which
case the real length is in a 4 byte field
bit 5 HAS_PATH the cell has a cell path, i.e. it belongs to a
complex column
bit 6 HAS_TTL ttl != NO_TTL, so a ttl field is present
bit 7 HAS_DELETION localDeletionTime != NO_DELETION_TIME, so a deletion
field is present
{code}
We can save more space by using delta encoding for timestamp value but it is
another amount of changes (to do it we need a logic to store and access
baseline value), so it is out of scope now.
Savings from using such schema:
{code:java}
┌────────────────────────────────────────────┬───────┐
│ cell │ saved │
├────────────────────────────────────────────┼───────┤
│ live, value < 31 bytes │ 12 │
├────────────────────────────────────────────┼───────┤
│ live, value ≥ 31 bytes (extended length) │ 8 │
├────────────────────────────────────────────┼───────┤
│ tombstone (deletion time, empty value) │ 8 │
├────────────────────────────────────────────┼───────┤
│ expiring, value < 31 (ttl + deletion time) │ 4 │
├────────────────────────────────────────────┼───────┤
│ expiring, value ≥ 31 │ 0 │
└────────────────────────────────────────────┴───────┘
{code}
{code:java}
┌───────────────────────────────────┬───────┬─────────┬───────┬────────┐
│ cell │ trunk │ current │ saved │ │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ tinyint / boolean │ 22 │ 10 │ 12 │ −54.5% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ int / float │ 25 │ 13 │ 12 │ −48.0% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ bigint / double / timestamp │ 29 │ 17 │ 12 │ −41.4% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ uuid / timeuuid / inet │ 37 │ 25 │ 12 │ −32.4% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ text, 12 bytes │ 33 │ 21 │ 12 │ −36.4% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ text, 30 bytes │ 51 │ 39 │ 12 │ −23.5% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ text, 50 bytes │ 71 │ 63 │ 8 │ −11.3% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ text, 200 bytes │ 221 │ 213 │ 8 │ −3.6% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ blob, 1 KiB │ 1045 │ 1037 │ 8 │ −0.8% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ tombstone (empty value) │ 21 │ 13 │ 8 │ −38.1% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ expiring int (ttl + ldt) │ 25 │ 21 │ 4 │ −16.0% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ list<int> element │ 45 │ 33 │ 12 │ −26.7% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ list<text> element, 50B value │ 91 │ 83 │ 8 │ −8.8% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ map<text,int> element, 8-byte key │ 37 │ 25 │ 12 │ −32.4% │
└───────────────────────────────────┴───────┴─────────┴───────┴────────┘
{code}
was (Author: dnk):
A draft version for more compact off-heap cell layout (I have a prototype and
trying now to make an access logic for cell data fast enough):
{code:java}
[ flags ][ timestamp ][ value length ][ path length ][ ttl ][ local deletion ][
value ][ path ]
[ 1b ][ 8b ][ 0b / 4b ][ 0b / 4b ][0b/4b][ 0b / 4b ][
arb ][ arb ]
{code}
Only the flags and the timestamp are always present.
The flags byte carries the value length in its low bits, so we can read a short
length + flags using a single load, length is placed to lower bits to extract
it faster.
{code:java}
bits 0-4 the value length, or {@link #LENGTH_EXTENDED} when it does not fit in
five bits, in which
case the real length is in a 4 byte field
bit 5 HAS_PATH the cell has a cell path, i.e. it belongs to a
complex column
bit 6 HAS_TTL ttl != NO_TTL, so a ttl field is present
bit 7 HAS_DELETION localDeletionTime != NO_DELETION_TIME, so a deletion
field is present
{code}
We can save more space by using delta encoding for timestamp value but it is
another amount of changes (to do it we need a logic to store and access
baseline value), so it is out of scope now.
Savings from using such schema:
{code:java}
┌────────────────────────────────────────────┬───────┐
│ cell │ saved │
├────────────────────────────────────────────┼───────┤
│ live, value < 31 bytes │ 12 │
├────────────────────────────────────────────┼───────┤
│ live, value ≥ 31 bytes (extended length) │ 8 │
├────────────────────────────────────────────┼───────┤
│ tombstone (deletion time, empty value) │ 8 │
├────────────────────────────────────────────┼───────┤
│ expiring, value < 31 (ttl + deletion time) │ 4 │
├────────────────────────────────────────────┼───────┤
│ expiring, value ≥ 31 │ 0 │
└────────────────────────────────────────────┴───────┘
{code}
{code:java}
┌───────────────────────────────────┬───────┬─────────┬───────┬────────┐
│ cell │ trunk │ current │ saved │ │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ tinyint / boolean │ 22 │ 10 │ 12 │ −54.5% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ int / float │ 25 │ 13 │ 12 │ −48.0% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ bigint / double / timestamp │ 29 │ 17 │ 12 │ −41.4% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ uuid / timeuuid / inet │ 37 │ 25 │ 12 │ −32.4% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ text, 12 bytes │ 33 │ 21 │ 12 │ −36.4% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ text, 30 bytes │ 51 │ 39 │ 12 │ −23.5% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ text, 50 bytes │ 71 │ 63 │ 8 │ −11.3% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ text, 200 bytes │ 221 │ 213 │ 8 │ −3.6% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ blob, 1 KiB │ 1045 │ 1037 │ 8 │ −0.8% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ tombstone (empty value) │ 21 │ 13 │ 8 │ −38.1% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ expiring int (ttl + ldt) │ 25 │ 21 │ 4 │ −16.0% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ list<int> element │ 45 │ 33 │ 12 │ −26.7% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ list<text> element, 50B value │ 91 │ 83 │ 8 │ −8.8% │
├───────────────────────────────────┼───────┼─────────┼───────┼────────┤
│ map<text,int> element, 8-byte key │ 37 │ 25 │ 12 │ −32.4% │
└───────────────────────────────────┴───────┴─────────┴───────┴────────┘
{code}
> More compact native memory layout for NativeCell
> ------------------------------------------------
>
> Key: CASSANDRA-20280
> URL: https://issues.apache.org/jira/browse/CASSANDRA-20280
> Project: Apache Cassandra
> Issue Type: Improvement
> Components: Local/Memtable
> Reporter: Dmitry Konstantinov
> Assignee: Dmitry Konstantinov
> Priority: Normal
> Fix For: 7.x
>
> Attachments: cells_heap_layout.png,
> image-2025-02-01-15-10-15-176.png, image-2025-02-01-15-21-22-653.png
>
>
> To capture an idea here, I going to return to it soon after finishing with
> the current in-progress tickets.
> The current NativeCell has the following native memory layout:
> !image-2025-02-01-15-21-22-653.png|width=400!
> So, when we store an integer value (4 bytes) we have total size 25 bytes.
> For an ASCII string with 10 symbols - 31 bytes.
> If we can make it more compact -> more data can be stored in memtables and
> with a potentially better CPU cache usage on lookup.
> The idea is to use the first byte to store more flags to differentiate
> typical use cases:
> # A usual cell without TTL
> # Alive: we do not need to store localDeletionInfo
> # Value is frequently a small value and if it is not more than 128 bytes
> (256 using unsigned byte), we can use 1 byte to store length (varint is an
> alternative but it is harder to calculate offset for data after it)
> So, we can introduce flags in the first byte such as:
> * has path (the existing one)
> * has TTL
> * has delete info
> * one byte length
> When we read some component of the cell - we read flags and calculate offsets
> for the component using information from the flags
> Using this approach we can reduce native memory overhead to the following
> values in the following typical cases:
> !image-2025-02-01-15-10-15-176.png|width=400!
> These changes are local and incapsulated in NativeCell logic. The downside of
> the approach - extra calculations are needed to lookup a component from a
> NativeCell (read flags, if component is present then calculate an offset
> based on it and read the component by the offset)
> Additional but more complicated options:
> * use a delta encoding for timestamp (similar to what we have in SSTables)
> but it is more complicated logic which will require to store somewhere (on a
> partition or memtable level) base timestamp and store delta (as a short or
> int) in the cell if the delta is small enough (timestamp technically can be
> set by a client to any value, so we have to support still the option with a
> full long).
> * if timestamp and LocalDelInfo has the same values (taking in account micro
> to milliseconds conversion) we can use another flag bit to mark it and store
> only timestamp and calculate LocalDelInfo from it.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
