RonDB training · module 07 of 25 · 20 min

Data structure layout

From the memory a data node takes at startup down to the bytes of one row, and what happens to them during an update.

Memory · allocated once

A data node takes all its memory at startup and never calls malloc again

  • No allocation or freeing in the hot path: no surprises under load, no fragmentation of the process heap.
  • A global memory manager hands out 32 KB pages to 12 resource groups.
  • Each group has a reserved size, a maximum and a priority, so memory moves to where it is needed.
  • By default the size of everything is computed from the machine (module 13).
Resource groupHolds
DataMemoryRows, hash indexes, ordered indexes
TransactionMemoryOperations, copy tuples
DiskPageBufferThe page cache for disk data
JobBuffer · TransporterSignals between threads and nodes
Schema · SchemaTransTable definitions, schema changes
Query · Replication · …Query workers, replication buffers

docs: automatic_memory_config.md (DataMemory) · code: src/kernel/blocks/record_types.hpp (RG_TRANSACTION_MEMORY 1 … RG_REPLICATION_MEMORY 12) · src/kernel/vm/ndbd_malloc_impl.hpp (MM_RG_COUNT 12)

Ownership · from table to thread

Each fragment replica belongs to one ldm thread, which owns its pages

table t14 partitions data node 1 ldm thread 1fragments of P0 and P2 ldm thread 2fragments of P1 and P3 data node 2 · other replica ldm thread 1fragments of P0 and P2 ldm thread 2fragments of P1 and P3

A fragment replica is the part of one partition stored on one node. One ldm thread owns it: its row pages, hash index and ordered indexes.

The other replica lives on the other node of the node group. Writes go to the owning ldm thread; reads can also run in query workers (module 11).

docs: table_options.md (Partitioning of tables) · rondb_vm_arch.md (ldm threads) · module 02 (partitions and replicas)

PART 1

Row ids

Every row has an address that never changes.

Row id · logical page and index

A row id is a logical page number and an index in that page

row idlogical page 17 · index 100 page map of the fragmentnode 1 · logical 17 → physical 90412 32 KB page 9041220-word rows · row 5 at word 100 header row 5 row 0row 1row 2row 3row 4 page map on node 2logical 17 → physical 3051 same row id 32 KB page 3051 · index 100same row, other replica

The fixed part of a row never moves. A page map per fragment turns the logical page into a physical 32 KB page; the index is the row's word offset in that page.

The primary replica picks the row id at insert and sends it along: every replica uses the same row id, on its own physical pages.

docs: row_data_structure.md (Row format) · code: dbtup/DbtupPageMap.cpp (logical to physical pages) · tuppage.hpp (32-word page header) · ndb_limits.h (MAX_TUPLES_PER_PAGE 8191) · page numbers and row size are illustrations

Row ids · what depends on them

Recovery, indexes and checkpoints all rely on stable row ids

Node restart

A starting node and a live node compare rows by row id to synchronise, page by page (module 16).

Indexes

The hash index stores row ids; ordered indexes store the physical page and offset. A moved row would break both.

OPTIMIZE TABLE

Compacts variable-size parts, never the fixed parts: those are the row ids.

The fixed part is the row's anchor. Everything that can change size lives elsewhere and is reached through a reference from it.

docs: row_data_structure.md · basic_sql.md (Index sizes, Optimize/Analyze Table)

PART 2

Anatomy of a row

A fixed part, a variable part, a disk part.

Row parts · up to three

Row parts: a fixed part, plus variable and disk parts when the columns need them

fixed part header + fixed-size columnsfixed-size page · found by row idalways there reference variable part variable-size columns+ the dynamic partvariable-size page · may move disk reference, 8 bytes disk part disk columns, variable sizepage in a tablespacepoints back to the memory row

The fixed part is the entry point: header and fixed-size columns, at the row id.

Variable-size and dynamic columns live in the variable part. When it moves to a bigger slot, RonDB updates the reference in the fixed part.

Disk columns live in the disk part, variable-size since RonDB 22.10, cached in memory by PGMAN.

