About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / filesystems / xfs-delayed-logging-design.txt




Custom Search

Based on kernel version 3.15.4. Page generated on 2014-07-07 09:03 EST.

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

Information is copyright its respective author. All material is available from the Linux Kernel Source distributed under a GPL License. This page is provided as a free service by mjmwired.net.