XFS Logging Design

문서 목적과 전개 순서

이 문서는 `GPL-2.0`으로 배포되는 “XFS Logging Design” 문서이며, XFS journalling subsystem의 기반 설계와 algorithm을 설명합니다. 독자가 XFS의 transaction 처리가 어떻게 동작하는지 전체 개념을 익힐 수 있도록 작성됐습니다.

설명은 XFS transaction의 개요에서 시작해 transaction reservation의 구조와 계산 방식으로 이어집니다. 그런 다음 제한된 초기 reservation으로 장시간 transaction의 forward progress를 보장하는 방법, relogging의 의미, delayed logging mechanism의 설계를 차례로 다룹니다.

.. SPDX-License-Identifier: GPL-2.0

==================
XFS Logging Design
==================

Preamble
========

This document describes the design and algorithms that the XFS journalling
subsystem is based on. This document describes the design and algorithms that
the XFS journalling subsystem is based on so that readers may familiarize
themselves with the general concepts of how transaction processing in XFS works.

We begin with an overview of transactions in XFS, followed by describing how
transaction reservations are structured and accounted, and then move into how we
guarantee forwards progress for long running transactions with finite initial
reservations bounds. At this point we need to explain how relogging works. With
the basic concepts covered, the design of the delayed logging mechanism is
documented.

Write Ahead Logging과 object별 기록 방식

XFS는 filesystem metadata 변경을 atomic하고 복구 가능하게 만들기 위해 Write Ahead Logging을 사용합니다. 공간과 처리 시간의 효율을 위해 하나의 방식만 쓰지 않고 intent, logical logging, physical logging을 결합해 필요한 recovery 보장을 제공합니다.

Inode와 dquot 같은 일부 object는 on-disk structure 전체가 아니라 in-core structure의 변경 내용을 logical format으로 기록합니다. 반면 보통 buffer인 다른 object는 physical change를 기록합니다. 오래 실행되는 atomic modification은 개별 변경을 intent로 연결하므로, system이 중단됐을 때 journal recovery가 부분 수행된 operation을 다시 시작해 끝낼 수 있습니다.

이 차이는 변경 object를 처리하는 log space와 CPU 시간을 줄여 metadata logging overhead를 최소화하기 위한 것입니다. 어떤 item은 매우 자주 바뀌고 object 안에서도 특정 부분이 더 자주 바뀌므로 낮은 logging overhead가 중요합니다.

이 문서의 범위에서는 object를 기록하거나 변경을 연결하는 구체적 방법보다 logging subsystem이 요구하는 규칙이 중요합니다. 실제 방식은 object와 modification에 따라 다르지만, 모두 forward progress를 보장하고 deadlock을 막는 규칙을 지켜야 합니다.

Introduction
============

XFS uses Write Ahead Logging for ensuring changes to the filesystem metadata
are atomic and recoverable. For reasons of space and time efficiency, the
logging mechanisms are varied and complex, combining intents, logical and
physical logging mechanisms to provide the necessary recovery guarantees the
filesystem requires.

Some objects, such as inodes and dquots, are logged in logical format where the
details logged are made up of the changes to in-core structures rather than
on-disk structures. Other objects - typically buffers - have their physical
changes logged. Long running atomic modifications have individual changes
chained together by intents, ensuring that journal recovery can restart and
finish an operation that was only partially done when the system stopped
functioning.

The reason for these differences is to keep the amount of log space and CPU time
required to process objects being modified as small as possible and hence the
logging overhead as low as possible. Some items are very frequently modified,
and some parts of objects are more frequently modified than others, so keeping
the overhead of metadata logging low is of prime importance.

The method used to log an item or chain modifications together isn't
particularly important in the scope of this document. It suffices to know that
the method used for logging a particular object or chaining modifications
together are different and are dependent on the object and/or modification being
performed. The logging subsystem only cares that certain specific rules are
followed to guarantee forwards progress and prevent deadlocks.

One-shot과 permanent transaction

XFS의 상위 transaction은 log space reservation 유형에 따라 `one-shot`과 `permanent` 두 종류입니다. Permanent reservation은 commit 경계를 넘어 유지될 수 있지만, one-shot transaction은 한 번의 atomic modification만 수행합니다. Reservation 유형과 크기는 modification에 맞아야 하므로 permanent reservation으로 one-shot 변경을 수행할 수는 있어도 그 반대는 허용되지 않습니다.

One-shot pattern은 `xfs_trans_alloc(<reservation>)`으로 transaction을 만들고 item을 잠가 join한 뒤 변경을 수행하고 `xfs_trans_commit(tp)`으로 끝냅니다. Transaction handle은 item의 dirty region을 추적하며, commit 후에는 join된 resource와 allocation 시점에 확보했다가 사용하지 않은 reservation space가 모두 해제됩니다.

Permanent transaction은 여러 개의 연결된 개별 transaction으로 구성됩니다. Inode를 `XFS_ILOCK_EXCL`로 잠근 채 loop마다 `xfs_trans_ijoin`, 수정, `xfs_trans_log_inode`, `xfs_trans_roll`을 수행하고 마지막에 commit과 unlock을 합니다. `xfs_trans_roll()`은 기존 transaction을 복제하고 commit한 뒤 새 transaction에 space를 reserve해 두 transaction을 연결합니다.

이 rolling transaction chain에서는 inode lock이 전체 chain에 걸쳐 유지되므로 외부 관찰자에게 복잡한 변경이 atomic하게 보입니다. 그러나 journal 관점에서 chain 전체가 atomic한 것은 아닙니다. 각 개별 변경만 atomic하며 crash 후에는 journal에 commit된 마지막 transaction까지만 replay됩니다.

따라서 여러 transaction이 필요한 상위 operation은 첫 transaction이 on-disk journal에 지속된 뒤 recovery가 나머지를 완료할 수 있도록 intent와 deferred operation을 사용해야 합니다. 장시간 operation의 어느 지점까지 stale storage에 도달했는지는 예측할 수 없습니다.

Transactions in XFS
===================

XFS has two types of high level transactions, defined by the type of log space
reservation they take. These are known as "one shot" and "permanent"
transactions. Permanent transaction reservations can take reservations that span
commit boundaries, whilst "one shot" transactions are for a single atomic
modification.

The type and size of reservation must be matched to the modification taking
place.  This means that permanent transactions can be used for one-shot
modifications, but one-shot reservations cannot be used for permanent
transactions.

In the code, a one-shot transaction pattern looks somewhat like this::

        tp = xfs_trans_alloc(<reservation>)
        <lock items>
        <join item to transaction>
        <do modification>
        xfs_trans_commit(tp);

As items are modified in the transaction, the dirty regions in those items are
tracked via the transaction handle.  Once the transaction is committed, all
resources joined to it are released, along with the remaining unused reservation
space that was taken at the transaction allocation time.

In contrast, a permanent transaction is made up of multiple linked individual
transactions, and the pattern looks like this::

        tp = xfs_trans_alloc(<reservation>)
        xfs_ilock(ip, XFS_ILOCK_EXCL)

        loop {
                xfs_trans_ijoin(tp, 0);
                <do modification>
                xfs_trans_log_inode(tp, ip);
                xfs_trans_roll(&tp);
        }

        xfs_trans_commit(tp);
        xfs_iunlock(ip, XFS_ILOCK_EXCL);

While this might look similar to a one-shot transaction, there is an important
difference: xfs_trans_roll() performs a specific operation that links two
transactions together::

        ntp = xfs_trans_dup(tp);
        xfs_trans_commit(tp);
        xfs_trans_reserve(ntp);

This results in a series of "rolling transactions" where the inode is locked
across the entire chain of transactions.  Hence while this series of rolling
transactions is running, nothing else can read from or write to the inode and
this provides a mechanism for complex changes to appear atomic from an external
observer's point of view.

It is important to note that a series of rolling transactions in a permanent
transaction does not form an atomic change in the journal. While each
individual modification is atomic, the chain is *not atomic*. If we crash half
way through, then recovery will only replay up to the last transactional
modification the loop made that was committed to the journal.

This affects long running permanent transactions in that it is not possible to
predict how much of a long running operation will actually be recovered because
there is no guarantee of how much of the operation reached stale storage. Hence
if a long running operation requires multiple transactions to fully complete,
the high level operation must use intents and deferred operations to guarantee
recovery can complete the operation once the first transactions is persisted in
the on-disk journal.

비동기 commit과 log force

XFS의 모든 상위 transaction은 기본적으로 asynchronous입니다. 그러므로 `xfs_trans_commit()`이 반환됐다고 modification이 stable storage에 기록됐다는 보장은 없고, crash가 발생하면 완료됐던 transaction 중 일부는 recovery에서 replay되지 않을 수 있습니다.

다만 logging subsystem은 전역 순서를 보장합니다. Recovery 뒤 특정 변경이 보인다면 그 변경보다 먼저 commit된 모든 metadata modification도 함께 보입니다.

즉시 stable storage에 도달해야 하는 one-shot operation이나 완료된 permanent transaction 전체를 지속해야 할 때는 transaction을 synchronous로 표시할 수 있습니다. 그러면 `log force`가 아직 남은 committed transaction을 journal의 stable storage로 flush하고 완료를 기다립니다.

