Logindex Anatomy

01What logindex is

An inverted index over WAL: given a page tag and an LSN range, hand back every record LSN that modified that page, in ascending order.

On a PolarDB replica the buffer pool is local but the data files are not. A backend that faults in a block gets whatever the primary last wrote to shared storage — a page that may be older than the replica's own replay position. The backend must therefore replay the missing WAL itself, for that one page, before anyone reads it. Logindex is the structure that makes this cheap: instead of scanning WAL, the backend asks for the LSNs that touch (rnode, forknum, blocknum) between the page's LSN and the replay point, and applies only those records.

Two independent snapshots are instantiated, each a complete self-contained logindex with its own directory, memory tables and bloom cache:

wal logindex — pg_logindex/, 75% of polar_logindex_mem_size. Indexes ordinary WAL records by page.
fullpage logindex — polar_fullpage/, 25%. Indexes full-page snapshots used when a replica reads a page from the future and must fall back to an older image. It is created with flush_active_table = true, which is the one behavioural difference between the two.

Figure 1. One snapshot end to end. Only the node that owns the WAL writes tables to shared storage; a replica's background worker instead re-reads log_index_meta and marks its own memory tables flushed, so its ring can be recycled.

02Constants that shape everything

Every size below is fixed at compile time in polar_logindex_internal.h. They determine the file layout, the bloom false-positive rate and the 12-bit order encoding.

Segments per table: 4096LOG_INDEX_MEM_TBL_SEG_NUM
Segment size: 48 Bhead and seg both
Hash buckets: 2048SEG_NUM / 2
Hash locks: 10242 buckets per lock
LSNs per head: 2then it chains
LSNs per seg: 10
Order slots: 409604096 × 10
Table on disk: 282664 B276.04 KB
Tables per file: 6417.25 MB per .tbl
Bloom slot: 4096 B2 per 8 KB SLRU page
Bloom bitset: 16384 bits2 KB actually used
Bloom hashes: k = 10capped at MAX_HASH_FUNCS

Table count is not a constant: polar_logindex_convert_mem_tbl_size() divides the configured megabytes by sizeof(log_mem_table_t) plus one padded LWLock, so roughly 3.7 memory tables per MB of polar_logindex_mem_size, split 75/25 between the two snapshots. Fewer than three tables is fatal at startup.

03Inside one table

A logindex table is three parallel arrays in one flat 276 KB struct — a bucket array, a segment arena, and an insertion-order log. No pointers, so the same bytes are the memory layout and the disk layout.

The unit of everything is log_idx_table_data_t. It holds a 32-bit prefix_lsn — the high half of every LSN in the table — and stores only 32-bit suffixes thereafter. That halves the LSN cost and is why a table is sealed the moment an LSN arrives with a different high word, whether or not the table is full (LOG_INDEX_SAME_TABLE_LSN_PREFIX). A table therefore spans at most 4 GB of WAL.

Buckets index into a 4096-slot arena of 48-byte cells. A cell is either a log_item_head_t (one page tag, 2 LSNs, a next_item pointer for the bucket chain and prev_page_lsn) or a log_item_seg_t (10 more LSNs, doubly linked to its siblings). Slot ids are 1-based; 0 means "none", which is why LOG_INDEX_ITEM_HEAD subtracts one.

Figure 2. The two access paths through a table. By tag — hash bucket, then a next_item chain of heads, then a next_seg chain of LSNs — serves the page iterator. By idx_order — a flat append log of (cell, index) pairs — serves the LSN iterator, which needs global WAL order rather than per-page order.

Derived from the encoding

LOG_INDEX_ORDER_SEG_MASK is 0x0FFF, so a cell id must fit in 12 bits, and LOG_INDEX_MEM_TBL_ADD_ORDER asserts seg_id < 4096. The allocator returns free_head and post-increments, while LOG_INDEX_MEM_TBL_FULL fires at free_head == 4096 — so ids 1…4095 are issued and the last arena slot, segment[4095], is unreachable by design. The 4-bit index field allows 0…14 and the widest cell holds 10 LSNs, so that half never saturates.

04The ring and the state machine

Tables live in a fixed circular array. Table id t always occupies slot (t-1) % mem_tbl_size, which is what lets every lookup jump straight to a slot and then verify the id.

Figure 3. State lives in an atomic uint32, so it can be read without the table lock; every transition is made under LOG_INDEX_MEM_TBL_LOCK. The active table also carries a fifth, implicit state — new — recognised by LOG_INDEX_MEM_TBL_IS_NEW when max_lsn, min_lsn, prefix_lsn and free_head are still at their initial values, because a fresh table cannot know its prefix until the first LSN arrives.

