1.. SPDX-License-Identifier: GPL-2.0
   2
   3==================
   4XFS Logging Design
   5==================
   6
   7Preamble
   8========
   9
  10This document describes the design and algorithms that the XFS journalling
  11subsystem is based on. This document describes the design and algorithms that
  12the XFS journalling subsystem is based on so that readers may familiarize
  13themselves with the general concepts of how transaction processing in XFS works.
  14
  15We begin with an overview of transactions in XFS, followed by describing how
  16transaction reservations are structured and accounted, and then move into how we
  17guarantee forwards progress for long running transactions with finite initial
  18reservations bounds. At this point we need to explain how relogging works. With
  19the basic concepts covered, the design of the delayed logging mechanism is
  20documented.
  21
  22
  23Introduction
  24============
  25
  26XFS uses Write Ahead Logging for ensuring changes to the filesystem metadata
  27are atomic and recoverable. For reasons of space and time efficiency, the
  28logging mechanisms are varied and complex, combining intents, logical and
  29physical logging mechanisms to provide the necessary recovery guarantees the
  30filesystem requires.
  31
  32Some objects, such as inodes and dquots, are logged in logical format where the
  33details logged are made up of the changes to in-core structures rather than
  34on-disk structures. Other objects - typically buffers - have their physical
  35changes logged. Long running atomic modifications have individual changes
  36chained together by intents, ensuring that journal recovery can restart and
  37finish an operation that was only partially done when the system stopped
  38functioning.
  39
  40The reason for these differences is to keep the amount of log space and CPU time
  41required to process objects being modified as small as possible and hence the
  42logging overhead as low as possible. Some items are very frequently modified,
  43and some parts of objects are more frequently modified than others, so keeping
  44the overhead of metadata logging low is of prime importance.
  45
  46The method used to log an item or chain modifications together isn't
  47particularly important in the scope of this document. It suffices to know that
  48the method used for logging a particular object or chaining modifications
  49together are different and are dependent on the object and/or modification being
  50performed. The logging subsystem only cares that certain specific rules are
  51followed to guarantee forwards progress and prevent deadlocks.
  52
  53
  54Transactions in XFS
  55===================
  56
  57XFS has two types of high level transactions, defined by the type of log space
  58reservation they take. These are known as "one shot" and "permanent"
  59transactions. Permanent transaction reservations can take reservations that span
  60commit boundaries, whilst "one shot" transactions are for a single atomic
  61modification.
  62
  63The type and size of reservation must be matched to the modification taking
  64place.  This means that permanent transactions can be used for one-shot
  65modifications, but one-shot reservations cannot be used for permanent
  66transactions.
  67
  68In the code, a one-shot transaction pattern looks somewhat like this::
  69
  70	tp = xfs_trans_alloc(<reservation>)
  71	<lock items>
  72	<join item to transaction>
  73	<do modification>
  74	xfs_trans_commit(tp);
  75
  76As items are modified in the transaction, the dirty regions in those items are
  77tracked via the transaction handle.  Once the transaction is committed, all
  78resources joined to it are released, along with the remaining unused reservation
  79space that was taken at the transaction allocation time.
  80
  81In contrast, a permanent transaction is made up of multiple linked individual
  82transactions, and the pattern looks like this::
  83
  84	tp = xfs_trans_alloc(<reservation>)
  85	xfs_ilock(ip, XFS_ILOCK_EXCL)
  86
  87	loop {
  88		xfs_trans_ijoin(tp, 0);
  89		<do modification>
  90		xfs_trans_log_inode(tp, ip);
  91		xfs_trans_roll(&tp);
  92	}
  93
  94	xfs_trans_commit(tp);
  95	xfs_iunlock(ip, XFS_ILOCK_EXCL);
  96
  97While this might look similar to a one-shot transaction, there is an important
  98difference: xfs_trans_roll() performs a specific operation that links two
  99transactions together::
 100
 101	ntp = xfs_trans_dup(tp);
 102	xfs_trans_commit(tp);
 103	xfs_trans_reserve(ntp);
 104
 105This results in a series of "rolling transactions" where the inode is locked
 106across the entire chain of transactions.  Hence while this series of rolling
 107transactions is running, nothing else can read from or write to the inode and
 108this provides a mechanism for complex changes to appear atomic from an external
 109observer's point of view.
 110
 111It is important to note that a series of rolling transactions in a permanent
 112transaction does not form an atomic change in the journal. While each
 113individual modification is atomic, the chain is *not atomic*. If we crash half
 114way through, then recovery will only replay up to the last transactional
 115modification the loop made that was committed to the journal.
 116
 117This affects long running permanent transactions in that it is not possible to
 118predict how much of a long running operation will actually be recovered because
 119there is no guarantee of how much of the operation reached stale storage. Hence
 120if a long running operation requires multiple transactions to fully complete,
 121the high level operation must use intents and deferred operations to guarantee
 122recovery can complete the operation once the first transactions is persisted in
 123the on-disk journal.
 124
 125
 126Transactions are Asynchronous
 127=============================
 128
 129In XFS, all high level transactions are asynchronous by default. This means that
 130xfs_trans_commit() does not guarantee that the modification has been committed
 131to stable storage when it returns. Hence when a system crashes, not all the
 132completed transactions will be replayed during recovery.
 133
 134However, the logging subsystem does provide global ordering guarantees, such
 135that if a specific change is seen after recovery, all metadata modifications
 136that were committed prior to that change will also be seen.
 137
 138For single shot operations that need to reach stable storage immediately, or
 139ensuring that a long running permanent transaction is fully committed once it is
 140complete, we can explicitly tag a transaction as synchronous. This will trigger
 141a "log force" to flush the outstanding committed transactions to stable storage
 142in the journal and wait for that to complete.
 143
 144Synchronous transactions are rarely used, however, because they limit logging
 145throughput to the IO latency limitations of the underlying storage. Instead, we
 146tend to use log forces to ensure modifications are on stable storage only when
 147a user operation requires a synchronisation point to occur (e.g. fsync).
 148
 149
 150Transaction Reservations
 151========================
 152
 153It has been mentioned a number of times now that the logging subsystem needs to
 154provide a forwards progress guarantee so that no modification ever stalls
 155because it can't be written to the journal due to a lack of space in the
 156journal. This is achieved by the transaction reservations that are made when
 157a transaction is first allocated. For permanent transactions, these reservations
 158are maintained as part of the transaction rolling mechanism.
 159
 160A transaction reservation provides a guarantee that there is physical log space
 161available to write the modification into the journal before we start making
 162modifications to objects and items. As such, the reservation needs to be large
 163enough to take into account the amount of metadata that the change might need to
 164log in the worst case. This means that if we are modifying a btree in the
 165transaction, we have to reserve enough space to record a full leaf-to-root split
 166of the btree. As such, the reservations are quite complex because we have to
 167take into account all the hidden changes that might occur.
 168
 169For example, a user data extent allocation involves allocating an extent from
 170free space, which modifies the free space trees. That's two btrees.  Inserting
 171the extent into the inode's extent map might require a split of the extent map
 172btree, which requires another allocation that can modify the free space trees
 173again.  Then we might have to update reverse mappings, which modifies yet
 174another btree which might require more space. And so on.  Hence the amount of
 175metadata that a "simple" operation can modify can be quite large.
 176
 177This "worst case" calculation provides us with the static "unit reservation"
 178for the transaction that is calculated at mount time. We must guarantee that the
 179log has this much space available before the transaction is allowed to proceed
 180so that when we come to write the dirty metadata into the log we don't run out
 181of log space half way through the write.
 182
 183For one-shot transactions, a single unit space reservation is all that is
 184required for the transaction to proceed. For permanent transactions, however, we
 185also have a "log count" that affects the size of the reservation that is to be
 186made.
 187
 188While a permanent transaction can get by with a single unit of space
 189reservation, it is somewhat inefficient to do this as it requires the
 190transaction rolling mechanism to re-reserve space on every transaction roll. We
 191know from the implementation of the permanent transactions how many transaction
 192rolls are likely for the common modifications that need to be made.
 193
 194For example, an inode allocation is typically two transactions - one to
 195physically allocate a free inode chunk on disk, and another to allocate an inode
 196from an inode chunk that has free inodes in it.  Hence for an inode allocation
 197transaction, we might set the reservation log count to a value of 2 to indicate
 198that the common/fast path transaction will commit two linked transactions in a
 199chain. Each time a permanent transaction rolls, it consumes an entire unit
 200reservation.
 201
 202Hence when the permanent transaction is first allocated, the log space
 203reservation is increased from a single unit reservation to multiple unit
 204reservations. That multiple is defined by the reservation log count, and this
 205means we can roll the transaction multiple times before we have to re-reserve
 206log space when we roll the transaction. This ensures that the common
 207modifications we make only need to reserve log space once.
 208
 209If the log count for a permanent transaction reaches zero, then it needs to
 210re-reserve physical space in the log. This is somewhat complex, and requires
 211an understanding of how the log accounts for space that has been reserved.
 212
 213
 214Log Space Accounting
 215====================
 216
 217The position in the log is typically referred to as a Log Sequence Number (LSN).
 218The log is circular, so the positions in the log are defined by the combination
 219of a cycle number - the number of times the log has been overwritten - and the
 220offset into the log.  A LSN carries the cycle in the upper 32 bits and the
 221offset in the lower 32 bits. The offset is in units of "basic blocks" (512
 222bytes). Hence we can do realtively simple LSN based math to keep track of
 223available space in the log.
 224
 225Log space accounting is done via a pair of constructs called "grant heads".  The
 226position of the grant heads is an absolute value, so the amount of space
 227available in the log is defined by the distance between the position of the
 228grant head and the current log tail. That is, how much space can be
 229reserved/consumed before the grant heads would fully wrap the log and overtake
 230the tail position.
 231
 232The first grant head is the "reserve" head. This tracks the byte count of the
 233reservations currently held by active transactions. It is a purely in-memory
 234accounting of the space reservation and, as such, actually tracks byte offsets
 235into the log rather than basic blocks. Hence it technically isn't using LSNs to
 236represent the log position, but it is still treated like a split {cycle,offset}
 237tuple for the purposes of tracking reservation space.
 238
 239The reserve grant head is used to accurately account for exact transaction
 240reservations amounts and the exact byte count that modifications actually make
 241and need to write into the log. The reserve head is used to prevent new
 242transactions from taking new reservations when the head reaches the current
 243tail. It will block new reservations in a FIFO queue and as the log tail moves
 244forward it will wake them in order once sufficient space is available. This FIFO
 245mechanism ensures no transaction is starved of resources when log space
 246shortages occur.
 247
 248The other grant head is the "write" head. Unlike the reserve head, this grant
 249head contains an LSN and it tracks the physical space usage in the log. While
 250this might sound like it is accounting the same state as the reserve grant head
 251- and it mostly does track exactly the same location as the reserve grant head -
 252there are critical differences in behaviour between them that provides the
 253forwards progress guarantees that rolling permanent transactions require.
 254
 255These differences when a permanent transaction is rolled and the internal "log
 256count" reaches zero and the initial set of unit reservations have been
 257exhausted. At this point, we still require a log space reservation to continue
 258the next transaction in the sequeunce, but we have none remaining. We cannot
 259sleep during the transaction commit process waiting for new log space to become
 260available, as we may end up on the end of the FIFO queue and the items we have
 261locked while we sleep could end up pinning the tail of the log before there is
 262enough free space in the log to fulfill all of the pending reservations and
 263then wake up transaction commit in progress.
 264
 265To take a new reservation without sleeping requires us to be able to take a
 266reservation even if there is no reservation space currently available. That is,
 267we need to be able to *overcommit* the log reservation space. As has already
 268been detailed, we cannot overcommit physical log space. However, the reserve
 269grant head does not track physical space - it only accounts for the amount of
 270reservations we currently have outstanding. Hence if the reserve head passes
 271over the tail of the log all it means is that new reservations will be throttled
 272immediately and remain throttled until the log tail is moved forward far enough
 273to remove the overcommit and start taking new reservations. In other words, we
 274can overcommit the reserve head without violating the physical log head and tail
 275rules.
 276
 277As a result, permanent transactions only "regrant" reservation space during
 278xfs_trans_commit() calls, while the physical log space reservation - tracked by
 279the write head - is then reserved separately by a call to xfs_log_reserve()
 280after the commit completes. Once the commit completes, we can sleep waiting for
 281physical log space to be reserved from the write grant head, but only if one
 282critical rule has been observed::
 283
 284	Code using permanent reservations must always log the items they hold
 285	locked across each transaction they roll in the chain.
 286
 287"Re-logging" the locked items on every transaction roll ensures that the items
 288attached to the transaction chain being rolled are always relocated to the
 289physical head of the log and so do not pin the tail of the log. If a locked item
 290pins the tail of the log when we sleep on the write reservation, then we will
 291deadlock the log as we cannot take the locks needed to write back that item and
 292move the tail of the log forwards to free up write grant space. Re-logging the
 293locked items avoids this deadlock and guarantees that the log reservation we are
 294making cannot self-deadlock.
 295
 296If all rolling transactions obey this rule, then they can all make forwards
 297progress independently because nothing will block the progress of the log
 298tail moving forwards and hence ensuring that write grant space is always
 299(eventually) made available to permanent transactions no matter how many times
 300they roll.
 301
 302
 303Re-logging Explained
 304====================
 305
 306XFS allows multiple separate modifications to a single object to be carried in
 307the log at any given time.  This allows the log to avoid needing to flush each
 308change to disk before recording a new change to the object. XFS does this via a
 309method called "re-logging". Conceptually, this is quite simple - all it requires
 310is that any new change to the object is recorded with a *new copy* of all the
 311existing changes in the new transaction that is written to the log.
 312
 313That is, if we have a sequence of changes A through to F, and the object was
 314written to disk after change D, we would see in the log the following series
 315of transactions, their contents and the log sequence number (LSN) of the
 316transaction::
 317
 318	Transaction		Contents	LSN
 319	   A			   A		   X
 320	   B			  A+B		  X+n
 321	   C			 A+B+C		 X+n+m
 322	   D			A+B+C+D		X+n+m+o
 323	    <object written to disk>
 324	   E			   E		   Y (> X+n+m+o)
 325	   F			  E+F		  Y+p
 326
 327In other words, each time an object is relogged, the new transaction contains
 328the aggregation of all the previous changes currently held only in the log.
 329
 330This relogging technique allows objects to be moved forward in the log so that
 331an object being relogged does not prevent the tail of the log from ever moving
 332forward.  This can be seen in the table above by the changing (increasing) LSN
 333of each subsequent transaction, and it's the technique that allows us to
 334implement long-running, multiple-commit permanent transactions. 
 335
 336A typical example of a rolling transaction is the removal of extents from an
 
 
 
 337inode which can only be done at a rate of two extents per transaction because
 338of reservation size limitations. Hence a rolling extent removal transaction
 339keeps relogging the inode and btree buffers as they get modified in each
 340removal operation. This keeps them moving forward in the log as the operation
 341progresses, ensuring that current operation never gets blocked by itself if the
 342log wraps around.
 343
 344Hence it can be seen that the relogging operation is fundamental to the correct
 345working of the XFS journalling subsystem. From the above description, most
 346people should be able to see why the XFS metadata operations writes so much to
 347the log - repeated operations to the same objects write the same changes to
 348the log over and over again. Worse is the fact that objects tend to get
 349dirtier as they get relogged, so each subsequent transaction is writing more
 350metadata into the log.
 351
 352It should now also be obvious how relogging and asynchronous transactions go
 353hand in hand. That is, transactions don't get written to the physical journal
 354until either a log buffer is filled (a log buffer can hold multiple
 355transactions) or a synchronous operation forces the log buffers holding the
 356transactions to disk. This means that XFS is doing aggregation of transactions
 357in memory - batching them, if you like - to minimise the impact of the log IO on
 358transaction throughput.
 359
 360The limitation on asynchronous transaction throughput is the number and size of
 361log buffers made available by the log manager. By default there are 8 log
 362buffers available and the size of each is 32kB - the size can be increased up
 363to 256kB by use of a mount option.
 364
 365Effectively, this gives us the maximum bound of outstanding metadata changes
 366that can be made to the filesystem at any point in time - if all the log
 367buffers are full and under IO, then no more transactions can be committed until
 368the current batch completes. It is now common for a single current CPU core to
 369be to able to issue enough transactions to keep the log buffers full and under
 370IO permanently. Hence the XFS journalling subsystem can be considered to be IO
 371bound.
 372
 373Delayed Logging: Concepts
 374=========================
 375
 376The key thing to note about the asynchronous logging combined with the
 377relogging technique XFS uses is that we can be relogging changed objects
 378multiple times before they are committed to disk in the log buffers. If we
 379return to the previous relogging example, it is entirely possible that
 380transactions A through D are committed to disk in the same log buffer.
 381
 382That is, a single log buffer may contain multiple copies of the same object,
 383but only one of those copies needs to be there - the last one "D", as it
 384contains all the changes from the previous changes. In other words, we have one
 385necessary copy in the log buffer, and three stale copies that are simply
 386wasting space. When we are doing repeated operations on the same set of
 387objects, these "stale objects" can be over 90% of the space used in the log
 388buffers. It is clear that reducing the number of stale objects written to the
 389log would greatly reduce the amount of metadata we write to the log, and this
 390is the fundamental goal of delayed logging.
 391
 392From a conceptual point of view, XFS is already doing relogging in memory (where
 393memory == log buffer), only it is doing it extremely inefficiently. It is using
 394logical to physical formatting to do the relogging because there is no
 395infrastructure to keep track of logical changes in memory prior to physically
 396formatting the changes in a transaction to the log buffer. Hence we cannot avoid
 397accumulating stale objects in the log buffers.
 398
 399Delayed logging is the name we've given to keeping and tracking transactional
 400changes to objects in memory outside the log buffer infrastructure. Because of
 401the relogging concept fundamental to the XFS journalling subsystem, this is
 402actually relatively easy to do - all the changes to logged items are already
 403tracked in the current infrastructure. The big problem is how to accumulate
 404them and get them to the log in a consistent, recoverable manner.
 405Describing the problems and how they have been solved is the focus of this
 406document.
 407
 408One of the key changes that delayed logging makes to the operation of the
 409journalling subsystem is that it disassociates the amount of outstanding
 410metadata changes from the size and number of log buffers available. In other
 411words, instead of there only being a maximum of 2MB of transaction changes not
 412written to the log at any point in time, there may be a much greater amount
 413being accumulated in memory. Hence the potential for loss of metadata on a
 414crash is much greater than for the existing logging mechanism.
 415
 416It should be noted that this does not change the guarantee that log recovery
 417will result in a consistent filesystem. What it does mean is that as far as the
 418recovered filesystem is concerned, there may be many thousands of transactions
 419that simply did not occur as a result of the crash. This makes it even more
 420important that applications that care about their data use fsync() where they
 421need to ensure application level data integrity is maintained.
 422
 423It should be noted that delayed logging is not an innovative new concept that
 424warrants rigorous proofs to determine whether it is correct or not. The method
 425of accumulating changes in memory for some period before writing them to the
 426log is used effectively in many filesystems including ext3 and ext4. Hence
 427no time is spent in this document trying to convince the reader that the
 428concept is sound. Instead it is simply considered a "solved problem" and as
 429such implementing it in XFS is purely an exercise in software engineering.
 430
 431The fundamental requirements for delayed logging in XFS are simple:
 432
 433	1. Reduce the amount of metadata written to the log by at least
 434	   an order of magnitude.
 435	2. Supply sufficient statistics to validate Requirement #1.
 436	3. Supply sufficient new tracing infrastructure to be able to debug
 437	   problems with the new code.
 438	4. No on-disk format change (metadata or log format).
 439	5. Enable and disable with a mount option.
 440	6. No performance regressions for synchronous transaction workloads.
 441
 442Delayed Logging: Design
 443=======================
 444
 445Storing Changes
 446---------------
 447
 448The problem with accumulating changes at a logical level (i.e. just using the
 449existing log item dirty region tracking) is that when it comes to writing the
 450changes to the log buffers, we need to ensure that the object we are formatting
 451is not changing while we do this. This requires locking the object to prevent
 452concurrent modification. Hence flushing the logical changes to the log would
 453require us to lock every object, format them, and then unlock them again.
 454
 455This introduces lots of scope for deadlocks with transactions that are already
 456running. For example, a transaction has object A locked and modified, but needs
 457the delayed logging tracking lock to commit the transaction. However, the
 458flushing thread has the delayed logging tracking lock already held, and is
 459trying to get the lock on object A to flush it to the log buffer. This appears
 460to be an unsolvable deadlock condition, and it was solving this problem that
 461was the barrier to implementing delayed logging for so long.
 462
 463The solution is relatively simple - it just took a long time to recognise it.
 464Put simply, the current logging code formats the changes to each item into an
 465vector array that points to the changed regions in the item. The log write code
 466simply copies the memory these vectors point to into the log buffer during
 467transaction commit while the item is locked in the transaction. Instead of
 468using the log buffer as the destination of the formatting code, we can use an
 469allocated memory buffer big enough to fit the formatted vector.
 470
 471If we then copy the vector into the memory buffer and rewrite the vector to
 472point to the memory buffer rather than the object itself, we now have a copy of
 473the changes in a format that is compatible with the log buffer writing code.
 474that does not require us to lock the item to access. This formatting and
 475rewriting can all be done while the object is locked during transaction commit,
 476resulting in a vector that is transactionally consistent and can be accessed
 477without needing to lock the owning item.
 478
 479Hence we avoid the need to lock items when we need to flush outstanding
 480asynchronous transactions to the log. The differences between the existing
 481formatting method and the delayed logging formatting can be seen in the
 482diagram below.
 483
 484Current format log vector::
 485
 486    Object    +---------------------------------------------+
 487    Vector 1      +----+
 488    Vector 2                    +----+
 489    Vector 3                                   +----------+
 490
 491After formatting::
 492
 493    Log Buffer    +-V1-+-V2-+----V3----+
 494
 495Delayed logging vector::
 496
 497    Object    +---------------------------------------------+
 498    Vector 1      +----+
 499    Vector 2                    +----+
 500    Vector 3                                   +----------+
 501
 502After formatting::
 503
 504    Memory Buffer +-V1-+-V2-+----V3----+
 505    Vector 1      +----+
 506    Vector 2           +----+
 507    Vector 3                +----------+
 508
 509The memory buffer and associated vector need to be passed as a single object,
 510but still need to be associated with the parent object so if the object is
 511relogged we can replace the current memory buffer with a new memory buffer that
 512contains the latest changes.
 513
 514The reason for keeping the vector around after we've formatted the memory
 515buffer is to support splitting vectors across log buffer boundaries correctly.
 516If we don't keep the vector around, we do not know where the region boundaries
 517are in the item, so we'd need a new encapsulation method for regions in the log
 518buffer writing (i.e. double encapsulation). This would be an on-disk format
 519change and as such is not desirable.  It also means we'd have to write the log
 520region headers in the formatting stage, which is problematic as there is per
 521region state that needs to be placed into the headers during the log write.
 522
 523Hence we need to keep the vector, but by attaching the memory buffer to it and
 524rewriting the vector addresses to point at the memory buffer we end up with a
 525self-describing object that can be passed to the log buffer write code to be
 526handled in exactly the same manner as the existing log vectors are handled.
 527Hence we avoid needing a new on-disk format to handle items that have been
 528relogged in memory.
 529
 530
 531Tracking Changes
 532----------------
 533
 534Now that we can record transactional changes in memory in a form that allows
 535them to be used without limitations, we need to be able to track and accumulate
 536them so that they can be written to the log at some later point in time.  The
 537log item is the natural place to store this vector and buffer, and also makes sense
 538to be the object that is used to track committed objects as it will always
 539exist once the object has been included in a transaction.
 540
 541The log item is already used to track the log items that have been written to
 542the log but not yet written to disk. Such log items are considered "active"
 543and as such are stored in the Active Item List (AIL) which is a LSN-ordered
 544double linked list. Items are inserted into this list during log buffer IO
 545completion, after which they are unpinned and can be written to disk. An object
 546that is in the AIL can be relogged, which causes the object to be pinned again
 547and then moved forward in the AIL when the log buffer IO completes for that
 548transaction.
 549
 550Essentially, this shows that an item that is in the AIL can still be modified
 551and relogged, so any tracking must be separate to the AIL infrastructure. As
 552such, we cannot reuse the AIL list pointers for tracking committed items, nor
 553can we store state in any field that is protected by the AIL lock. Hence the
 554committed item tracking needs its own locks, lists and state fields in the log
 555item.
 556
 557Similar to the AIL, tracking of committed items is done through a new list
 558called the Committed Item List (CIL).  The list tracks log items that have been
 559committed and have formatted memory buffers attached to them. It tracks objects
 560in transaction commit order, so when an object is relogged it is removed from
 561its place in the list and re-inserted at the tail. This is entirely arbitrary
 562and done to make it easy for debugging - the last items in the list are the
 563ones that are most recently modified. Ordering of the CIL is not necessary for
 564transactional integrity (as discussed in the next section) so the ordering is
 565done for convenience/sanity of the developers.
 566
 567
 568Delayed Logging: Checkpoints
 569----------------------------
 570
 571When we have a log synchronisation event, commonly known as a "log force",
 572all the items in the CIL must be written into the log via the log buffers.
 573We need to write these items in the order that they exist in the CIL, and they
 574need to be written as an atomic transaction. The need for all the objects to be
 575written as an atomic transaction comes from the requirements of relogging and
 576log replay - all the changes in all the objects in a given transaction must
 577either be completely replayed during log recovery, or not replayed at all. If
 578a transaction is not replayed because it is not complete in the log, then
 579no later transactions should be replayed, either.
 580
 581To fulfill this requirement, we need to write the entire CIL in a single log
 582transaction. Fortunately, the XFS log code has no fixed limit on the size of a
 583transaction, nor does the log replay code. The only fundamental limit is that
 584the transaction cannot be larger than just under half the size of the log.  The
 585reason for this limit is that to find the head and tail of the log, there must
 586be at least one complete transaction in the log at any given time. If a
 587transaction is larger than half the log, then there is the possibility that a
 588crash during the write of a such a transaction could partially overwrite the
 589only complete previous transaction in the log. This will result in a recovery
 590failure and an inconsistent filesystem and hence we must enforce the maximum
 591size of a checkpoint to be slightly less than a half the log.
 592
 593Apart from this size requirement, a checkpoint transaction looks no different
 594to any other transaction - it contains a transaction header, a series of
 595formatted log items and a commit record at the tail. From a recovery
 596perspective, the checkpoint transaction is also no different - just a lot
 597bigger with a lot more items in it. The worst case effect of this is that we
 598might need to tune the recovery transaction object hash size.
 599
 600Because the checkpoint is just another transaction and all the changes to log
 601items are stored as log vectors, we can use the existing log buffer writing
 602code to write the changes into the log. To do this efficiently, we need to
 603minimise the time we hold the CIL locked while writing the checkpoint
 604transaction. The current log write code enables us to do this easily with the
 605way it separates the writing of the transaction contents (the log vectors) from
 606the transaction commit record, but tracking this requires us to have a
 607per-checkpoint context that travels through the log write process through to
 608checkpoint completion.
 609
 610Hence a checkpoint has a context that tracks the state of the current
 611checkpoint from initiation to checkpoint completion. A new context is initiated
 612at the same time a checkpoint transaction is started. That is, when we remove
 613all the current items from the CIL during a checkpoint operation, we move all
 614those changes into the current checkpoint context. We then initialise a new
 615context and attach that to the CIL for aggregation of new transactions.
 616
 617This allows us to unlock the CIL immediately after transfer of all the
 618committed items and effectively allows new transactions to be issued while we
 619are formatting the checkpoint into the log. It also allows concurrent
 620checkpoints to be written into the log buffers in the case of log force heavy
 621workloads, just like the existing transaction commit code does. This, however,
 622requires that we strictly order the commit records in the log so that
 623checkpoint sequence order is maintained during log replay.
 624
 625To ensure that we can be writing an item into a checkpoint transaction at
 626the same time another transaction modifies the item and inserts the log item
 627into the new CIL, then checkpoint transaction commit code cannot use log items
 628to store the list of log vectors that need to be written into the transaction.
 629Hence log vectors need to be able to be chained together to allow them to be
 630detached from the log items. That is, when the CIL is flushed the memory
 631buffer and log vector attached to each log item needs to be attached to the
 632checkpoint context so that the log item can be released. In diagrammatic form,
 633the CIL would look like this before the flush::
 634
 635	CIL Head
 636	   |
 637	   V
 638	Log Item <-> log vector 1	-> memory buffer
 639	   |				-> vector array
 640	   V
 641	Log Item <-> log vector 2	-> memory buffer
 642	   |				-> vector array
 643	   V
 644	......
 645	   |
 646	   V
 647	Log Item <-> log vector N-1	-> memory buffer
 648	   |				-> vector array
 649	   V
 650	Log Item <-> log vector N	-> memory buffer
 651					-> vector array
 652
 653And after the flush the CIL head is empty, and the checkpoint context log
 654vector list would look like::
 655
 656	Checkpoint Context
 657	   |
 658	   V
 659	log vector 1	-> memory buffer
 660	   |		-> vector array
 661	   |		-> Log Item
 662	   V
 663	log vector 2	-> memory buffer
 664	   |		-> vector array
 665	   |		-> Log Item
 666	   V
 667	......
 668	   |
 669	   V
 670	log vector N-1	-> memory buffer
 671	   |		-> vector array
 672	   |		-> Log Item
 673	   V
 674	log vector N	-> memory buffer
 675			-> vector array
 676			-> Log Item
 677
 678Once this transfer is done, the CIL can be unlocked and new transactions can
 679start, while the checkpoint flush code works over the log vector chain to
 680commit the checkpoint.
 681
 682Once the checkpoint is written into the log buffers, the checkpoint context is
 683attached to the log buffer that the commit record was written to along with a
 684completion callback. Log IO completion will call that callback, which can then
 685run transaction committed processing for the log items (i.e. insert into AIL
 686and unpin) in the log vector chain and then free the log vector chain and
 687checkpoint context.
 688
 689Discussion Point: I am uncertain as to whether the log item is the most
 690efficient way to track vectors, even though it seems like the natural way to do
 691it. The fact that we walk the log items (in the CIL) just to chain the log
 692vectors and break the link between the log item and the log vector means that
 693we take a cache line hit for the log item list modification, then another for
 694the log vector chaining. If we track by the log vectors, then we only need to
 695break the link between the log item and the log vector, which means we should
 696dirty only the log item cachelines. Normally I wouldn't be concerned about one
 697vs two dirty cachelines except for the fact I've seen upwards of 80,000 log
 698vectors in one checkpoint transaction. I'd guess this is a "measure and
 699compare" situation that can be done after a working and reviewed implementation
 700is in the dev tree....
 701
 702Delayed Logging: Checkpoint Sequencing
 703--------------------------------------
 704
 705One of the key aspects of the XFS transaction subsystem is that it tags
 706committed transactions with the log sequence number of the transaction commit.
 707This allows transactions to be issued asynchronously even though there may be
 708future operations that cannot be completed until that transaction is fully
 709committed to the log. In the rare case that a dependent operation occurs (e.g.
 710re-using a freed metadata extent for a data extent), a special, optimised log
 711force can be issued to force the dependent transaction to disk immediately.
 712
 713To do this, transactions need to record the LSN of the commit record of the
 714transaction. This LSN comes directly from the log buffer the transaction is
 715written into. While this works just fine for the existing transaction
 716mechanism, it does not work for delayed logging because transactions are not
 717written directly into the log buffers. Hence some other method of sequencing
 718transactions is required.
 719
 720As discussed in the checkpoint section, delayed logging uses per-checkpoint
 721contexts, and as such it is simple to assign a sequence number to each
 722checkpoint. Because the switching of checkpoint contexts must be done
 723atomically, it is simple to ensure that each new context has a monotonically
 724increasing sequence number assigned to it without the need for an external
 725atomic counter - we can just take the current context sequence number and add
 726one to it for the new context.
 727
 728Then, instead of assigning a log buffer LSN to the transaction commit LSN
 729during the commit, we can assign the current checkpoint sequence. This allows
 730operations that track transactions that have not yet completed know what
 731checkpoint sequence needs to be committed before they can continue. As a
 732result, the code that forces the log to a specific LSN now needs to ensure that
 733the log forces to a specific checkpoint.
 734
 735To ensure that we can do this, we need to track all the checkpoint contexts
 736that are currently committing to the log. When we flush a checkpoint, the
 737context gets added to a "committing" list which can be searched. When a
 738checkpoint commit completes, it is removed from the committing list. Because
 739the checkpoint context records the LSN of the commit record for the checkpoint,
 740we can also wait on the log buffer that contains the commit record, thereby
 741using the existing log force mechanisms to execute synchronous forces.
 742
 743It should be noted that the synchronous forces may need to be extended with
 744mitigation algorithms similar to the current log buffer code to allow
 745aggregation of multiple synchronous transactions if there are already
 746synchronous transactions being flushed. Investigation of the performance of the
 747current design is needed before making any decisions here.
 748
 749The main concern with log forces is to ensure that all the previous checkpoints
 750are also committed to disk before the one we need to wait for. Therefore we
 751need to check that all the prior contexts in the committing list are also
 752complete before waiting on the one we need to complete. We do this
 753synchronisation in the log force code so that we don't need to wait anywhere
 754else for such serialisation - it only matters when we do a log force.
 755
 756The only remaining complexity is that a log force now also has to handle the
 757case where the forcing sequence number is the same as the current context. That
 758is, we need to flush the CIL and potentially wait for it to complete. This is a
 759simple addition to the existing log forcing code to check the sequence numbers
 760and push if required. Indeed, placing the current sequence checkpoint flush in
 761the log force code enables the current mechanism for issuing synchronous
 762transactions to remain untouched (i.e. commit an asynchronous transaction, then
 763force the log at the LSN of that transaction) and so the higher level code
 764behaves the same regardless of whether delayed logging is being used or not.
 765
 766Delayed Logging: Checkpoint Log Space Accounting
 767------------------------------------------------
 768
 769The big issue for a checkpoint transaction is the log space reservation for the
 770transaction. We don't know how big a checkpoint transaction is going to be
 771ahead of time, nor how many log buffers it will take to write out, nor the
 772number of split log vector regions are going to be used. We can track the
 773amount of log space required as we add items to the commit item list, but we
 774still need to reserve the space in the log for the checkpoint.
 775
 776A typical transaction reserves enough space in the log for the worst case space
 777usage of the transaction. The reservation accounts for log record headers,
 778transaction and region headers, headers for split regions, buffer tail padding,
 779etc. as well as the actual space for all the changed metadata in the
 780transaction. While some of this is fixed overhead, much of it is dependent on
 781the size of the transaction and the number of regions being logged (the number
 782of log vectors in the transaction).
 783
 784An example of the differences would be logging directory changes versus logging
 785inode changes. If you modify lots of inode cores (e.g. ``chmod -R g+w *``), then
 786there are lots of transactions that only contain an inode core and an inode log
 787format structure. That is, two vectors totaling roughly 150 bytes. If we modify
 78810,000 inodes, we have about 1.5MB of metadata to write in 20,000 vectors. Each
 789vector is 12 bytes, so the total to be logged is approximately 1.75MB. In
 790comparison, if we are logging full directory buffers, they are typically 4KB
 791each, so we in 1.5MB of directory buffers we'd have roughly 400 buffers and a
 792buffer format structure for each buffer - roughly 800 vectors or 1.51MB total
 793space.  From this, it should be obvious that a static log space reservation is
 794not particularly flexible and is difficult to select the "optimal value" for
 795all workloads.
 796
 797Further, if we are going to use a static reservation, which bit of the entire
 798reservation does it cover? We account for space used by the transaction
 799reservation by tracking the space currently used by the object in the CIL and
 800then calculating the increase or decrease in space used as the object is
 801relogged. This allows for a checkpoint reservation to only have to account for
 802log buffer metadata used such as log header records.
 803
 804However, even using a static reservation for just the log metadata is
 805problematic. Typically log record headers use at least 16KB of log space per
 8061MB of log space consumed (512 bytes per 32k) and the reservation needs to be
 807large enough to handle arbitrary sized checkpoint transactions. This
 808reservation needs to be made before the checkpoint is started, and we need to
 809be able to reserve the space without sleeping.  For a 8MB checkpoint, we need a
 810reservation of around 150KB, which is a non-trivial amount of space.
 811
 812A static reservation needs to manipulate the log grant counters - we can take a
 813permanent reservation on the space, but we still need to make sure we refresh
 814the write reservation (the actual space available to the transaction) after
 815every checkpoint transaction completion. Unfortunately, if this space is not
 816available when required, then the regrant code will sleep waiting for it.
 817
 818The problem with this is that it can lead to deadlocks as we may need to commit
 819checkpoints to be able to free up log space (refer back to the description of
 820rolling transactions for an example of this).  Hence we *must* always have
 821space available in the log if we are to use static reservations, and that is
 822very difficult and complex to arrange. It is possible to do, but there is a
 823simpler way.
 824
 825The simpler way of doing this is tracking the entire log space used by the
 826items in the CIL and using this to dynamically calculate the amount of log
 827space required by the log metadata. If this log metadata space changes as a
 828result of a transaction commit inserting a new memory buffer into the CIL, then
 829the difference in space required is removed from the transaction that causes
 830the change. Transactions at this level will *always* have enough space
 831available in their reservation for this as they have already reserved the
 832maximal amount of log metadata space they require, and such a delta reservation
 833will always be less than or equal to the maximal amount in the reservation.
 834
 835Hence we can grow the checkpoint transaction reservation dynamically as items
 836are added to the CIL and avoid the need for reserving and regranting log space
 837up front. This avoids deadlocks and removes a blocking point from the
 838checkpoint flush code.
 839
 840As mentioned early, transactions can't grow to more than half the size of the
 841log. Hence as part of the reservation growing, we need to also check the size
 842of the reservation against the maximum allowed transaction size. If we reach
 843the maximum threshold, we need to push the CIL to the log. This is effectively
 844a "background flush" and is done on demand. This is identical to
 845a CIL push triggered by a log force, only that there is no waiting for the
 846checkpoint commit to complete. This background push is checked and executed by
 847transaction commit code.
 848
 849If the transaction subsystem goes idle while we still have items in the CIL,
 850they will be flushed by the periodic log force issued by the xfssyncd. This log
 851force will push the CIL to disk, and if the transaction subsystem stays idle,
 852allow the idle log to be covered (effectively marked clean) in exactly the same
 853manner that is done for the existing logging method. A discussion point is
 854whether this log force needs to be done more frequently than the current rate
 855which is once every 30s.
 856
 857
 858Delayed Logging: Log Item Pinning
 859---------------------------------
 860
 861Currently log items are pinned during transaction commit while the items are
 862still locked. This happens just after the items are formatted, though it could
 863be done any time before the items are unlocked. The result of this mechanism is
 864that items get pinned once for every transaction that is committed to the log
 865buffers. Hence items that are relogged in the log buffers will have a pin count
 866for every outstanding transaction they were dirtied in. When each of these
 867transactions is completed, they will unpin the item once. As a result, the item
 868only becomes unpinned when all the transactions complete and there are no
 869pending transactions. Thus the pinning and unpinning of a log item is symmetric
 870as there is a 1:1 relationship with transaction commit and log item completion.
 871
 872For delayed logging, however, we have an asymmetric transaction commit to
 873completion relationship. Every time an object is relogged in the CIL it goes
 874through the commit process without a corresponding completion being registered.
 875That is, we now have a many-to-one relationship between transaction commit and
 876log item completion. The result of this is that pinning and unpinning of the
 877log items becomes unbalanced if we retain the "pin on transaction commit, unpin
 878on transaction completion" model.
 879
 880To keep pin/unpin symmetry, the algorithm needs to change to a "pin on
 881insertion into the CIL, unpin on checkpoint completion". In other words, the
 882pinning and unpinning becomes symmetric around a checkpoint context. We have to
 883pin the object the first time it is inserted into the CIL - if it is already in
 884the CIL during a transaction commit, then we do not pin it again. Because there
 885can be multiple outstanding checkpoint contexts, we can still see elevated pin
 886counts, but as each checkpoint completes the pin count will retain the correct
 887value according to its context.
 888
 889Just to make matters slightly more complex, this checkpoint level context
 890for the pin count means that the pinning of an item must take place under the
 891CIL commit/flush lock. If we pin the object outside this lock, we cannot
 892guarantee which context the pin count is associated with. This is because of
 893the fact pinning the item is dependent on whether the item is present in the
 894current CIL or not. If we don't pin the CIL first before we check and pin the
 895object, we have a race with CIL being flushed between the check and the pin
 896(or not pinning, as the case may be). Hence we must hold the CIL flush/commit
 897lock to guarantee that we pin the items correctly.
 898
 899Delayed Logging: Concurrent Scalability
 900---------------------------------------
 901
 902A fundamental requirement for the CIL is that accesses through transaction
 903commits must scale to many concurrent commits. The current transaction commit
 904code does not break down even when there are transactions coming from 2048
 905processors at once. The current transaction code does not go any faster than if
 906there was only one CPU using it, but it does not slow down either.
 907
 908As a result, the delayed logging transaction commit code needs to be designed
 909for concurrency from the ground up. It is obvious that there are serialisation
 910points in the design - the three important ones are:
 911
 912	1. Locking out new transaction commits while flushing the CIL
 913	2. Adding items to the CIL and updating item space accounting
 914	3. Checkpoint commit ordering
 915
 916Looking at the transaction commit and CIL flushing interactions, it is clear
 917that we have a many-to-one interaction here. That is, the only restriction on
 918the number of concurrent transactions that can be trying to commit at once is
 919the amount of space available in the log for their reservations. The practical
 920limit here is in the order of several hundred concurrent transactions for a
 921128MB log, which means that it is generally one per CPU in a machine.
 922
 923The amount of time a transaction commit needs to hold out a flush is a
 924relatively long period of time - the pinning of log items needs to be done
 925while we are holding out a CIL flush, so at the moment that means it is held
 926across the formatting of the objects into memory buffers (i.e. while memcpy()s
 927are in progress). Ultimately a two pass algorithm where the formatting is done
 928separately to the pinning of objects could be used to reduce the hold time of
 929the transaction commit side.
 930
 931Because of the number of potential transaction commit side holders, the lock
 932really needs to be a sleeping lock - if the CIL flush takes the lock, we do not
 933want every other CPU in the machine spinning on the CIL lock. Given that
 934flushing the CIL could involve walking a list of tens of thousands of log
 935items, it will get held for a significant time and so spin contention is a
 936significant concern. Preventing lots of CPUs spinning doing nothing is the
 937main reason for choosing a sleeping lock even though nothing in either the
 938transaction commit or CIL flush side sleeps with the lock held.
 939
 940It should also be noted that CIL flushing is also a relatively rare operation
 941compared to transaction commit for asynchronous transaction workloads - only
 942time will tell if using a read-write semaphore for exclusion will limit
 943transaction commit concurrency due to cache line bouncing of the lock on the
 944read side.
 945
 946The second serialisation point is on the transaction commit side where items
 947are inserted into the CIL. Because transactions can enter this code
 948concurrently, the CIL needs to be protected separately from the above
 949commit/flush exclusion. It also needs to be an exclusive lock but it is only
 950held for a very short time and so a spin lock is appropriate here. It is
 951possible that this lock will become a contention point, but given the short
 952hold time once per transaction I think that contention is unlikely.
 953
 954The final serialisation point is the checkpoint commit record ordering code
 955that is run as part of the checkpoint commit and log force sequencing. The code
 956path that triggers a CIL flush (i.e. whatever triggers the log force) will enter
 957an ordering loop after writing all the log vectors into the log buffers but
 958before writing the commit record. This loop walks the list of committing
 959checkpoints and needs to block waiting for checkpoints to complete their commit
 960record write. As a result it needs a lock and a wait variable. Log force
 961sequencing also requires the same lock, list walk, and blocking mechanism to
 962ensure completion of checkpoints.
 963
 964These two sequencing operations can use the mechanism even though the
 965events they are waiting for are different. The checkpoint commit record
 966sequencing needs to wait until checkpoint contexts contain a commit LSN
 967(obtained through completion of a commit record write) while log force
 968sequencing needs to wait until previous checkpoint contexts are removed from
 969the committing list (i.e. they've completed). A simple wait variable and
 970broadcast wakeups (thundering herds) has been used to implement these two
 971serialisation queues. They use the same lock as the CIL, too. If we see too
 972much contention on the CIL lock, or too many context switches as a result of
 973the broadcast wakeups these operations can be put under a new spinlock and
 974given separate wait lists to reduce lock contention and the number of processes
 975woken by the wrong event.
 976
 977
 978Lifecycle Changes
 979-----------------
 980
 981The existing log item life cycle is as follows::
 982
 983	1. Transaction allocate
 984	2. Transaction reserve
 985	3. Lock item
 986	4. Join item to transaction
 987		If not already attached,
 988			Allocate log item
 989			Attach log item to owner item
 990		Attach log item to transaction
 991	5. Modify item
 992		Record modifications in log item
 993	6. Transaction commit
 994		Pin item in memory
 995		Format item into log buffer
 996		Write commit LSN into transaction
 997		Unlock item
 998		Attach transaction to log buffer
 999
1000	<log buffer IO dispatched>
1001	<log buffer IO completes>
1002
1003	7. Transaction completion
1004		Mark log item committed
1005		Insert log item into AIL
1006			Write commit LSN into log item
1007		Unpin log item
1008	8. AIL traversal
1009		Lock item
1010		Mark log item clean
1011		Flush item to disk
1012
1013	<item IO completion>
1014
1015	9. Log item removed from AIL
1016		Moves log tail
1017		Item unlocked
1018
1019Essentially, steps 1-6 operate independently from step 7, which is also
1020independent of steps 8-9. An item can be locked in steps 1-6 or steps 8-9
1021at the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur
1022at the same time. If the log item is in the AIL or between steps 6 and 7
1023and steps 1-6 are re-entered, then the item is relogged. Only when steps 8-9
1024are entered and completed is the object considered clean.
1025
1026With delayed logging, there are new steps inserted into the life cycle::
1027
1028	1. Transaction allocate
1029	2. Transaction reserve
1030	3. Lock item
1031	4. Join item to transaction
1032		If not already attached,
1033			Allocate log item
1034			Attach log item to owner item
1035		Attach log item to transaction
1036	5. Modify item
1037		Record modifications in log item
1038	6. Transaction commit
1039		Pin item in memory if not pinned in CIL
1040		Format item into log vector + buffer
1041		Attach log vector and buffer to log item
1042		Insert log item into CIL
1043		Write CIL context sequence into transaction
1044		Unlock item
1045
1046	<next log force>
1047
1048	7. CIL push
1049		lock CIL flush
1050		Chain log vectors and buffers together
1051		Remove items from CIL
1052		unlock CIL flush
1053		write log vectors into log
1054		sequence commit records
1055		attach checkpoint context to log buffer
1056
1057	<log buffer IO dispatched>
1058	<log buffer IO completes>
1059
1060	8. Checkpoint completion
1061		Mark log item committed
1062		Insert item into AIL
1063			Write commit LSN into log item
1064		Unpin log item
1065	9. AIL traversal
1066		Lock item
1067		Mark log item clean
1068		Flush item to disk
1069	<item IO completion>
1070	10. Log item removed from AIL
1071		Moves log tail
1072		Item unlocked
1073
1074From this, it can be seen that the only life cycle differences between the two
1075logging methods are in the middle of the life cycle - they still have the same
1076beginning and end and execution constraints. The only differences are in the
1077committing of the log items to the log itself and the completion processing.
1078Hence delayed logging should not introduce any constraints on log item
1079behaviour, allocation or freeing that don't already exist.
1080
1081As a result of this zero-impact "insertion" of delayed logging infrastructure
1082and the design of the internal structures to avoid on disk format changes, we
1083can basically switch between delayed logging and the existing mechanism with a
1084mount option. Fundamentally, there is no reason why the log manager would not
1085be able to swap methods automatically and transparently depending on load
1086characteristics, but this should not be necessary if delayed logging works as
1087designed.

  1.. SPDX-License-Identifier: GPL-2.0
  2
  3==========================
  4XFS Delayed Logging Design
  5==========================
  6
  7Introduction to Re-logging in XFS
  8=================================
  9
 10XFS logging is a combination of logical and physical logging. Some objects,
 11such as inodes and dquots, are logged in logical format where the details
 12logged are made up of the changes to in-core structures rather than on-disk
 13structures. Other objects - typically buffers - have their physical changes
 14logged. The reason for these differences is to reduce the amount of log space
 15required for objects that are frequently logged. Some parts of inodes are more
 16frequently logged than others, and inodes are typically more frequently logged
 17than any other object (except maybe the superblock buffer) so keeping the
 18amount of metadata logged low is of prime importance.
 19
 20The reason that this is such a concern is that XFS allows multiple separate
 21modifications to a single object to be carried in the log at any given time.
 22This allows the log to avoid needing to flush each change to disk before
 23recording a new change to the object. XFS does this via a method called
 24"re-logging". Conceptually, this is quite simple - all it requires is that any
 25new change to the object is recorded with a *new copy* of all the existing
 26changes in the new transaction that is written to the log.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 27
 28That is, if we have a sequence of changes A through to F, and the object was
 29written to disk after change D, we would see in the log the following series
 30of transactions, their contents and the log sequence number (LSN) of the
 31transaction::
 32
 33	Transaction		Contents	LSN
 34	   A			   A		   X
 35	   B			  A+B		  X+n
 36	   C			 A+B+C		 X+n+m
 37	   D			A+B+C+D		X+n+m+o
 38	    <object written to disk>
 39	   E			   E		   Y (> X+n+m+o)
 40	   F			  E+F		  Y+p
 41
 42In other words, each time an object is relogged, the new transaction contains
 43the aggregation of all the previous changes currently held only in the log.
 44
 45This relogging technique also allows objects to be moved forward in the log so
 46that an object being relogged does not prevent the tail of the log from ever
 47moving forward.  This can be seen in the table above by the changing
 48(increasing) LSN of each subsequent transaction - the LSN is effectively a
 49direct encoding of the location in the log of the transaction.
 50
 51This relogging is also used to implement long-running, multiple-commit
 52transactions.  These transaction are known as rolling transactions, and require
 53a special log reservation known as a permanent transaction reservation. A
 54typical example of a rolling transaction is the removal of extents from an
 55inode which can only be done at a rate of two extents per transaction because
 56of reservation size limitations. Hence a rolling extent removal transaction
 57keeps relogging the inode and btree buffers as they get modified in each
 58removal operation. This keeps them moving forward in the log as the operation
 59progresses, ensuring that current operation never gets blocked by itself if the
 60log wraps around.
 61
 62Hence it can be seen that the relogging operation is fundamental to the correct
 63working of the XFS journalling subsystem. From the above description, most
 64people should be able to see why the XFS metadata operations writes so much to
 65the log - repeated operations to the same objects write the same changes to
 66the log over and over again. Worse is the fact that objects tend to get
 67dirtier as they get relogged, so each subsequent transaction is writing more
 68metadata into the log.
 69
 70Another feature of the XFS transaction subsystem is that most transactions are
 71asynchronous. That is, they don't commit to disk until either a log buffer is
 72filled (a log buffer can hold multiple transactions) or a synchronous operation
 73forces the log buffers holding the transactions to disk. This means that XFS is
 74doing aggregation of transactions in memory - batching them, if you like - to
 75minimise the impact of the log IO on transaction throughput.
 
 76
 77The limitation on asynchronous transaction throughput is the number and size of
 78log buffers made available by the log manager. By default there are 8 log
 79buffers available and the size of each is 32kB - the size can be increased up
 80to 256kB by use of a mount option.
 81
 82Effectively, this gives us the maximum bound of outstanding metadata changes
 83that can be made to the filesystem at any point in time - if all the log
 84buffers are full and under IO, then no more transactions can be committed until
 85the current batch completes. It is now common for a single current CPU core to
 86be to able to issue enough transactions to keep the log buffers full and under
 87IO permanently. Hence the XFS journalling subsystem can be considered to be IO
 88bound.
 89
 90Delayed Logging: Concepts
 91=========================
 92
 93The key thing to note about the asynchronous logging combined with the
 94relogging technique XFS uses is that we can be relogging changed objects
 95multiple times before they are committed to disk in the log buffers. If we
 96return to the previous relogging example, it is entirely possible that
 97transactions A through D are committed to disk in the same log buffer.
 98
 99That is, a single log buffer may contain multiple copies of the same object,
100but only one of those copies needs to be there - the last one "D", as it
101contains all the changes from the previous changes. In other words, we have one
102necessary copy in the log buffer, and three stale copies that are simply
103wasting space. When we are doing repeated operations on the same set of
104objects, these "stale objects" can be over 90% of the space used in the log
105buffers. It is clear that reducing the number of stale objects written to the
106log would greatly reduce the amount of metadata we write to the log, and this
107is the fundamental goal of delayed logging.
108
109From a conceptual point of view, XFS is already doing relogging in memory (where
110memory == log buffer), only it is doing it extremely inefficiently. It is using
111logical to physical formatting to do the relogging because there is no
112infrastructure to keep track of logical changes in memory prior to physically
113formatting the changes in a transaction to the log buffer. Hence we cannot avoid
114accumulating stale objects in the log buffers.
115
116Delayed logging is the name we've given to keeping and tracking transactional
117changes to objects in memory outside the log buffer infrastructure. Because of
118the relogging concept fundamental to the XFS journalling subsystem, this is
119actually relatively easy to do - all the changes to logged items are already
120tracked in the current infrastructure. The big problem is how to accumulate
121them and get them to the log in a consistent, recoverable manner.
122Describing the problems and how they have been solved is the focus of this
123document.
124
125One of the key changes that delayed logging makes to the operation of the
126journalling subsystem is that it disassociates the amount of outstanding
127metadata changes from the size and number of log buffers available. In other
128words, instead of there only being a maximum of 2MB of transaction changes not
129written to the log at any point in time, there may be a much greater amount
130being accumulated in memory. Hence the potential for loss of metadata on a
131crash is much greater than for the existing logging mechanism.
132
133It should be noted that this does not change the guarantee that log recovery
134will result in a consistent filesystem. What it does mean is that as far as the
135recovered filesystem is concerned, there may be many thousands of transactions
136that simply did not occur as a result of the crash. This makes it even more
137important that applications that care about their data use fsync() where they
138need to ensure application level data integrity is maintained.
139
140It should be noted that delayed logging is not an innovative new concept that
141warrants rigorous proofs to determine whether it is correct or not. The method
142of accumulating changes in memory for some period before writing them to the
143log is used effectively in many filesystems including ext3 and ext4. Hence
144no time is spent in this document trying to convince the reader that the
145concept is sound. Instead it is simply considered a "solved problem" and as
146such implementing it in XFS is purely an exercise in software engineering.
147
148The fundamental requirements for delayed logging in XFS are simple:
149
150	1. Reduce the amount of metadata written to the log by at least
151	   an order of magnitude.
152	2. Supply sufficient statistics to validate Requirement #1.
153	3. Supply sufficient new tracing infrastructure to be able to debug
154	   problems with the new code.
155	4. No on-disk format change (metadata or log format).
156	5. Enable and disable with a mount option.
157	6. No performance regressions for synchronous transaction workloads.
158
159Delayed Logging: Design
160=======================
161
162Storing Changes
163---------------
164
165The problem with accumulating changes at a logical level (i.e. just using the
166existing log item dirty region tracking) is that when it comes to writing the
167changes to the log buffers, we need to ensure that the object we are formatting
168is not changing while we do this. This requires locking the object to prevent
169concurrent modification. Hence flushing the logical changes to the log would
170require us to lock every object, format them, and then unlock them again.
171
172This introduces lots of scope for deadlocks with transactions that are already
173running. For example, a transaction has object A locked and modified, but needs
174the delayed logging tracking lock to commit the transaction. However, the
175flushing thread has the delayed logging tracking lock already held, and is
176trying to get the lock on object A to flush it to the log buffer. This appears
177to be an unsolvable deadlock condition, and it was solving this problem that
178was the barrier to implementing delayed logging for so long.
179
180The solution is relatively simple - it just took a long time to recognise it.
181Put simply, the current logging code formats the changes to each item into an
182vector array that points to the changed regions in the item. The log write code
183simply copies the memory these vectors point to into the log buffer during
184transaction commit while the item is locked in the transaction. Instead of
185using the log buffer as the destination of the formatting code, we can use an
186allocated memory buffer big enough to fit the formatted vector.
187
188If we then copy the vector into the memory buffer and rewrite the vector to
189point to the memory buffer rather than the object itself, we now have a copy of
190the changes in a format that is compatible with the log buffer writing code.
191that does not require us to lock the item to access. This formatting and
192rewriting can all be done while the object is locked during transaction commit,
193resulting in a vector that is transactionally consistent and can be accessed
194without needing to lock the owning item.
195
196Hence we avoid the need to lock items when we need to flush outstanding
197asynchronous transactions to the log. The differences between the existing
198formatting method and the delayed logging formatting can be seen in the
199diagram below.
200
201Current format log vector::
202
203    Object    +---------------------------------------------+
204    Vector 1      +----+
205    Vector 2                    +----+
206    Vector 3                                   +----------+
207
208After formatting::
209
210    Log Buffer    +-V1-+-V2-+----V3----+
211
212Delayed logging vector::
213
214    Object    +---------------------------------------------+
215    Vector 1      +----+
216    Vector 2                    +----+
217    Vector 3                                   +----------+
218
219After formatting::
220
221    Memory Buffer +-V1-+-V2-+----V3----+
222    Vector 1      +----+
223    Vector 2           +----+
224    Vector 3                +----------+
225
226The memory buffer and associated vector need to be passed as a single object,
227but still need to be associated with the parent object so if the object is
228relogged we can replace the current memory buffer with a new memory buffer that
229contains the latest changes.
230
231The reason for keeping the vector around after we've formatted the memory
232buffer is to support splitting vectors across log buffer boundaries correctly.
233If we don't keep the vector around, we do not know where the region boundaries
234are in the item, so we'd need a new encapsulation method for regions in the log
235buffer writing (i.e. double encapsulation). This would be an on-disk format
236change and as such is not desirable.  It also means we'd have to write the log
237region headers in the formatting stage, which is problematic as there is per
238region state that needs to be placed into the headers during the log write.
239
240Hence we need to keep the vector, but by attaching the memory buffer to it and
241rewriting the vector addresses to point at the memory buffer we end up with a
242self-describing object that can be passed to the log buffer write code to be
243handled in exactly the same manner as the existing log vectors are handled.
244Hence we avoid needing a new on-disk format to handle items that have been
245relogged in memory.
246
247
248Tracking Changes
249----------------
250
251Now that we can record transactional changes in memory in a form that allows
252them to be used without limitations, we need to be able to track and accumulate
253them so that they can be written to the log at some later point in time.  The
254log item is the natural place to store this vector and buffer, and also makes sense
255to be the object that is used to track committed objects as it will always
256exist once the object has been included in a transaction.
257
258The log item is already used to track the log items that have been written to
259the log but not yet written to disk. Such log items are considered "active"
260and as such are stored in the Active Item List (AIL) which is a LSN-ordered
261double linked list. Items are inserted into this list during log buffer IO
262completion, after which they are unpinned and can be written to disk. An object
263that is in the AIL can be relogged, which causes the object to be pinned again
264and then moved forward in the AIL when the log buffer IO completes for that
265transaction.
266
267Essentially, this shows that an item that is in the AIL can still be modified
268and relogged, so any tracking must be separate to the AIL infrastructure. As
269such, we cannot reuse the AIL list pointers for tracking committed items, nor
270can we store state in any field that is protected by the AIL lock. Hence the
271committed item tracking needs it's own locks, lists and state fields in the log
272item.
273
274Similar to the AIL, tracking of committed items is done through a new list
275called the Committed Item List (CIL).  The list tracks log items that have been
276committed and have formatted memory buffers attached to them. It tracks objects
277in transaction commit order, so when an object is relogged it is removed from
278it's place in the list and re-inserted at the tail. This is entirely arbitrary
279and done to make it easy for debugging - the last items in the list are the
280ones that are most recently modified. Ordering of the CIL is not necessary for
281transactional integrity (as discussed in the next section) so the ordering is
282done for convenience/sanity of the developers.
283
284
285Delayed Logging: Checkpoints
286----------------------------
287
288When we have a log synchronisation event, commonly known as a "log force",
289all the items in the CIL must be written into the log via the log buffers.
290We need to write these items in the order that they exist in the CIL, and they
291need to be written as an atomic transaction. The need for all the objects to be
292written as an atomic transaction comes from the requirements of relogging and
293log replay - all the changes in all the objects in a given transaction must
294either be completely replayed during log recovery, or not replayed at all. If
295a transaction is not replayed because it is not complete in the log, then
296no later transactions should be replayed, either.
297
298To fulfill this requirement, we need to write the entire CIL in a single log
299transaction. Fortunately, the XFS log code has no fixed limit on the size of a
300transaction, nor does the log replay code. The only fundamental limit is that
301the transaction cannot be larger than just under half the size of the log.  The
302reason for this limit is that to find the head and tail of the log, there must
303be at least one complete transaction in the log at any given time. If a
304transaction is larger than half the log, then there is the possibility that a
305crash during the write of a such a transaction could partially overwrite the
306only complete previous transaction in the log. This will result in a recovery
307failure and an inconsistent filesystem and hence we must enforce the maximum
308size of a checkpoint to be slightly less than a half the log.
309
310Apart from this size requirement, a checkpoint transaction looks no different
311to any other transaction - it contains a transaction header, a series of
312formatted log items and a commit record at the tail. From a recovery
313perspective, the checkpoint transaction is also no different - just a lot
314bigger with a lot more items in it. The worst case effect of this is that we
315might need to tune the recovery transaction object hash size.
316
317Because the checkpoint is just another transaction and all the changes to log
318items are stored as log vectors, we can use the existing log buffer writing
319code to write the changes into the log. To do this efficiently, we need to
320minimise the time we hold the CIL locked while writing the checkpoint
321transaction. The current log write code enables us to do this easily with the
322way it separates the writing of the transaction contents (the log vectors) from
323the transaction commit record, but tracking this requires us to have a
324per-checkpoint context that travels through the log write process through to
325checkpoint completion.
326
327Hence a checkpoint has a context that tracks the state of the current
328checkpoint from initiation to checkpoint completion. A new context is initiated
329at the same time a checkpoint transaction is started. That is, when we remove
330all the current items from the CIL during a checkpoint operation, we move all
331those changes into the current checkpoint context. We then initialise a new
332context and attach that to the CIL for aggregation of new transactions.
333
334This allows us to unlock the CIL immediately after transfer of all the
335committed items and effectively allow new transactions to be issued while we
336are formatting the checkpoint into the log. It also allows concurrent
337checkpoints to be written into the log buffers in the case of log force heavy
338workloads, just like the existing transaction commit code does. This, however,
339requires that we strictly order the commit records in the log so that
340checkpoint sequence order is maintained during log replay.
341
342To ensure that we can be writing an item into a checkpoint transaction at
343the same time another transaction modifies the item and inserts the log item
344into the new CIL, then checkpoint transaction commit code cannot use log items
345to store the list of log vectors that need to be written into the transaction.
346Hence log vectors need to be able to be chained together to allow them to be
347detached from the log items. That is, when the CIL is flushed the memory
348buffer and log vector attached to each log item needs to be attached to the
349checkpoint context so that the log item can be released. In diagrammatic form,
350the CIL would look like this before the flush::
351
352	CIL Head
353	   |
354	   V
355	Log Item <-> log vector 1	-> memory buffer
356	   |				-> vector array
357	   V
358	Log Item <-> log vector 2	-> memory buffer
359	   |				-> vector array
360	   V
361	......
362	   |
363	   V
364	Log Item <-> log vector N-1	-> memory buffer
365	   |				-> vector array
366	   V
367	Log Item <-> log vector N	-> memory buffer
368					-> vector array
369
370And after the flush the CIL head is empty, and the checkpoint context log
371vector list would look like::
372
373	Checkpoint Context
374	   |
375	   V
376	log vector 1	-> memory buffer
377	   |		-> vector array
378	   |		-> Log Item
379	   V
380	log vector 2	-> memory buffer
381	   |		-> vector array
382	   |		-> Log Item
383	   V
384	......
385	   |
386	   V
387	log vector N-1	-> memory buffer
388	   |		-> vector array
389	   |		-> Log Item
390	   V
391	log vector N	-> memory buffer
392			-> vector array
393			-> Log Item
394
395Once this transfer is done, the CIL can be unlocked and new transactions can
396start, while the checkpoint flush code works over the log vector chain to
397commit the checkpoint.
398
399Once the checkpoint is written into the log buffers, the checkpoint context is
400attached to the log buffer that the commit record was written to along with a
401completion callback. Log IO completion will call that callback, which can then
402run transaction committed processing for the log items (i.e. insert into AIL
403and unpin) in the log vector chain and then free the log vector chain and
404checkpoint context.
405
406Discussion Point: I am uncertain as to whether the log item is the most
407efficient way to track vectors, even though it seems like the natural way to do
408it. The fact that we walk the log items (in the CIL) just to chain the log
409vectors and break the link between the log item and the log vector means that
410we take a cache line hit for the log item list modification, then another for
411the log vector chaining. If we track by the log vectors, then we only need to
412break the link between the log item and the log vector, which means we should
413dirty only the log item cachelines. Normally I wouldn't be concerned about one
414vs two dirty cachelines except for the fact I've seen upwards of 80,000 log
415vectors in one checkpoint transaction. I'd guess this is a "measure and
416compare" situation that can be done after a working and reviewed implementation
417is in the dev tree....
418
419Delayed Logging: Checkpoint Sequencing
420--------------------------------------
421
422One of the key aspects of the XFS transaction subsystem is that it tags
423committed transactions with the log sequence number of the transaction commit.
424This allows transactions to be issued asynchronously even though there may be
425future operations that cannot be completed until that transaction is fully
426committed to the log. In the rare case that a dependent operation occurs (e.g.
427re-using a freed metadata extent for a data extent), a special, optimised log
428force can be issued to force the dependent transaction to disk immediately.
429
430To do this, transactions need to record the LSN of the commit record of the
431transaction. This LSN comes directly from the log buffer the transaction is
432written into. While this works just fine for the existing transaction
433mechanism, it does not work for delayed logging because transactions are not
434written directly into the log buffers. Hence some other method of sequencing
435transactions is required.
436
437As discussed in the checkpoint section, delayed logging uses per-checkpoint
438contexts, and as such it is simple to assign a sequence number to each
439checkpoint. Because the switching of checkpoint contexts must be done
440atomically, it is simple to ensure that each new context has a monotonically
441increasing sequence number assigned to it without the need for an external
442atomic counter - we can just take the current context sequence number and add
443one to it for the new context.
444
445Then, instead of assigning a log buffer LSN to the transaction commit LSN
446during the commit, we can assign the current checkpoint sequence. This allows
447operations that track transactions that have not yet completed know what
448checkpoint sequence needs to be committed before they can continue. As a
449result, the code that forces the log to a specific LSN now needs to ensure that
450the log forces to a specific checkpoint.
451
452To ensure that we can do this, we need to track all the checkpoint contexts
453that are currently committing to the log. When we flush a checkpoint, the
454context gets added to a "committing" list which can be searched. When a
455checkpoint commit completes, it is removed from the committing list. Because
456the checkpoint context records the LSN of the commit record for the checkpoint,
457we can also wait on the log buffer that contains the commit record, thereby
458using the existing log force mechanisms to execute synchronous forces.
459
460It should be noted that the synchronous forces may need to be extended with
461mitigation algorithms similar to the current log buffer code to allow
462aggregation of multiple synchronous transactions if there are already
463synchronous transactions being flushed. Investigation of the performance of the
464current design is needed before making any decisions here.
465
466The main concern with log forces is to ensure that all the previous checkpoints
467are also committed to disk before the one we need to wait for. Therefore we
468need to check that all the prior contexts in the committing list are also
469complete before waiting on the one we need to complete. We do this
470synchronisation in the log force code so that we don't need to wait anywhere
471else for such serialisation - it only matters when we do a log force.
472
473The only remaining complexity is that a log force now also has to handle the
474case where the forcing sequence number is the same as the current context. That
475is, we need to flush the CIL and potentially wait for it to complete. This is a
476simple addition to the existing log forcing code to check the sequence numbers
477and push if required. Indeed, placing the current sequence checkpoint flush in
478the log force code enables the current mechanism for issuing synchronous
479transactions to remain untouched (i.e. commit an asynchronous transaction, then
480force the log at the LSN of that transaction) and so the higher level code
481behaves the same regardless of whether delayed logging is being used or not.
482
483Delayed Logging: Checkpoint Log Space Accounting
484------------------------------------------------
485
486The big issue for a checkpoint transaction is the log space reservation for the
487transaction. We don't know how big a checkpoint transaction is going to be
488ahead of time, nor how many log buffers it will take to write out, nor the
489number of split log vector regions are going to be used. We can track the
490amount of log space required as we add items to the commit item list, but we
491still need to reserve the space in the log for the checkpoint.
492
493A typical transaction reserves enough space in the log for the worst case space
494usage of the transaction. The reservation accounts for log record headers,
495transaction and region headers, headers for split regions, buffer tail padding,
496etc. as well as the actual space for all the changed metadata in the
497transaction. While some of this is fixed overhead, much of it is dependent on
498the size of the transaction and the number of regions being logged (the number
499of log vectors in the transaction).
500
501An example of the differences would be logging directory changes versus logging
502inode changes. If you modify lots of inode cores (e.g. ``chmod -R g+w *``), then
503there are lots of transactions that only contain an inode core and an inode log
504format structure. That is, two vectors totaling roughly 150 bytes. If we modify
50510,000 inodes, we have about 1.5MB of metadata to write in 20,000 vectors. Each
506vector is 12 bytes, so the total to be logged is approximately 1.75MB. In
507comparison, if we are logging full directory buffers, they are typically 4KB
508each, so we in 1.5MB of directory buffers we'd have roughly 400 buffers and a
509buffer format structure for each buffer - roughly 800 vectors or 1.51MB total
510space.  From this, it should be obvious that a static log space reservation is
511not particularly flexible and is difficult to select the "optimal value" for
512all workloads.
513
514Further, if we are going to use a static reservation, which bit of the entire
515reservation does it cover? We account for space used by the transaction
516reservation by tracking the space currently used by the object in the CIL and
517then calculating the increase or decrease in space used as the object is
518relogged. This allows for a checkpoint reservation to only have to account for
519log buffer metadata used such as log header records.
520
521However, even using a static reservation for just the log metadata is
522problematic. Typically log record headers use at least 16KB of log space per
5231MB of log space consumed (512 bytes per 32k) and the reservation needs to be
524large enough to handle arbitrary sized checkpoint transactions. This
525reservation needs to be made before the checkpoint is started, and we need to
526be able to reserve the space without sleeping.  For a 8MB checkpoint, we need a
527reservation of around 150KB, which is a non-trivial amount of space.
528
529A static reservation needs to manipulate the log grant counters - we can take a
530permanent reservation on the space, but we still need to make sure we refresh
531the write reservation (the actual space available to the transaction) after
532every checkpoint transaction completion. Unfortunately, if this space is not
533available when required, then the regrant code will sleep waiting for it.
534
535The problem with this is that it can lead to deadlocks as we may need to commit
536checkpoints to be able to free up log space (refer back to the description of
537rolling transactions for an example of this).  Hence we *must* always have
538space available in the log if we are to use static reservations, and that is
539very difficult and complex to arrange. It is possible to do, but there is a
540simpler way.
541
542The simpler way of doing this is tracking the entire log space used by the
543items in the CIL and using this to dynamically calculate the amount of log
544space required by the log metadata. If this log metadata space changes as a
545result of a transaction commit inserting a new memory buffer into the CIL, then
546the difference in space required is removed from the transaction that causes
547the change. Transactions at this level will *always* have enough space
548available in their reservation for this as they have already reserved the
549maximal amount of log metadata space they require, and such a delta reservation
550will always be less than or equal to the maximal amount in the reservation.
551
552Hence we can grow the checkpoint transaction reservation dynamically as items
553are added to the CIL and avoid the need for reserving and regranting log space
554up front. This avoids deadlocks and removes a blocking point from the
555checkpoint flush code.
556
557As mentioned early, transactions can't grow to more than half the size of the
558log. Hence as part of the reservation growing, we need to also check the size
559of the reservation against the maximum allowed transaction size. If we reach
560the maximum threshold, we need to push the CIL to the log. This is effectively
561a "background flush" and is done on demand. This is identical to
562a CIL push triggered by a log force, only that there is no waiting for the
563checkpoint commit to complete. This background push is checked and executed by
564transaction commit code.
565
566If the transaction subsystem goes idle while we still have items in the CIL,
567they will be flushed by the periodic log force issued by the xfssyncd. This log
568force will push the CIL to disk, and if the transaction subsystem stays idle,
569allow the idle log to be covered (effectively marked clean) in exactly the same
570manner that is done for the existing logging method. A discussion point is
571whether this log force needs to be done more frequently than the current rate
572which is once every 30s.
573
574
575Delayed Logging: Log Item Pinning
576---------------------------------
577
578Currently log items are pinned during transaction commit while the items are
579still locked. This happens just after the items are formatted, though it could
580be done any time before the items are unlocked. The result of this mechanism is
581that items get pinned once for every transaction that is committed to the log
582buffers. Hence items that are relogged in the log buffers will have a pin count
583for every outstanding transaction they were dirtied in. When each of these
584transactions is completed, they will unpin the item once. As a result, the item
585only becomes unpinned when all the transactions complete and there are no
586pending transactions. Thus the pinning and unpinning of a log item is symmetric
587as there is a 1:1 relationship with transaction commit and log item completion.
588
589For delayed logging, however, we have an asymmetric transaction commit to
590completion relationship. Every time an object is relogged in the CIL it goes
591through the commit process without a corresponding completion being registered.
592That is, we now have a many-to-one relationship between transaction commit and
593log item completion. The result of this is that pinning and unpinning of the
594log items becomes unbalanced if we retain the "pin on transaction commit, unpin
595on transaction completion" model.
596
597To keep pin/unpin symmetry, the algorithm needs to change to a "pin on
598insertion into the CIL, unpin on checkpoint completion". In other words, the
599pinning and unpinning becomes symmetric around a checkpoint context. We have to
600pin the object the first time it is inserted into the CIL - if it is already in
601the CIL during a transaction commit, then we do not pin it again. Because there
602can be multiple outstanding checkpoint contexts, we can still see elevated pin
603counts, but as each checkpoint completes the pin count will retain the correct
604value according to it's context.
605
606Just to make matters more slightly more complex, this checkpoint level context
607for the pin count means that the pinning of an item must take place under the
608CIL commit/flush lock. If we pin the object outside this lock, we cannot
609guarantee which context the pin count is associated with. This is because of
610the fact pinning the item is dependent on whether the item is present in the
611current CIL or not. If we don't pin the CIL first before we check and pin the
612object, we have a race with CIL being flushed between the check and the pin
613(or not pinning, as the case may be). Hence we must hold the CIL flush/commit
614lock to guarantee that we pin the items correctly.
615
616Delayed Logging: Concurrent Scalability
617---------------------------------------
618
619A fundamental requirement for the CIL is that accesses through transaction
620commits must scale to many concurrent commits. The current transaction commit
621code does not break down even when there are transactions coming from 2048
622processors at once. The current transaction code does not go any faster than if
623there was only one CPU using it, but it does not slow down either.
624
625As a result, the delayed logging transaction commit code needs to be designed
626for concurrency from the ground up. It is obvious that there are serialisation
627points in the design - the three important ones are:
628
629	1. Locking out new transaction commits while flushing the CIL
630	2. Adding items to the CIL and updating item space accounting
631	3. Checkpoint commit ordering
632
633Looking at the transaction commit and CIL flushing interactions, it is clear
634that we have a many-to-one interaction here. That is, the only restriction on
635the number of concurrent transactions that can be trying to commit at once is
636the amount of space available in the log for their reservations. The practical
637limit here is in the order of several hundred concurrent transactions for a
638128MB log, which means that it is generally one per CPU in a machine.
639
640The amount of time a transaction commit needs to hold out a flush is a
641relatively long period of time - the pinning of log items needs to be done
642while we are holding out a CIL flush, so at the moment that means it is held
643across the formatting of the objects into memory buffers (i.e. while memcpy()s
644are in progress). Ultimately a two pass algorithm where the formatting is done
645separately to the pinning of objects could be used to reduce the hold time of
646the transaction commit side.
647
648Because of the number of potential transaction commit side holders, the lock
649really needs to be a sleeping lock - if the CIL flush takes the lock, we do not
650want every other CPU in the machine spinning on the CIL lock. Given that
651flushing the CIL could involve walking a list of tens of thousands of log
652items, it will get held for a significant time and so spin contention is a
653significant concern. Preventing lots of CPUs spinning doing nothing is the
654main reason for choosing a sleeping lock even though nothing in either the
655transaction commit or CIL flush side sleeps with the lock held.
656
657It should also be noted that CIL flushing is also a relatively rare operation
658compared to transaction commit for asynchronous transaction workloads - only
659time will tell if using a read-write semaphore for exclusion will limit
660transaction commit concurrency due to cache line bouncing of the lock on the
661read side.
662
663The second serialisation point is on the transaction commit side where items
664are inserted into the CIL. Because transactions can enter this code
665concurrently, the CIL needs to be protected separately from the above
666commit/flush exclusion. It also needs to be an exclusive lock but it is only
667held for a very short time and so a spin lock is appropriate here. It is
668possible that this lock will become a contention point, but given the short
669hold time once per transaction I think that contention is unlikely.
670
671The final serialisation point is the checkpoint commit record ordering code
672that is run as part of the checkpoint commit and log force sequencing. The code
673path that triggers a CIL flush (i.e. whatever triggers the log force) will enter
674an ordering loop after writing all the log vectors into the log buffers but
675before writing the commit record. This loop walks the list of committing
676checkpoints and needs to block waiting for checkpoints to complete their commit
677record write. As a result it needs a lock and a wait variable. Log force
678sequencing also requires the same lock, list walk, and blocking mechanism to
679ensure completion of checkpoints.
680
681These two sequencing operations can use the mechanism even though the
682events they are waiting for are different. The checkpoint commit record
683sequencing needs to wait until checkpoint contexts contain a commit LSN
684(obtained through completion of a commit record write) while log force
685sequencing needs to wait until previous checkpoint contexts are removed from
686the committing list (i.e. they've completed). A simple wait variable and
687broadcast wakeups (thundering herds) has been used to implement these two
688serialisation queues. They use the same lock as the CIL, too. If we see too
689much contention on the CIL lock, or too many context switches as a result of
690the broadcast wakeups these operations can be put under a new spinlock and
691given separate wait lists to reduce lock contention and the number of processes
692woken by the wrong event.
693
694
695Lifecycle Changes
696-----------------
697
698The existing log item life cycle is as follows::
699
700	1. Transaction allocate
701	2. Transaction reserve
702	3. Lock item
703	4. Join item to transaction
704		If not already attached,
705			Allocate log item
706			Attach log item to owner item
707		Attach log item to transaction
708	5. Modify item
709		Record modifications in log item
710	6. Transaction commit
711		Pin item in memory
712		Format item into log buffer
713		Write commit LSN into transaction
714		Unlock item
715		Attach transaction to log buffer
716
717	<log buffer IO dispatched>
718	<log buffer IO completes>
719
720	7. Transaction completion
721		Mark log item committed
722		Insert log item into AIL
723			Write commit LSN into log item
724		Unpin log item
725	8. AIL traversal
726		Lock item
727		Mark log item clean
728		Flush item to disk
729
730	<item IO completion>
731
732	9. Log item removed from AIL
733		Moves log tail
734		Item unlocked
735
736Essentially, steps 1-6 operate independently from step 7, which is also
737independent of steps 8-9. An item can be locked in steps 1-6 or steps 8-9
738at the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur
739at the same time. If the log item is in the AIL or between steps 6 and 7
740and steps 1-6 are re-entered, then the item is relogged. Only when steps 8-9
741are entered and completed is the object considered clean.
742
743With delayed logging, there are new steps inserted into the life cycle::
744
745	1. Transaction allocate
746	2. Transaction reserve
747	3. Lock item
748	4. Join item to transaction
749		If not already attached,
750			Allocate log item
751			Attach log item to owner item
752		Attach log item to transaction
753	5. Modify item
754		Record modifications in log item
755	6. Transaction commit
756		Pin item in memory if not pinned in CIL
757		Format item into log vector + buffer
758		Attach log vector and buffer to log item
759		Insert log item into CIL
760		Write CIL context sequence into transaction
761		Unlock item
762
763	<next log force>
764
765	7. CIL push
766		lock CIL flush
767		Chain log vectors and buffers together
768		Remove items from CIL
769		unlock CIL flush
770		write log vectors into log
771		sequence commit records
772		attach checkpoint context to log buffer
773
774	<log buffer IO dispatched>
775	<log buffer IO completes>
776
777	8. Checkpoint completion
778		Mark log item committed
779		Insert item into AIL
780			Write commit LSN into log item
781		Unpin log item
782	9. AIL traversal
783		Lock item
784		Mark log item clean
785		Flush item to disk
786	<item IO completion>
787	10. Log item removed from AIL
788		Moves log tail
789		Item unlocked
790
791From this, it can be seen that the only life cycle differences between the two
792logging methods are in the middle of the life cycle - they still have the same
793beginning and end and execution constraints. The only differences are in the
794committing of the log items to the log itself and the completion processing.
795Hence delayed logging should not introduce any constraints on log item
796behaviour, allocation or freeing that don't already exist.
797
798As a result of this zero-impact "insertion" of delayed logging infrastructure
799and the design of the internal structures to avoid on disk format changes, we
800can basically switch between delayed logging and the existing mechanism with a
801mount option. Fundamentally, there is no reason why the log manager would not
802be able to swap methods automatically and transparently depending on load
803characteristics, but this should not be necessary if delayed logging works as
804designed.