Synchronous transaction은 logging throughput을 underlying storage의 I/O latency로 제한하므로 드물게 사용됩니다. 보통 `fsync`처럼 user operation이 synchronization point를 요구할 때만 log force로 지속성을 확보합니다.

Transactions are Asynchronous
=============================

In XFS, all high level transactions are asynchronous by default. This means that
xfs_trans_commit() does not guarantee that the modification has been committed
to stable storage when it returns. Hence when a system crashes, not all the
completed transactions will be replayed during recovery.

However, the logging subsystem does provide global ordering guarantees, such
that if a specific change is seen after recovery, all metadata modifications
that were committed prior to that change will also be seen.

For single shot operations that need to reach stable storage immediately, or
ensuring that a long running permanent transaction is fully committed once it is
complete, we can explicitly tag a transaction as synchronous. This will trigger
a "log force" to flush the outstanding committed transactions to stable storage
in the journal and wait for that to complete.

Synchronous transactions are rarely used, however, because they limit logging
throughput to the IO latency limitations of the underlying storage. Instead, we
tend to use log forces to ensure modifications are on stable storage only when
a user operation requires a synchronisation point to occur (e.g. fsync).

최악 조건의 unit reservation과 log count

Transaction reservation은 journal 공간 부족 때문에 modification이 중간에 멈추지 않도록 forward progress를 보장합니다. Transaction을 처음 할당할 때, object를 바꾸기 전에 해당 변경을 journal에 기록할 physical log space가 있음을 보장하며 permanent transaction에서는 rolling mechanism이 reservation을 유지합니다.

Reservation은 최악 조건에서 기록할 metadata 양보다 충분히 커야 합니다. 예를 들어 transaction이 btree를 수정하면 leaf에서 root까지 full split을 기록할 공간을 포함해야 합니다. User data extent allocation 하나도 free-space btree 두 개, inode extent-map btree, 추가 allocation에 따른 free-space tree 재수정, reverse-mapping btree 변경까지 연쇄할 수 있으므로 단순해 보이는 operation이 많은 metadata를 바꿀 수 있습니다.

이 최악 조건 계산으로 mount 시 transaction의 정적 `unit reservation`을 정합니다. Transaction이 진행하기 전에 log에 이만큼의 여유를 보장해 dirty metadata를 쓰는 도중 공간이 고갈되지 않게 합니다.

One-shot transaction에는 unit 하나면 충분합니다. Permanent transaction에는 예상 roll 횟수를 나타내는 `log count`가 추가됩니다. Unit 하나만 매번 다시 reserve할 수도 있지만, 구현이 흔한 경로의 roll 횟수를 알기 때문에 여러 unit을 처음부터 확보하면 각 roll마다 re-reserve할 필요가 없습니다.

예를 들어 inode allocation은 보통 free inode chunk를 disk에 할당하는 transaction과 그 chunk에서 inode를 할당하는 transaction 두 개이므로 log count를 2로 둘 수 있습니다. 각 roll이 unit 하나를 소비하고 count가 0이 되면 physical log space를 다시 reserve해야 합니다.

Transaction Reservations
========================

It has been mentioned a number of times now that the logging subsystem needs to
provide a forwards progress guarantee so that no modification ever stalls
because it can't be written to the journal due to a lack of space in the
journal. This is achieved by the transaction reservations that are made when
a transaction is first allocated. For permanent transactions, these reservations
are maintained as part of the transaction rolling mechanism.

A transaction reservation provides a guarantee that there is physical log space
available to write the modification into the journal before we start making
modifications to objects and items. As such, the reservation needs to be large
enough to take into account the amount of metadata that the change might need to
log in the worst case. This means that if we are modifying a btree in the
transaction, we have to reserve enough space to record a full leaf-to-root split
of the btree. As such, the reservations are quite complex because we have to
take into account all the hidden changes that might occur.

For example, a user data extent allocation involves allocating an extent from
free space, which modifies the free space trees. That's two btrees.  Inserting
the extent into the inode's extent map might require a split of the extent map
btree, which requires another allocation that can modify the free space trees
again.  Then we might have to update reverse mappings, which modifies yet
another btree which might require more space. And so on.  Hence the amount of
metadata that a "simple" operation can modify can be quite large.

This "worst case" calculation provides us with the static "unit reservation"
for the transaction that is calculated at mount time. We must guarantee that the
log has this much space available before the transaction is allowed to proceed
so that when we come to write the dirty metadata into the log we don't run out
of log space half way through the write.

For one-shot transactions, a single unit space reservation is all that is
required for the transaction to proceed. For permanent transactions, however, we
also have a "log count" that affects the size of the reservation that is to be
made.

While a permanent transaction can get by with a single unit of space
reservation, it is somewhat inefficient to do this as it requires the
transaction rolling mechanism to re-reserve space on every transaction roll. We
know from the implementation of the permanent transactions how many transaction
rolls are likely for the common modifications that need to be made.

For example, an inode allocation is typically two transactions - one to
physically allocate a free inode chunk on disk, and another to allocate an inode
from an inode chunk that has free inodes in it.  Hence for an inode allocation
transaction, we might set the reservation log count to a value of 2 to indicate
that the common/fast path transaction will commit two linked transactions in a
chain. Each time a permanent transaction rolls, it consumes an entire unit
reservation.

Hence when the permanent transaction is first allocated, the log space
reservation is increased from a single unit reservation to multiple unit
reservations. That multiple is defined by the reservation log count, and this
means we can roll the transaction multiple times before we have to re-reserve
log space when we roll the transaction. This ensures that the common
modifications we make only need to reserve log space once.

If the log count for a permanent transaction reaches zero, then it needs to
re-reserve physical space in the log. This is somewhat complex, and requires
an understanding of how the log accounts for space that has been reserved.

LSN과 reserve/write grant head

Log 위치는 일반적으로 Log Sequence Number(LSN)로 표현합니다. Circular log에서 LSN의 상위 32bit는 log가 덮어써진 cycle 횟수이고 하위 32bit는 512byte `basic block` 단위 offset입니다. 이 표현으로 log의 사용 가능 공간을 비교적 간단히 계산합니다.

공간 accounting에는 두 `grant head`를 사용합니다. Grant head는 absolute position이며, 현재 log tail과 head 사이의 거리가 head가 log를 완전히 돌아 tail을 추월하기 전 reserve하거나 소비할 수 있는 공간입니다.

`reserve` head는 active transaction이 보유한 reservation의 byte count를 추적하는 순수 in-memory accounting입니다. 정확한 byte offset을 추적하므로 엄밀히는 basic-block LSN이 아니지만 `{cycle, offset}` tuple처럼 다룹니다. Reserve head가 tail에 도달하면 새 reservation을 FIFO queue에서 막고, tail이 전진해 충분한 공간이 생기면 순서대로 깨웁니다. 이 FIFO는 공간 부족 때 transaction starvation을 막습니다.

`write` head는 실제 LSN을 가지며 log의 physical space 사용량을 추적합니다. 평상시 두 head는 거의 같은 위치지만, rolling permanent transaction의 log count가 0이 됐을 때 차이가 forward progress를 보장합니다.

Commit 도중 새 공간을 기다리며 sleep하면 lock을 잡은 item이 log tail을 pin할 수 있고, FIFO 앞 reservation이 충족될 만큼 tail이 움직이지 못해 self-deadlock이 생길 수 있습니다. 따라서 physical space는 overcommit할 수 없지만 accounting만 하는 reserve head는 tail을 넘어 overcommit할 수 있습니다. 이 경우 새 reservation만 즉시 throttle되고 tail이 전진할 때까지 기다립니다.

Permanent transaction은 `xfs_trans_commit()` 중 reservation space를 `regrant`하고, commit이 끝난 뒤 `xfs_log_reserve()`로 write head의 physical space를 별도로 reserve합니다. 이때 안전하게 sleep하려면 rolling chain이 잠근 item을 매 roll마다 반드시 log해야 합니다.

매 roll에서 잠근 item을 relog하면 item이 physical log head 쪽으로 이동해 tail을 pin하지 않습니다. 그래야 write reservation을 기다리는 동안 해당 item의 writeback lock을 얻지 못해 생기는 deadlock을 피하고, 모든 rolling transaction이 독립적으로 forward progress를 낼 수 있습니다.

Log Space Accounting
====================

The position in the log is typically referred to as a Log Sequence Number (LSN).
The log is circular, so the positions in the log are defined by the combination
of a cycle number - the number of times the log has been overwritten - and the
offset into the log.  A LSN carries the cycle in the upper 32 bits and the
offset in the lower 32 bits. The offset is in units of "basic blocks" (512
bytes). Hence we can do relatively simple LSN based math to keep track of
available space in the log.

Log space accounting is done via a pair of constructs called "grant heads".  The
position of the grant heads is an absolute value, so the amount of space
available in the log is defined by the distance between the position of the
grant head and the current log tail. That is, how much space can be
reserved/consumed before the grant heads would fully wrap the log and overtake
the tail position.

The first grant head is the "reserve" head. This tracks the byte count of the
reservations currently held by active transactions. It is a purely in-memory
accounting of the space reservation and, as such, actually tracks byte offsets
into the log rather than basic blocks. Hence it technically isn't using LSNs to
represent the log position, but it is still treated like a split {cycle,offset}
tuple for the purposes of tracking reservation space.