When a producer needs space and the active table is full or the prefix changed, it seals the current table, advances to the next slot and calls log_index_wait_active(). That routine spins — pg_usleep(10) with interrupt handling — until the target slot reaches ACTIVE, and if it finds the slot still INACTIVE it force-saves it inline rather than waiting for the background worker. This is the path taken during primary crash recovery, when no bgwriter exists yet.

05On disk

Three file kinds in one directory: a single meta record, fixed-stride table segments, and SLRU-managed bloom segments. Table id alone determines every offset.

Figure 4. Everything is O(1) address arithmetic from the table id. Both the table struct and each bloom slot carry their own CRC32C; a mismatch on read is a FATAL, not a silent skip.

Truncation and file reuse

polar_logindex_truncate(lsn) walks segments from the oldest while min_seg->max_lsn < lsn, always updating meta before touching files — a crash between the two leaves unreferenced files, which is recoverable, whereas the opposite order leaves meta pointing at files that no longer exist. The dropped file is not always deleted: if fewer than polar_max_logindex_files (default 80) segments are live, it is durable_rename()d forward to max_seg_no + 1 and reused, avoiding allocation churn on shared storage. Because a renamed file keeps stale tables past the ones just written, log_index_read_seg_file() scans backwards from the end of the buffer to find the highest id that is both in range and ≤ meta.max_idx_table_id.

Per-backend cost

log_index_read_table() caches one whole segment file in a function-level static log_table_cache_t — 64 tables, so about 17.25 MB of BSS per process that touches logindex from storage, faulted in lazily. The cache is keyed by directory name plus id range, so alternating reads between the wal and fullpage snapshots evict it every time.

06The writer

One process at a time inserts. That single-producer assumption is what the fast path in log_index_insert_lsn() is built on — and it is the reason the hash lock is only ever taken around the mutation itself.

Entry is polar_logindex_add_lsn(snapshot, tag, prev, lsn). Before the snapshot reaches the ADDING state it filters overlap against what storage already holds: LSNs below meta->start_lsn or below meta->max_lsn are dropped, and one exactly equal to max_lsn is checked tag-by-tag against the last flushed table by log_index_exists_in_saved_table(). The first LSN that survives flips the state bit permanently and logs "log index is insert from …".

Figure 5. The write barrier inside LOG_INDEX_MEM_TBL_ADD_ORDER publishes the order slot before last_order advances, and the matching pg_read_barrier() in log_index_get_order_lsn() keeps a concurrent LSN iterator from reading a slot the writer has not filled yet. That pair is the only lock-free handoff in the structure.

Why the flush-active lock exists at all

Only the fullpage snapshot sets flush_active_table. For it, the checkpointer may copy the currently active table out to disk while the writer is still inserting into it, which would compute a CRC over bytes that changed mid-copy. LOG_INDEX_FLUSH_ACTIVE_TBL_LOCK serialises the two: the writer holds it across the mutation and the max_lsn update, releasing it last precisely because max_lsn is covered by the CRC. For the wal snapshot the flag is false and the lock is never taken on the insert path.

07Saving: three writers, two rules

Bloom before table, table before meta. Everything else about flushing is scheduling.

Three distinct processes push tables toward storage, all funnelling into log_index_write_table():

logindex bg worker — polar_logindex_bg_write() each loop; on a writable node flushes up to polar_logindex_table_batch_size (default 100) INACTIVE tables per pass.
checkpointer — polar_logindex_redo_flush_data(checkpoint_lsn), which keeps flushing until the saved LSN passes the checkpoint rather than stopping at a batch limit.
logindex saver — a registered bgworker started only on a primary at PM_RUN. It drains the xlog send queue into the index (polar_logindex_save_lsn) and, every polar_write_logindex_active_table_delay, flushes the fullpage snapshot's active table.

Plus the inline fallback, log_index_force_save_table(), used by log_index_wait_active() when a producer needs a slot and no background process has freed it.

Figure 6. A flush of an active table stops after step 3: meta is deliberately not advanced, so the table remains re-writable and a reader still treats it as unsaved. Only the INACTIVE→FLUSHED path publishes durability.

The replica's version of flushing

A replica cannot write. log_index_replica_bg_write() instead re-reads log_index_meta from shared storage under the IO lock, then walks the ring backwards from (max_saved_tid - 1) % size marking every INACTIVE table with tid <= max_saved_tid as FLUSHED and invalidating its bloom cache page. It stops at the first non-INACTIVE table, relying on the invariant that inactive tables are contiguous. It also short-circuits entirely when max_idx_table_id has not moved since the last pass — so a quiet replica does no I/O.

Loop shape worth knowing

log_index_flush_table()'s outer do…while (need_flush) has no iteration bound when checkpoint_lsn is valid: it continues while the active table id exceeds meta->max_idx_table_id + 1 and checkpoint_lsn > meta->max_lsn and the checkpoint LSN is outside the active table's range. The batch-size cap applies only in the InvalidXLogRecPtr (background) case. Any state in which log_index_write_table() stops advancing meta->max_idx_table_id — for example the post-promote path where tables saved by the old primary are marked FLUSHED without a write — leaves that loop with no exit.

