1088 lines · plain
1.. SPDX-License-Identifier: GPL-2.02 3==================4XFS Logging Design5==================6 7Preamble8========9 10This document describes the design and algorithms that the XFS journalling11subsystem is based on. This document describes the design and algorithms that12the XFS journalling subsystem is based on so that readers may familiarize13themselves with the general concepts of how transaction processing in XFS works.14 15We begin with an overview of transactions in XFS, followed by describing how16transaction reservations are structured and accounted, and then move into how we17guarantee forwards progress for long running transactions with finite initial18reservations bounds. At this point we need to explain how relogging works. With19the basic concepts covered, the design of the delayed logging mechanism is20documented.21 22 23Introduction24============25 26XFS uses Write Ahead Logging for ensuring changes to the filesystem metadata27are atomic and recoverable. For reasons of space and time efficiency, the28logging mechanisms are varied and complex, combining intents, logical and29physical logging mechanisms to provide the necessary recovery guarantees the30filesystem requires.31 32Some objects, such as inodes and dquots, are logged in logical format where the33details logged are made up of the changes to in-core structures rather than34on-disk structures. Other objects - typically buffers - have their physical35changes logged. Long running atomic modifications have individual changes36chained together by intents, ensuring that journal recovery can restart and37finish an operation that was only partially done when the system stopped38functioning.39 40The reason for these differences is to keep the amount of log space and CPU time41required to process objects being modified as small as possible and hence the42logging overhead as low as possible. Some items are very frequently modified,43and some parts of objects are more frequently modified than others, so keeping44the overhead of metadata logging low is of prime importance.45 46The method used to log an item or chain modifications together isn't47particularly important in the scope of this document. It suffices to know that48the method used for logging a particular object or chaining modifications49together are different and are dependent on the object and/or modification being50performed. The logging subsystem only cares that certain specific rules are51followed to guarantee forwards progress and prevent deadlocks.52 53 54Transactions in XFS55===================56 57XFS has two types of high level transactions, defined by the type of log space58reservation they take. These are known as "one shot" and "permanent"59transactions. Permanent transaction reservations can take reservations that span60commit boundaries, whilst "one shot" transactions are for a single atomic61modification.62 63The type and size of reservation must be matched to the modification taking64place. This means that permanent transactions can be used for one-shot65modifications, but one-shot reservations cannot be used for permanent66transactions.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 are77tracked via the transaction handle. Once the transaction is committed, all78resources joined to it are released, along with the remaining unused reservation79space that was taken at the transaction allocation time.80 81In contrast, a permanent transaction is made up of multiple linked individual82transactions, 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 important98difference: xfs_trans_roll() performs a specific operation that links two99transactions 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 locked106across the entire chain of transactions. Hence while this series of rolling107transactions is running, nothing else can read from or write to the inode and108this provides a mechanism for complex changes to appear atomic from an external109observer's point of view.110 111It is important to note that a series of rolling transactions in a permanent112transaction does not form an atomic change in the journal. While each113individual modification is atomic, the chain is *not atomic*. If we crash half114way through, then recovery will only replay up to the last transactional115modification the loop made that was committed to the journal.116 117This affects long running permanent transactions in that it is not possible to118predict how much of a long running operation will actually be recovered because119there is no guarantee of how much of the operation reached stale storage. Hence120if a long running operation requires multiple transactions to fully complete,121the high level operation must use intents and deferred operations to guarantee122recovery can complete the operation once the first transactions is persisted in123the on-disk journal.124 125 126Transactions are Asynchronous127=============================128 129In XFS, all high level transactions are asynchronous by default. This means that130xfs_trans_commit() does not guarantee that the modification has been committed131to stable storage when it returns. Hence when a system crashes, not all the132completed transactions will be replayed during recovery.133 134However, the logging subsystem does provide global ordering guarantees, such135that if a specific change is seen after recovery, all metadata modifications136that were committed prior to that change will also be seen.137 138For single shot operations that need to reach stable storage immediately, or139ensuring that a long running permanent transaction is fully committed once it is140complete, we can explicitly tag a transaction as synchronous. This will trigger141a "log force" to flush the outstanding committed transactions to stable storage142in the journal and wait for that to complete.143 144Synchronous transactions are rarely used, however, because they limit logging145throughput to the IO latency limitations of the underlying storage. Instead, we146tend to use log forces to ensure modifications are on stable storage only when147a user operation requires a synchronisation point to occur (e.g. fsync).148 149 150Transaction Reservations151========================152 153It has been mentioned a number of times now that the logging subsystem needs to154provide a forwards progress guarantee so that no modification ever stalls155because it can't be written to the journal due to a lack of space in the156journal. This is achieved by the transaction reservations that are made when157a transaction is first allocated. For permanent transactions, these reservations158are maintained as part of the transaction rolling mechanism.159 160A transaction reservation provides a guarantee that there is physical log space161available to write the modification into the journal before we start making162modifications to objects and items. As such, the reservation needs to be large163enough to take into account the amount of metadata that the change might need to164log in the worst case. This means that if we are modifying a btree in the165transaction, we have to reserve enough space to record a full leaf-to-root split166of the btree. As such, the reservations are quite complex because we have to167take into account all the hidden changes that might occur.168 169For example, a user data extent allocation involves allocating an extent from170free space, which modifies the free space trees. That's two btrees. Inserting171the extent into the inode's extent map might require a split of the extent map172btree, which requires another allocation that can modify the free space trees173again. Then we might have to update reverse mappings, which modifies yet174another btree which might require more space. And so on. Hence the amount of175metadata 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 the179log has this much space available before the transaction is allowed to proceed180so that when we come to write the dirty metadata into the log we don't run out181of log space half way through the write.182 183For one-shot transactions, a single unit space reservation is all that is184required for the transaction to proceed. For permanent transactions, however, we185also have a "log count" that affects the size of the reservation that is to be186made.187 188While a permanent transaction can get by with a single unit of space189reservation, it is somewhat inefficient to do this as it requires the190transaction rolling mechanism to re-reserve space on every transaction roll. We191know from the implementation of the permanent transactions how many transaction192rolls are likely for the common modifications that need to be made.193 194For example, an inode allocation is typically two transactions - one to195physically allocate a free inode chunk on disk, and another to allocate an inode196from an inode chunk that has free inodes in it. Hence for an inode allocation197transaction, we might set the reservation log count to a value of 2 to indicate198that the common/fast path transaction will commit two linked transactions in a199chain. Each time a permanent transaction rolls, it consumes an entire unit200reservation.201 202Hence when the permanent transaction is first allocated, the log space203reservation is increased from a single unit reservation to multiple unit204reservations. That multiple is defined by the reservation log count, and this205means we can roll the transaction multiple times before we have to re-reserve206log space when we roll the transaction. This ensures that the common207modifications we make only need to reserve log space once.208 209If the log count for a permanent transaction reaches zero, then it needs to210re-reserve physical space in the log. This is somewhat complex, and requires211an understanding of how the log accounts for space that has been reserved.212 213 214Log Space Accounting215====================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 combination219of a cycle number - the number of times the log has been overwritten - and the220offset into the log. A LSN carries the cycle in the upper 32 bits and the221offset in the lower 32 bits. The offset is in units of "basic blocks" (512222bytes). Hence we can do realtively simple LSN based math to keep track of223available space in the log.224 225Log space accounting is done via a pair of constructs called "grant heads". The226position of the grant heads is an absolute value, so the amount of space227available in the log is defined by the distance between the position of the228grant head and the current log tail. That is, how much space can be229reserved/consumed before the grant heads would fully wrap the log and overtake230the tail position.231 232The first grant head is the "reserve" head. This tracks the byte count of the233reservations currently held by active transactions. It is a purely in-memory234accounting of the space reservation and, as such, actually tracks byte offsets235into the log rather than basic blocks. Hence it technically isn't using LSNs to236represent 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 transaction240reservations amounts and the exact byte count that modifications actually make241and need to write into the log. The reserve head is used to prevent new242transactions from taking new reservations when the head reaches the current243tail. It will block new reservations in a FIFO queue and as the log tail moves244forward it will wake them in order once sufficient space is available. This FIFO245mechanism ensures no transaction is starved of resources when log space246shortages occur.247 248The other grant head is the "write" head. Unlike the reserve head, this grant249head contains an LSN and it tracks the physical space usage in the log. While250this might sound like it is accounting the same state as the reserve grant head251- and it mostly does track exactly the same location as the reserve grant head -252there are critical differences in behaviour between them that provides the253forwards progress guarantees that rolling permanent transactions require.254 255These differences when a permanent transaction is rolled and the internal "log256count" reaches zero and the initial set of unit reservations have been257exhausted. At this point, we still require a log space reservation to continue258the next transaction in the sequeunce, but we have none remaining. We cannot259sleep during the transaction commit process waiting for new log space to become260available, as we may end up on the end of the FIFO queue and the items we have261locked while we sleep could end up pinning the tail of the log before there is262enough free space in the log to fulfill all of the pending reservations and263then wake up transaction commit in progress.264 265To take a new reservation without sleeping requires us to be able to take a266reservation even if there is no reservation space currently available. That is,267we need to be able to *overcommit* the log reservation space. As has already268been detailed, we cannot overcommit physical log space. However, the reserve269grant head does not track physical space - it only accounts for the amount of270reservations we currently have outstanding. Hence if the reserve head passes271over the tail of the log all it means is that new reservations will be throttled272immediately and remain throttled until the log tail is moved forward far enough273to remove the overcommit and start taking new reservations. In other words, we274can overcommit the reserve head without violating the physical log head and tail275rules.276 277As a result, permanent transactions only "regrant" reservation space during278xfs_trans_commit() calls, while the physical log space reservation - tracked by279the 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 for281physical log space to be reserved from the write grant head, but only if one282critical rule has been observed::283 284 Code using permanent reservations must always log the items they hold285 locked across each transaction they roll in the chain.286 287"Re-logging" the locked items on every transaction roll ensures that the items288attached to the transaction chain being rolled are always relocated to the289physical head of the log and so do not pin the tail of the log. If a locked item290pins the tail of the log when we sleep on the write reservation, then we will291deadlock the log as we cannot take the locks needed to write back that item and292move the tail of the log forwards to free up write grant space. Re-logging the293locked items avoids this deadlock and guarantees that the log reservation we are294making cannot self-deadlock.295 296If all rolling transactions obey this rule, then they can all make forwards297progress independently because nothing will block the progress of the log298tail moving forwards and hence ensuring that write grant space is always299(eventually) made available to permanent transactions no matter how many times300they roll.301 302 303Re-logging Explained304====================305 306XFS allows multiple separate modifications to a single object to be carried in307the log at any given time. This allows the log to avoid needing to flush each308change to disk before recording a new change to the object. XFS does this via a309method called "re-logging". Conceptually, this is quite simple - all it requires310is that any new change to the object is recorded with a *new copy* of all the311existing 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 was314written to disk after change D, we would see in the log the following series315of transactions, their contents and the log sequence number (LSN) of the316transaction::317 318 Transaction Contents LSN319 A A X320 B A+B X+n321 C A+B+C X+n+m322 D A+B+C+D X+n+m+o323 <object written to disk>324 E E Y (> X+n+m+o)325 F E+F Y+p326 327In other words, each time an object is relogged, the new transaction contains328the 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 that331an object being relogged does not prevent the tail of the log from ever moving332forward. This can be seen in the table above by the changing (increasing) LSN333of each subsequent transaction, and it's the technique that allows us to334implement long-running, multiple-commit permanent transactions. 335 336A typical example of a rolling transaction is the removal of extents from an337inode which can only be done at a rate of two extents per transaction because338of reservation size limitations. Hence a rolling extent removal transaction339keeps relogging the inode and btree buffers as they get modified in each340removal operation. This keeps them moving forward in the log as the operation341progresses, ensuring that current operation never gets blocked by itself if the342log wraps around.343 344Hence it can be seen that the relogging operation is fundamental to the correct345working of the XFS journalling subsystem. From the above description, most346people should be able to see why the XFS metadata operations writes so much to347the log - repeated operations to the same objects write the same changes to348the log over and over again. Worse is the fact that objects tend to get349dirtier as they get relogged, so each subsequent transaction is writing more350metadata into the log.351 352It should now also be obvious how relogging and asynchronous transactions go353hand in hand. That is, transactions don't get written to the physical journal354until either a log buffer is filled (a log buffer can hold multiple355transactions) or a synchronous operation forces the log buffers holding the356transactions to disk. This means that XFS is doing aggregation of transactions357in memory - batching them, if you like - to minimise the impact of the log IO on358transaction throughput.359 360The limitation on asynchronous transaction throughput is the number and size of361log buffers made available by the log manager. By default there are 8 log362buffers available and the size of each is 32kB - the size can be increased up363to 256kB by use of a mount option.364 365Effectively, this gives us the maximum bound of outstanding metadata changes366that can be made to the filesystem at any point in time - if all the log367buffers are full and under IO, then no more transactions can be committed until368the current batch completes. It is now common for a single current CPU core to369be to able to issue enough transactions to keep the log buffers full and under370IO permanently. Hence the XFS journalling subsystem can be considered to be IO371bound.372 373Delayed Logging: Concepts374=========================375 376The key thing to note about the asynchronous logging combined with the377relogging technique XFS uses is that we can be relogging changed objects378multiple times before they are committed to disk in the log buffers. If we379return to the previous relogging example, it is entirely possible that380transactions 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 it384contains all the changes from the previous changes. In other words, we have one385necessary copy in the log buffer, and three stale copies that are simply386wasting space. When we are doing repeated operations on the same set of387objects, these "stale objects" can be over 90% of the space used in the log388buffers. It is clear that reducing the number of stale objects written to the389log would greatly reduce the amount of metadata we write to the log, and this390is the fundamental goal of delayed logging.391 392From a conceptual point of view, XFS is already doing relogging in memory (where393memory == log buffer), only it is doing it extremely inefficiently. It is using394logical to physical formatting to do the relogging because there is no395infrastructure to keep track of logical changes in memory prior to physically396formatting the changes in a transaction to the log buffer. Hence we cannot avoid397accumulating stale objects in the log buffers.398 399Delayed logging is the name we've given to keeping and tracking transactional400changes to objects in memory outside the log buffer infrastructure. Because of401the relogging concept fundamental to the XFS journalling subsystem, this is402actually relatively easy to do - all the changes to logged items are already403tracked in the current infrastructure. The big problem is how to accumulate404them and get them to the log in a consistent, recoverable manner.405Describing the problems and how they have been solved is the focus of this406document.407 408One of the key changes that delayed logging makes to the operation of the409journalling subsystem is that it disassociates the amount of outstanding410metadata changes from the size and number of log buffers available. In other411words, instead of there only being a maximum of 2MB of transaction changes not412written to the log at any point in time, there may be a much greater amount413being accumulated in memory. Hence the potential for loss of metadata on a414crash is much greater than for the existing logging mechanism.415 416It should be noted that this does not change the guarantee that log recovery417will result in a consistent filesystem. What it does mean is that as far as the418recovered filesystem is concerned, there may be many thousands of transactions419that simply did not occur as a result of the crash. This makes it even more420important that applications that care about their data use fsync() where they421need to ensure application level data integrity is maintained.422 423It should be noted that delayed logging is not an innovative new concept that424warrants rigorous proofs to determine whether it is correct or not. The method425of accumulating changes in memory for some period before writing them to the426log is used effectively in many filesystems including ext3 and ext4. Hence427no time is spent in this document trying to convince the reader that the428concept is sound. Instead it is simply considered a "solved problem" and as429such 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 least434 an order of magnitude.435 2. Supply sufficient statistics to validate Requirement #1.436 3. Supply sufficient new tracing infrastructure to be able to debug437 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: Design443=======================444 445Storing Changes446---------------447 448The problem with accumulating changes at a logical level (i.e. just using the449existing log item dirty region tracking) is that when it comes to writing the450changes to the log buffers, we need to ensure that the object we are formatting451is not changing while we do this. This requires locking the object to prevent452concurrent modification. Hence flushing the logical changes to the log would453require us to lock every object, format them, and then unlock them again.454 455This introduces lots of scope for deadlocks with transactions that are already456running. For example, a transaction has object A locked and modified, but needs457the delayed logging tracking lock to commit the transaction. However, the458flushing thread has the delayed logging tracking lock already held, and is459trying to get the lock on object A to flush it to the log buffer. This appears460to be an unsolvable deadlock condition, and it was solving this problem that461was 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 an465vector array that points to the changed regions in the item. The log write code466simply copies the memory these vectors point to into the log buffer during467transaction commit while the item is locked in the transaction. Instead of468using the log buffer as the destination of the formatting code, we can use an469allocated memory buffer big enough to fit the formatted vector.470 471If we then copy the vector into the memory buffer and rewrite the vector to472point to the memory buffer rather than the object itself, we now have a copy of473the 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 and475rewriting can all be done while the object is locked during transaction commit,476resulting in a vector that is transactionally consistent and can be accessed477without needing to lock the owning item.478 479Hence we avoid the need to lock items when we need to flush outstanding480asynchronous transactions to the log. The differences between the existing481formatting method and the delayed logging formatting can be seen in the482diagram 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 is511relogged we can replace the current memory buffer with a new memory buffer that512contains the latest changes.513 514The reason for keeping the vector around after we've formatted the memory515buffer 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 boundaries517are in the item, so we'd need a new encapsulation method for regions in the log518buffer writing (i.e. double encapsulation). This would be an on-disk format519change and as such is not desirable. It also means we'd have to write the log520region headers in the formatting stage, which is problematic as there is per521region 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 and524rewriting the vector addresses to point at the memory buffer we end up with a525self-describing object that can be passed to the log buffer write code to be526handled 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 been528relogged in memory.529 530 531Tracking Changes532----------------533 534Now that we can record transactional changes in memory in a form that allows535them to be used without limitations, we need to be able to track and accumulate536them so that they can be written to the log at some later point in time. The537log item is the natural place to store this vector and buffer, and also makes sense538to be the object that is used to track committed objects as it will always539exist 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 to542the 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-ordered544double linked list. Items are inserted into this list during log buffer IO545completion, after which they are unpinned and can be written to disk. An object546that is in the AIL can be relogged, which causes the object to be pinned again547and then moved forward in the AIL when the log buffer IO completes for that548transaction.549 550Essentially, this shows that an item that is in the AIL can still be modified551and relogged, so any tracking must be separate to the AIL infrastructure. As552such, we cannot reuse the AIL list pointers for tracking committed items, nor553can we store state in any field that is protected by the AIL lock. Hence the554committed item tracking needs its own locks, lists and state fields in the log555item.556 557Similar to the AIL, tracking of committed items is done through a new list558called the Committed Item List (CIL). The list tracks log items that have been559committed and have formatted memory buffers attached to them. It tracks objects560in transaction commit order, so when an object is relogged it is removed from561its place in the list and re-inserted at the tail. This is entirely arbitrary562and done to make it easy for debugging - the last items in the list are the563ones that are most recently modified. Ordering of the CIL is not necessary for564transactional integrity (as discussed in the next section) so the ordering is565done for convenience/sanity of the developers.566 567 568Delayed Logging: Checkpoints569----------------------------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 they574need to be written as an atomic transaction. The need for all the objects to be575written as an atomic transaction comes from the requirements of relogging and576log replay - all the changes in all the objects in a given transaction must577either be completely replayed during log recovery, or not replayed at all. If578a transaction is not replayed because it is not complete in the log, then579no later transactions should be replayed, either.580 581To fulfill this requirement, we need to write the entire CIL in a single log582transaction. Fortunately, the XFS log code has no fixed limit on the size of a583transaction, nor does the log replay code. The only fundamental limit is that584the transaction cannot be larger than just under half the size of the log. The585reason for this limit is that to find the head and tail of the log, there must586be at least one complete transaction in the log at any given time. If a587transaction is larger than half the log, then there is the possibility that a588crash during the write of a such a transaction could partially overwrite the589only complete previous transaction in the log. This will result in a recovery590failure and an inconsistent filesystem and hence we must enforce the maximum591size of a checkpoint to be slightly less than a half the log.592 593Apart from this size requirement, a checkpoint transaction looks no different594to any other transaction - it contains a transaction header, a series of595formatted log items and a commit record at the tail. From a recovery596perspective, the checkpoint transaction is also no different - just a lot597bigger with a lot more items in it. The worst case effect of this is that we598might need to tune the recovery transaction object hash size.599 600Because the checkpoint is just another transaction and all the changes to log601items are stored as log vectors, we can use the existing log buffer writing602code to write the changes into the log. To do this efficiently, we need to603minimise the time we hold the CIL locked while writing the checkpoint604transaction. The current log write code enables us to do this easily with the605way it separates the writing of the transaction contents (the log vectors) from606the transaction commit record, but tracking this requires us to have a607per-checkpoint context that travels through the log write process through to608checkpoint completion.609 610Hence a checkpoint has a context that tracks the state of the current611checkpoint from initiation to checkpoint completion. A new context is initiated612at the same time a checkpoint transaction is started. That is, when we remove613all the current items from the CIL during a checkpoint operation, we move all614those changes into the current checkpoint context. We then initialise a new615context and attach that to the CIL for aggregation of new transactions.616 617This allows us to unlock the CIL immediately after transfer of all the618committed items and effectively allows new transactions to be issued while we619are formatting the checkpoint into the log. It also allows concurrent620checkpoints to be written into the log buffers in the case of log force heavy621workloads, just like the existing transaction commit code does. This, however,622requires that we strictly order the commit records in the log so that623checkpoint sequence order is maintained during log replay.624 625To ensure that we can be writing an item into a checkpoint transaction at626the same time another transaction modifies the item and inserts the log item627into the new CIL, then checkpoint transaction commit code cannot use log items628to 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 be630detached from the log items. That is, when the CIL is flushed the memory631buffer and log vector attached to each log item needs to be attached to the632checkpoint context so that the log item can be released. In diagrammatic form,633the CIL would look like this before the flush::634 635 CIL Head636 |637 V638 Log Item <-> log vector 1 -> memory buffer639 | -> vector array640 V641 Log Item <-> log vector 2 -> memory buffer642 | -> vector array643 V644 ......645 |646 V647 Log Item <-> log vector N-1 -> memory buffer648 | -> vector array649 V650 Log Item <-> log vector N -> memory buffer651 -> vector array652 653And after the flush the CIL head is empty, and the checkpoint context log654vector list would look like::655 656 Checkpoint Context657 |658 V659 log vector 1 -> memory buffer660 | -> vector array661 | -> Log Item662 V663 log vector 2 -> memory buffer664 | -> vector array665 | -> Log Item666 V667 ......668 |669 V670 log vector N-1 -> memory buffer671 | -> vector array672 | -> Log Item673 V674 log vector N -> memory buffer675 -> vector array676 -> Log Item677 678Once this transfer is done, the CIL can be unlocked and new transactions can679start, while the checkpoint flush code works over the log vector chain to680commit the checkpoint.681 682Once the checkpoint is written into the log buffers, the checkpoint context is683attached to the log buffer that the commit record was written to along with a684completion callback. Log IO completion will call that callback, which can then685run transaction committed processing for the log items (i.e. insert into AIL686and unpin) in the log vector chain and then free the log vector chain and687checkpoint context.688 689Discussion Point: I am uncertain as to whether the log item is the most690efficient way to track vectors, even though it seems like the natural way to do691it. The fact that we walk the log items (in the CIL) just to chain the log692vectors and break the link between the log item and the log vector means that693we take a cache line hit for the log item list modification, then another for694the log vector chaining. If we track by the log vectors, then we only need to695break the link between the log item and the log vector, which means we should696dirty only the log item cachelines. Normally I wouldn't be concerned about one697vs two dirty cachelines except for the fact I've seen upwards of 80,000 log698vectors in one checkpoint transaction. I'd guess this is a "measure and699compare" situation that can be done after a working and reviewed implementation700is in the dev tree....701 702Delayed Logging: Checkpoint Sequencing703--------------------------------------704 705One of the key aspects of the XFS transaction subsystem is that it tags706committed transactions with the log sequence number of the transaction commit.707This allows transactions to be issued asynchronously even though there may be708future operations that cannot be completed until that transaction is fully709committed 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 log711force 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 the714transaction. This LSN comes directly from the log buffer the transaction is715written into. While this works just fine for the existing transaction716mechanism, it does not work for delayed logging because transactions are not717written directly into the log buffers. Hence some other method of sequencing718transactions is required.719 720As discussed in the checkpoint section, delayed logging uses per-checkpoint721contexts, and as such it is simple to assign a sequence number to each722checkpoint. Because the switching of checkpoint contexts must be done723atomically, it is simple to ensure that each new context has a monotonically724increasing sequence number assigned to it without the need for an external725atomic counter - we can just take the current context sequence number and add726one to it for the new context.727 728Then, instead of assigning a log buffer LSN to the transaction commit LSN729during the commit, we can assign the current checkpoint sequence. This allows730operations that track transactions that have not yet completed know what731checkpoint sequence needs to be committed before they can continue. As a732result, the code that forces the log to a specific LSN now needs to ensure that733the log forces to a specific checkpoint.734 735To ensure that we can do this, we need to track all the checkpoint contexts736that are currently committing to the log. When we flush a checkpoint, the737context gets added to a "committing" list which can be searched. When a738checkpoint commit completes, it is removed from the committing list. Because739the 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, thereby741using the existing log force mechanisms to execute synchronous forces.742 743It should be noted that the synchronous forces may need to be extended with744mitigation algorithms similar to the current log buffer code to allow745aggregation of multiple synchronous transactions if there are already746synchronous transactions being flushed. Investigation of the performance of the747current design is needed before making any decisions here.748 749The main concern with log forces is to ensure that all the previous checkpoints750are also committed to disk before the one we need to wait for. Therefore we751need to check that all the prior contexts in the committing list are also752complete before waiting on the one we need to complete. We do this753synchronisation in the log force code so that we don't need to wait anywhere754else 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 the757case where the forcing sequence number is the same as the current context. That758is, we need to flush the CIL and potentially wait for it to complete. This is a759simple addition to the existing log forcing code to check the sequence numbers760and push if required. Indeed, placing the current sequence checkpoint flush in761the log force code enables the current mechanism for issuing synchronous762transactions to remain untouched (i.e. commit an asynchronous transaction, then763force the log at the LSN of that transaction) and so the higher level code764behaves the same regardless of whether delayed logging is being used or not.765 766Delayed Logging: Checkpoint Log Space Accounting767------------------------------------------------768 769The big issue for a checkpoint transaction is the log space reservation for the770transaction. We don't know how big a checkpoint transaction is going to be771ahead of time, nor how many log buffers it will take to write out, nor the772number of split log vector regions are going to be used. We can track the773amount of log space required as we add items to the commit item list, but we774still 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 space777usage 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 the780transaction. While some of this is fixed overhead, much of it is dependent on781the size of the transaction and the number of regions being logged (the number782of log vectors in the transaction).783 784An example of the differences would be logging directory changes versus logging785inode changes. If you modify lots of inode cores (e.g. ``chmod -R g+w *``), then786there are lots of transactions that only contain an inode core and an inode log787format structure. That is, two vectors totaling roughly 150 bytes. If we modify78810,000 inodes, we have about 1.5MB of metadata to write in 20,000 vectors. Each789vector is 12 bytes, so the total to be logged is approximately 1.75MB. In790comparison, if we are logging full directory buffers, they are typically 4KB791each, so we in 1.5MB of directory buffers we'd have roughly 400 buffers and a792buffer format structure for each buffer - roughly 800 vectors or 1.51MB total793space. From this, it should be obvious that a static log space reservation is794not particularly flexible and is difficult to select the "optimal value" for795all workloads.796 797Further, if we are going to use a static reservation, which bit of the entire798reservation does it cover? We account for space used by the transaction799reservation by tracking the space currently used by the object in the CIL and800then calculating the increase or decrease in space used as the object is801relogged. This allows for a checkpoint reservation to only have to account for802log buffer metadata used such as log header records.803 804However, even using a static reservation for just the log metadata is805problematic. Typically log record headers use at least 16KB of log space per8061MB of log space consumed (512 bytes per 32k) and the reservation needs to be807large enough to handle arbitrary sized checkpoint transactions. This808reservation needs to be made before the checkpoint is started, and we need to809be able to reserve the space without sleeping. For a 8MB checkpoint, we need a810reservation 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 a813permanent reservation on the space, but we still need to make sure we refresh814the write reservation (the actual space available to the transaction) after815every checkpoint transaction completion. Unfortunately, if this space is not816available 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 commit819checkpoints to be able to free up log space (refer back to the description of820rolling transactions for an example of this). Hence we *must* always have821space available in the log if we are to use static reservations, and that is822very difficult and complex to arrange. It is possible to do, but there is a823simpler way.824 825The simpler way of doing this is tracking the entire log space used by the826items in the CIL and using this to dynamically calculate the amount of log827space required by the log metadata. If this log metadata space changes as a828result of a transaction commit inserting a new memory buffer into the CIL, then829the difference in space required is removed from the transaction that causes830the change. Transactions at this level will *always* have enough space831available in their reservation for this as they have already reserved the832maximal amount of log metadata space they require, and such a delta reservation833will always be less than or equal to the maximal amount in the reservation.834 835Hence we can grow the checkpoint transaction reservation dynamically as items836are added to the CIL and avoid the need for reserving and regranting log space837up front. This avoids deadlocks and removes a blocking point from the838checkpoint flush code.839 840As mentioned early, transactions can't grow to more than half the size of the841log. Hence as part of the reservation growing, we need to also check the size842of the reservation against the maximum allowed transaction size. If we reach843the maximum threshold, we need to push the CIL to the log. This is effectively844a "background flush" and is done on demand. This is identical to845a CIL push triggered by a log force, only that there is no waiting for the846checkpoint commit to complete. This background push is checked and executed by847transaction 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 log851force 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 same853manner that is done for the existing logging method. A discussion point is854whether this log force needs to be done more frequently than the current rate855which is once every 30s.856 857 858Delayed Logging: Log Item Pinning859---------------------------------860 861Currently log items are pinned during transaction commit while the items are862still locked. This happens just after the items are formatted, though it could863be done any time before the items are unlocked. The result of this mechanism is864that items get pinned once for every transaction that is committed to the log865buffers. Hence items that are relogged in the log buffers will have a pin count866for every outstanding transaction they were dirtied in. When each of these867transactions is completed, they will unpin the item once. As a result, the item868only becomes unpinned when all the transactions complete and there are no869pending transactions. Thus the pinning and unpinning of a log item is symmetric870as there is a 1:1 relationship with transaction commit and log item completion.871 872For delayed logging, however, we have an asymmetric transaction commit to873completion relationship. Every time an object is relogged in the CIL it goes874through the commit process without a corresponding completion being registered.875That is, we now have a many-to-one relationship between transaction commit and876log item completion. The result of this is that pinning and unpinning of the877log items becomes unbalanced if we retain the "pin on transaction commit, unpin878on transaction completion" model.879 880To keep pin/unpin symmetry, the algorithm needs to change to a "pin on881insertion into the CIL, unpin on checkpoint completion". In other words, the882pinning and unpinning becomes symmetric around a checkpoint context. We have to883pin the object the first time it is inserted into the CIL - if it is already in884the CIL during a transaction commit, then we do not pin it again. Because there885can be multiple outstanding checkpoint contexts, we can still see elevated pin886counts, but as each checkpoint completes the pin count will retain the correct887value according to its context.888 889Just to make matters slightly more complex, this checkpoint level context890for the pin count means that the pinning of an item must take place under the891CIL commit/flush lock. If we pin the object outside this lock, we cannot892guarantee which context the pin count is associated with. This is because of893the fact pinning the item is dependent on whether the item is present in the894current CIL or not. If we don't pin the CIL first before we check and pin the895object, we have a race with CIL being flushed between the check and the pin896(or not pinning, as the case may be). Hence we must hold the CIL flush/commit897lock to guarantee that we pin the items correctly.898 899Delayed Logging: Concurrent Scalability900---------------------------------------901 902A fundamental requirement for the CIL is that accesses through transaction903commits must scale to many concurrent commits. The current transaction commit904code does not break down even when there are transactions coming from 2048905processors at once. The current transaction code does not go any faster than if906there 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 designed909for concurrency from the ground up. It is obvious that there are serialisation910points in the design - the three important ones are:911 912 1. Locking out new transaction commits while flushing the CIL913 2. Adding items to the CIL and updating item space accounting914 3. Checkpoint commit ordering915 916Looking at the transaction commit and CIL flushing interactions, it is clear917that we have a many-to-one interaction here. That is, the only restriction on918the number of concurrent transactions that can be trying to commit at once is919the amount of space available in the log for their reservations. The practical920limit here is in the order of several hundred concurrent transactions for a921128MB 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 a924relatively long period of time - the pinning of log items needs to be done925while we are holding out a CIL flush, so at the moment that means it is held926across the formatting of the objects into memory buffers (i.e. while memcpy()s927are in progress). Ultimately a two pass algorithm where the formatting is done928separately to the pinning of objects could be used to reduce the hold time of929the transaction commit side.930 931Because of the number of potential transaction commit side holders, the lock932really needs to be a sleeping lock - if the CIL flush takes the lock, we do not933want every other CPU in the machine spinning on the CIL lock. Given that934flushing the CIL could involve walking a list of tens of thousands of log935items, it will get held for a significant time and so spin contention is a936significant concern. Preventing lots of CPUs spinning doing nothing is the937main reason for choosing a sleeping lock even though nothing in either the938transaction commit or CIL flush side sleeps with the lock held.939 940It should also be noted that CIL flushing is also a relatively rare operation941compared to transaction commit for asynchronous transaction workloads - only942time will tell if using a read-write semaphore for exclusion will limit943transaction commit concurrency due to cache line bouncing of the lock on the944read side.945 946The second serialisation point is on the transaction commit side where items947are inserted into the CIL. Because transactions can enter this code948concurrently, the CIL needs to be protected separately from the above949commit/flush exclusion. It also needs to be an exclusive lock but it is only950held for a very short time and so a spin lock is appropriate here. It is951possible that this lock will become a contention point, but given the short952hold time once per transaction I think that contention is unlikely.953 954The final serialisation point is the checkpoint commit record ordering code955that is run as part of the checkpoint commit and log force sequencing. The code956path that triggers a CIL flush (i.e. whatever triggers the log force) will enter957an ordering loop after writing all the log vectors into the log buffers but958before writing the commit record. This loop walks the list of committing959checkpoints and needs to block waiting for checkpoints to complete their commit960record write. As a result it needs a lock and a wait variable. Log force961sequencing also requires the same lock, list walk, and blocking mechanism to962ensure completion of checkpoints.963 964These two sequencing operations can use the mechanism even though the965events they are waiting for are different. The checkpoint commit record966sequencing needs to wait until checkpoint contexts contain a commit LSN967(obtained through completion of a commit record write) while log force968sequencing needs to wait until previous checkpoint contexts are removed from969the committing list (i.e. they've completed). A simple wait variable and970broadcast wakeups (thundering herds) has been used to implement these two971serialisation queues. They use the same lock as the CIL, too. If we see too972much contention on the CIL lock, or too many context switches as a result of973the broadcast wakeups these operations can be put under a new spinlock and974given separate wait lists to reduce lock contention and the number of processes975woken by the wrong event.976 977 978Lifecycle Changes979-----------------980 981The existing log item life cycle is as follows::982 983 1. Transaction allocate984 2. Transaction reserve985 3. Lock item986 4. Join item to transaction987 If not already attached,988 Allocate log item989 Attach log item to owner item990 Attach log item to transaction991 5. Modify item992 Record modifications in log item993 6. Transaction commit994 Pin item in memory995 Format item into log buffer996 Write commit LSN into transaction997 Unlock item998 Attach transaction to log buffer999 1000 <log buffer IO dispatched>1001 <log buffer IO completes>1002 1003 7. Transaction completion1004 Mark log item committed1005 Insert log item into AIL1006 Write commit LSN into log item1007 Unpin log item1008 8. AIL traversal1009 Lock item1010 Mark log item clean1011 Flush item to disk1012 1013 <item IO completion>1014 1015 9. Log item removed from AIL1016 Moves log tail1017 Item unlocked1018 1019Essentially, steps 1-6 operate independently from step 7, which is also1020independent of steps 8-9. An item can be locked in steps 1-6 or steps 8-91021at the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur1022at the same time. If the log item is in the AIL or between steps 6 and 71023and steps 1-6 are re-entered, then the item is relogged. Only when steps 8-91024are 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 allocate1029 2. Transaction reserve1030 3. Lock item1031 4. Join item to transaction1032 If not already attached,1033 Allocate log item1034 Attach log item to owner item1035 Attach log item to transaction1036 5. Modify item1037 Record modifications in log item1038 6. Transaction commit1039 Pin item in memory if not pinned in CIL1040 Format item into log vector + buffer1041 Attach log vector and buffer to log item1042 Insert log item into CIL1043 Write CIL context sequence into transaction1044 Unlock item1045 1046 <next log force>1047 1048 7. CIL push1049 lock CIL flush1050 Chain log vectors and buffers together1051 Remove items from CIL1052 unlock CIL flush1053 write log vectors into log1054 sequence commit records1055 attach checkpoint context to log buffer1056 1057 <log buffer IO dispatched>1058 <log buffer IO completes>1059 1060 8. Checkpoint completion1061 Mark log item committed1062 Insert item into AIL1063 Write commit LSN into log item1064 Unpin log item1065 9. AIL traversal1066 Lock item1067 Mark log item clean1068 Flush item to disk1069 <item IO completion>1070 10. Log item removed from AIL1071 Moves log tail1072 Item unlocked1073 1074From this, it can be seen that the only life cycle differences between the two1075logging methods are in the middle of the life cycle - they still have the same1076beginning and end and execution constraints. The only differences are in the1077committing of the log items to the log itself and the completion processing.1078Hence delayed logging should not introduce any constraints on log item1079behaviour, allocation or freeing that don't already exist.1080 1081As a result of this zero-impact "insertion" of delayed logging infrastructure1082and the design of the internal structures to avoid on disk format changes, we1083can basically switch between delayed logging and the existing mechanism with a1084mount option. Fundamentally, there is no reason why the log manager would not1085be able to swap methods automatically and transparently depending on load1086characteristics, but this should not be necessary if delayed logging works as1087designed.1088