The reserve grant head is used to accurately account for exact transaction
reservations amounts and the exact byte count that modifications actually make
and need to write into the log. The reserve head is used to prevent new
transactions from taking new reservations when the head reaches the current
tail. It will block new reservations in a FIFO queue and as the log tail moves
forward it will wake them in order once sufficient space is available. This FIFO
mechanism ensures no transaction is starved of resources when log space
shortages occur.

The other grant head is the "write" head. Unlike the reserve head, this grant
head contains an LSN and it tracks the physical space usage in the log. While
this might sound like it is accounting the same state as the reserve grant head
- and it mostly does track exactly the same location as the reserve grant head -
there are critical differences in behaviour between them that provides the
forwards progress guarantees that rolling permanent transactions require.

These differences when a permanent transaction is rolled and the internal "log
count" reaches zero and the initial set of unit reservations have been
exhausted. At this point, we still require a log space reservation to continue
the next transaction in the sequeunce, but we have none remaining. We cannot
sleep during the transaction commit process waiting for new log space to become
available, as we may end up on the end of the FIFO queue and the items we have
locked while we sleep could end up pinning the tail of the log before there is
enough free space in the log to fulfill all of the pending reservations and
then wake up transaction commit in progress.

To take a new reservation without sleeping requires us to be able to take a
reservation even if there is no reservation space currently available. That is,
we need to be able to *overcommit* the log reservation space. As has already
been detailed, we cannot overcommit physical log space. However, the reserve
grant head does not track physical space - it only accounts for the amount of
reservations we currently have outstanding. Hence if the reserve head passes
over the tail of the log all it means is that new reservations will be throttled
immediately and remain throttled until the log tail is moved forward far enough
to remove the overcommit and start taking new reservations. In other words, we
can overcommit the reserve head without violating the physical log head and tail
rules.

As a result, permanent transactions only "regrant" reservation space during
xfs_trans_commit() calls, while the physical log space reservation - tracked by
the write head - is then reserved separately by a call to xfs_log_reserve()
after the commit completes. Once the commit completes, we can sleep waiting for
physical log space to be reserved from the write grant head, but only if one
critical rule has been observed::

        Code using permanent reservations must always log the items they hold
        locked across each transaction they roll in the chain.

"Re-logging" the locked items on every transaction roll ensures that the items
attached to the transaction chain being rolled are always relocated to the
physical head of the log and so do not pin the tail of the log. If a locked item
pins the tail of the log when we sleep on the write reservation, then we will
deadlock the log as we cannot take the locks needed to write back that item and
move the tail of the log forwards to free up write grant space. Re-logging the
locked items avoids this deadlock and guarantees that the log reservation we are
making cannot self-deadlock.

If all rolling transactions obey this rule, then they can all make forwards
progress independently because nothing will block the progress of the log
tail moving forwards and hence ensuring that write grant space is always
(eventually) made available to permanent transactions no matter how many times
they roll.

Relogging의 누적 변경과 I/O 한계

XFS는 한 object의 서로 다른 modification 여러 개를 동시에 log에 보관할 수 있으며, 새 변경을 기록하기 전에 이전 변경을 disk로 flush할 필요가 없습니다. `Relogging`은 새 transaction에 새 변경뿐 아니라 아직 log에만 존재하는 기존 변경의 새 copy를 모두 함께 기록하는 방식입니다.

변경 A부터 D까지 object가 disk에 기록되지 않았다면 각 transaction의 내용은 A, A+B, A+B+C, A+B+C+D로 누적됩니다. D 뒤 object가 disk에 기록되면 새 기준에서 E와 E+F가 기록됩니다. 각 relogging에서 LSN이 증가하므로 object가 log head 쪽으로 이동하고 tail을 계속 붙잡지 않습니다.

대표적인 rolling transaction은 reservation 크기 때문에 transaction 하나에서 extent 두 개씩만 제거할 수 있는 inode extent removal입니다. 각 반복에서 inode와 btree buffer를 relog해 log가 wrap되어도 현재 operation이 자기 자신을 막지 않게 합니다.

Relogging은 XFS journal의 올바른 동작에 필수지만 같은 변경을 여러 번 기록해 metadata log write를 늘립니다. Object가 점점 더 dirty해지므로 후속 transaction이 더 많은 metadata를 기록할 수도 있습니다.

Asynchronous transaction은 log buffer가 가득 차거나 synchronous operation이 force할 때까지 physical journal에 쓰이지 않으므로 transaction을 memory에서 batch합니다. 기본 log manager는 32KiB buffer 8개를 제공하고 mount option으로 각 buffer를 최대 256KiB까지 늘릴 수 있습니다. 모든 buffer가 I/O 중이면 batch가 끝날 때까지 새 transaction을 commit할 수 없으며, 현재는 CPU core 하나만으로도 buffer를 계속 가득 채울 수 있어 logging subsystem이 I/O bound가 될 수 있습니다.

Re-logging Explained
====================

XFS allows multiple separate modifications to a single object to be carried in
the log at any given time.  This allows the log to avoid needing to flush each
change to disk before recording a new change to the object. XFS does this via a
method called "re-logging". Conceptually, this is quite simple - all it requires
is that any new change to the object is recorded with a *new copy* of all the
existing changes in the new transaction that is written to the log.

That is, if we have a sequence of changes A through to F, and the object was
written to disk after change D, we would see in the log the following series
of transactions, their contents and the log sequence number (LSN) of the
transaction::

        Transaction                Contents        LSN
           A                           A                   X
           B                          A+B                  X+n
           C                         A+B+C                 X+n+m
           D                        A+B+C+D                X+n+m+o
            <object written to disk>
           E                           E                   Y (> X+n+m+o)
           F                          E+F                  Y+p

In other words, each time an object is relogged, the new transaction contains
the aggregation of all the previous changes currently held only in the log.

This relogging technique allows objects to be moved forward in the log so that
an object being relogged does not prevent the tail of the log from ever moving
forward.  This can be seen in the table above by the changing (increasing) LSN
of each subsequent transaction, and it's the technique that allows us to
implement long-running, multiple-commit permanent transactions. 

A typical example of a rolling transaction is the removal of extents from an
inode which can only be done at a rate of two extents per transaction because
of reservation size limitations. Hence a rolling extent removal transaction
keeps relogging the inode and btree buffers as they get modified in each
removal operation. This keeps them moving forward in the log as the operation
progresses, ensuring that current operation never gets blocked by itself if the
log wraps around.

Hence it can be seen that the relogging operation is fundamental to the correct
working of the XFS journalling subsystem. From the above description, most
people should be able to see why the XFS metadata operations writes so much to
the log - repeated operations to the same objects write the same changes to
the log over and over again. Worse is the fact that objects tend to get
dirtier as they get relogged, so each subsequent transaction is writing more
metadata into the log.

It should now also be obvious how relogging and asynchronous transactions go
hand in hand. That is, transactions don't get written to the physical journal
until either a log buffer is filled (a log buffer can hold multiple
transactions) or a synchronous operation forces the log buffers holding the
transactions to disk. This means that XFS is doing aggregation of transactions
in memory - batching them, if you like - to minimise the impact of the log IO on
transaction throughput.

The limitation on asynchronous transaction throughput is the number and size of
log buffers made available by the log manager. By default there are 8 log
buffers available and the size of each is 32kB - the size can be increased up
to 256kB by use of a mount option.

Effectively, this gives us the maximum bound of outstanding metadata changes
that can be made to the filesystem at any point in time - if all the log
buffers are full and under IO, then no more transactions can be committed until
the current batch completes. It is now common for a single current CPU core to
be to able to issue enough transactions to keep the log buffers full and under
IO permanently. Hence the XFS journalling subsystem can be considered to be IO
bound.

Stale copy 제거와 delayed logging 요구사항

Asynchronous logging과 relogging을 함께 사용하면 object가 log buffer에 commit되기 전에 memory에서 여러 번 relog될 수 있습니다. 예를 들어 A부터 D까지 같은 buffer에 들어가면 마지막 D copy가 이전 변경을 전부 포함하므로 A, B, C copy는 필요 없는 stale copy입니다.

같은 object 집합을 반복 수정하는 workload에서는 stale object가 log buffer 공간의 90%를 넘을 수 있습니다. 이를 줄여 metadata log write를 대폭 감소시키는 것이 delayed logging의 핵심 목표입니다.

기존 XFS도 사실상 log buffer memory 안에서 relogging하지만 logical change를 physical format으로 바꾼 뒤 추적하기 때문에 비효율적입니다. Log buffer 밖의 memory에서 transaction change를 logical하게 유지하고 추적하는 방식을 `delayed logging`이라 부릅니다. 기존 log item이 변경을 이미 추적하므로 핵심 문제는 이를 누적한 뒤 일관되고 복구 가능한 형태로 log에 전달하는 것입니다.

Delayed logging은 outstanding metadata 양을 log buffer 수와 크기로부터 분리합니다. 기존 약 2MiB 경계보다 훨씬 많은 변경이 memory에 누적될 수 있어 crash 때 사라질 수 있는 transaction 수가 커집니다. 그러나 recovery가 consistent filesystem을 만든다는 보장은 변하지 않습니다. 지속성이 필요한 application은 필요한 지점에서 `fsync()`를 사용해야 합니다.

