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