08Bloom filters

One filter per table, sized to skip a 276 KB read. It answers exactly one question: could this page tag appear anywhere in table t?

The filter is the shortcut for the page iterator's descent into storage. Without it, walking back through history for one page would mean reading every table between the current one and the target LSN — 276 KB each. With it, the iterator reads a 4 KB slot (usually already in the SLRU cache) and skips the table outright on a negative.

The sizing chain

Each slot is LOG_INDEX_FILE_TBL_BLOOM_SIZE = 4096 bytes. The header — table id, min/max LSN, buf_size, CRC — takes 32, leaving buf_size = 4064. polar_bloom_init_struct() overlays a bloom_filter whose own header is 24 bytes, leaving 4040 bytes of bitset. Then my_bloom_power() rounds the bit count down to a power of two: 32320 bits becomes 2¹⁴ = 16384 bits, so only 2 KB of the 4040 is addressable — the rest is padding that exists because the slot is sized for page alignment, not for the filter.

LOG_INDEX_BLOOM_ELEMS_NUM is 4096 × 0.2 = 819 expected tags. optimal_k() would want ⌈ln2 · 16384/819⌉ = 14 hash functions but MAX_HASH_FUNCS caps it at 10.

Figure 7. The filter is tuned for tables where each page accumulates several LSNs. A table dominated by distinct pages — a bulk load, an index build, a large sequential scan being written — approaches 4095 heads and the filter stops filtering; the iterator then reads and discards the full 276 KB table.

Cache mechanics

Blooms live in an SLRU (logindex_snapshot->bloom_ctl) sized by polar_logindex_bloom_blocks — 1024 pages by default, split 768/256 between the two snapshots. Two quirks matter:

Zero-page on the second half. Two blooms share an 8 KB page. A replica can read the page while only the first half is populated, so log_index_check_bloom_not_exists() checks for idx_table_id == 0, releases the LRU lock, force-invalidates the page and re-reads. A mismatch after that is a PANIC.
Lock returned held. log_index_get_tbl_bloom() calls SimpleLruReadPage_ReadOnly(), which returns with the SLRU lock still held; the caller memcpys the slot and releases LOG_INDEX_BLOOM_LRU_LOCK itself. The lock is not visible in the function signature.
Zeroing on write. A slot at page offset 0 is created with SimpleLruZeroPage(); any other offset reads the existing page first, so the neighbouring bloom survives.

09Page iterator

Search backwards, yield forwards. Given a tag and [min_lsn, max_lsn], it collects every matching LSN by walking table ids downward, then replays them in ascending order.

polar_logindex_create_page_iterator() does all the work up front — by the time it returns, every LSN is already materialised in memory, and _next() is a pure pop. That matters for locking: no logindex lock is held while WAL is being read and applied.

Figure 8. Two orderings in one pass. Tables are visited newest first so the scan can stop as soon as it reaches min_lsn; within the resulting stack-of-stacks the pop order restores WAL order. iter_max_lsn is tightened after each table so overlapping entries are not pushed twice.

Correctness guards

Hollow detection. Each item head stores prev_page_lsn. If the iterator reaches an in-range LSN before it has confirmed the predecessor, the requested history is not fully flushed and it raises an error rather than replaying a page from a gap.
Promote fence. With before_promote, the scan is capped at old_primary_max_tid and asserts max_lsn < old_primary_max_inserted_lsn, so a newly promoted primary never mixes its own index entries into a replay of the old primary's WAL.
One at a time. A backend may hold only one wal page iterator and one fullpage iterator; the statics wal_page_iter / fullpage_page_iter exist so an ERROR unwinds them.

10LSN iterator

The other consumer wants the opposite shape: every (tag, lsn) pair from a starting LSN forward, in WAL order, across all pages. That is a walk over idx_order.

It is created once by the background replay controller and pulled record by record. The first _next() call resolves the starting position in two stages — log_index_search_mem_tbl_lsn() descending the ring, falling through to log_index_search_file_tbl_lsn() — landing on a table and an order index, then flips to ITERATE_STATE_BACKWARD, which here means "now iterate forward through order slots".

Figure 9. One iterator, two mutually exclusive consumers — polar_logindex_redo_bg_replay() switches on bg_redo_state, so only one of the two ever runs. The active-table boundary is the subtle part: log_index_lsn_iterator_update() reads the table's state before reading last_order. Reading them the other way round would let the writer seal the table between the two loads, and the iterator would advance past entries appended in the window.

11The replica backend read path

Where all of this is actually spent: an ordinary ReadBuffer() on a replica, which must not return a page until the WAL that touches it has been applied.