Memory에서 변경을 모았다가 log에 쓰는 개념은 ext3와 ext4에서도 사용되므로 문서는 개념의 타당성 증명보다 XFS 구현 engineering에 집중합니다.

요구사항은 metadata log write를 최소 한 order of magnitude 줄이고 이를 검증할 통계와 debugging trace를 제공하며, on-disk metadata와 log format을 바꾸지 않는 것입니다. Mount option으로 enable/disable할 수 있어야 하고 synchronous transaction workload에 performance regression이 없어야 합니다.

Delayed Logging: Concepts
=========================

The key thing to note about the asynchronous logging combined with the
relogging technique XFS uses is that we can be relogging changed objects
multiple times before they are committed to disk in the log buffers. If we
return to the previous relogging example, it is entirely possible that
transactions A through D are committed to disk in the same log buffer.

That is, a single log buffer may contain multiple copies of the same object,
but only one of those copies needs to be there - the last one "D", as it
contains all the changes from the previous changes. In other words, we have one
necessary copy in the log buffer, and three stale copies that are simply
wasting space. When we are doing repeated operations on the same set of
objects, these "stale objects" can be over 90% of the space used in the log
buffers. It is clear that reducing the number of stale objects written to the
log would greatly reduce the amount of metadata we write to the log, and this
is the fundamental goal of delayed logging.

From a conceptual point of view, XFS is already doing relogging in memory (where
memory == log buffer), only it is doing it extremely inefficiently. It is using
logical to physical formatting to do the relogging because there is no
infrastructure to keep track of logical changes in memory prior to physically
formatting the changes in a transaction to the log buffer. Hence we cannot avoid
accumulating stale objects in the log buffers.

Delayed logging is the name we've given to keeping and tracking transactional
changes to objects in memory outside the log buffer infrastructure. Because of
the relogging concept fundamental to the XFS journalling subsystem, this is
actually relatively easy to do - all the changes to logged items are already
tracked in the current infrastructure. The big problem is how to accumulate
them and get them to the log in a consistent, recoverable manner.
Describing the problems and how they have been solved is the focus of this
document.

One of the key changes that delayed logging makes to the operation of the
journalling subsystem is that it disassociates the amount of outstanding
metadata changes from the size and number of log buffers available. In other
words, instead of there only being a maximum of 2MB of transaction changes not
written to the log at any point in time, there may be a much greater amount
being accumulated in memory. Hence the potential for loss of metadata on a
crash is much greater than for the existing logging mechanism.

It should be noted that this does not change the guarantee that log recovery
will result in a consistent filesystem. What it does mean is that as far as the
recovered filesystem is concerned, there may be many thousands of transactions
that simply did not occur as a result of the crash. This makes it even more
important that applications that care about their data use fsync() where they
need to ensure application level data integrity is maintained.

It should be noted that delayed logging is not an innovative new concept that
warrants rigorous proofs to determine whether it is correct or not. The method
of accumulating changes in memory for some period before writing them to the
log is used effectively in many filesystems including ext3 and ext4. Hence
no time is spent in this document trying to convince the reader that the
concept is sound. Instead it is simply considered a "solved problem" and as
such implementing it in XFS is purely an exercise in software engineering.

The fundamental requirements for delayed logging in XFS are simple:

        1. Reduce the amount of metadata written to the log by at least
           an order of magnitude.
        2. Supply sufficient statistics to validate Requirement #1.
        3. Supply sufficient new tracing infrastructure to be able to debug
           problems with the new code.
        4. No on-disk format change (metadata or log format).
        5. Enable and disable with a mount option.
        6. No performance regressions for synchronous transaction workloads.

일관된 log vector snapshot 저장

Logical dirty-region tracking만 유지하다 flush 시 object를 format하면 동시 변경을 막기 위해 모든 object를 다시 lock해야 합니다. Transaction이 object A를 잠근 채 delayed-logging tracking lock을 기다리고 flush thread가 tracking lock을 잡은 채 A의 lock을 기다리면 해소할 수 없는 deadlock이 됩니다.

해결책은 transaction commit 중 object가 이미 잠겨 있을 때 기존 formatter가 만든 vector array를 별도 memory buffer로 복사하는 것입니다. Vector address도 object가 아니라 이 buffer를 가리키게 다시 쓰면 transactionally consistent한 snapshot이 만들어지고, 이후 item lock 없이 기존 log-buffer writer가 사용할 수 있습니다.

기존 방식은 vector가 object의 변경 region을 직접 가리키고 commit 중 해당 memory를 log buffer로 복사합니다. Delayed 방식은 먼저 memory buffer에 V1, V2, V3를 연속 복사한 뒤 각 vector를 buffer 안의 대응 region으로 다시 연결합니다.

Memory buffer와 vector는 하나의 object처럼 전달하되, object가 다시 relog될 때 최신 변경을 담은 새 buffer로 교체할 수 있도록 parent log item과 연결돼야 합니다.

Vector를 유지하는 이유는 log buffer 경계에서 region을 올바르게 split하기 위해서입니다. Vector를 버리면 region boundary를 알 수 없어 이중 encapsulation이나 새 on-disk format이 필요하고, log write 시점에만 알 수 있는 per-region state도 formatting 단계에서 header에 넣어야 합니다. Buffer를 vector에 붙이고 address만 다시 쓰면 기존 log vector와 동일하게 처리하는 self-describing object가 되어 on-disk format 변경을 피합니다.

Delayed Logging: Design
=======================

Storing Changes
---------------

The problem with accumulating changes at a logical level (i.e. just using the
existing log item dirty region tracking) is that when it comes to writing the
changes to the log buffers, we need to ensure that the object we are formatting
is not changing while we do this. This requires locking the object to prevent
concurrent modification. Hence flushing the logical changes to the log would
require us to lock every object, format them, and then unlock them again.

This introduces lots of scope for deadlocks with transactions that are already
running. For example, a transaction has object A locked and modified, but needs
the delayed logging tracking lock to commit the transaction. However, the
flushing thread has the delayed logging tracking lock already held, and is
trying to get the lock on object A to flush it to the log buffer. This appears
to be an unsolvable deadlock condition, and it was solving this problem that
was the barrier to implementing delayed logging for so long.

The solution is relatively simple - it just took a long time to recognise it.
Put simply, the current logging code formats the changes to each item into an
vector array that points to the changed regions in the item. The log write code
simply copies the memory these vectors point to into the log buffer during
transaction commit while the item is locked in the transaction. Instead of
using the log buffer as the destination of the formatting code, we can use an
allocated memory buffer big enough to fit the formatted vector.

If we then copy the vector into the memory buffer and rewrite the vector to
point to the memory buffer rather than the object itself, we now have a copy of
the changes in a format that is compatible with the log buffer writing code.
that does not require us to lock the item to access. This formatting and
rewriting can all be done while the object is locked during transaction commit,
resulting in a vector that is transactionally consistent and can be accessed
without needing to lock the owning item.

Hence we avoid the need to lock items when we need to flush outstanding
asynchronous transactions to the log. The differences between the existing
formatting method and the delayed logging formatting can be seen in the
diagram below.

Current format log vector::

    Object    +---------------------------------------------+
    Vector 1      +----+
    Vector 2                    +----+
    Vector 3                                   +----------+

After formatting::

    Log Buffer    +-V1-+-V2-+----V3----+

Delayed logging vector::

    Object    +---------------------------------------------+
    Vector 1      +----+
    Vector 2                    +----+
    Vector 3                                   +----------+

After formatting::

    Memory Buffer +-V1-+-V2-+----V3----+
    Vector 1      +----+
    Vector 2           +----+
    Vector 3                +----------+

The memory buffer and associated vector need to be passed as a single object,
but still need to be associated with the parent object so if the object is
relogged we can replace the current memory buffer with a new memory buffer that
contains the latest changes.

The reason for keeping the vector around after we've formatted the memory
buffer is to support splitting vectors across log buffer boundaries correctly.
If we don't keep the vector around, we do not know where the region boundaries
are in the item, so we'd need a new encapsulation method for regions in the log
buffer writing (i.e. double encapsulation). This would be an on-disk format
change and as such is not desirable.  It also means we'd have to write the log
region headers in the formatting stage, which is problematic as there is per
region state that needs to be placed into the headers during the log write.

Hence we need to keep the vector, but by attaching the memory buffer to it and
rewriting the vector addresses to point at the memory buffer we end up with a
self-describing object that can be passed to the log buffer write code to be
handled in exactly the same manner as the existing log vectors are handled.
Hence we avoid needing a new on-disk format to handle items that have been
relogged in memory.

AIL과 분리된 Committed Item List

Memory에 만든 transactionally consistent vector와 buffer는 나중에 log로 쓸 수 있도록 추적하고 누적해야 합니다. Log item은 object가 transaction에 포함된 뒤 항상 존재하고 parent object와 연결되므로 이 snapshot을 보관하기에 자연스러운 위치입니다.

