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