Lines Matching full:the

11 such as inodes and dquots, are logged in logical format where the details
12 logged are made up of the changes to in-core structures rather than on-disk
14 logged. The reason for these differences is to reduce the amount of log space
17 than any other object (except maybe the superblock buffer) so keeping the
20 The reason that this is such a concern is that XFS allows multiple separate
21 modifications to a single object to be carried in the log at any given time.
22 This allows the log to avoid needing to flush each change to disk before
23 recording a new change to the object. XFS does this via a method called
25 new change to the object is recorded with a *new copy* of all the existing
26 changes in the new transaction that is written to the log.
28 That is, if we have a sequence of changes A through to F, and the object was
29 written to disk after change D, we would see in the log the following series
30 of transactions, their contents and the log sequence number (LSN) of the
42 In other words, each time an object is relogged, the new transaction contains
43 the aggregation of all the previous changes currently held only in the log.
45 This relogging technique also allows objects to be moved forward in the log so
46 that an object being relogged does not prevent the tail of the log from ever
47 moving forward.  This can be seen in the table above by the changing
48 (increasing) LSN of each subsequent transaction - the LSN is effectively a
49 direct encoding of the location in the log of the transaction.
54 typical example of a rolling transaction is the removal of extents from an
57 keeps relogging the inode and btree buffers as they get modified in each
58 removal operation. This keeps them moving forward in the log as the operation
59 progresses, ensuring that current operation never gets blocked by itself if the
62 Hence it can be seen that the relogging operation is fundamental to the correct
63 working of the XFS journalling subsystem. From the above description, most
64 people should be able to see why the XFS metadata operations writes so much to
65 the log - repeated operations to the same objects write the same changes to
66 the log over and over again. Worse is the fact that objects tend to get
68 metadata into the log.
70 Another feature of the XFS transaction subsystem is that most transactions are
73 forces the log buffers holding the transactions to disk. This means that XFS is
75 minimise the impact of the log IO on transaction throughput.
77 The limitation on asynchronous transaction throughput is the number and size of
78 log buffers made available by the log manager. By default there are 8 log
79 buffers available and the size of each is 32kB - the size can be increased up
82 Effectively, this gives us the maximum bound of outstanding metadata changes
83 that can be made to the filesystem at any point in time - if all the log
85 the current batch completes. It is now common for a single current CPU core to
86 be to able to issue enough transactions to keep the log buffers full and under
87 IO permanently. Hence the XFS journalling subsystem can be considered to be IO
93 The key thing to note about the asynchronous logging combined with the
95 multiple times before they are committed to disk in the log buffers. If we
96 return to the previous relogging example, it is entirely possible that
97 transactions A through D are committed to disk in the same log buffer.
99 That is, a single log buffer may contain multiple copies of the same object,
100 but only one of those copies needs to be there - the last one "D", as it
101 contains all the changes from the previous changes. In other words, we have one
102 necessary copy in the log buffer, and three stale copies that are simply
103 wasting space. When we are doing repeated operations on the same set of
104 objects, these "stale objects" can be over 90% of the space used in the log
105 buffers. It is clear that reducing the number of stale objects written to the
106 log would greatly reduce the amount of metadata we write to the log, and this
107 is the fundamental goal of delayed logging.
111 logical to physical formatting to do the relogging because there is no
113 formatting the changes in a transaction to the log buffer. Hence we cannot avoid
114 accumulating stale objects in the log buffers.
116 Delayed logging is the name we've given to keeping and tracking transactional
117 changes to objects in memory outside the log buffer infrastructure. Because of
118 the relogging concept fundamental to the XFS journalling subsystem, this is
119 actually relatively easy to do - all the changes to logged items are already
120 tracked in the current infrastructure. The big problem is how to accumulate
121 them and get them to the log in a consistent, recoverable manner.
122 Describing the problems and how they have been solved is the focus of this
125 One of the key changes that delayed logging makes to the operation of the
126 journalling subsystem is that it disassociates the amount of outstanding
127 metadata changes from the size and number of log buffers available. In other
129 written to the log at any point in time, there may be a much greater amount
130 being accumulated in memory. Hence the potential for loss of metadata on a
131 crash is much greater than for the existing logging mechanism.
133 It should be noted that this does not change the guarantee that log recovery
134 will result in a consistent filesystem. What it does mean is that as far as the
136 that simply did not occur as a result of the crash. This makes it even more
141 warrants rigorous proofs to determine whether it is correct or not. The method
142 of accumulating changes in memory for some period before writing them to the
144 no time is spent in this document trying to convince the reader that the
148 The fundamental requirements for delayed logging in XFS are simple:
150 	1. Reduce the amount of metadata written to the log by at least
154 	   problems with the new code.
165 The problem with accumulating changes at a logical level (i.e. just using the
166 existing log item dirty region tracking) is that when it comes to writing the
167 changes to the log buffers, we need to ensure that the object we are formatting
168 is not changing while we do this. This requires locking the object to prevent
169 concurrent modification. Hence flushing the logical changes to the log would
174 the delayed logging tracking lock to commit the transaction. However, the
175 flushing thread has the delayed logging tracking lock already held, and is
176 trying to get the lock on object A to flush it to the log buffer. This appears
178 was the barrier to implementing delayed logging for so long.
180 The solution is relatively simple - it just took a long time to recognise it.
181 Put simply, the current logging code formats the changes to each item into an
182 vector array that points to the changed regions in the item. The log write code
183 simply copies the memory these vectors point to into the log buffer during
184 transaction commit while the item is locked in the transaction. Instead of
185 using the log buffer as the destination of the formatting code, we can use an
186 allocated memory buffer big enough to fit the formatted vector.
188 If we then copy the vector into the memory buffer and rewrite the vector to
189 point to the memory buffer rather than the object itself, we now have a copy of
190 the changes in a format that is compatible with the log buffer writing code.
191 that does not require us to lock the item to access. This formatting and
192 rewriting can all be done while the object is locked during transaction commit,
194 without needing to lock the owning item.
196 Hence we avoid the need to lock items when we need to flush outstanding
197 asynchronous transactions to the log. The differences between the existing
198 formatting method and the delayed logging formatting can be seen in the
226 The memory buffer and associated vector need to be passed as a single object,
227 but still need to be associated with the parent object so if the object is
228 relogged we can replace the current memory buffer with a new memory buffer that
229 contains the latest changes.
231 The reason for keeping the vector around after we've formatted the memory
233 If we don't keep the vector around, we do not know where the region boundaries
234 are in the item, so we'd need a new encapsulation method for regions in the log
236 change and as such is not desirable.  It also means we'd have to write the log
237 region headers in the formatting stage, which is problematic as there is per
238 region state that needs to be placed into the headers during the log write.
240 Hence we need to keep the vector, but by attaching the memory buffer to it and
241 rewriting the vector addresses to point at the memory buffer we end up with a
242 self-describing object that can be passed to the log buffer write code to be
243 handled in exactly the same manner as the existing log vectors are handled.
253 them so that they can be written to the log at some later point in time.  The
254 log item is the natural place to store this vector and buffer, and also makes sense
255 to be the object that is used to track committed objects as it will always
256 exist once the object has been included in a transaction.
258 The log item is already used to track the log items that have been written to
259 the log but not yet written to disk. Such log items are considered "active"
260 and as such are stored in the Active Item List (AIL) which is a LSN-ordered
263 that is in the AIL can be relogged, which causes the object to be pinned again
264 and then moved forward in the AIL when the log buffer IO completes for that
267 Essentially, this shows that an item that is in the AIL can still be modified
268 and relogged, so any tracking must be separate to the AIL infrastructure. As
269 such, we cannot reuse the AIL list pointers for tracking committed items, nor
270 can we store state in any field that is protected by the AIL lock. Hence the
271 committed item tracking needs it's own locks, lists and state fields in the log
274 Similar to the AIL, tracking of committed items is done through a new list
275 called the Committed Item List (CIL).  The list tracks log items that have been
278 it's place in the list and re-inserted at the tail. This is entirely arbitrary
279 and done to make it easy for debugging - the last items in the list are the
280 ones that are most recently modified. Ordering of the CIL is not necessary for
281 transactional integrity (as discussed in the next section) so the ordering is
282 done for convenience/sanity of the developers.
289 all the items in the CIL must be written into the log via the log buffers.
290 We need to write these items in the order that they exist in the CIL, and they
291 need to be written as an atomic transaction. The need for all the objects to be
292 written as an atomic transaction comes from the requirements of relogging and
293 log replay - all the changes in all the objects in a given transaction must
295 a transaction is not replayed because it is not complete in the log, then
298 To fulfill this requirement, we need to write the entire CIL in a single log
299 transaction. Fortunately, the XFS log code has no fixed limit on the size of a
300 transaction, nor does the log replay code. The only fundamental limit is that
301 the transaction cannot be larger than just under half the size of the log.  The
302 reason for this limit is that to find the head and tail of the log, there must
303 be at least one complete transaction in the log at any given time. If a
304 transaction is larger than half the log, then there is the possibility that a
305 crash during the write of a such a transaction could partially overwrite the
306 only complete previous transaction in the log. This will result in a recovery
307 failure and an inconsistent filesystem and hence we must enforce the maximum
308 size of a checkpoint to be slightly less than a half the log.
312 formatted log items and a commit record at the tail. From a recovery
313 perspective, the checkpoint transaction is also no different - just a lot
314 bigger with a lot more items in it. The worst case effect of this is that we
315 might need to tune the recovery transaction object hash size.
317 Because the checkpoint is just another transaction and all the changes to log
318 items are stored as log vectors, we can use the existing log buffer writing
319 code to write the changes into the log. To do this efficiently, we need to
320 minimise the time we hold the CIL locked while writing the checkpoint
321 transaction. The current log write code enables us to do this easily with the
322 way it separates the writing of the transaction contents (the log vectors) from
323 the transaction commit record, but tracking this requires us to have a
324 per-checkpoint context that travels through the log write process through to
327 Hence a checkpoint has a context that tracks the state of the current
329 at the same time a checkpoint transaction is started. That is, when we remove
330 all the current items from the CIL during a checkpoint operation, we move all
331 those changes into the current checkpoint context. We then initialise a new
332 context and attach that to the CIL for aggregation of new transactions.
334 This allows us to unlock the CIL immediately after transfer of all the
336 are formatting the checkpoint into the log. It also allows concurrent
337 checkpoints to be written into the log buffers in the case of log force heavy
338 workloads, just like the existing transaction commit code does. This, however,
339 requires that we strictly order the commit records in the log so that
343 the same time another transaction modifies the item and inserts the log item
344 into the new CIL, then checkpoint transaction commit code cannot use log items
345 to store the list of log vectors that need to be written into the transaction.
347 detached from the log items. That is, when the CIL is flushed the memory
348 buffer and log vector attached to each log item needs to be attached to the
349 checkpoint context so that the log item can be released. In diagrammatic form,
350 the CIL would look like this before the flush::
370 And after the flush the CIL head is empty, and the checkpoint context log
395 Once this transfer is done, the CIL can be unlocked and new transactions can
396 start, while the checkpoint flush code works over the log vector chain to
397 commit the checkpoint.
399 Once the checkpoint is written into the log buffers, the checkpoint context is
400 attached to the log buffer that the commit record was written to along with a
402 run transaction committed processing for the log items (i.e. insert into AIL
403 and unpin) in the log vector chain and then free the log vector chain and
406 Discussion Point: I am uncertain as to whether the log item is the most
407 efficient way to track vectors, even though it seems like the natural way to do
408 it. The fact that we walk the log items (in the CIL) just to chain the log
409 vectors and break the link between the log item and the log vector means that
410 we take a cache line hit for the log item list modification, then another for
411 the log vector chaining. If we track by the log vectors, then we only need to
412 break the link between the log item and the log vector, which means we should
413 dirty only the log item cachelines. Normally I wouldn't be concerned about one
414 vs two dirty cachelines except for the fact I've seen upwards of 80,000 log
417 is in the dev tree....
422 One of the key aspects of the XFS transaction subsystem is that it tags
423 committed transactions with the log sequence number of the transaction commit.
426 committed to the log. In the rare case that a dependent operation occurs (e.g.
428 force can be issued to force the dependent transaction to disk immediately.
430 To do this, transactions need to record the LSN of the commit record of the
431 transaction. This LSN comes directly from the log buffer the transaction is
432 written into. While this works just fine for the existing transaction
434 written directly into the log buffers. Hence some other method of sequencing
437 As discussed in the checkpoint section, delayed logging uses per-checkpoint
439 checkpoint. Because the switching of checkpoint contexts must be done
441 increasing sequence number assigned to it without the need for an external
442 atomic counter - we can just take the current context sequence number and add
443 one to it for the new context.
445 Then, instead of assigning a log buffer LSN to the transaction commit LSN
446 during the commit, we can assign the current checkpoint sequence. This allows
449 result, the code that forces the log to a specific LSN now needs to ensure that
450 the log forces to a specific checkpoint.
452 To ensure that we can do this, we need to track all the checkpoint contexts
453 that are currently committing to the log. When we flush a checkpoint, the
455 checkpoint commit completes, it is removed from the committing list. Because
456 the checkpoint context records the LSN of the commit record for the checkpoint,
457 we can also wait on the log buffer that contains the commit record, thereby
458 using the existing log force mechanisms to execute synchronous forces.
460 It should be noted that the synchronous forces may need to be extended with
461 mitigation algorithms similar to the current log buffer code to allow
463 synchronous transactions being flushed. Investigation of the performance of the
466 The main concern with log forces is to ensure that all the previous checkpoints
467 are also committed to disk before the one we need to wait for. Therefore we
468 need to check that all the prior contexts in the committing list are also
469 complete before waiting on the one we need to complete. We do this
470 synchronisation in the log force code so that we don't need to wait anywhere
473 The only remaining complexity is that a log force now also has to handle the
474 case where the forcing sequence number is the same as the current context. That
475 is, we need to flush the CIL and potentially wait for it to complete. This is a
476 simple addition to the existing log forcing code to check the sequence numbers
477 and push if required. Indeed, placing the current sequence checkpoint flush in
478 the log force code enables the current mechanism for issuing synchronous
480 force the log at the LSN of that transaction) and so the higher level code
481 behaves the same regardless of whether delayed logging is being used or not.
486 The big issue for a checkpoint transaction is the log space reservation for the
488 ahead of time, nor how many log buffers it will take to write out, nor the
489 number of split log vector regions are going to be used. We can track the
490 amount of log space required as we add items to the commit item list, but we
491 still need to reserve the space in the log for the checkpoint.
493 A typical transaction reserves enough space in the log for the worst case space
494 usage of the transaction. The reservation accounts for log record headers,
496 etc. as well as the actual space for all the changed metadata in the
498 the size of the transaction and the number of regions being logged (the number
499 of log vectors in the transaction).
501 An example of the differences would be logging directory changes versus logging
506 vector is 12 bytes, so the total to be logged is approximately 1.75MB. In
511 not particularly flexible and is difficult to select the "optimal value" for
514 Further, if we are going to use a static reservation, which bit of the entire
515 reservation does it cover? We account for space used by the transaction
516 reservation by tracking the space currently used by the object in the CIL and
517 then calculating the increase or decrease in space used as the object is
521 However, even using a static reservation for just the log metadata is
523 1MB of log space consumed (512 bytes per 32k) and the reservation needs to be
525 reservation needs to be made before the checkpoint is started, and we need to
526 be able to reserve the space without sleeping.  For a 8MB checkpoint, we need a
529 A static reservation needs to manipulate the log grant counters - we can take a
530 permanent reservation on the space, but we still need to make sure we refresh
531 the write reservation (the actual space available to the transaction) after
533 available when required, then the regrant code will sleep waiting for it.
535 The problem with this is that it can lead to deadlocks as we may need to commit
536 checkpoints to be able to free up log space (refer back to the description of
538 space available in the log if we are to use static reservations, and that is
542 The simpler way of doing this is tracking the entire log space used by the
543 items in the CIL and using this to dynamically calculate the amount of log
544 space required by the log metadata. If this log metadata space changes as a
545 result of a transaction commit inserting a new memory buffer into the CIL, then
546 the difference in space required is removed from the transaction that causes
547 the change. Transactions at this level will *always* have enough space
548 available in their reservation for this as they have already reserved the
550 will always be less than or equal to the maximal amount in the reservation.
552 Hence we can grow the checkpoint transaction reservation dynamically as items
553 are added to the CIL and avoid the need for reserving and regranting log space
554 up front. This avoids deadlocks and removes a blocking point from the
557 As mentioned early, transactions can't grow to more than half the size of the
558 log. Hence as part of the reservation growing, we need to also check the size
559 of the reservation against the maximum allowed transaction size. If we reach
560 the maximum threshold, we need to push the CIL to the log. This is effectively
562 a CIL push triggered by a log force, only that there is no waiting for the
566 If the transaction subsystem goes idle while we still have items in the CIL,
567 they will be flushed by the periodic log force issued by the xfssyncd. This log
568 force will push the CIL to disk, and if the transaction subsystem stays idle,
569 allow the idle log to be covered (effectively marked clean) in exactly the same
570 manner that is done for the existing logging method. A discussion point is
571 whether this log force needs to be done more frequently than the current rate
578 Currently log items are pinned during transaction commit while the items are
579 still locked. This happens just after the items are formatted, though it could
580 be done any time before the items are unlocked. The result of this mechanism is
581 that items get pinned once for every transaction that is committed to the log
582 buffers. Hence items that are relogged in the log buffers will have a pin count
584 transactions is completed, they will unpin the item once. As a result, the item
585 only becomes unpinned when all the transactions complete and there are no
586 pending transactions. Thus the pinning and unpinning of a log item is symmetric
590 completion relationship. Every time an object is relogged in the CIL it goes
591 through the commit process without a corresponding completion being registered.
593 log item completion. The result of this is that pinning and unpinning of the
594 log items becomes unbalanced if we retain the "pin on transaction commit, unpin
597 To keep pin/unpin symmetry, the algorithm needs to change to a "pin on
598 insertion into the CIL, unpin on checkpoint completion". In other words, the
600 pin the object the first time it is inserted into the CIL - if it is already in
601 the CIL during a transaction commit, then we do not pin it again. Because there
603 counts, but as each checkpoint completes the pin count will retain the correct
607 for the pin count means that the pinning of an item must take place under the
608 CIL commit/flush lock. If we pin the object outside this lock, we cannot
609 guarantee which context the pin count is associated with. This is because of
610 the fact pinning the item is dependent on whether the item is present in the
611 current CIL or not. If we don't pin the CIL first before we check and pin the
612 object, we have a race with CIL being flushed between the check and the pin
613 (or not pinning, as the case may be). Hence we must hold the CIL flush/commit
614 lock to guarantee that we pin the items correctly.
619 A fundamental requirement for the CIL is that accesses through transaction
620 commits must scale to many concurrent commits. The current transaction commit
622 processors at once. The current transaction code does not go any faster than if
625 As a result, the delayed logging transaction commit code needs to be designed
626 for concurrency from the ground up. It is obvious that there are serialisation
627 points in the design - the three important ones are:
629 	1. Locking out new transaction commits while flushing the CIL
630 	2. Adding items to the CIL and updating item space accounting
633 Looking at the transaction commit and CIL flushing interactions, it is clear
634 that we have a many-to-one interaction here. That is, the only restriction on
635 the number of concurrent transactions that can be trying to commit at once is
636 the amount of space available in the log for their reservations. The practical
637 limit here is in the order of several hundred concurrent transactions for a
640 The amount of time a transaction commit needs to hold out a flush is a
641 relatively long period of time - the pinning of log items needs to be done
642 while we are holding out a CIL flush, so at the moment that means it is held
643 across the formatting of the objects into memory buffers (i.e. while memcpy()s
644 are in progress). Ultimately a two pass algorithm where the formatting is done
645 separately to the pinning of objects could be used to reduce the hold time of
646 the transaction commit side.
648 Because of the number of potential transaction commit side holders, the lock
649 really needs to be a sleeping lock - if the CIL flush takes the lock, we do not
650 want every other CPU in the machine spinning on the CIL lock. Given that
651 flushing the CIL could involve walking a list of tens of thousands of log
653 significant concern. Preventing lots of CPUs spinning doing nothing is the
654 main reason for choosing a sleeping lock even though nothing in either the
655 transaction commit or CIL flush side sleeps with the lock held.
660 transaction commit concurrency due to cache line bouncing of the lock on the
663 The second serialisation point is on the transaction commit side where items
664 are inserted into the CIL. Because transactions can enter this code
665 concurrently, the CIL needs to be protected separately from the above
668 possible that this lock will become a contention point, but given the short
671 The final serialisation point is the checkpoint commit record ordering code
672 that is run as part of the checkpoint commit and log force sequencing. The code
673 path that triggers a CIL flush (i.e. whatever triggers the log force) will enter
674 an ordering loop after writing all the log vectors into the log buffers but
675 before writing the commit record. This loop walks the list of committing
678 sequencing also requires the same lock, list walk, and blocking mechanism to
681 These two sequencing operations can use the mechanism even though the
682 events they are waiting for are different. The checkpoint commit record
686 the committing list (i.e. they've completed). A simple wait variable and
688 serialisation queues. They use the same lock as the CIL, too. If we see too
689 much contention on the CIL lock, or too many context switches as a result of
690 the broadcast wakeups these operations can be put under a new spinlock and
691 given separate wait lists to reduce lock contention and the number of processes
692 woken by the wrong event.
698 The existing log item life cycle is as follows::
738 at the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur
739 at the same time. If the log item is in the AIL or between steps 6 and 7
740 and steps 1-6 are re-entered, then the item is relogged. Only when steps 8-9
741 are entered and completed is the object considered clean.
743 With delayed logging, there are new steps inserted into the life cycle::
791 From this, it can be seen that the only life cycle differences between the two
792 logging methods are in the middle of the life cycle - they still have the same
793 beginning and end and execution constraints. The only differences are in the
794 committing of the log items to the log itself and the completion processing.
799 and the design of the internal structures to avoid on disk format changes, we
800 can basically switch between delayed logging and the existing mechanism with a
801 mount option. Fundamentally, there is no reason why the log manager would not