Active Item List(AIL)는 log에는 기록됐지만 아직 disk object로 writeback되지 않은 active log item을 LSN 순서의 doubly linked list로 추적합니다. Log buffer I/O completion 때 item을 AIL에 넣고 unpin하며, AIL item이 다시 relog되면 pin됐다가 새 transaction I/O 완료 후 더 앞선 LSN 위치로 이동합니다.

AIL item도 수정과 relogging이 가능하므로 committed-but-not-yet-checkpointed item 추적은 AIL과 분리해야 합니다. AIL list pointer나 AIL lock으로 보호되는 field를 재사용할 수 없고 log item에 별도 lock, list, state field가 필요합니다.

새 Committed Item List(CIL)는 commit됐고 formatted memory buffer가 붙은 log item을 추적합니다. Transaction commit 순서대로 관리하며 object가 relog되면 기존 위치에서 빼 tail에 다시 넣습니다. 이 순서는 integrity에 필수는 아니며 가장 최근 수정 item을 list 끝에서 쉽게 찾기 위한 debugging 편의입니다.

Tracking Changes
----------------

Now that we can record transactional changes in memory in a form that allows
them to be used without limitations, we need to be able to track and accumulate
them so that they can be written to the log at some later point in time.  The
log item is the natural place to store this vector and buffer, and also makes sense
to be the object that is used to track committed objects as it will always
exist once the object has been included in a transaction.

The log item is already used to track the log items that have been written to
the log but not yet written to disk. Such log items are considered "active"
and as such are stored in the Active Item List (AIL) which is a LSN-ordered
double linked list. Items are inserted into this list during log buffer IO
completion, after which they are unpinned and can be written to disk. An object
that is in the AIL can be relogged, which causes the object to be pinned again
and then moved forward in the AIL when the log buffer IO completes for that
transaction.

Essentially, this shows that an item that is in the AIL can still be modified
and relogged, so any tracking must be separate to the AIL infrastructure. As
such, we cannot reuse the AIL list pointers for tracking committed items, nor
can we store state in any field that is protected by the AIL lock. Hence the
committed item tracking needs its own locks, lists and state fields in the log
item.

Similar to the AIL, tracking of committed items is done through a new list
called the Committed Item List (CIL).  The list tracks log items that have been
committed and have formatted memory buffers attached to them. It tracks objects
in transaction commit order, so when an object is relogged it is removed from
its place in the list and re-inserted at the tail. This is entirely arbitrary
and done to make it easy for debugging - the last items in the list are the
ones that are most recently modified. Ordering of the CIL is not necessary for
transactional integrity (as discussed in the next section) so the ordering is
done for convenience/sanity of the developers.

CIL을 atomic checkpoint로 flush

일반적으로 `log force`라 부르는 synchronization event가 발생하면 CIL의 모든 item을 CIL 순서대로 log buffer에 하나의 atomic transaction으로 써야 합니다. Recovery는 한 transaction의 모든 object 변경을 전부 replay하거나 전혀 replay하지 않아야 하며, 불완전한 transaction 뒤의 transaction도 replay해서는 안 됩니다.

XFS log와 recovery code에는 transaction 크기의 고정 한계가 없지만 checkpoint는 log 크기의 절반보다 조금 작아야 합니다. 언제든 log head와 tail을 찾으려면 완전한 transaction이 하나 이상 남아야 하는데, 절반보다 큰 transaction을 쓰다 crash하면 이전의 유일한 완전한 transaction 일부를 덮어써 recovery failure와 inconsistent filesystem을 만들 수 있기 때문입니다.

Checkpoint도 transaction header, formatted log item들, tail의 commit record로 구성된 일반 transaction이며 단지 더 큽니다. 기존 log-vector writer를 재사용하되 CIL lock 보유 시간을 줄이기 위해 checkpoint 시작부터 completion까지 상태를 운반하는 per-checkpoint context를 사용합니다.

Flush할 때 현재 CIL item을 current checkpoint context로 옮기고, 새 context를 CIL에 붙여 후속 transaction을 즉시 aggregation합니다. 그래서 이전 checkpoint를 format하는 동안 새 transaction을 받을 수 있고 log-force-heavy workload에서는 여러 checkpoint가 동시에 log buffer에 쓰일 수 있습니다. Recovery 순서를 지키려면 commit record는 checkpoint sequence대로 엄격히 기록해야 합니다.

같은 item을 이전 checkpoint가 쓰는 동안 새 transaction이 수정해 새 CIL에 넣을 수 있으므로 checkpoint writer는 log item 자체에 vector list를 보관할 수 없습니다. CIL flush 때 각 log item의 memory buffer와 vector를 checkpoint context의 독립된 vector chain으로 떼어 내고 log item을 release합니다.

Commit record가 기록된 log buffer에는 checkpoint context와 completion callback을 붙입니다. Log I/O completion callback은 vector chain의 item을 AIL에 insert하고 unpin한 다음 vector chain과 context를 해제합니다.

원문은 log item을 거쳐 vector를 추적하면 CIL list 수정과 vector chaining에 각각 cache-line write가 발생할 수 있다고 토론합니다. Checkpoint 하나에 80,000개가 넘는 vector가 관찰되기도 했으므로 vector 직접 추적과의 성능 차이는 구현 후 측정·비교할 사항입니다.

Delayed Logging: Checkpoints
----------------------------

When we have a log synchronisation event, commonly known as a "log force",
all the items in the CIL must be written into the log via the log buffers.
We need to write these items in the order that they exist in the CIL, and they
need to be written as an atomic transaction. The need for all the objects to be
written as an atomic transaction comes from the requirements of relogging and
log replay - all the changes in all the objects in a given transaction must
either be completely replayed during log recovery, or not replayed at all. If
a transaction is not replayed because it is not complete in the log, then
no later transactions should be replayed, either.

To fulfill this requirement, we need to write the entire CIL in a single log
transaction. Fortunately, the XFS log code has no fixed limit on the size of a
transaction, nor does the log replay code. The only fundamental limit is that
the transaction cannot be larger than just under half the size of the log.  The
reason for this limit is that to find the head and tail of the log, there must
be at least one complete transaction in the log at any given time. If a
transaction is larger than half the log, then there is the possibility that a
crash during the write of a such a transaction could partially overwrite the
only complete previous transaction in the log. This will result in a recovery
failure and an inconsistent filesystem and hence we must enforce the maximum
size of a checkpoint to be slightly less than a half the log.

Apart from this size requirement, a checkpoint transaction looks no different
to any other transaction - it contains a transaction header, a series of
formatted log items and a commit record at the tail. From a recovery
perspective, the checkpoint transaction is also no different - just a lot
bigger with a lot more items in it. The worst case effect of this is that we
might need to tune the recovery transaction object hash size.

Because the checkpoint is just another transaction and all the changes to log
items are stored as log vectors, we can use the existing log buffer writing
code to write the changes into the log. To do this efficiently, we need to
minimise the time we hold the CIL locked while writing the checkpoint
transaction. The current log write code enables us to do this easily with the
way it separates the writing of the transaction contents (the log vectors) from
the transaction commit record, but tracking this requires us to have a
per-checkpoint context that travels through the log write process through to
checkpoint completion.

Hence a checkpoint has a context that tracks the state of the current
checkpoint from initiation to checkpoint completion. A new context is initiated
at the same time a checkpoint transaction is started. That is, when we remove
all the current items from the CIL during a checkpoint operation, we move all
those changes into the current checkpoint context. We then initialise a new
context and attach that to the CIL for aggregation of new transactions.

This allows us to unlock the CIL immediately after transfer of all the
committed items and effectively allows new transactions to be issued while we
are formatting the checkpoint into the log. It also allows concurrent
checkpoints to be written into the log buffers in the case of log force heavy
workloads, just like the existing transaction commit code does. This, however,
requires that we strictly order the commit records in the log so that
checkpoint sequence order is maintained during log replay.

To ensure that we can be writing an item into a checkpoint transaction at
the same time another transaction modifies the item and inserts the log item
into the new CIL, then checkpoint transaction commit code cannot use log items
to store the list of log vectors that need to be written into the transaction.
Hence log vectors need to be able to be chained together to allow them to be
detached from the log items. That is, when the CIL is flushed the memory
buffer and log vector attached to each log item needs to be attached to the
checkpoint context so that the log item can be released. In diagrammatic form,
the CIL would look like this before the flush::

        CIL Head
           |
           V
        Log Item <-> log vector 1        -> memory buffer
           |                                -> vector array
           V
        Log Item <-> log vector 2        -> memory buffer
           |                                -> vector array
           V
        ......
           |
           V
        Log Item <-> log vector N-1        -> memory buffer
           |                                -> vector array
           V
        Log Item <-> log vector N        -> memory buffer
                                        -> vector array

And after the flush the CIL head is empty, and the checkpoint context log
vector list would look like::

        Checkpoint Context
           |
           V
        log vector 1        -> memory buffer
           |                -> vector array
           |                -> Log Item
           V
        log vector 2        -> memory buffer
           |                -> vector array
           |                -> Log Item
           V
        ......
           |
           V
        log vector N-1        -> memory buffer
           |                -> vector array
           |                -> Log Item
           V
        log vector N        -> memory buffer
                        -> vector array
                        -> Log Item

