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