docs: row_data_structure.md (Row format) · code: Dbtup.hpp (Var_part_ref; m_base_record_page_no/idx: the disk part's reference back) · DbtupVarAlloc.cpp (realloc_var_part)

Header bits · word 1

Header bits: sixteen bits of version, sixteen bits of state

BitsNameMeaning
0–15versionRow version; ordered index scans use it to see which version they read
16COPY_TUPLEThis is a copy made by an update, not the row itself
17 · 30DISK_PART · DISK_VAR_PARTThe row has a disk part · a variable-size one
20 · 23ALLOC · FREEInserted by a transaction not yet committed · free slot
22MM_GROWNThe variable part was grown for an update not yet committed
24 · 28LCP_SKIP · LCP_DELETEBookkeeping for the checkpoint scan running now
26VAR_PARTA variable part exists
29DELETE_WAITMarked for delete, waiting for its disk page

code: storage/ndb/src/kernel/blocks/dbtup/Dbtup.hpp (Tuple_header: TUP_VERSION_MASK 0xFFFF, COPY_TUPLE 0x00010000 … DISK_VAR_PART 0x40000000; a few flags left out)

Fixed-size page · one row size per fragment

A fixed-size page is a header and an array of equal slots

header32 words row 0index 0 row 1index 20 free row 3index 60 row 4index 80 free … 8160 data words: as many fixed parts as fit, each the same size for the whole fragment header: page state, free space, next free slot, table and fragment ids, and a change map with a bit per 4 KB for partial checkpoints

Every slot on a page has the same size: header plus fixed columns of this table. The index in the row id is the slot's word offset: with 20-word slots, row 3 is at index 60.

The page header tracks free slots and which 4 KB parts changed since the last checkpoint, so a checkpoint can skip what did not (module 14).

code: dbtup/tuppage.hpp (Tup_fixsize_page: HEADER_WORDS 32, DATA_WORDS = 8192 − 32, change map bits 24–31 of m_flags, 4 kB per bit)

Variable-size page · data from the front, directory from the back

A variable-size page finds each entry through a directory at its end

header entry 0 · 54 words entry 1 entry 2 · 71 words free space 2 1 0 ← directoryentries → CHAIN FREE length · 15 bits position · 15 bits CHAIN · a variable part, reached from its fixed part: every in-memory row no CHAIN · a whole row with its own header: variable-size disk rows FREE · an unused slot; length and position then link the free slots

Entries grow from the front, the directory from the back. A row's variable-part reference names the page and its directory slot.

One directory word per entry: length and position in words, plus two flags. Pages sit in free lists by free space: 0–199, 200–499, 500–999, 1000–4079, 4080–7783 and 7784–8159 words.

code: dbtup/tuppage.hpp (Tup_varsize_page: CHAIN, FREE, LEN_MASK, POS_MASK) · tuppage.cpp (free_record) · dbtup/DbtupVarAlloc.cpp (alloc_record with CHAIN, init_list_sizes) · DbtupDiskAlloc.cpp (disk rows without CHAIN)

Variable part · what one entry holds

The variable part: column offsets, column data, then the dynamic part

offsets2 bytes per var column, + 2 for the end variable-size column dataname = 'Ada' · city = 'London' · padded to a word dynamic partbitmap + columns that are not NULL Around it: an 8-byte reference in the fixed part and a 4-byte entry in the page directory. No reference back. NULL bits of variable-size columns sit in the fixed part.

A column's length is the next offset minus its own, so any column is found with two reads. To grow an entry, RonDB moves it and updates the reference in the fixed part.

code: DbtupExecQuery.cpp (shrink_tuple: num_vars + 1 offsets, data, ALIGN_WORD, dynamic part) · DbtupVarAlloc.cpp (realloc_var_part, move_var_part update the fixed part's Var_part_ref) · tuppage.hpp (32-bit directory entry) · the column values are an illustration

Column format · COLUMN_FORMAT FIXED or DYNAMIC

FIXED or DYNAMIC columns: dynamic ones cost CPU and buy flexibility

FIXED · the default

  • Fixed-size columns in the fixed part, variable ones in the variable part.
  • Space is always there, even for NULL.
  • Fastest to read and write.

DYNAMIC

  • In the dynamic part: NULL takes no space.
  • Added online (module 05) and compacted by OPTIMIZE TABLE.
  • About 40% more CPU to read and write the row: under 5% of a key lookup, close to 40% in a full table scan.
-- the default comes from ndb-default-column-format, FIXED unless set
CREATE TABLE t1 (a INT COLUMN_FORMAT FIXED, b INT COLUMN_FORMAT DYNAMIC) ENGINE=NDB;

docs: row_data_structure.md (Fixed row format, Dynamic row format) · code: ha_ndbcluster.cc (ndb_default_column_format, default FIXED)

Sizing · memory per row, from the parts

What one row of a typical table costs in DataMemory

PartBytes per rowSource
Header with NULL bits and var reference28row_data_structure.md
Fixed-size columnstheir sizesa BIGINT is 8, an INT 4
Variable part: directory entry and end offset, + 2 per var column6tuppage.hpp, shrink_tuple
Variable-size valuestheir lengthsutf8mb4: up to 4 per character
Primary key hash index≈15basic_sql.md
Each ordered index, PRIMARY included unless USING HASH≈10basic_sql.md

Then multiply by the number of replicas. Words are 4 bytes, so parts are rounded up to whole words.

docs: row_data_structure.md · basic_sql.md (Index sizes) · module 13 sizes DataMemory for a whole cluster

PART 3

Changing a row

Updates work on a copy until commit.

Copy tuple · the uncommitted version

Copy tuples: an update writes a copy of the row in TransactionMemory

DataMemory row · version 7 · committedoperation word → the update below TransactionMemory operation record of the update header4 words change maskbit per column copy · version 8full row, new valuesevery column full size copied at the first write

The row's first header word points to the operation that owns it; RNIL means no transaction has it.

The first write copies the whole row into TransactionMemory and changes the copy. Every column gets its full size there, variable-size and disk columns too. The change mask records which columns changed.

code: dbtup/Dbtup.hpp (alloc_copy_tuple from RG_TRANSACTION_MEMORY, total_rec_size, COPY_TUPLE_HEADER32 4, ChangeMask) · DbtupMeta.cpp (total_rec_size: every column at its maximum size) · docs: row_data_structure.md (row header)

Concurrency · readers never wait for the writer

Concurrency: readers see the committed row; commit installs the copy, abort drops it

Read committed

Reads the committed version in DataMemory while the update works on its copy. No lock, no wait.

Commit

Copies the new values and version into the row at its row id. The copy is freed.

Abort

Frees the copy. The row in DataMemory was never touched.

If the update makes the variable part bigger, RonDB grows it at once and marks the row MM_GROWN: commit can then never run out of memory. An abort shrinks it back.

code: dbtup/Dbtup.hpp (Tuple_header comment on MM_GROWN) · module 09 covers locks and the commit protocol

Recap · module 07

What to take away

  • All memory is taken at startup, as 32 KB pages in 12 resource groups.
  • A row id is logical page + index; it never changes and is the same on every replica.
  • A row is a fixed part (header 16–36 bytes), a variable part and maybe a disk part.
  • Variable-size pages find entries through a directory at the end of the page.
  • Updates work on a copy in TransactionMemory; readers keep reading the committed row.

Next · 08 · Index structures

RonDB training · 25 modules · you are at 07

Next · 08 · Index structures