Once this transfer is done, the CIL can be unlocked and new transactions can
start, while the checkpoint flush code works over the log vector chain to
commit the checkpoint.

Once the checkpoint is written into the log buffers, the checkpoint context is
attached to the log buffer that the commit record was written to along with a
completion callback. Log IO completion will call that callback, which can then
run transaction committed processing for the log items (i.e. insert into AIL
and unpin) in the log vector chain and then free the log vector chain and
checkpoint context.

Discussion Point: I am uncertain as to whether the log item is the most
efficient way to track vectors, even though it seems like the natural way to do
it. The fact that we walk the log items (in the CIL) just to chain the log
vectors and break the link between the log item and the log vector means that
we take a cache line hit for the log item list modification, then another for
the log vector chaining. If we track by the log vectors, then we only need to
break the link between the log item and the log vector, which means we should
dirty only the log item cachelines. Normally I wouldn't be concerned about one
vs two dirty cachelines except for the fact I've seen upwards of 80,000 log
vectors in one checkpoint transaction. I'd guess this is a "measure and
compare" situation that can be done after a working and reviewed implementation
is in the dev tree....

Checkpoint sequence와 특정 지점 log force

기존 transaction subsystem은 commit record의 LSN을 transaction에 붙입니다. 비동기 transaction 뒤에 freed metadata extent를 data extent로 재사용하는 것처럼 dependency가 생기면 해당 LSN까지 최적화된 log force를 수행할 수 있습니다.

Delayed logging에서는 개별 transaction이 log buffer에 직접 쓰이지 않으므로 commit 시점에 buffer LSN을 얻을 수 없습니다. 대신 checkpoint context를 atomic하게 switch할 때 현재 sequence에 1을 더해 단조 증가하는 sequence number를 부여합니다.

Transaction의 commit LSN 자리에 current checkpoint sequence를 기록하면 미완료 transaction을 기다리는 operation이 어느 checkpoint까지 commit돼야 하는지 알 수 있습니다. 기존의 특정 LSN force는 특정 checkpoint force 의미로 확장됩니다.

Flush를 시작한 context는 searchable `committing` list에 넣고 checkpoint commit이 끝나면 제거합니다. Context가 checkpoint commit record의 실제 LSN을 저장하므로 해당 record를 담은 log buffer를 기다리는 기존 synchronous force mechanism을 재사용할 수 있습니다.

필요한 checkpoint를 기다리기 전에 committing list의 모든 이전 context도 완료됐는지 확인해야 합니다. 이 serialization은 log force code에서만 수행합니다. 요청 sequence가 current context와 같으면 CIL을 push하고 필요할 경우 완료까지 기다립니다.

이 배치 덕분에 상위 synchronous transaction code는 비동기 commit 뒤 해당 transaction의 sequence까지 log force하는 기존 형태를 유지합니다. 원문은 동시 synchronous transaction을 aggregation하는 완화 algorithm이 필요할 수 있지만 먼저 현재 설계의 성능을 조사해야 한다고 남깁니다.

Delayed Logging: Checkpoint Sequencing
--------------------------------------

One of the key aspects of the XFS transaction subsystem is that it tags
committed transactions with the log sequence number of the transaction commit.
This allows transactions to be issued asynchronously even though there may be
future operations that cannot be completed until that transaction is fully
committed to the log. In the rare case that a dependent operation occurs (e.g.
re-using a freed metadata extent for a data extent), a special, optimised log
force can be issued to force the dependent transaction to disk immediately.

To do this, transactions need to record the LSN of the commit record of the
transaction. This LSN comes directly from the log buffer the transaction is
written into. While this works just fine for the existing transaction
mechanism, it does not work for delayed logging because transactions are not
written directly into the log buffers. Hence some other method of sequencing
transactions is required.

As discussed in the checkpoint section, delayed logging uses per-checkpoint
contexts, and as such it is simple to assign a sequence number to each
checkpoint. Because the switching of checkpoint contexts must be done
atomically, it is simple to ensure that each new context has a monotonically
increasing sequence number assigned to it without the need for an external
atomic counter - we can just take the current context sequence number and add
one to it for the new context.

Then, instead of assigning a log buffer LSN to the transaction commit LSN
during the commit, we can assign the current checkpoint sequence. This allows
operations that track transactions that have not yet completed know what
checkpoint sequence needs to be committed before they can continue. As a
result, the code that forces the log to a specific LSN now needs to ensure that
the log forces to a specific checkpoint.

To ensure that we can do this, we need to track all the checkpoint contexts
that are currently committing to the log. When we flush a checkpoint, the
context gets added to a "committing" list which can be searched. When a
checkpoint commit completes, it is removed from the committing list. Because
the checkpoint context records the LSN of the commit record for the checkpoint,
we can also wait on the log buffer that contains the commit record, thereby
using the existing log force mechanisms to execute synchronous forces.

It should be noted that the synchronous forces may need to be extended with
mitigation algorithms similar to the current log buffer code to allow
aggregation of multiple synchronous transactions if there are already
synchronous transactions being flushed. Investigation of the performance of the
current design is needed before making any decisions here.

The main concern with log forces is to ensure that all the previous checkpoints
are also committed to disk before the one we need to wait for. Therefore we
need to check that all the prior contexts in the committing list are also
complete before waiting on the one we need to complete. We do this
synchronisation in the log force code so that we don't need to wait anywhere
else for such serialisation - it only matters when we do a log force.

The only remaining complexity is that a log force now also has to handle the
case where the forcing sequence number is the same as the current context. That
is, we need to flush the CIL and potentially wait for it to complete. This is a
simple addition to the existing log forcing code to check the sequence numbers
and push if required. Indeed, placing the current sequence checkpoint flush in
the log force code enables the current mechanism for issuing synchronous
transactions to remain untouched (i.e. commit an asynchronous transaction, then
force the log at the LSN of that transaction) and so the higher level code
behaves the same regardless of whether delayed logging is being used or not.

동적 checkpoint reservation 계산

Checkpoint 크기, 필요한 log buffer 수, split되는 vector region 수는 미리 알 수 없습니다. CIL에 item을 넣으며 필요 공간을 추적할 수는 있지만 checkpoint가 사용할 log space 자체는 reserve해야 합니다.

일반 transaction reservation은 log record, transaction/region header, split-region header, buffer-tail padding과 실제 changed metadata를 모두 최악 조건으로 계산합니다. 고정 overhead도 있지만 많은 부분이 transaction 크기와 vector 수에 의존합니다.

예를 들어 `chmod -R g+w *`처럼 inode core 10,000개를 수정하면 inode core와 inode log-format 두 vector씩 약 1.5MiB metadata, 20,000 vector의 header 12byte씩을 더해 약 1.75MiB를 기록합니다. 반면 4KiB directory buffer 약 400개와 각 format structure는 약 800 vector, 총 1.51MiB입니다. 같은 metadata 양이라도 vector 수가 크게 달라 정적 reservation의 최적값을 고르기 어렵습니다.

Object가 relog될 때 CIL에서 이전 snapshot이 차지한 공간과 새 snapshot 공간의 차이를 계산할 수 있으므로 checkpoint reservation은 log-buffer metadata overhead만 따로 고려할 수 있습니다. 그러나 header만 정적으로 reserve해도 1MiB당 최소 약 16KiB, 8MiB checkpoint라면 약 150KiB가 필요하며 checkpoint 전에 sleep 없이 확보해야 합니다.

Permanent static reservation은 checkpoint 완료마다 write reservation을 refresh해야 하고 공간이 없으면 regrant code가 sleep합니다. Log space를 비우려면 checkpoint commit이 필요한 상황에서 이 sleep은 rolling transaction과 같은 deadlock을 만들 수 있으므로 항상 충분한 정적 공간을 남기는 방식은 복잡합니다.

더 단순한 방식은 CIL item의 전체 log-space usage를 추적하고 새 memory buffer를 insert할 때 log metadata 증가분을 원인 transaction의 reservation에서 떼어 checkpoint reservation을 동적으로 키우는 것입니다. 각 transaction은 이미 자신이 요구할 최대 metadata overhead를 reserve했으므로 delta는 그 최대값보다 크지 않습니다.

이렇게 하면 upfront reserve와 regrant 없이 checkpoint reservation을 키워 deadlock과 flush blocking point를 제거합니다. Reservation이 log 절반보다 작은 최대 transaction threshold에 도달하면 transaction commit code가 CIL background push를 수행하되 완료를 기다리지는 않습니다.

Transaction subsystem이 idle인데 CIL에 item이 남으면 `xfssyncd`의 periodic log force가 flush하고 idle log를 clean 상태로 덮습니다. 당시 주기인 30초보다 더 자주 force해야 하는지는 토론 사항입니다.

Delayed Logging: Checkpoint Log Space Accounting
------------------------------------------------

The big issue for a checkpoint transaction is the log space reservation for the
transaction. We don't know how big a checkpoint transaction is going to be
ahead of time, nor how many log buffers it will take to write out, nor the
number of split log vector regions are going to be used. We can track the
amount of log space required as we add items to the commit item list, but we
still need to reserve the space in the log for the checkpoint.