Figure 10. The mini transaction is what makes multi-page records atomic for readers. If the backend can take the page's mini-transaction lock, the record is known to be fully parsed and replay may run to GetCurrentReplayRecPtr(); otherwise it stops at the last fully replayed record, polar_get_xlog_replay_recptr_nolock().

The OUTDATE handshake

Startup and the backend race over the same buffer. Three redo-state bits in the buffer descriptor arbitrate:

POLAR_REDO_READ_IO_END — the backend has finished physical I/O; only then is the page's own LSN meaningful.
POLAR_REDO_REPLAYING — a backend is inside the apply loop.
POLAR_REDO_OUTDATE — startup added an LSN for this page after the backend snapshotted the replay boundary.

If startup finds a buffer that is not yet read or is being replayed, it sets OUTDATE and moves on; the backend's do…while (redo_state & POLAR_REDO_REPLAYING) loop notices and replays again. If instead the buffer is settled, startup takes the content lock itself, adds the LSN under a freshly acquired mini-transaction lock, and marks OUTDATE — so parallel-replay backends know to catch up lazily.

Failure handling

Because replay runs inside HOLD_INTERRUPTS() with buffer redo state modified, an ERROR anywhere in the path would strand flags. Two aborts clean up: polar_logindex_abort_replaying_buffer() clears REPLAYING on polar_replaying_buffer, and polar_logindex_abort_mini_transaction() walks the per-process acquired_lock[] array releasing every mini-transaction page lock the process still holds.

12Lock reference

Five LWLock roles plus one spinlock per snapshot, laid out in a single padded array. The array order and the tranche-assignment order are not the same.

Offset	Lock	Count	Guards	Held by
0	MEM_TBL_LOCK(t)	mem_tbl_size	A table's state transition and its `data` when copied in or out wholesale	X: flusher, promote, load-from-storage. S: both iterators, `read_table`
+size	BLOOM_LRU_LOCK	1	The bloom SLRU's buffer pool — it is the SLRU control lock	X: `save_bloom`. S: returned held by `get_tbl_bloom`
+1	HASH_LOCK(key)	1024	Bucket chain and cell links in the ACTIVE table; 2 buckets per lock	X: writer, around the mutation only. S: page iterator, only when the table is ACTIVE
+1024	IO_LOCK	1	meta read/write and the whole bloom→table→meta write sequence	X: write_table, truncate, promote, set_start_lsn. S: COPY_META, start_lsn
+1	FLUSH_ACTIVE_TBL_LOCK	1	Copying an ACTIVE table for CRC while the writer inserts — fullpage snapshot only	X: writer and checkpointer, mutually
—	SNAPSHOT_LOCK (spin)	1	`max_idx_table_id`, `active_table`, `max_lsn`, `max_parsed_lsn`, and meta's max fields during a write	Every producer and every iterator, briefly

Tranche assignment ≠ array order

log_index_init_lwlock_array() assigns tranche ids in the order memtbl, hash, io, flush_active, bloom, matching the LWTRANCHE_WAL_LOGINDEX_* enum, while the array positions run memtbl, bloom, hash, io, flush_active. Both are correct — the offsets and the tranche loop are independent — but a new lock added to one list must be added to the other, and the enum's BEGIN/END pair must widen to match or the tranche_id == tranche_id_end assertion fires at startup.

Acquisition order

Table lock before hash lock. The page iterator takes MEM_TBL_LOCK shared, then HASH_LOCK shared, and releases in reverse. Nothing takes them the other way round.
Flush-active lock before hash lock. On the insert path, FLUSH_ACTIVE_TBL_LOCK is acquired outside HASH_LOCK and released after the snapshot spinlock section.
IO lock is outermost, and nests the bloom LRU lock. log_index_write_table() holds IO exclusively across save_bloom, which takes the bloom LRU lock inside it.
Spinlock is always innermost. No LWLock is acquired while SNAPSHOT_LOCK is held; the one place both appear — polar_logindex_used_mem_tbl_size() — takes IO first.
Mini-transaction locks sit outside all of them. The startup process holds a page's mini-transaction lock across polar_logindex_add_lsn(), which then takes the logindex locks inside it.
Conditional where a wait would be a deadlock. log_index_read_table() and the file-table phase of the page iterator use LWLockConditionalAcquire on ring slots — a miss simply means reading from storage instead.

Lock-free by design

Table state is pg_atomic_uint32, read without any lock to pick a fast path; every write happens under the table lock.
The writer scans the active table for an existing tag with no lock at all, valid only because there is exactly one producer per snapshot.
idx_order publication is a pg_write_barrier() / pg_read_barrier() pair around last_order.
Mini-transaction refcount is atomic; mini_trans_end() spins on it rather than holding the table lock while it drains.