A typical transaction reserves enough space in the log for the worst case space
usage of the transaction. The reservation accounts for log record headers,
transaction and region headers, headers for split regions, buffer tail padding,
etc. as well as the actual space for all the changed metadata in the
transaction. While some of this is fixed overhead, much of it is dependent on
the size of the transaction and the number of regions being logged (the number
of log vectors in the transaction).

An example of the differences would be logging directory changes versus logging
inode changes. If you modify lots of inode cores (e.g. ``chmod -R g+w *``), then
there are lots of transactions that only contain an inode core and an inode log
format structure. That is, two vectors totaling roughly 150 bytes. If we modify
10,000 inodes, we have about 1.5MB of metadata to write in 20,000 vectors. Each
vector is 12 bytes, so the total to be logged is approximately 1.75MB. In
comparison, if we are logging full directory buffers, they are typically 4KB
each, so we in 1.5MB of directory buffers we'd have roughly 400 buffers and a
buffer format structure for each buffer - roughly 800 vectors or 1.51MB total
space.  From this, it should be obvious that a static log space reservation is
not particularly flexible and is difficult to select the "optimal value" for
all workloads.

Further, if we are going to use a static reservation, which bit of the entire
reservation does it cover? We account for space used by the transaction
reservation by tracking the space currently used by the object in the CIL and
then calculating the increase or decrease in space used as the object is
relogged. This allows for a checkpoint reservation to only have to account for
log buffer metadata used such as log header records.

However, even using a static reservation for just the log metadata is
problematic. Typically log record headers use at least 16KB of log space per
1MB of log space consumed (512 bytes per 32k) and the reservation needs to be
large enough to handle arbitrary sized checkpoint transactions. This
reservation needs to be made before the checkpoint is started, and we need to
be able to reserve the space without sleeping.  For a 8MB checkpoint, we need a
reservation of around 150KB, which is a non-trivial amount of space.

A static reservation needs to manipulate the log grant counters - we can take a
permanent reservation on the space, but we still need to make sure we refresh
the write reservation (the actual space available to the transaction) after
every checkpoint transaction completion. Unfortunately, if this space is not
available when required, then the regrant code will sleep waiting for it.

The problem with this is that it can lead to deadlocks as we may need to commit
checkpoints to be able to free up log space (refer back to the description of
rolling transactions for an example of this).  Hence we *must* always have
space available in the log if we are to use static reservations, and that is
very difficult and complex to arrange. It is possible to do, but there is a
simpler way.

The simpler way of doing this is tracking the entire log space used by the
items in the CIL and using this to dynamically calculate the amount of log
space required by the log metadata. If this log metadata space changes as a
result of a transaction commit inserting a new memory buffer into the CIL, then
the difference in space required is removed from the transaction that causes
the change. Transactions at this level will *always* have enough space
available in their reservation for this as they have already reserved the
maximal amount of log metadata space they require, and such a delta reservation
will always be less than or equal to the maximal amount in the reservation.

Hence we can grow the checkpoint transaction reservation dynamically as items
are added to the CIL and avoid the need for reserving and regranting log space
up front. This avoids deadlocks and removes a blocking point from the
checkpoint flush code.

As mentioned early, transactions can't grow to more than half the size of the
log. Hence as part of the reservation growing, we need to also check the size
of the reservation against the maximum allowed transaction size. If we reach
the maximum threshold, we need to push the CIL to the log. This is effectively
a "background flush" and is done on demand. This is identical to
a CIL push triggered by a log force, only that there is no waiting for the
checkpoint commit to complete. This background push is checked and executed by
transaction commit code.

If the transaction subsystem goes idle while we still have items in the CIL,
they will be flushed by the periodic log force issued by the xfssyncd. This log
force will push the CIL to disk, and if the transaction subsystem stays idle,
allow the idle log to be covered (effectively marked clean) in exactly the same
manner that is done for the existing logging method. A discussion point is
whether this log force needs to be done more frequently than the current rate
which is once every 30s.

Checkpoint context 기준 pin/unpin 대칭

기존 방식은 transaction commit마다 잠긴 item을 한 번 pin하고 해당 transaction completion마다 한 번 unpin합니다. 여러 outstanding transaction에서 relog된 item은 transaction 수만큼 pin count가 올라가며 모두 완료돼 pending transaction이 없어질 때 비로소 unpin됩니다. Commit과 completion이 1:1이므로 대칭입니다.

Delayed logging에서는 object가 CIL에서 relog될 때마다 commit process를 거치지만 completion은 checkpoint 하나에 한 번만 발생해 many-to-one 관계가 됩니다. 기존 `commit마다 pin, completion마다 unpin` 규칙을 유지하면 count가 불균형해집니다.

새 규칙은 `CIL에 처음 insert할 때 pin, checkpoint completion 때 unpin`입니다. Item이 이미 current CIL에 있으면 relogging commit에서 다시 pin하지 않습니다. 여러 outstanding checkpoint context가 있으면 pin count가 1보다 높을 수 있지만 각 context 완료가 정확한 count를 내립니다.

Pin 여부가 current CIL 포함 여부에 의존하므로 CIL commit/flush lock 아래에서 검사와 pin을 함께 해야 합니다. Lock 없이 확인 후 pin하면 그 사이 CIL flush가 일어나 pin이 어느 context에 속하는지 알 수 없는 race가 생깁니다.

Delayed Logging: Log Item Pinning
---------------------------------

Currently log items are pinned during transaction commit while the items are
still locked. This happens just after the items are formatted, though it could
be done any time before the items are unlocked. The result of this mechanism is
that items get pinned once for every transaction that is committed to the log
buffers. Hence items that are relogged in the log buffers will have a pin count
for every outstanding transaction they were dirtied in. When each of these
transactions is completed, they will unpin the item once. As a result, the item
only becomes unpinned when all the transactions complete and there are no
pending transactions. Thus the pinning and unpinning of a log item is symmetric
as there is a 1:1 relationship with transaction commit and log item completion.

For delayed logging, however, we have an asymmetric transaction commit to
completion relationship. Every time an object is relogged in the CIL it goes
through the commit process without a corresponding completion being registered.
That is, we now have a many-to-one relationship between transaction commit and
log item completion. The result of this is that pinning and unpinning of the
log items becomes unbalanced if we retain the "pin on transaction commit, unpin
on transaction completion" model.

To keep pin/unpin symmetry, the algorithm needs to change to a "pin on
insertion into the CIL, unpin on checkpoint completion". In other words, the
pinning and unpinning becomes symmetric around a checkpoint context. We have to
pin the object the first time it is inserted into the CIL - if it is already in
the CIL during a transaction commit, then we do not pin it again. Because there
can be multiple outstanding checkpoint contexts, we can still see elevated pin
counts, but as each checkpoint completes the pin count will retain the correct
value according to its context.

Just to make matters slightly more complex, this checkpoint level context
for the pin count means that the pinning of an item must take place under the
CIL commit/flush lock. If we pin the object outside this lock, we cannot
guarantee which context the pin count is associated with. This is because of
the fact pinning the item is dependent on whether the item is present in the
current CIL or not. If we don't pin the CIL first before we check and pin the
object, we have a race with CIL being flushed between the check and the pin
(or not pinning, as the case may be). Hence we must hold the CIL flush/commit
lock to guarantee that we pin the items correctly.

CIL의 세 serialization 지점

CIL transaction commit path는 많은 동시 commit에 scale해야 합니다. 기존 code는 2,048 processor에서 동시에 transaction이 들어와도 한 CPU보다 빨라지지는 않지만 느려지지도 않으므로 delayed logging도 처음부터 concurrency를 고려해야 합니다.

핵심 serialization point는 CIL flush 동안 새 commit 배제, CIL item insertion과 space accounting, checkpoint commit ordering 세 곳입니다.

Commit 대 flush는 many-to-one 관계이며 128MiB log에서는 reservation 공간상 수백 개 transaction, 보통 CPU당 하나가 동시에 commit할 수 있습니다. Commit side는 item pinning과 memory-buffer formatting의 `memcpy()` 동안 flush를 막아 비교적 오래 lock을 잡습니다. 두 pass로 formatting과 pinning을 분리하면 hold time을 줄일 수 있습니다.

CIL flush는 수만 log item을 순회할 수 있어 오래 걸리므로 다른 모든 CPU가 spin하지 않게 commit/flush exclusion에는 sleeping lock이 필요합니다. Lock 아래에서 실제 sleep은 하지 않지만 spinning 낭비를 막기 위한 선택입니다. Flush는 asynchronous commit보다 드물며 read-write semaphore의 read-side cache-line bouncing이 concurrency를 제한하는지는 측정해야 합니다.

CIL insertion은 commit끼리 동시에 진입하므로 commit/flush lock과 별도의 exclusive lock이 필요합니다. Hold time이 매우 짧아 spin lock이 적합하며 transaction당 한 번이어서 contention 가능성이 낮다고 봅니다.

Checkpoint commit-record ordering과 log-force sequencing은 committing list를 순회하며 event를 기다려야 하므로 lock과 wait variable을 공유합니다. Commit ordering은 context에 commit LSN이 생길 때까지, log force는 이전 context가 list에서 제거돼 완료될 때까지 기다립니다.

단순 wait variable과 broadcast wakeup은 thundering herd를 만들 수 있습니다. CIL lock contention이나 잘못된 event로 깨어나는 context switch가 많다면 별도 spinlock과 wait list로 분리할 수 있습니다.

Delayed Logging: Concurrent Scalability
---------------------------------------

A fundamental requirement for the CIL is that accesses through transaction
commits must scale to many concurrent commits. The current transaction commit
code does not break down even when there are transactions coming from 2048
processors at once. The current transaction code does not go any faster than if
there was only one CPU using it, but it does not slow down either.

As a result, the delayed logging transaction commit code needs to be designed
for concurrency from the ground up. It is obvious that there are serialisation
points in the design - the three important ones are:

        1. Locking out new transaction commits while flushing the CIL
        2. Adding items to the CIL and updating item space accounting
        3. Checkpoint commit ordering

Looking at the transaction commit and CIL flushing interactions, it is clear
that we have a many-to-one interaction here. That is, the only restriction on
the number of concurrent transactions that can be trying to commit at once is
the amount of space available in the log for their reservations. The practical
limit here is in the order of several hundred concurrent transactions for a
128MB log, which means that it is generally one per CPU in a machine.

The amount of time a transaction commit needs to hold out a flush is a
relatively long period of time - the pinning of log items needs to be done
while we are holding out a CIL flush, so at the moment that means it is held
across the formatting of the objects into memory buffers (i.e. while memcpy()s
are in progress). Ultimately a two pass algorithm where the formatting is done
separately to the pinning of objects could be used to reduce the hold time of
the transaction commit side.

Because of the number of potential transaction commit side holders, the lock
really needs to be a sleeping lock - if the CIL flush takes the lock, we do not
want every other CPU in the machine spinning on the CIL lock. Given that
flushing the CIL could involve walking a list of tens of thousands of log
items, it will get held for a significant time and so spin contention is a
significant concern. Preventing lots of CPUs spinning doing nothing is the
main reason for choosing a sleeping lock even though nothing in either the
transaction commit or CIL flush side sleeps with the lock held.

It should also be noted that CIL flushing is also a relatively rare operation
compared to transaction commit for asynchronous transaction workloads - only
time will tell if using a read-write semaphore for exclusion will limit
transaction commit concurrency due to cache line bouncing of the lock on the
read side.

The second serialisation point is on the transaction commit side where items
are inserted into the CIL. Because transactions can enter this code
concurrently, the CIL needs to be protected separately from the above
commit/flush exclusion. It also needs to be an exclusive lock but it is only
held for a very short time and so a spin lock is appropriate here. It is
possible that this lock will become a contention point, but given the short
hold time once per transaction I think that contention is unlikely.

The final serialisation point is the checkpoint commit record ordering code
that is run as part of the checkpoint commit and log force sequencing. The code
path that triggers a CIL flush (i.e. whatever triggers the log force) will enter
an ordering loop after writing all the log vectors into the log buffers but
before writing the commit record. This loop walks the list of committing
checkpoints and needs to block waiting for checkpoints to complete their commit
record write. As a result it needs a lock and a wait variable. Log force
sequencing also requires the same lock, list walk, and blocking mechanism to
ensure completion of checkpoints.

These two sequencing operations can use the mechanism even though the
events they are waiting for are different. The checkpoint commit record
sequencing needs to wait until checkpoint contexts contain a commit LSN
(obtained through completion of a commit record write) while log force
sequencing needs to wait until previous checkpoint contexts are removed from
the committing list (i.e. they've completed). A simple wait variable and
broadcast wakeups (thundering herds) has been used to implement these two
serialisation queues. They use the same lock as the CIL, too. If we see too
much contention on the CIL lock, or too many context switches as a result of
the broadcast wakeups these operations can be put under a new spinlock and
given separate wait lists to reduce lock contention and the number of processes
woken by the wrong event.

기존 lifecycle에 CIL checkpoint 삽입

기존 log-item lifecycle은 transaction allocation과 reservation, item lock/join, modification 기록, commit으로 시작합니다. Commit에서 item을 pin하고 log buffer로 format하며 transaction에 commit LSN을 쓰고 item을 unlock한 뒤 transaction을 log buffer에 붙입니다.

Log buffer I/O가 끝나면 transaction completion이 item을 committed로 표시하고 commit LSN과 함께 AIL에 넣고 unpin합니다. 이후 AIL traversal이 item을 lock하고 clean으로 표시해 disk로 flush하며, item I/O completion 뒤 AIL에서 제거해 log tail을 움직이고 unlock합니다.

기존 단계 1–6, 단계 7, 단계 8–9는 각각 독립적으로 동작합니다. 단계 7과 transaction 또는 AIL 경로는 겹칠 수 있지만 transaction 단계 1–6과 AIL 단계 8–9는 동시에 같은 item에 수행될 수 없습니다. Item이 AIL에 있거나 commit과 completion 사이에 있는데 다시 단계 1–6으로 들어오면 relogging이며, 단계 8–9가 끝나야 object가 clean입니다.

Delayed logging은 transaction commit 중 current CIL에서 아직 pin되지 않은 item만 pin하고, item을 `log vector + buffer`로 format해 log item에 붙인 뒤 CIL에 넣습니다. Transaction에는 commit LSN 대신 CIL context sequence를 기록하고 item을 unlock합니다.

다음 log force의 CIL push는 flush lock 아래 vector와 buffer를 chain하고 CIL에서 item을 제거한 뒤 lock을 놓습니다. Vector를 log에 쓰고 commit record 순서를 맞추며 checkpoint context를 log buffer에 붙입니다. I/O completion 후 checkpoint completion이 item을 committed로 표시하고 AIL에 넣어 commit LSN을 기록한 뒤 unpin합니다. 이후 AIL traversal과 tail 이동은 기존과 같습니다.

따라서 차이는 lifecycle 중간의 log commit과 completion 처리에만 있습니다. 시작과 끝, execution constraint는 같으므로 delayed logging은 기존에 없던 log-item behavior, allocation, freeing 제약을 추가하지 않아야 합니다.

Delayed logging infrastructure를 중간에 영향 없이 삽입하고 on-disk format을 유지했기 때문에 mount option으로 기존 방식과 전환할 수 있습니다. Load 특성에 따라 log manager가 자동 전환하는 것도 원리상 가능하지만 delayed logging이 설계대로 동작하면 필요하지 않습니다.

Lifecycle Changes
-----------------

The existing log item life cycle is as follows::

        1. Transaction allocate
        2. Transaction reserve
        3. Lock item
        4. Join item to transaction
                If not already attached,
                        Allocate log item
                        Attach log item to owner item
                Attach log item to transaction
        5. Modify item
                Record modifications in log item
        6. Transaction commit
                Pin item in memory
                Format item into log buffer
                Write commit LSN into transaction
                Unlock item
                Attach transaction to log buffer

        <log buffer IO dispatched>
        <log buffer IO completes>

        7. Transaction completion
                Mark log item committed
                Insert log item into AIL
                        Write commit LSN into log item
                Unpin log item
        8. AIL traversal
                Lock item
                Mark log item clean
                Flush item to disk

        <item IO completion>

        9. Log item removed from AIL
                Moves log tail
                Item unlocked

Essentially, steps 1-6 operate independently from step 7, which is also
independent of steps 8-9. An item can be locked in steps 1-6 or steps 8-9
at the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur
at the same time. If the log item is in the AIL or between steps 6 and 7
and steps 1-6 are re-entered, then the item is relogged. Only when steps 8-9
are entered and completed is the object considered clean.

With delayed logging, there are new steps inserted into the life cycle::

        1. Transaction allocate
        2. Transaction reserve
        3. Lock item
        4. Join item to transaction
                If not already attached,
                        Allocate log item
                        Attach log item to owner item
                Attach log item to transaction
        5. Modify item
                Record modifications in log item
        6. Transaction commit
                Pin item in memory if not pinned in CIL
                Format item into log vector + buffer
                Attach log vector and buffer to log item
                Insert log item into CIL
                Write CIL context sequence into transaction
                Unlock item

        <next log force>

        7. CIL push
                lock CIL flush
                Chain log vectors and buffers together
                Remove items from CIL
                unlock CIL flush
                write log vectors into log
                sequence commit records
                attach checkpoint context to log buffer

        <log buffer IO dispatched>
        <log buffer IO completes>

        8. Checkpoint completion
                Mark log item committed
                Insert item into AIL
                        Write commit LSN into log item
                Unpin log item
        9. AIL traversal
                Lock item
                Mark log item clean
                Flush item to disk
        <item IO completion>
        10. Log item removed from AIL
                Moves log tail
                Item unlocked

From this, it can be seen that the only life cycle differences between the two
logging methods are in the middle of the life cycle - they still have the same
beginning and end and execution constraints. The only differences are in the
committing of the log items to the log itself and the completion processing.
Hence delayed logging should not introduce any constraints on log item
behaviour, allocation or freeing that don't already exist.

As a result of this zero-impact "insertion" of delayed logging infrastructure
and the design of the internal structures to avoid on disk format changes, we
can basically switch between delayed logging and the existing mechanism with a
mount option. Fundamentally, there is no reason why the log manager would not
be able to swap methods automatically and transparently depending on load
characteristics, but this should not be necessary if delayed logging works as
designed.