1c3d2f6cbSMauro Carvalho Chehab.. SPDX-License-Identifier: GPL-2.0 2c3d2f6cbSMauro Carvalho Chehab 351a117edSDave Chinner================== 451a117edSDave ChinnerXFS Logging Design 551a117edSDave Chinner================== 6c3d2f6cbSMauro Carvalho Chehab 751a117edSDave ChinnerPreamble 851a117edSDave Chinner======== 9c3d2f6cbSMauro Carvalho Chehab 1051a117edSDave ChinnerThis document describes the design and algorithms that the XFS journalling 1151a117edSDave Chinnersubsystem is based on. This document describes the design and algorithms that 1251a117edSDave Chinnerthe XFS journalling subsystem is based on so that readers may familiarize 1351a117edSDave Chinnerthemselves with the general concepts of how transaction processing in XFS works. 14c3d2f6cbSMauro Carvalho Chehab 1551a117edSDave ChinnerWe begin with an overview of transactions in XFS, followed by describing how 1651a117edSDave Chinnertransaction reservations are structured and accounted, and then move into how we 1751a117edSDave Chinnerguarantee forwards progress for long running transactions with finite initial 1851a117edSDave Chinnerreservations bounds. At this point we need to explain how relogging works. With 1951a117edSDave Chinnerthe basic concepts covered, the design of the delayed logging mechanism is 2051a117edSDave Chinnerdocumented. 2151a117edSDave Chinner 2251a117edSDave Chinner 2351a117edSDave ChinnerIntroduction 2451a117edSDave Chinner============ 2551a117edSDave Chinner 2651a117edSDave ChinnerXFS uses Write Ahead Logging for ensuring changes to the filesystem metadata 2751a117edSDave Chinnerare atomic and recoverable. For reasons of space and time efficiency, the 2851a117edSDave Chinnerlogging mechanisms are varied and complex, combining intents, logical and 2951a117edSDave Chinnerphysical logging mechanisms to provide the necessary recovery guarantees the 3051a117edSDave Chinnerfilesystem requires. 3151a117edSDave Chinner 3251a117edSDave ChinnerSome objects, such as inodes and dquots, are logged in logical format where the 3351a117edSDave Chinnerdetails logged are made up of the changes to in-core structures rather than 3451a117edSDave Chinneron-disk structures. Other objects - typically buffers - have their physical 3551a117edSDave Chinnerchanges logged. Long running atomic modifications have individual changes 3651a117edSDave Chinnerchained together by intents, ensuring that journal recovery can restart and 3751a117edSDave Chinnerfinish an operation that was only partially done when the system stopped 3851a117edSDave Chinnerfunctioning. 3951a117edSDave Chinner 4051a117edSDave ChinnerThe reason for these differences is to keep the amount of log space and CPU time 4151a117edSDave Chinnerrequired to process objects being modified as small as possible and hence the 4251a117edSDave Chinnerlogging overhead as low as possible. Some items are very frequently modified, 4351a117edSDave Chinnerand some parts of objects are more frequently modified than others, so keeping 4451a117edSDave Chinnerthe overhead of metadata logging low is of prime importance. 4551a117edSDave Chinner 4651a117edSDave ChinnerThe method used to log an item or chain modifications together isn't 4751a117edSDave Chinnerparticularly important in the scope of this document. It suffices to know that 4851a117edSDave Chinnerthe method used for logging a particular object or chaining modifications 4951a117edSDave Chinnertogether are different and are dependent on the object and/or modification being 5051a117edSDave Chinnerperformed. The logging subsystem only cares that certain specific rules are 5151a117edSDave Chinnerfollowed to guarantee forwards progress and prevent deadlocks. 5251a117edSDave Chinner 5351a117edSDave Chinner 5451a117edSDave ChinnerTransactions in XFS 5551a117edSDave Chinner=================== 5651a117edSDave Chinner 5751a117edSDave ChinnerXFS has two types of high level transactions, defined by the type of log space 5851a117edSDave Chinnerreservation they take. These are known as "one shot" and "permanent" 5951a117edSDave Chinnertransactions. Permanent transaction reservations can take reservations that span 6051a117edSDave Chinnercommit boundaries, whilst "one shot" transactions are for a single atomic 6151a117edSDave Chinnermodification. 6251a117edSDave Chinner 6351a117edSDave ChinnerThe type and size of reservation must be matched to the modification taking 6451a117edSDave Chinnerplace. This means that permanent transactions can be used for one-shot 6551a117edSDave Chinnermodifications, but one-shot reservations cannot be used for permanent 6651a117edSDave Chinnertransactions. 6751a117edSDave Chinner 6851a117edSDave ChinnerIn the code, a one-shot transaction pattern looks somewhat like this:: 6951a117edSDave Chinner 7051a117edSDave Chinner tp = xfs_trans_alloc(<reservation>) 7151a117edSDave Chinner <lock items> 7251a117edSDave Chinner <join item to transaction> 7351a117edSDave Chinner <do modification> 7451a117edSDave Chinner xfs_trans_commit(tp); 7551a117edSDave Chinner 7651a117edSDave ChinnerAs items are modified in the transaction, the dirty regions in those items are 7751a117edSDave Chinnertracked via the transaction handle. Once the transaction is committed, all 7851a117edSDave Chinnerresources joined to it are released, along with the remaining unused reservation 7951a117edSDave Chinnerspace that was taken at the transaction allocation time. 8051a117edSDave Chinner 8151a117edSDave ChinnerIn contrast, a permanent transaction is made up of multiple linked individual 8251a117edSDave Chinnertransactions, and the pattern looks like this:: 8351a117edSDave Chinner 8451a117edSDave Chinner tp = xfs_trans_alloc(<reservation>) 8551a117edSDave Chinner xfs_ilock(ip, XFS_ILOCK_EXCL) 8651a117edSDave Chinner 8751a117edSDave Chinner loop { 8851a117edSDave Chinner xfs_trans_ijoin(tp, 0); 8951a117edSDave Chinner <do modification> 9051a117edSDave Chinner xfs_trans_log_inode(tp, ip); 9151a117edSDave Chinner xfs_trans_roll(&tp); 9251a117edSDave Chinner } 9351a117edSDave Chinner 9451a117edSDave Chinner xfs_trans_commit(tp); 9551a117edSDave Chinner xfs_iunlock(ip, XFS_ILOCK_EXCL); 9651a117edSDave Chinner 9751a117edSDave ChinnerWhile this might look similar to a one-shot transaction, there is an important 9851a117edSDave Chinnerdifference: xfs_trans_roll() performs a specific operation that links two 9951a117edSDave Chinnertransactions together:: 10051a117edSDave Chinner 10151a117edSDave Chinner ntp = xfs_trans_dup(tp); 10251a117edSDave Chinner xfs_trans_commit(tp); 103021904f3SZhao Mengmeng xfs_trans_reserve(ntp); 10451a117edSDave Chinner 10551a117edSDave ChinnerThis results in a series of "rolling transactions" where the inode is locked 10651a117edSDave Chinneracross the entire chain of transactions. Hence while this series of rolling 10751a117edSDave Chinnertransactions is running, nothing else can read from or write to the inode and 10851a117edSDave Chinnerthis provides a mechanism for complex changes to appear atomic from an external 10951a117edSDave Chinnerobserver's point of view. 11051a117edSDave Chinner 11151a117edSDave ChinnerIt is important to note that a series of rolling transactions in a permanent 11251a117edSDave Chinnertransaction does not form an atomic change in the journal. While each 11351a117edSDave Chinnerindividual modification is atomic, the chain is *not atomic*. If we crash half 11451a117edSDave Chinnerway through, then recovery will only replay up to the last transactional 11551a117edSDave Chinnermodification the loop made that was committed to the journal. 11651a117edSDave Chinner 11751a117edSDave ChinnerThis affects long running permanent transactions in that it is not possible to 11851a117edSDave Chinnerpredict how much of a long running operation will actually be recovered because 11951a117edSDave Chinnerthere is no guarantee of how much of the operation reached stale storage. Hence 12051a117edSDave Chinnerif a long running operation requires multiple transactions to fully complete, 12151a117edSDave Chinnerthe high level operation must use intents and deferred operations to guarantee 12251a117edSDave Chinnerrecovery can complete the operation once the first transactions is persisted in 12351a117edSDave Chinnerthe on-disk journal. 12451a117edSDave Chinner 12551a117edSDave Chinner 12651a117edSDave ChinnerTransactions are Asynchronous 12751a117edSDave Chinner============================= 12851a117edSDave Chinner 12951a117edSDave ChinnerIn XFS, all high level transactions are asynchronous by default. This means that 13051a117edSDave Chinnerxfs_trans_commit() does not guarantee that the modification has been committed 13151a117edSDave Chinnerto stable storage when it returns. Hence when a system crashes, not all the 13251a117edSDave Chinnercompleted transactions will be replayed during recovery. 13351a117edSDave Chinner 13451a117edSDave ChinnerHowever, the logging subsystem does provide global ordering guarantees, such 13551a117edSDave Chinnerthat if a specific change is seen after recovery, all metadata modifications 13651a117edSDave Chinnerthat were committed prior to that change will also be seen. 13751a117edSDave Chinner 13851a117edSDave ChinnerFor single shot operations that need to reach stable storage immediately, or 13951a117edSDave Chinnerensuring that a long running permanent transaction is fully committed once it is 14051a117edSDave Chinnercomplete, we can explicitly tag a transaction as synchronous. This will trigger 14151a117edSDave Chinnera "log force" to flush the outstanding committed transactions to stable storage 14251a117edSDave Chinnerin the journal and wait for that to complete. 14351a117edSDave Chinner 14451a117edSDave ChinnerSynchronous transactions are rarely used, however, because they limit logging 14551a117edSDave Chinnerthroughput to the IO latency limitations of the underlying storage. Instead, we 14651a117edSDave Chinnertend to use log forces to ensure modifications are on stable storage only when 14751a117edSDave Chinnera user operation requires a synchronisation point to occur (e.g. fsync). 14851a117edSDave Chinner 14951a117edSDave Chinner 15051a117edSDave ChinnerTransaction Reservations 15151a117edSDave Chinner======================== 15251a117edSDave Chinner 15351a117edSDave ChinnerIt has been mentioned a number of times now that the logging subsystem needs to 15451a117edSDave Chinnerprovide a forwards progress guarantee so that no modification ever stalls 15551a117edSDave Chinnerbecause it can't be written to the journal due to a lack of space in the 15651a117edSDave Chinnerjournal. This is achieved by the transaction reservations that are made when 15751a117edSDave Chinnera transaction is first allocated. For permanent transactions, these reservations 15851a117edSDave Chinnerare maintained as part of the transaction rolling mechanism. 15951a117edSDave Chinner 16051a117edSDave ChinnerA transaction reservation provides a guarantee that there is physical log space 16151a117edSDave Chinneravailable to write the modification into the journal before we start making 16251a117edSDave Chinnermodifications to objects and items. As such, the reservation needs to be large 16351a117edSDave Chinnerenough to take into account the amount of metadata that the change might need to 16451a117edSDave Chinnerlog in the worst case. This means that if we are modifying a btree in the 16551a117edSDave Chinnertransaction, we have to reserve enough space to record a full leaf-to-root split 16651a117edSDave Chinnerof the btree. As such, the reservations are quite complex because we have to 16751a117edSDave Chinnertake into account all the hidden changes that might occur. 16851a117edSDave Chinner 16951a117edSDave ChinnerFor example, a user data extent allocation involves allocating an extent from 17051a117edSDave Chinnerfree space, which modifies the free space trees. That's two btrees. Inserting 17151a117edSDave Chinnerthe extent into the inode's extent map might require a split of the extent map 17251a117edSDave Chinnerbtree, which requires another allocation that can modify the free space trees 17351a117edSDave Chinneragain. Then we might have to update reverse mappings, which modifies yet 17451a117edSDave Chinneranother btree which might require more space. And so on. Hence the amount of 17551a117edSDave Chinnermetadata that a "simple" operation can modify can be quite large. 17651a117edSDave Chinner 17751a117edSDave ChinnerThis "worst case" calculation provides us with the static "unit reservation" 17851a117edSDave Chinnerfor the transaction that is calculated at mount time. We must guarantee that the 17951a117edSDave Chinnerlog has this much space available before the transaction is allowed to proceed 18051a117edSDave Chinnerso that when we come to write the dirty metadata into the log we don't run out 18151a117edSDave Chinnerof log space half way through the write. 18251a117edSDave Chinner 18351a117edSDave ChinnerFor one-shot transactions, a single unit space reservation is all that is 18451a117edSDave Chinnerrequired for the transaction to proceed. For permanent transactions, however, we 18551a117edSDave Chinneralso have a "log count" that affects the size of the reservation that is to be 18651a117edSDave Chinnermade. 18751a117edSDave Chinner 18851a117edSDave ChinnerWhile a permanent transaction can get by with a single unit of space 18951a117edSDave Chinnerreservation, it is somewhat inefficient to do this as it requires the 19051a117edSDave Chinnertransaction rolling mechanism to re-reserve space on every transaction roll. We 19151a117edSDave Chinnerknow from the implementation of the permanent transactions how many transaction 19251a117edSDave Chinnerrolls are likely for the common modifications that need to be made. 19351a117edSDave Chinner 194021904f3SZhao MengmengFor example, an inode allocation is typically two transactions - one to 19551a117edSDave Chinnerphysically allocate a free inode chunk on disk, and another to allocate an inode 19651a117edSDave Chinnerfrom an inode chunk that has free inodes in it. Hence for an inode allocation 19751a117edSDave Chinnertransaction, we might set the reservation log count to a value of 2 to indicate 19851a117edSDave Chinnerthat the common/fast path transaction will commit two linked transactions in a 19951a117edSDave Chinnerchain. Each time a permanent transaction rolls, it consumes an entire unit 20051a117edSDave Chinnerreservation. 20151a117edSDave Chinner 20251a117edSDave ChinnerHence when the permanent transaction is first allocated, the log space 203021904f3SZhao Mengmengreservation is increased from a single unit reservation to multiple unit 20451a117edSDave Chinnerreservations. That multiple is defined by the reservation log count, and this 20551a117edSDave Chinnermeans we can roll the transaction multiple times before we have to re-reserve 20651a117edSDave Chinnerlog space when we roll the transaction. This ensures that the common 20751a117edSDave Chinnermodifications we make only need to reserve log space once. 20851a117edSDave Chinner 20951a117edSDave ChinnerIf the log count for a permanent transaction reaches zero, then it needs to 21051a117edSDave Chinnerre-reserve physical space in the log. This is somewhat complex, and requires 21151a117edSDave Chinneran understanding of how the log accounts for space that has been reserved. 21251a117edSDave Chinner 21351a117edSDave Chinner 21451a117edSDave ChinnerLog Space Accounting 21551a117edSDave Chinner==================== 21651a117edSDave Chinner 21751a117edSDave ChinnerThe position in the log is typically referred to as a Log Sequence Number (LSN). 21851a117edSDave ChinnerThe log is circular, so the positions in the log are defined by the combination 21951a117edSDave Chinnerof a cycle number - the number of times the log has been overwritten - and the 22051a117edSDave Chinneroffset into the log. A LSN carries the cycle in the upper 32 bits and the 22151a117edSDave Chinneroffset in the lower 32 bits. The offset is in units of "basic blocks" (512 22251a117edSDave Chinnerbytes). Hence we can do realtively simple LSN based math to keep track of 22351a117edSDave Chinneravailable space in the log. 22451a117edSDave Chinner 22551a117edSDave ChinnerLog space accounting is done via a pair of constructs called "grant heads". The 22651a117edSDave Chinnerposition of the grant heads is an absolute value, so the amount of space 22751a117edSDave Chinneravailable in the log is defined by the distance between the position of the 22851a117edSDave Chinnergrant head and the current log tail. That is, how much space can be 22951a117edSDave Chinnerreserved/consumed before the grant heads would fully wrap the log and overtake 23051a117edSDave Chinnerthe tail position. 23151a117edSDave Chinner 23251a117edSDave ChinnerThe first grant head is the "reserve" head. This tracks the byte count of the 23351a117edSDave Chinnerreservations currently held by active transactions. It is a purely in-memory 23451a117edSDave Chinneraccounting of the space reservation and, as such, actually tracks byte offsets 23551a117edSDave Chinnerinto the log rather than basic blocks. Hence it technically isn't using LSNs to 23651a117edSDave Chinnerrepresent the log position, but it is still treated like a split {cycle,offset} 23751a117edSDave Chinnertuple for the purposes of tracking reservation space. 23851a117edSDave Chinner 23951a117edSDave ChinnerThe reserve grant head is used to accurately account for exact transaction 24051a117edSDave Chinnerreservations amounts and the exact byte count that modifications actually make 24151a117edSDave Chinnerand need to write into the log. The reserve head is used to prevent new 24251a117edSDave Chinnertransactions from taking new reservations when the head reaches the current 24351a117edSDave Chinnertail. It will block new reservations in a FIFO queue and as the log tail moves 24451a117edSDave Chinnerforward it will wake them in order once sufficient space is available. This FIFO 24551a117edSDave Chinnermechanism ensures no transaction is starved of resources when log space 24651a117edSDave Chinnershortages occur. 24751a117edSDave Chinner 24851a117edSDave ChinnerThe other grant head is the "write" head. Unlike the reserve head, this grant 24951a117edSDave Chinnerhead contains an LSN and it tracks the physical space usage in the log. While 25051a117edSDave Chinnerthis might sound like it is accounting the same state as the reserve grant head 25151a117edSDave Chinner- and it mostly does track exactly the same location as the reserve grant head - 25251a117edSDave Chinnerthere are critical differences in behaviour between them that provides the 25351a117edSDave Chinnerforwards progress guarantees that rolling permanent transactions require. 25451a117edSDave Chinner 25551a117edSDave ChinnerThese differences when a permanent transaction is rolled and the internal "log 25651a117edSDave Chinnercount" reaches zero and the initial set of unit reservations have been 25751a117edSDave Chinnerexhausted. At this point, we still require a log space reservation to continue 25851a117edSDave Chinnerthe next transaction in the sequeunce, but we have none remaining. We cannot 25951a117edSDave Chinnersleep during the transaction commit process waiting for new log space to become 26051a117edSDave Chinneravailable, as we may end up on the end of the FIFO queue and the items we have 26151a117edSDave Chinnerlocked while we sleep could end up pinning the tail of the log before there is 262021904f3SZhao Mengmengenough free space in the log to fulfill all of the pending reservations and 26351a117edSDave Chinnerthen wake up transaction commit in progress. 26451a117edSDave Chinner 26551a117edSDave ChinnerTo take a new reservation without sleeping requires us to be able to take a 26651a117edSDave Chinnerreservation even if there is no reservation space currently available. That is, 26751a117edSDave Chinnerwe need to be able to *overcommit* the log reservation space. As has already 26851a117edSDave Chinnerbeen detailed, we cannot overcommit physical log space. However, the reserve 26951a117edSDave Chinnergrant head does not track physical space - it only accounts for the amount of 27051a117edSDave Chinnerreservations we currently have outstanding. Hence if the reserve head passes 27151a117edSDave Chinnerover the tail of the log all it means is that new reservations will be throttled 27251a117edSDave Chinnerimmediately and remain throttled until the log tail is moved forward far enough 27351a117edSDave Chinnerto remove the overcommit and start taking new reservations. In other words, we 27451a117edSDave Chinnercan overcommit the reserve head without violating the physical log head and tail 27551a117edSDave Chinnerrules. 27651a117edSDave Chinner 27751a117edSDave ChinnerAs a result, permanent transactions only "regrant" reservation space during 27851a117edSDave Chinnerxfs_trans_commit() calls, while the physical log space reservation - tracked by 27951a117edSDave Chinnerthe write head - is then reserved separately by a call to xfs_log_reserve() 28051a117edSDave Chinnerafter the commit completes. Once the commit completes, we can sleep waiting for 28151a117edSDave Chinnerphysical log space to be reserved from the write grant head, but only if one 28251a117edSDave Chinnercritical rule has been observed:: 28351a117edSDave Chinner 28451a117edSDave Chinner Code using permanent reservations must always log the items they hold 28551a117edSDave Chinner locked across each transaction they roll in the chain. 28651a117edSDave Chinner 28751a117edSDave Chinner"Re-logging" the locked items on every transaction roll ensures that the items 28851a117edSDave Chinnerattached to the transaction chain being rolled are always relocated to the 28951a117edSDave Chinnerphysical head of the log and so do not pin the tail of the log. If a locked item 29051a117edSDave Chinnerpins the tail of the log when we sleep on the write reservation, then we will 29151a117edSDave Chinnerdeadlock the log as we cannot take the locks needed to write back that item and 29251a117edSDave Chinnermove the tail of the log forwards to free up write grant space. Re-logging the 29351a117edSDave Chinnerlocked items avoids this deadlock and guarantees that the log reservation we are 29451a117edSDave Chinnermaking cannot self-deadlock. 29551a117edSDave Chinner 29651a117edSDave ChinnerIf all rolling transactions obey this rule, then they can all make forwards 29751a117edSDave Chinnerprogress independently because nothing will block the progress of the log 29851a117edSDave Chinnertail moving forwards and hence ensuring that write grant space is always 29951a117edSDave Chinner(eventually) made available to permanent transactions no matter how many times 30051a117edSDave Chinnerthey roll. 30151a117edSDave Chinner 30251a117edSDave Chinner 30351a117edSDave ChinnerRe-logging Explained 30451a117edSDave Chinner==================== 30551a117edSDave Chinner 30651a117edSDave ChinnerXFS allows multiple separate modifications to a single object to be carried in 30751a117edSDave Chinnerthe log at any given time. This allows the log to avoid needing to flush each 30851a117edSDave Chinnerchange to disk before recording a new change to the object. XFS does this via a 30951a117edSDave Chinnermethod called "re-logging". Conceptually, this is quite simple - all it requires 31051a117edSDave Chinneris that any new change to the object is recorded with a *new copy* of all the 31151a117edSDave Chinnerexisting changes in the new transaction that is written to the log. 312c3d2f6cbSMauro Carvalho Chehab 313c3d2f6cbSMauro Carvalho ChehabThat is, if we have a sequence of changes A through to F, and the object was 314c3d2f6cbSMauro Carvalho Chehabwritten to disk after change D, we would see in the log the following series 315c3d2f6cbSMauro Carvalho Chehabof transactions, their contents and the log sequence number (LSN) of the 316c3d2f6cbSMauro Carvalho Chehabtransaction:: 317c3d2f6cbSMauro Carvalho Chehab 318c3d2f6cbSMauro Carvalho Chehab Transaction Contents LSN 319c3d2f6cbSMauro Carvalho Chehab A A X 320c3d2f6cbSMauro Carvalho Chehab B A+B X+n 321c3d2f6cbSMauro Carvalho Chehab C A+B+C X+n+m 322c3d2f6cbSMauro Carvalho Chehab D A+B+C+D X+n+m+o 323c3d2f6cbSMauro Carvalho Chehab <object written to disk> 324c3d2f6cbSMauro Carvalho Chehab E E Y (> X+n+m+o) 325c3d2f6cbSMauro Carvalho Chehab F E+F Y+p 326c3d2f6cbSMauro Carvalho Chehab 327c3d2f6cbSMauro Carvalho ChehabIn other words, each time an object is relogged, the new transaction contains 328c3d2f6cbSMauro Carvalho Chehabthe aggregation of all the previous changes currently held only in the log. 329c3d2f6cbSMauro Carvalho Chehab 33051a117edSDave ChinnerThis relogging technique allows objects to be moved forward in the log so that 33151a117edSDave Chinneran object being relogged does not prevent the tail of the log from ever moving 33251a117edSDave Chinnerforward. This can be seen in the table above by the changing (increasing) LSN 33351a117edSDave Chinnerof each subsequent transaction, and it's the technique that allows us to 33451a117edSDave Chinnerimplement long-running, multiple-commit permanent transactions. 335c3d2f6cbSMauro Carvalho Chehab 33651a117edSDave ChinnerA typical example of a rolling transaction is the removal of extents from an 337c3d2f6cbSMauro Carvalho Chehabinode which can only be done at a rate of two extents per transaction because 338c3d2f6cbSMauro Carvalho Chehabof reservation size limitations. Hence a rolling extent removal transaction 339c3d2f6cbSMauro Carvalho Chehabkeeps relogging the inode and btree buffers as they get modified in each 340c3d2f6cbSMauro Carvalho Chehabremoval operation. This keeps them moving forward in the log as the operation 341c3d2f6cbSMauro Carvalho Chehabprogresses, ensuring that current operation never gets blocked by itself if the 342c3d2f6cbSMauro Carvalho Chehablog wraps around. 343c3d2f6cbSMauro Carvalho Chehab 344c3d2f6cbSMauro Carvalho ChehabHence it can be seen that the relogging operation is fundamental to the correct 345c3d2f6cbSMauro Carvalho Chehabworking of the XFS journalling subsystem. From the above description, most 346c3d2f6cbSMauro Carvalho Chehabpeople should be able to see why the XFS metadata operations writes so much to 347c3d2f6cbSMauro Carvalho Chehabthe log - repeated operations to the same objects write the same changes to 348c3d2f6cbSMauro Carvalho Chehabthe log over and over again. Worse is the fact that objects tend to get 349c3d2f6cbSMauro Carvalho Chehabdirtier as they get relogged, so each subsequent transaction is writing more 350c3d2f6cbSMauro Carvalho Chehabmetadata into the log. 351c3d2f6cbSMauro Carvalho Chehab 35251a117edSDave ChinnerIt should now also be obvious how relogging and asynchronous transactions go 35351a117edSDave Chinnerhand in hand. That is, transactions don't get written to the physical journal 35451a117edSDave Chinneruntil either a log buffer is filled (a log buffer can hold multiple 35551a117edSDave Chinnertransactions) or a synchronous operation forces the log buffers holding the 35651a117edSDave Chinnertransactions to disk. This means that XFS is doing aggregation of transactions 35751a117edSDave Chinnerin memory - batching them, if you like - to minimise the impact of the log IO on 35851a117edSDave Chinnertransaction throughput. 359c3d2f6cbSMauro Carvalho Chehab 360c3d2f6cbSMauro Carvalho ChehabThe limitation on asynchronous transaction throughput is the number and size of 361c3d2f6cbSMauro Carvalho Chehablog buffers made available by the log manager. By default there are 8 log 362c3d2f6cbSMauro Carvalho Chehabbuffers available and the size of each is 32kB - the size can be increased up 363c3d2f6cbSMauro Carvalho Chehabto 256kB by use of a mount option. 364c3d2f6cbSMauro Carvalho Chehab 365c3d2f6cbSMauro Carvalho ChehabEffectively, this gives us the maximum bound of outstanding metadata changes 366c3d2f6cbSMauro Carvalho Chehabthat can be made to the filesystem at any point in time - if all the log 367c3d2f6cbSMauro Carvalho Chehabbuffers are full and under IO, then no more transactions can be committed until 368c3d2f6cbSMauro Carvalho Chehabthe current batch completes. It is now common for a single current CPU core to 369c3d2f6cbSMauro Carvalho Chehabbe to able to issue enough transactions to keep the log buffers full and under 370c3d2f6cbSMauro Carvalho ChehabIO permanently. Hence the XFS journalling subsystem can be considered to be IO 371c3d2f6cbSMauro Carvalho Chehabbound. 372c3d2f6cbSMauro Carvalho Chehab 373c3d2f6cbSMauro Carvalho ChehabDelayed Logging: Concepts 374c3d2f6cbSMauro Carvalho Chehab========================= 375c3d2f6cbSMauro Carvalho Chehab 376c3d2f6cbSMauro Carvalho ChehabThe key thing to note about the asynchronous logging combined with the 377c3d2f6cbSMauro Carvalho Chehabrelogging technique XFS uses is that we can be relogging changed objects 378c3d2f6cbSMauro Carvalho Chehabmultiple times before they are committed to disk in the log buffers. If we 379c3d2f6cbSMauro Carvalho Chehabreturn to the previous relogging example, it is entirely possible that 380c3d2f6cbSMauro Carvalho Chehabtransactions A through D are committed to disk in the same log buffer. 381c3d2f6cbSMauro Carvalho Chehab 382c3d2f6cbSMauro Carvalho ChehabThat is, a single log buffer may contain multiple copies of the same object, 383c3d2f6cbSMauro Carvalho Chehabbut only one of those copies needs to be there - the last one "D", as it 384c3d2f6cbSMauro Carvalho Chehabcontains all the changes from the previous changes. In other words, we have one 385c3d2f6cbSMauro Carvalho Chehabnecessary copy in the log buffer, and three stale copies that are simply 386c3d2f6cbSMauro Carvalho Chehabwasting space. When we are doing repeated operations on the same set of 387c3d2f6cbSMauro Carvalho Chehabobjects, these "stale objects" can be over 90% of the space used in the log 388c3d2f6cbSMauro Carvalho Chehabbuffers. It is clear that reducing the number of stale objects written to the 389c3d2f6cbSMauro Carvalho Chehablog would greatly reduce the amount of metadata we write to the log, and this 390c3d2f6cbSMauro Carvalho Chehabis the fundamental goal of delayed logging. 391c3d2f6cbSMauro Carvalho Chehab 392c3d2f6cbSMauro Carvalho ChehabFrom a conceptual point of view, XFS is already doing relogging in memory (where 393c3d2f6cbSMauro Carvalho Chehabmemory == log buffer), only it is doing it extremely inefficiently. It is using 394c3d2f6cbSMauro Carvalho Chehablogical to physical formatting to do the relogging because there is no 395c3d2f6cbSMauro Carvalho Chehabinfrastructure to keep track of logical changes in memory prior to physically 396c3d2f6cbSMauro Carvalho Chehabformatting the changes in a transaction to the log buffer. Hence we cannot avoid 397c3d2f6cbSMauro Carvalho Chehabaccumulating stale objects in the log buffers. 398c3d2f6cbSMauro Carvalho Chehab 399c3d2f6cbSMauro Carvalho ChehabDelayed logging is the name we've given to keeping and tracking transactional 400c3d2f6cbSMauro Carvalho Chehabchanges to objects in memory outside the log buffer infrastructure. Because of 401c3d2f6cbSMauro Carvalho Chehabthe relogging concept fundamental to the XFS journalling subsystem, this is 402c3d2f6cbSMauro Carvalho Chehabactually relatively easy to do - all the changes to logged items are already 403c3d2f6cbSMauro Carvalho Chehabtracked in the current infrastructure. The big problem is how to accumulate 404c3d2f6cbSMauro Carvalho Chehabthem and get them to the log in a consistent, recoverable manner. 405c3d2f6cbSMauro Carvalho ChehabDescribing the problems and how they have been solved is the focus of this 406c3d2f6cbSMauro Carvalho Chehabdocument. 407c3d2f6cbSMauro Carvalho Chehab 408c3d2f6cbSMauro Carvalho ChehabOne of the key changes that delayed logging makes to the operation of the 409c3d2f6cbSMauro Carvalho Chehabjournalling subsystem is that it disassociates the amount of outstanding 410c3d2f6cbSMauro Carvalho Chehabmetadata changes from the size and number of log buffers available. In other 411c3d2f6cbSMauro Carvalho Chehabwords, instead of there only being a maximum of 2MB of transaction changes not 412c3d2f6cbSMauro Carvalho Chehabwritten to the log at any point in time, there may be a much greater amount 413c3d2f6cbSMauro Carvalho Chehabbeing accumulated in memory. Hence the potential for loss of metadata on a 414c3d2f6cbSMauro Carvalho Chehabcrash is much greater than for the existing logging mechanism. 415c3d2f6cbSMauro Carvalho Chehab 416c3d2f6cbSMauro Carvalho ChehabIt should be noted that this does not change the guarantee that log recovery 417c3d2f6cbSMauro Carvalho Chehabwill result in a consistent filesystem. What it does mean is that as far as the 418c3d2f6cbSMauro Carvalho Chehabrecovered filesystem is concerned, there may be many thousands of transactions 419c3d2f6cbSMauro Carvalho Chehabthat simply did not occur as a result of the crash. This makes it even more 420c3d2f6cbSMauro Carvalho Chehabimportant that applications that care about their data use fsync() where they 421c3d2f6cbSMauro Carvalho Chehabneed to ensure application level data integrity is maintained. 422c3d2f6cbSMauro Carvalho Chehab 423c3d2f6cbSMauro Carvalho ChehabIt should be noted that delayed logging is not an innovative new concept that 424c3d2f6cbSMauro Carvalho Chehabwarrants rigorous proofs to determine whether it is correct or not. The method 425c3d2f6cbSMauro Carvalho Chehabof accumulating changes in memory for some period before writing them to the 426c3d2f6cbSMauro Carvalho Chehablog is used effectively in many filesystems including ext3 and ext4. Hence 427c3d2f6cbSMauro Carvalho Chehabno time is spent in this document trying to convince the reader that the 428c3d2f6cbSMauro Carvalho Chehabconcept is sound. Instead it is simply considered a "solved problem" and as 429c3d2f6cbSMauro Carvalho Chehabsuch implementing it in XFS is purely an exercise in software engineering. 430c3d2f6cbSMauro Carvalho Chehab 431c3d2f6cbSMauro Carvalho ChehabThe fundamental requirements for delayed logging in XFS are simple: 432c3d2f6cbSMauro Carvalho Chehab 433c3d2f6cbSMauro Carvalho Chehab 1. Reduce the amount of metadata written to the log by at least 434c3d2f6cbSMauro Carvalho Chehab an order of magnitude. 435c3d2f6cbSMauro Carvalho Chehab 2. Supply sufficient statistics to validate Requirement #1. 436c3d2f6cbSMauro Carvalho Chehab 3. Supply sufficient new tracing infrastructure to be able to debug 437c3d2f6cbSMauro Carvalho Chehab problems with the new code. 438c3d2f6cbSMauro Carvalho Chehab 4. No on-disk format change (metadata or log format). 439c3d2f6cbSMauro Carvalho Chehab 5. Enable and disable with a mount option. 440c3d2f6cbSMauro Carvalho Chehab 6. No performance regressions for synchronous transaction workloads. 441c3d2f6cbSMauro Carvalho Chehab 442c3d2f6cbSMauro Carvalho ChehabDelayed Logging: Design 443c3d2f6cbSMauro Carvalho Chehab======================= 444c3d2f6cbSMauro Carvalho Chehab 445c3d2f6cbSMauro Carvalho ChehabStoring Changes 446c3d2f6cbSMauro Carvalho Chehab--------------- 447c3d2f6cbSMauro Carvalho Chehab 448c3d2f6cbSMauro Carvalho ChehabThe problem with accumulating changes at a logical level (i.e. just using the 449c3d2f6cbSMauro Carvalho Chehabexisting log item dirty region tracking) is that when it comes to writing the 450c3d2f6cbSMauro Carvalho Chehabchanges to the log buffers, we need to ensure that the object we are formatting 451c3d2f6cbSMauro Carvalho Chehabis not changing while we do this. This requires locking the object to prevent 452c3d2f6cbSMauro Carvalho Chehabconcurrent modification. Hence flushing the logical changes to the log would 453c3d2f6cbSMauro Carvalho Chehabrequire us to lock every object, format them, and then unlock them again. 454c3d2f6cbSMauro Carvalho Chehab 455c3d2f6cbSMauro Carvalho ChehabThis introduces lots of scope for deadlocks with transactions that are already 456c3d2f6cbSMauro Carvalho Chehabrunning. For example, a transaction has object A locked and modified, but needs 457c3d2f6cbSMauro Carvalho Chehabthe delayed logging tracking lock to commit the transaction. However, the 458c3d2f6cbSMauro Carvalho Chehabflushing thread has the delayed logging tracking lock already held, and is 459c3d2f6cbSMauro Carvalho Chehabtrying to get the lock on object A to flush it to the log buffer. This appears 460c3d2f6cbSMauro Carvalho Chehabto be an unsolvable deadlock condition, and it was solving this problem that 461c3d2f6cbSMauro Carvalho Chehabwas the barrier to implementing delayed logging for so long. 462c3d2f6cbSMauro Carvalho Chehab 463c3d2f6cbSMauro Carvalho ChehabThe solution is relatively simple - it just took a long time to recognise it. 464c3d2f6cbSMauro Carvalho ChehabPut simply, the current logging code formats the changes to each item into an 465c3d2f6cbSMauro Carvalho Chehabvector array that points to the changed regions in the item. The log write code 466c3d2f6cbSMauro Carvalho Chehabsimply copies the memory these vectors point to into the log buffer during 467c3d2f6cbSMauro Carvalho Chehabtransaction commit while the item is locked in the transaction. Instead of 468c3d2f6cbSMauro Carvalho Chehabusing the log buffer as the destination of the formatting code, we can use an 469c3d2f6cbSMauro Carvalho Chehaballocated memory buffer big enough to fit the formatted vector. 470c3d2f6cbSMauro Carvalho Chehab 471c3d2f6cbSMauro Carvalho ChehabIf we then copy the vector into the memory buffer and rewrite the vector to 472c3d2f6cbSMauro Carvalho Chehabpoint to the memory buffer rather than the object itself, we now have a copy of 473c3d2f6cbSMauro Carvalho Chehabthe changes in a format that is compatible with the log buffer writing code. 474c3d2f6cbSMauro Carvalho Chehabthat does not require us to lock the item to access. This formatting and 475c3d2f6cbSMauro Carvalho Chehabrewriting can all be done while the object is locked during transaction commit, 476c3d2f6cbSMauro Carvalho Chehabresulting in a vector that is transactionally consistent and can be accessed 477c3d2f6cbSMauro Carvalho Chehabwithout needing to lock the owning item. 478c3d2f6cbSMauro Carvalho Chehab 479c3d2f6cbSMauro Carvalho ChehabHence we avoid the need to lock items when we need to flush outstanding 480c3d2f6cbSMauro Carvalho Chehabasynchronous transactions to the log. The differences between the existing 481c3d2f6cbSMauro Carvalho Chehabformatting method and the delayed logging formatting can be seen in the 482c3d2f6cbSMauro Carvalho Chehabdiagram below. 483c3d2f6cbSMauro Carvalho Chehab 484c3d2f6cbSMauro Carvalho ChehabCurrent format log vector:: 485c3d2f6cbSMauro Carvalho Chehab 486c3d2f6cbSMauro Carvalho Chehab Object +---------------------------------------------+ 487c3d2f6cbSMauro Carvalho Chehab Vector 1 +----+ 488c3d2f6cbSMauro Carvalho Chehab Vector 2 +----+ 489c3d2f6cbSMauro Carvalho Chehab Vector 3 +----------+ 490c3d2f6cbSMauro Carvalho Chehab 491c3d2f6cbSMauro Carvalho ChehabAfter formatting:: 492c3d2f6cbSMauro Carvalho Chehab 493c3d2f6cbSMauro Carvalho Chehab Log Buffer +-V1-+-V2-+----V3----+ 494c3d2f6cbSMauro Carvalho Chehab 495c3d2f6cbSMauro Carvalho ChehabDelayed logging vector:: 496c3d2f6cbSMauro Carvalho Chehab 497c3d2f6cbSMauro Carvalho Chehab Object +---------------------------------------------+ 498c3d2f6cbSMauro Carvalho Chehab Vector 1 +----+ 499c3d2f6cbSMauro Carvalho Chehab Vector 2 +----+ 500c3d2f6cbSMauro Carvalho Chehab Vector 3 +----------+ 501c3d2f6cbSMauro Carvalho Chehab 502c3d2f6cbSMauro Carvalho ChehabAfter formatting:: 503c3d2f6cbSMauro Carvalho Chehab 504c3d2f6cbSMauro Carvalho Chehab Memory Buffer +-V1-+-V2-+----V3----+ 505c3d2f6cbSMauro Carvalho Chehab Vector 1 +----+ 506c3d2f6cbSMauro Carvalho Chehab Vector 2 +----+ 507c3d2f6cbSMauro Carvalho Chehab Vector 3 +----------+ 508c3d2f6cbSMauro Carvalho Chehab 509c3d2f6cbSMauro Carvalho ChehabThe memory buffer and associated vector need to be passed as a single object, 510c3d2f6cbSMauro Carvalho Chehabbut still need to be associated with the parent object so if the object is 511c3d2f6cbSMauro Carvalho Chehabrelogged we can replace the current memory buffer with a new memory buffer that 512c3d2f6cbSMauro Carvalho Chehabcontains the latest changes. 513c3d2f6cbSMauro Carvalho Chehab 514c3d2f6cbSMauro Carvalho ChehabThe reason for keeping the vector around after we've formatted the memory 515c3d2f6cbSMauro Carvalho Chehabbuffer is to support splitting vectors across log buffer boundaries correctly. 516c3d2f6cbSMauro Carvalho ChehabIf we don't keep the vector around, we do not know where the region boundaries 517c3d2f6cbSMauro Carvalho Chehabare in the item, so we'd need a new encapsulation method for regions in the log 518c3d2f6cbSMauro Carvalho Chehabbuffer writing (i.e. double encapsulation). This would be an on-disk format 519c3d2f6cbSMauro Carvalho Chehabchange and as such is not desirable. It also means we'd have to write the log 520c3d2f6cbSMauro Carvalho Chehabregion headers in the formatting stage, which is problematic as there is per 521c3d2f6cbSMauro Carvalho Chehabregion state that needs to be placed into the headers during the log write. 522c3d2f6cbSMauro Carvalho Chehab 523c3d2f6cbSMauro Carvalho ChehabHence we need to keep the vector, but by attaching the memory buffer to it and 524c3d2f6cbSMauro Carvalho Chehabrewriting the vector addresses to point at the memory buffer we end up with a 525c3d2f6cbSMauro Carvalho Chehabself-describing object that can be passed to the log buffer write code to be 526c3d2f6cbSMauro Carvalho Chehabhandled in exactly the same manner as the existing log vectors are handled. 527c3d2f6cbSMauro Carvalho ChehabHence we avoid needing a new on-disk format to handle items that have been 528c3d2f6cbSMauro Carvalho Chehabrelogged in memory. 529c3d2f6cbSMauro Carvalho Chehab 530c3d2f6cbSMauro Carvalho Chehab 531c3d2f6cbSMauro Carvalho ChehabTracking Changes 532c3d2f6cbSMauro Carvalho Chehab---------------- 533c3d2f6cbSMauro Carvalho Chehab 534c3d2f6cbSMauro Carvalho ChehabNow that we can record transactional changes in memory in a form that allows 535c3d2f6cbSMauro Carvalho Chehabthem to be used without limitations, we need to be able to track and accumulate 536c3d2f6cbSMauro Carvalho Chehabthem so that they can be written to the log at some later point in time. The 537c3d2f6cbSMauro Carvalho Chehablog item is the natural place to store this vector and buffer, and also makes sense 538c3d2f6cbSMauro Carvalho Chehabto be the object that is used to track committed objects as it will always 539c3d2f6cbSMauro Carvalho Chehabexist once the object has been included in a transaction. 540c3d2f6cbSMauro Carvalho Chehab 541c3d2f6cbSMauro Carvalho ChehabThe log item is already used to track the log items that have been written to 542c3d2f6cbSMauro Carvalho Chehabthe log but not yet written to disk. Such log items are considered "active" 543c3d2f6cbSMauro Carvalho Chehaband as such are stored in the Active Item List (AIL) which is a LSN-ordered 544c3d2f6cbSMauro Carvalho Chehabdouble linked list. Items are inserted into this list during log buffer IO 545c3d2f6cbSMauro Carvalho Chehabcompletion, after which they are unpinned and can be written to disk. An object 546c3d2f6cbSMauro Carvalho Chehabthat is in the AIL can be relogged, which causes the object to be pinned again 547c3d2f6cbSMauro Carvalho Chehaband then moved forward in the AIL when the log buffer IO completes for that 548c3d2f6cbSMauro Carvalho Chehabtransaction. 549c3d2f6cbSMauro Carvalho Chehab 550c3d2f6cbSMauro Carvalho ChehabEssentially, this shows that an item that is in the AIL can still be modified 551c3d2f6cbSMauro Carvalho Chehaband relogged, so any tracking must be separate to the AIL infrastructure. As 552c3d2f6cbSMauro Carvalho Chehabsuch, we cannot reuse the AIL list pointers for tracking committed items, nor 553c3d2f6cbSMauro Carvalho Chehabcan we store state in any field that is protected by the AIL lock. Hence the 554*622d6f19SRandy Dunlapcommitted item tracking needs its own locks, lists and state fields in the log 555c3d2f6cbSMauro Carvalho Chehabitem. 556c3d2f6cbSMauro Carvalho Chehab 557c3d2f6cbSMauro Carvalho ChehabSimilar to the AIL, tracking of committed items is done through a new list 558c3d2f6cbSMauro Carvalho Chehabcalled the Committed Item List (CIL). The list tracks log items that have been 559c3d2f6cbSMauro Carvalho Chehabcommitted and have formatted memory buffers attached to them. It tracks objects 560c3d2f6cbSMauro Carvalho Chehabin transaction commit order, so when an object is relogged it is removed from 561*622d6f19SRandy Dunlapits place in the list and re-inserted at the tail. This is entirely arbitrary 562c3d2f6cbSMauro Carvalho Chehaband done to make it easy for debugging - the last items in the list are the 563c3d2f6cbSMauro Carvalho Chehabones that are most recently modified. Ordering of the CIL is not necessary for 564c3d2f6cbSMauro Carvalho Chehabtransactional integrity (as discussed in the next section) so the ordering is 565c3d2f6cbSMauro Carvalho Chehabdone for convenience/sanity of the developers. 566c3d2f6cbSMauro Carvalho Chehab 567c3d2f6cbSMauro Carvalho Chehab 568c3d2f6cbSMauro Carvalho ChehabDelayed Logging: Checkpoints 569c3d2f6cbSMauro Carvalho Chehab---------------------------- 570c3d2f6cbSMauro Carvalho Chehab 571c3d2f6cbSMauro Carvalho ChehabWhen we have a log synchronisation event, commonly known as a "log force", 572c3d2f6cbSMauro Carvalho Chehaball the items in the CIL must be written into the log via the log buffers. 573c3d2f6cbSMauro Carvalho ChehabWe need to write these items in the order that they exist in the CIL, and they 574c3d2f6cbSMauro Carvalho Chehabneed to be written as an atomic transaction. The need for all the objects to be 575c3d2f6cbSMauro Carvalho Chehabwritten as an atomic transaction comes from the requirements of relogging and 576c3d2f6cbSMauro Carvalho Chehablog replay - all the changes in all the objects in a given transaction must 577c3d2f6cbSMauro Carvalho Chehabeither be completely replayed during log recovery, or not replayed at all. If 578c3d2f6cbSMauro Carvalho Chehaba transaction is not replayed because it is not complete in the log, then 579c3d2f6cbSMauro Carvalho Chehabno later transactions should be replayed, either. 580c3d2f6cbSMauro Carvalho Chehab 581c3d2f6cbSMauro Carvalho ChehabTo fulfill this requirement, we need to write the entire CIL in a single log 582c3d2f6cbSMauro Carvalho Chehabtransaction. Fortunately, the XFS log code has no fixed limit on the size of a 583c3d2f6cbSMauro Carvalho Chehabtransaction, nor does the log replay code. The only fundamental limit is that 584c3d2f6cbSMauro Carvalho Chehabthe transaction cannot be larger than just under half the size of the log. The 585c3d2f6cbSMauro Carvalho Chehabreason for this limit is that to find the head and tail of the log, there must 586c3d2f6cbSMauro Carvalho Chehabbe at least one complete transaction in the log at any given time. If a 587c3d2f6cbSMauro Carvalho Chehabtransaction is larger than half the log, then there is the possibility that a 588c3d2f6cbSMauro Carvalho Chehabcrash during the write of a such a transaction could partially overwrite the 589c3d2f6cbSMauro Carvalho Chehabonly complete previous transaction in the log. This will result in a recovery 590c3d2f6cbSMauro Carvalho Chehabfailure and an inconsistent filesystem and hence we must enforce the maximum 591c3d2f6cbSMauro Carvalho Chehabsize of a checkpoint to be slightly less than a half the log. 592c3d2f6cbSMauro Carvalho Chehab 593c3d2f6cbSMauro Carvalho ChehabApart from this size requirement, a checkpoint transaction looks no different 594c3d2f6cbSMauro Carvalho Chehabto any other transaction - it contains a transaction header, a series of 595c3d2f6cbSMauro Carvalho Chehabformatted log items and a commit record at the tail. From a recovery 596c3d2f6cbSMauro Carvalho Chehabperspective, the checkpoint transaction is also no different - just a lot 597c3d2f6cbSMauro Carvalho Chehabbigger with a lot more items in it. The worst case effect of this is that we 598c3d2f6cbSMauro Carvalho Chehabmight need to tune the recovery transaction object hash size. 599c3d2f6cbSMauro Carvalho Chehab 600c3d2f6cbSMauro Carvalho ChehabBecause the checkpoint is just another transaction and all the changes to log 601c3d2f6cbSMauro Carvalho Chehabitems are stored as log vectors, we can use the existing log buffer writing 602c3d2f6cbSMauro Carvalho Chehabcode to write the changes into the log. To do this efficiently, we need to 603c3d2f6cbSMauro Carvalho Chehabminimise the time we hold the CIL locked while writing the checkpoint 604c3d2f6cbSMauro Carvalho Chehabtransaction. The current log write code enables us to do this easily with the 605c3d2f6cbSMauro Carvalho Chehabway it separates the writing of the transaction contents (the log vectors) from 606c3d2f6cbSMauro Carvalho Chehabthe transaction commit record, but tracking this requires us to have a 607c3d2f6cbSMauro Carvalho Chehabper-checkpoint context that travels through the log write process through to 608c3d2f6cbSMauro Carvalho Chehabcheckpoint completion. 609c3d2f6cbSMauro Carvalho Chehab 610c3d2f6cbSMauro Carvalho ChehabHence a checkpoint has a context that tracks the state of the current 611c3d2f6cbSMauro Carvalho Chehabcheckpoint from initiation to checkpoint completion. A new context is initiated 612c3d2f6cbSMauro Carvalho Chehabat the same time a checkpoint transaction is started. That is, when we remove 613c3d2f6cbSMauro Carvalho Chehaball the current items from the CIL during a checkpoint operation, we move all 614c3d2f6cbSMauro Carvalho Chehabthose changes into the current checkpoint context. We then initialise a new 615c3d2f6cbSMauro Carvalho Chehabcontext and attach that to the CIL for aggregation of new transactions. 616c3d2f6cbSMauro Carvalho Chehab 617c3d2f6cbSMauro Carvalho ChehabThis allows us to unlock the CIL immediately after transfer of all the 618021904f3SZhao Mengmengcommitted items and effectively allows new transactions to be issued while we 619c3d2f6cbSMauro Carvalho Chehabare formatting the checkpoint into the log. It also allows concurrent 620c3d2f6cbSMauro Carvalho Chehabcheckpoints to be written into the log buffers in the case of log force heavy 621c3d2f6cbSMauro Carvalho Chehabworkloads, just like the existing transaction commit code does. This, however, 622c3d2f6cbSMauro Carvalho Chehabrequires that we strictly order the commit records in the log so that 623c3d2f6cbSMauro Carvalho Chehabcheckpoint sequence order is maintained during log replay. 624c3d2f6cbSMauro Carvalho Chehab 625c3d2f6cbSMauro Carvalho ChehabTo ensure that we can be writing an item into a checkpoint transaction at 626c3d2f6cbSMauro Carvalho Chehabthe same time another transaction modifies the item and inserts the log item 627c3d2f6cbSMauro Carvalho Chehabinto the new CIL, then checkpoint transaction commit code cannot use log items 628c3d2f6cbSMauro Carvalho Chehabto store the list of log vectors that need to be written into the transaction. 629c3d2f6cbSMauro Carvalho ChehabHence log vectors need to be able to be chained together to allow them to be 630c3d2f6cbSMauro Carvalho Chehabdetached from the log items. That is, when the CIL is flushed the memory 631c3d2f6cbSMauro Carvalho Chehabbuffer and log vector attached to each log item needs to be attached to the 632c3d2f6cbSMauro Carvalho Chehabcheckpoint context so that the log item can be released. In diagrammatic form, 633c3d2f6cbSMauro Carvalho Chehabthe CIL would look like this before the flush:: 634c3d2f6cbSMauro Carvalho Chehab 635c3d2f6cbSMauro Carvalho Chehab CIL Head 636c3d2f6cbSMauro Carvalho Chehab | 637c3d2f6cbSMauro Carvalho Chehab V 638c3d2f6cbSMauro Carvalho Chehab Log Item <-> log vector 1 -> memory buffer 639c3d2f6cbSMauro Carvalho Chehab | -> vector array 640c3d2f6cbSMauro Carvalho Chehab V 641c3d2f6cbSMauro Carvalho Chehab Log Item <-> log vector 2 -> memory buffer 642c3d2f6cbSMauro Carvalho Chehab | -> vector array 643c3d2f6cbSMauro Carvalho Chehab V 644c3d2f6cbSMauro Carvalho Chehab ...... 645c3d2f6cbSMauro Carvalho Chehab | 646c3d2f6cbSMauro Carvalho Chehab V 647c3d2f6cbSMauro Carvalho Chehab Log Item <-> log vector N-1 -> memory buffer 648c3d2f6cbSMauro Carvalho Chehab | -> vector array 649c3d2f6cbSMauro Carvalho Chehab V 650c3d2f6cbSMauro Carvalho Chehab Log Item <-> log vector N -> memory buffer 651c3d2f6cbSMauro Carvalho Chehab -> vector array 652c3d2f6cbSMauro Carvalho Chehab 653c3d2f6cbSMauro Carvalho ChehabAnd after the flush the CIL head is empty, and the checkpoint context log 654c3d2f6cbSMauro Carvalho Chehabvector list would look like:: 655c3d2f6cbSMauro Carvalho Chehab 656c3d2f6cbSMauro Carvalho Chehab Checkpoint Context 657c3d2f6cbSMauro Carvalho Chehab | 658c3d2f6cbSMauro Carvalho Chehab V 659c3d2f6cbSMauro Carvalho Chehab log vector 1 -> memory buffer 660c3d2f6cbSMauro Carvalho Chehab | -> vector array 661c3d2f6cbSMauro Carvalho Chehab | -> Log Item 662c3d2f6cbSMauro Carvalho Chehab V 663c3d2f6cbSMauro Carvalho Chehab log vector 2 -> memory buffer 664c3d2f6cbSMauro Carvalho Chehab | -> vector array 665c3d2f6cbSMauro Carvalho Chehab | -> Log Item 666c3d2f6cbSMauro Carvalho Chehab V 667c3d2f6cbSMauro Carvalho Chehab ...... 668c3d2f6cbSMauro Carvalho Chehab | 669c3d2f6cbSMauro Carvalho Chehab V 670c3d2f6cbSMauro Carvalho Chehab log vector N-1 -> memory buffer 671c3d2f6cbSMauro Carvalho Chehab | -> vector array 672c3d2f6cbSMauro Carvalho Chehab | -> Log Item 673c3d2f6cbSMauro Carvalho Chehab V 674c3d2f6cbSMauro Carvalho Chehab log vector N -> memory buffer 675c3d2f6cbSMauro Carvalho Chehab -> vector array 676c3d2f6cbSMauro Carvalho Chehab -> Log Item 677c3d2f6cbSMauro Carvalho Chehab 678c3d2f6cbSMauro Carvalho ChehabOnce this transfer is done, the CIL can be unlocked and new transactions can 679c3d2f6cbSMauro Carvalho Chehabstart, while the checkpoint flush code works over the log vector chain to 680c3d2f6cbSMauro Carvalho Chehabcommit the checkpoint. 681c3d2f6cbSMauro Carvalho Chehab 682c3d2f6cbSMauro Carvalho ChehabOnce the checkpoint is written into the log buffers, the checkpoint context is 683c3d2f6cbSMauro Carvalho Chehabattached to the log buffer that the commit record was written to along with a 684c3d2f6cbSMauro Carvalho Chehabcompletion callback. Log IO completion will call that callback, which can then 685c3d2f6cbSMauro Carvalho Chehabrun transaction committed processing for the log items (i.e. insert into AIL 686c3d2f6cbSMauro Carvalho Chehaband unpin) in the log vector chain and then free the log vector chain and 687c3d2f6cbSMauro Carvalho Chehabcheckpoint context. 688c3d2f6cbSMauro Carvalho Chehab 689c3d2f6cbSMauro Carvalho ChehabDiscussion Point: I am uncertain as to whether the log item is the most 690c3d2f6cbSMauro Carvalho Chehabefficient way to track vectors, even though it seems like the natural way to do 691c3d2f6cbSMauro Carvalho Chehabit. The fact that we walk the log items (in the CIL) just to chain the log 692c3d2f6cbSMauro Carvalho Chehabvectors and break the link between the log item and the log vector means that 693c3d2f6cbSMauro Carvalho Chehabwe take a cache line hit for the log item list modification, then another for 694c3d2f6cbSMauro Carvalho Chehabthe log vector chaining. If we track by the log vectors, then we only need to 695c3d2f6cbSMauro Carvalho Chehabbreak the link between the log item and the log vector, which means we should 696c3d2f6cbSMauro Carvalho Chehabdirty only the log item cachelines. Normally I wouldn't be concerned about one 697c3d2f6cbSMauro Carvalho Chehabvs two dirty cachelines except for the fact I've seen upwards of 80,000 log 698c3d2f6cbSMauro Carvalho Chehabvectors in one checkpoint transaction. I'd guess this is a "measure and 699c3d2f6cbSMauro Carvalho Chehabcompare" situation that can be done after a working and reviewed implementation 700c3d2f6cbSMauro Carvalho Chehabis in the dev tree.... 701c3d2f6cbSMauro Carvalho Chehab 702c3d2f6cbSMauro Carvalho ChehabDelayed Logging: Checkpoint Sequencing 703c3d2f6cbSMauro Carvalho Chehab-------------------------------------- 704c3d2f6cbSMauro Carvalho Chehab 705c3d2f6cbSMauro Carvalho ChehabOne of the key aspects of the XFS transaction subsystem is that it tags 706c3d2f6cbSMauro Carvalho Chehabcommitted transactions with the log sequence number of the transaction commit. 707c3d2f6cbSMauro Carvalho ChehabThis allows transactions to be issued asynchronously even though there may be 708c3d2f6cbSMauro Carvalho Chehabfuture operations that cannot be completed until that transaction is fully 709c3d2f6cbSMauro Carvalho Chehabcommitted to the log. In the rare case that a dependent operation occurs (e.g. 710c3d2f6cbSMauro Carvalho Chehabre-using a freed metadata extent for a data extent), a special, optimised log 711c3d2f6cbSMauro Carvalho Chehabforce can be issued to force the dependent transaction to disk immediately. 712c3d2f6cbSMauro Carvalho Chehab 713c3d2f6cbSMauro Carvalho ChehabTo do this, transactions need to record the LSN of the commit record of the 714c3d2f6cbSMauro Carvalho Chehabtransaction. This LSN comes directly from the log buffer the transaction is 715c3d2f6cbSMauro Carvalho Chehabwritten into. While this works just fine for the existing transaction 716c3d2f6cbSMauro Carvalho Chehabmechanism, it does not work for delayed logging because transactions are not 717c3d2f6cbSMauro Carvalho Chehabwritten directly into the log buffers. Hence some other method of sequencing 718c3d2f6cbSMauro Carvalho Chehabtransactions is required. 719c3d2f6cbSMauro Carvalho Chehab 720c3d2f6cbSMauro Carvalho ChehabAs discussed in the checkpoint section, delayed logging uses per-checkpoint 721c3d2f6cbSMauro Carvalho Chehabcontexts, and as such it is simple to assign a sequence number to each 722c3d2f6cbSMauro Carvalho Chehabcheckpoint. Because the switching of checkpoint contexts must be done 723c3d2f6cbSMauro Carvalho Chehabatomically, it is simple to ensure that each new context has a monotonically 724c3d2f6cbSMauro Carvalho Chehabincreasing sequence number assigned to it without the need for an external 725c3d2f6cbSMauro Carvalho Chehabatomic counter - we can just take the current context sequence number and add 726c3d2f6cbSMauro Carvalho Chehabone to it for the new context. 727c3d2f6cbSMauro Carvalho Chehab 728c3d2f6cbSMauro Carvalho ChehabThen, instead of assigning a log buffer LSN to the transaction commit LSN 729c3d2f6cbSMauro Carvalho Chehabduring the commit, we can assign the current checkpoint sequence. This allows 730c3d2f6cbSMauro Carvalho Chehaboperations that track transactions that have not yet completed know what 731c3d2f6cbSMauro Carvalho Chehabcheckpoint sequence needs to be committed before they can continue. As a 732c3d2f6cbSMauro Carvalho Chehabresult, the code that forces the log to a specific LSN now needs to ensure that 733c3d2f6cbSMauro Carvalho Chehabthe log forces to a specific checkpoint. 734c3d2f6cbSMauro Carvalho Chehab 735c3d2f6cbSMauro Carvalho ChehabTo ensure that we can do this, we need to track all the checkpoint contexts 736c3d2f6cbSMauro Carvalho Chehabthat are currently committing to the log. When we flush a checkpoint, the 737c3d2f6cbSMauro Carvalho Chehabcontext gets added to a "committing" list which can be searched. When a 738c3d2f6cbSMauro Carvalho Chehabcheckpoint commit completes, it is removed from the committing list. Because 739c3d2f6cbSMauro Carvalho Chehabthe checkpoint context records the LSN of the commit record for the checkpoint, 740c3d2f6cbSMauro Carvalho Chehabwe can also wait on the log buffer that contains the commit record, thereby 741c3d2f6cbSMauro Carvalho Chehabusing the existing log force mechanisms to execute synchronous forces. 742c3d2f6cbSMauro Carvalho Chehab 743c3d2f6cbSMauro Carvalho ChehabIt should be noted that the synchronous forces may need to be extended with 744c3d2f6cbSMauro Carvalho Chehabmitigation algorithms similar to the current log buffer code to allow 745c3d2f6cbSMauro Carvalho Chehabaggregation of multiple synchronous transactions if there are already 746c3d2f6cbSMauro Carvalho Chehabsynchronous transactions being flushed. Investigation of the performance of the 747c3d2f6cbSMauro Carvalho Chehabcurrent design is needed before making any decisions here. 748c3d2f6cbSMauro Carvalho Chehab 749c3d2f6cbSMauro Carvalho ChehabThe main concern with log forces is to ensure that all the previous checkpoints 750c3d2f6cbSMauro Carvalho Chehabare also committed to disk before the one we need to wait for. Therefore we 751c3d2f6cbSMauro Carvalho Chehabneed to check that all the prior contexts in the committing list are also 752c3d2f6cbSMauro Carvalho Chehabcomplete before waiting on the one we need to complete. We do this 753c3d2f6cbSMauro Carvalho Chehabsynchronisation in the log force code so that we don't need to wait anywhere 754c3d2f6cbSMauro Carvalho Chehabelse for such serialisation - it only matters when we do a log force. 755c3d2f6cbSMauro Carvalho Chehab 756c3d2f6cbSMauro Carvalho ChehabThe only remaining complexity is that a log force now also has to handle the 757c3d2f6cbSMauro Carvalho Chehabcase where the forcing sequence number is the same as the current context. That 758c3d2f6cbSMauro Carvalho Chehabis, we need to flush the CIL and potentially wait for it to complete. This is a 759c3d2f6cbSMauro Carvalho Chehabsimple addition to the existing log forcing code to check the sequence numbers 760c3d2f6cbSMauro Carvalho Chehaband push if required. Indeed, placing the current sequence checkpoint flush in 761c3d2f6cbSMauro Carvalho Chehabthe log force code enables the current mechanism for issuing synchronous 762c3d2f6cbSMauro Carvalho Chehabtransactions to remain untouched (i.e. commit an asynchronous transaction, then 763c3d2f6cbSMauro Carvalho Chehabforce the log at the LSN of that transaction) and so the higher level code 764c3d2f6cbSMauro Carvalho Chehabbehaves the same regardless of whether delayed logging is being used or not. 765c3d2f6cbSMauro Carvalho Chehab 766c3d2f6cbSMauro Carvalho ChehabDelayed Logging: Checkpoint Log Space Accounting 767c3d2f6cbSMauro Carvalho Chehab------------------------------------------------ 768c3d2f6cbSMauro Carvalho Chehab 769c3d2f6cbSMauro Carvalho ChehabThe big issue for a checkpoint transaction is the log space reservation for the 770c3d2f6cbSMauro Carvalho Chehabtransaction. We don't know how big a checkpoint transaction is going to be 771c3d2f6cbSMauro Carvalho Chehabahead of time, nor how many log buffers it will take to write out, nor the 772c3d2f6cbSMauro Carvalho Chehabnumber of split log vector regions are going to be used. We can track the 773c3d2f6cbSMauro Carvalho Chehabamount of log space required as we add items to the commit item list, but we 774c3d2f6cbSMauro Carvalho Chehabstill need to reserve the space in the log for the checkpoint. 775c3d2f6cbSMauro Carvalho Chehab 776c3d2f6cbSMauro Carvalho ChehabA typical transaction reserves enough space in the log for the worst case space 777c3d2f6cbSMauro Carvalho Chehabusage of the transaction. The reservation accounts for log record headers, 778c3d2f6cbSMauro Carvalho Chehabtransaction and region headers, headers for split regions, buffer tail padding, 779c3d2f6cbSMauro Carvalho Chehabetc. as well as the actual space for all the changed metadata in the 780c3d2f6cbSMauro Carvalho Chehabtransaction. While some of this is fixed overhead, much of it is dependent on 781c3d2f6cbSMauro Carvalho Chehabthe size of the transaction and the number of regions being logged (the number 782c3d2f6cbSMauro Carvalho Chehabof log vectors in the transaction). 783c3d2f6cbSMauro Carvalho Chehab 784c3d2f6cbSMauro Carvalho ChehabAn example of the differences would be logging directory changes versus logging 785c3d2f6cbSMauro Carvalho Chehabinode changes. If you modify lots of inode cores (e.g. ``chmod -R g+w *``), then 786c3d2f6cbSMauro Carvalho Chehabthere are lots of transactions that only contain an inode core and an inode log 787c3d2f6cbSMauro Carvalho Chehabformat structure. That is, two vectors totaling roughly 150 bytes. If we modify 788c3d2f6cbSMauro Carvalho Chehab10,000 inodes, we have about 1.5MB of metadata to write in 20,000 vectors. Each 789c3d2f6cbSMauro Carvalho Chehabvector is 12 bytes, so the total to be logged is approximately 1.75MB. In 790c3d2f6cbSMauro Carvalho Chehabcomparison, if we are logging full directory buffers, they are typically 4KB 791c3d2f6cbSMauro Carvalho Chehabeach, so we in 1.5MB of directory buffers we'd have roughly 400 buffers and a 792c3d2f6cbSMauro Carvalho Chehabbuffer format structure for each buffer - roughly 800 vectors or 1.51MB total 793c3d2f6cbSMauro Carvalho Chehabspace. From this, it should be obvious that a static log space reservation is 794c3d2f6cbSMauro Carvalho Chehabnot particularly flexible and is difficult to select the "optimal value" for 795c3d2f6cbSMauro Carvalho Chehaball workloads. 796c3d2f6cbSMauro Carvalho Chehab 797c3d2f6cbSMauro Carvalho ChehabFurther, if we are going to use a static reservation, which bit of the entire 798c3d2f6cbSMauro Carvalho Chehabreservation does it cover? We account for space used by the transaction 799c3d2f6cbSMauro Carvalho Chehabreservation by tracking the space currently used by the object in the CIL and 800c3d2f6cbSMauro Carvalho Chehabthen calculating the increase or decrease in space used as the object is 801c3d2f6cbSMauro Carvalho Chehabrelogged. This allows for a checkpoint reservation to only have to account for 802c3d2f6cbSMauro Carvalho Chehablog buffer metadata used such as log header records. 803c3d2f6cbSMauro Carvalho Chehab 804c3d2f6cbSMauro Carvalho ChehabHowever, even using a static reservation for just the log metadata is 805c3d2f6cbSMauro Carvalho Chehabproblematic. Typically log record headers use at least 16KB of log space per 806c3d2f6cbSMauro Carvalho Chehab1MB of log space consumed (512 bytes per 32k) and the reservation needs to be 807c3d2f6cbSMauro Carvalho Chehablarge enough to handle arbitrary sized checkpoint transactions. This 808c3d2f6cbSMauro Carvalho Chehabreservation needs to be made before the checkpoint is started, and we need to 809c3d2f6cbSMauro Carvalho Chehabbe able to reserve the space without sleeping. For a 8MB checkpoint, we need a 810c3d2f6cbSMauro Carvalho Chehabreservation of around 150KB, which is a non-trivial amount of space. 811c3d2f6cbSMauro Carvalho Chehab 812c3d2f6cbSMauro Carvalho ChehabA static reservation needs to manipulate the log grant counters - we can take a 813c3d2f6cbSMauro Carvalho Chehabpermanent reservation on the space, but we still need to make sure we refresh 814c3d2f6cbSMauro Carvalho Chehabthe write reservation (the actual space available to the transaction) after 815c3d2f6cbSMauro Carvalho Chehabevery checkpoint transaction completion. Unfortunately, if this space is not 816c3d2f6cbSMauro Carvalho Chehabavailable when required, then the regrant code will sleep waiting for it. 817c3d2f6cbSMauro Carvalho Chehab 818c3d2f6cbSMauro Carvalho ChehabThe problem with this is that it can lead to deadlocks as we may need to commit 819c3d2f6cbSMauro Carvalho Chehabcheckpoints to be able to free up log space (refer back to the description of 820c3d2f6cbSMauro Carvalho Chehabrolling transactions for an example of this). Hence we *must* always have 821c3d2f6cbSMauro Carvalho Chehabspace available in the log if we are to use static reservations, and that is 822c3d2f6cbSMauro Carvalho Chehabvery difficult and complex to arrange. It is possible to do, but there is a 823c3d2f6cbSMauro Carvalho Chehabsimpler way. 824c3d2f6cbSMauro Carvalho Chehab 825c3d2f6cbSMauro Carvalho ChehabThe simpler way of doing this is tracking the entire log space used by the 826c3d2f6cbSMauro Carvalho Chehabitems in the CIL and using this to dynamically calculate the amount of log 827c3d2f6cbSMauro Carvalho Chehabspace required by the log metadata. If this log metadata space changes as a 828c3d2f6cbSMauro Carvalho Chehabresult of a transaction commit inserting a new memory buffer into the CIL, then 829c3d2f6cbSMauro Carvalho Chehabthe difference in space required is removed from the transaction that causes 830c3d2f6cbSMauro Carvalho Chehabthe change. Transactions at this level will *always* have enough space 831c3d2f6cbSMauro Carvalho Chehabavailable in their reservation for this as they have already reserved the 832c3d2f6cbSMauro Carvalho Chehabmaximal amount of log metadata space they require, and such a delta reservation 833c3d2f6cbSMauro Carvalho Chehabwill always be less than or equal to the maximal amount in the reservation. 834c3d2f6cbSMauro Carvalho Chehab 835c3d2f6cbSMauro Carvalho ChehabHence we can grow the checkpoint transaction reservation dynamically as items 836c3d2f6cbSMauro Carvalho Chehabare added to the CIL and avoid the need for reserving and regranting log space 837c3d2f6cbSMauro Carvalho Chehabup front. This avoids deadlocks and removes a blocking point from the 838c3d2f6cbSMauro Carvalho Chehabcheckpoint flush code. 839c3d2f6cbSMauro Carvalho Chehab 840c3d2f6cbSMauro Carvalho ChehabAs mentioned early, transactions can't grow to more than half the size of the 841c3d2f6cbSMauro Carvalho Chehablog. Hence as part of the reservation growing, we need to also check the size 842c3d2f6cbSMauro Carvalho Chehabof the reservation against the maximum allowed transaction size. If we reach 843c3d2f6cbSMauro Carvalho Chehabthe maximum threshold, we need to push the CIL to the log. This is effectively 844c3d2f6cbSMauro Carvalho Chehaba "background flush" and is done on demand. This is identical to 845c3d2f6cbSMauro Carvalho Chehaba CIL push triggered by a log force, only that there is no waiting for the 846c3d2f6cbSMauro Carvalho Chehabcheckpoint commit to complete. This background push is checked and executed by 847c3d2f6cbSMauro Carvalho Chehabtransaction commit code. 848c3d2f6cbSMauro Carvalho Chehab 849c3d2f6cbSMauro Carvalho ChehabIf the transaction subsystem goes idle while we still have items in the CIL, 850c3d2f6cbSMauro Carvalho Chehabthey will be flushed by the periodic log force issued by the xfssyncd. This log 851c3d2f6cbSMauro Carvalho Chehabforce will push the CIL to disk, and if the transaction subsystem stays idle, 852c3d2f6cbSMauro Carvalho Chehaballow the idle log to be covered (effectively marked clean) in exactly the same 853c3d2f6cbSMauro Carvalho Chehabmanner that is done for the existing logging method. A discussion point is 854c3d2f6cbSMauro Carvalho Chehabwhether this log force needs to be done more frequently than the current rate 855c3d2f6cbSMauro Carvalho Chehabwhich is once every 30s. 856c3d2f6cbSMauro Carvalho Chehab 857c3d2f6cbSMauro Carvalho Chehab 858c3d2f6cbSMauro Carvalho ChehabDelayed Logging: Log Item Pinning 859c3d2f6cbSMauro Carvalho Chehab--------------------------------- 860c3d2f6cbSMauro Carvalho Chehab 861c3d2f6cbSMauro Carvalho ChehabCurrently log items are pinned during transaction commit while the items are 862c3d2f6cbSMauro Carvalho Chehabstill locked. This happens just after the items are formatted, though it could 863c3d2f6cbSMauro Carvalho Chehabbe done any time before the items are unlocked. The result of this mechanism is 864c3d2f6cbSMauro Carvalho Chehabthat items get pinned once for every transaction that is committed to the log 865c3d2f6cbSMauro Carvalho Chehabbuffers. Hence items that are relogged in the log buffers will have a pin count 866c3d2f6cbSMauro Carvalho Chehabfor every outstanding transaction they were dirtied in. When each of these 867c3d2f6cbSMauro Carvalho Chehabtransactions is completed, they will unpin the item once. As a result, the item 868c3d2f6cbSMauro Carvalho Chehabonly becomes unpinned when all the transactions complete and there are no 869c3d2f6cbSMauro Carvalho Chehabpending transactions. Thus the pinning and unpinning of a log item is symmetric 870c3d2f6cbSMauro Carvalho Chehabas there is a 1:1 relationship with transaction commit and log item completion. 871c3d2f6cbSMauro Carvalho Chehab 872c3d2f6cbSMauro Carvalho ChehabFor delayed logging, however, we have an asymmetric transaction commit to 873c3d2f6cbSMauro Carvalho Chehabcompletion relationship. Every time an object is relogged in the CIL it goes 874c3d2f6cbSMauro Carvalho Chehabthrough the commit process without a corresponding completion being registered. 875c3d2f6cbSMauro Carvalho ChehabThat is, we now have a many-to-one relationship between transaction commit and 876c3d2f6cbSMauro Carvalho Chehablog item completion. The result of this is that pinning and unpinning of the 877c3d2f6cbSMauro Carvalho Chehablog items becomes unbalanced if we retain the "pin on transaction commit, unpin 878c3d2f6cbSMauro Carvalho Chehabon transaction completion" model. 879c3d2f6cbSMauro Carvalho Chehab 880c3d2f6cbSMauro Carvalho ChehabTo keep pin/unpin symmetry, the algorithm needs to change to a "pin on 881c3d2f6cbSMauro Carvalho Chehabinsertion into the CIL, unpin on checkpoint completion". In other words, the 882c3d2f6cbSMauro Carvalho Chehabpinning and unpinning becomes symmetric around a checkpoint context. We have to 883c3d2f6cbSMauro Carvalho Chehabpin the object the first time it is inserted into the CIL - if it is already in 884c3d2f6cbSMauro Carvalho Chehabthe CIL during a transaction commit, then we do not pin it again. Because there 885c3d2f6cbSMauro Carvalho Chehabcan be multiple outstanding checkpoint contexts, we can still see elevated pin 886c3d2f6cbSMauro Carvalho Chehabcounts, but as each checkpoint completes the pin count will retain the correct 887*622d6f19SRandy Dunlapvalue according to its context. 888c3d2f6cbSMauro Carvalho Chehab 889021904f3SZhao MengmengJust to make matters slightly more complex, this checkpoint level context 890c3d2f6cbSMauro Carvalho Chehabfor the pin count means that the pinning of an item must take place under the 891c3d2f6cbSMauro Carvalho ChehabCIL commit/flush lock. If we pin the object outside this lock, we cannot 892c3d2f6cbSMauro Carvalho Chehabguarantee which context the pin count is associated with. This is because of 893c3d2f6cbSMauro Carvalho Chehabthe fact pinning the item is dependent on whether the item is present in the 894c3d2f6cbSMauro Carvalho Chehabcurrent CIL or not. If we don't pin the CIL first before we check and pin the 895c3d2f6cbSMauro Carvalho Chehabobject, we have a race with CIL being flushed between the check and the pin 896c3d2f6cbSMauro Carvalho Chehab(or not pinning, as the case may be). Hence we must hold the CIL flush/commit 897c3d2f6cbSMauro Carvalho Chehablock to guarantee that we pin the items correctly. 898c3d2f6cbSMauro Carvalho Chehab 899c3d2f6cbSMauro Carvalho ChehabDelayed Logging: Concurrent Scalability 900c3d2f6cbSMauro Carvalho Chehab--------------------------------------- 901c3d2f6cbSMauro Carvalho Chehab 902c3d2f6cbSMauro Carvalho ChehabA fundamental requirement for the CIL is that accesses through transaction 903c3d2f6cbSMauro Carvalho Chehabcommits must scale to many concurrent commits. The current transaction commit 904c3d2f6cbSMauro Carvalho Chehabcode does not break down even when there are transactions coming from 2048 905c3d2f6cbSMauro Carvalho Chehabprocessors at once. The current transaction code does not go any faster than if 906c3d2f6cbSMauro Carvalho Chehabthere was only one CPU using it, but it does not slow down either. 907c3d2f6cbSMauro Carvalho Chehab 908c3d2f6cbSMauro Carvalho ChehabAs a result, the delayed logging transaction commit code needs to be designed 909c3d2f6cbSMauro Carvalho Chehabfor concurrency from the ground up. It is obvious that there are serialisation 910c3d2f6cbSMauro Carvalho Chehabpoints in the design - the three important ones are: 911c3d2f6cbSMauro Carvalho Chehab 912c3d2f6cbSMauro Carvalho Chehab 1. Locking out new transaction commits while flushing the CIL 913c3d2f6cbSMauro Carvalho Chehab 2. Adding items to the CIL and updating item space accounting 914c3d2f6cbSMauro Carvalho Chehab 3. Checkpoint commit ordering 915c3d2f6cbSMauro Carvalho Chehab 916c3d2f6cbSMauro Carvalho ChehabLooking at the transaction commit and CIL flushing interactions, it is clear 917c3d2f6cbSMauro Carvalho Chehabthat we have a many-to-one interaction here. That is, the only restriction on 918c3d2f6cbSMauro Carvalho Chehabthe number of concurrent transactions that can be trying to commit at once is 919c3d2f6cbSMauro Carvalho Chehabthe amount of space available in the log for their reservations. The practical 920c3d2f6cbSMauro Carvalho Chehablimit here is in the order of several hundred concurrent transactions for a 921c3d2f6cbSMauro Carvalho Chehab128MB log, which means that it is generally one per CPU in a machine. 922c3d2f6cbSMauro Carvalho Chehab 923c3d2f6cbSMauro Carvalho ChehabThe amount of time a transaction commit needs to hold out a flush is a 924c3d2f6cbSMauro Carvalho Chehabrelatively long period of time - the pinning of log items needs to be done 925c3d2f6cbSMauro Carvalho Chehabwhile we are holding out a CIL flush, so at the moment that means it is held 926c3d2f6cbSMauro Carvalho Chehabacross the formatting of the objects into memory buffers (i.e. while memcpy()s 927c3d2f6cbSMauro Carvalho Chehabare in progress). Ultimately a two pass algorithm where the formatting is done 928c3d2f6cbSMauro Carvalho Chehabseparately to the pinning of objects could be used to reduce the hold time of 929c3d2f6cbSMauro Carvalho Chehabthe transaction commit side. 930c3d2f6cbSMauro Carvalho Chehab 931c3d2f6cbSMauro Carvalho ChehabBecause of the number of potential transaction commit side holders, the lock 932c3d2f6cbSMauro Carvalho Chehabreally needs to be a sleeping lock - if the CIL flush takes the lock, we do not 933c3d2f6cbSMauro Carvalho Chehabwant every other CPU in the machine spinning on the CIL lock. Given that 934c3d2f6cbSMauro Carvalho Chehabflushing the CIL could involve walking a list of tens of thousands of log 935c3d2f6cbSMauro Carvalho Chehabitems, it will get held for a significant time and so spin contention is a 936c3d2f6cbSMauro Carvalho Chehabsignificant concern. Preventing lots of CPUs spinning doing nothing is the 937c3d2f6cbSMauro Carvalho Chehabmain reason for choosing a sleeping lock even though nothing in either the 938c3d2f6cbSMauro Carvalho Chehabtransaction commit or CIL flush side sleeps with the lock held. 939c3d2f6cbSMauro Carvalho Chehab 940c3d2f6cbSMauro Carvalho ChehabIt should also be noted that CIL flushing is also a relatively rare operation 941c3d2f6cbSMauro Carvalho Chehabcompared to transaction commit for asynchronous transaction workloads - only 942c3d2f6cbSMauro Carvalho Chehabtime will tell if using a read-write semaphore for exclusion will limit 943c3d2f6cbSMauro Carvalho Chehabtransaction commit concurrency due to cache line bouncing of the lock on the 944c3d2f6cbSMauro Carvalho Chehabread side. 945c3d2f6cbSMauro Carvalho Chehab 946c3d2f6cbSMauro Carvalho ChehabThe second serialisation point is on the transaction commit side where items 947c3d2f6cbSMauro Carvalho Chehabare inserted into the CIL. Because transactions can enter this code 948c3d2f6cbSMauro Carvalho Chehabconcurrently, the CIL needs to be protected separately from the above 949c3d2f6cbSMauro Carvalho Chehabcommit/flush exclusion. It also needs to be an exclusive lock but it is only 950c3d2f6cbSMauro Carvalho Chehabheld for a very short time and so a spin lock is appropriate here. It is 951c3d2f6cbSMauro Carvalho Chehabpossible that this lock will become a contention point, but given the short 952c3d2f6cbSMauro Carvalho Chehabhold time once per transaction I think that contention is unlikely. 953c3d2f6cbSMauro Carvalho Chehab 954c3d2f6cbSMauro Carvalho ChehabThe final serialisation point is the checkpoint commit record ordering code 955c3d2f6cbSMauro Carvalho Chehabthat is run as part of the checkpoint commit and log force sequencing. The code 956c3d2f6cbSMauro Carvalho Chehabpath that triggers a CIL flush (i.e. whatever triggers the log force) will enter 957c3d2f6cbSMauro Carvalho Chehaban ordering loop after writing all the log vectors into the log buffers but 958c3d2f6cbSMauro Carvalho Chehabbefore writing the commit record. This loop walks the list of committing 959c3d2f6cbSMauro Carvalho Chehabcheckpoints and needs to block waiting for checkpoints to complete their commit 960c3d2f6cbSMauro Carvalho Chehabrecord write. As a result it needs a lock and a wait variable. Log force 961c3d2f6cbSMauro Carvalho Chehabsequencing also requires the same lock, list walk, and blocking mechanism to 962c3d2f6cbSMauro Carvalho Chehabensure completion of checkpoints. 963c3d2f6cbSMauro Carvalho Chehab 964c3d2f6cbSMauro Carvalho ChehabThese two sequencing operations can use the mechanism even though the 965c3d2f6cbSMauro Carvalho Chehabevents they are waiting for are different. The checkpoint commit record 966c3d2f6cbSMauro Carvalho Chehabsequencing needs to wait until checkpoint contexts contain a commit LSN 967c3d2f6cbSMauro Carvalho Chehab(obtained through completion of a commit record write) while log force 968c3d2f6cbSMauro Carvalho Chehabsequencing needs to wait until previous checkpoint contexts are removed from 969c3d2f6cbSMauro Carvalho Chehabthe committing list (i.e. they've completed). A simple wait variable and 970c3d2f6cbSMauro Carvalho Chehabbroadcast wakeups (thundering herds) has been used to implement these two 971c3d2f6cbSMauro Carvalho Chehabserialisation queues. They use the same lock as the CIL, too. If we see too 972c3d2f6cbSMauro Carvalho Chehabmuch contention on the CIL lock, or too many context switches as a result of 973c3d2f6cbSMauro Carvalho Chehabthe broadcast wakeups these operations can be put under a new spinlock and 974c3d2f6cbSMauro Carvalho Chehabgiven separate wait lists to reduce lock contention and the number of processes 975c3d2f6cbSMauro Carvalho Chehabwoken by the wrong event. 976c3d2f6cbSMauro Carvalho Chehab 977c3d2f6cbSMauro Carvalho Chehab 978c3d2f6cbSMauro Carvalho ChehabLifecycle Changes 979c3d2f6cbSMauro Carvalho Chehab----------------- 980c3d2f6cbSMauro Carvalho Chehab 981c3d2f6cbSMauro Carvalho ChehabThe existing log item life cycle is as follows:: 982c3d2f6cbSMauro Carvalho Chehab 983c3d2f6cbSMauro Carvalho Chehab 1. Transaction allocate 984c3d2f6cbSMauro Carvalho Chehab 2. Transaction reserve 985c3d2f6cbSMauro Carvalho Chehab 3. Lock item 986c3d2f6cbSMauro Carvalho Chehab 4. Join item to transaction 987c3d2f6cbSMauro Carvalho Chehab If not already attached, 988c3d2f6cbSMauro Carvalho Chehab Allocate log item 989c3d2f6cbSMauro Carvalho Chehab Attach log item to owner item 990c3d2f6cbSMauro Carvalho Chehab Attach log item to transaction 991c3d2f6cbSMauro Carvalho Chehab 5. Modify item 992c3d2f6cbSMauro Carvalho Chehab Record modifications in log item 993c3d2f6cbSMauro Carvalho Chehab 6. Transaction commit 994c3d2f6cbSMauro Carvalho Chehab Pin item in memory 995c3d2f6cbSMauro Carvalho Chehab Format item into log buffer 996c3d2f6cbSMauro Carvalho Chehab Write commit LSN into transaction 997c3d2f6cbSMauro Carvalho Chehab Unlock item 998c3d2f6cbSMauro Carvalho Chehab Attach transaction to log buffer 999c3d2f6cbSMauro Carvalho Chehab 1000c3d2f6cbSMauro Carvalho Chehab <log buffer IO dispatched> 1001c3d2f6cbSMauro Carvalho Chehab <log buffer IO completes> 1002c3d2f6cbSMauro Carvalho Chehab 1003c3d2f6cbSMauro Carvalho Chehab 7. Transaction completion 1004c3d2f6cbSMauro Carvalho Chehab Mark log item committed 1005c3d2f6cbSMauro Carvalho Chehab Insert log item into AIL 1006c3d2f6cbSMauro Carvalho Chehab Write commit LSN into log item 1007c3d2f6cbSMauro Carvalho Chehab Unpin log item 1008c3d2f6cbSMauro Carvalho Chehab 8. AIL traversal 1009c3d2f6cbSMauro Carvalho Chehab Lock item 1010c3d2f6cbSMauro Carvalho Chehab Mark log item clean 1011c3d2f6cbSMauro Carvalho Chehab Flush item to disk 1012c3d2f6cbSMauro Carvalho Chehab 1013c3d2f6cbSMauro Carvalho Chehab <item IO completion> 1014c3d2f6cbSMauro Carvalho Chehab 1015c3d2f6cbSMauro Carvalho Chehab 9. Log item removed from AIL 1016c3d2f6cbSMauro Carvalho Chehab Moves log tail 1017c3d2f6cbSMauro Carvalho Chehab Item unlocked 1018c3d2f6cbSMauro Carvalho Chehab 1019c3d2f6cbSMauro Carvalho ChehabEssentially, steps 1-6 operate independently from step 7, which is also 1020c3d2f6cbSMauro Carvalho Chehabindependent of steps 8-9. An item can be locked in steps 1-6 or steps 8-9 1021c3d2f6cbSMauro Carvalho Chehabat the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur 1022c3d2f6cbSMauro Carvalho Chehabat the same time. If the log item is in the AIL or between steps 6 and 7 1023c3d2f6cbSMauro Carvalho Chehaband steps 1-6 are re-entered, then the item is relogged. Only when steps 8-9 1024c3d2f6cbSMauro Carvalho Chehabare entered and completed is the object considered clean. 1025c3d2f6cbSMauro Carvalho Chehab 1026c3d2f6cbSMauro Carvalho ChehabWith delayed logging, there are new steps inserted into the life cycle:: 1027c3d2f6cbSMauro Carvalho Chehab 1028c3d2f6cbSMauro Carvalho Chehab 1. Transaction allocate 1029c3d2f6cbSMauro Carvalho Chehab 2. Transaction reserve 1030c3d2f6cbSMauro Carvalho Chehab 3. Lock item 1031c3d2f6cbSMauro Carvalho Chehab 4. Join item to transaction 1032c3d2f6cbSMauro Carvalho Chehab If not already attached, 1033c3d2f6cbSMauro Carvalho Chehab Allocate log item 1034c3d2f6cbSMauro Carvalho Chehab Attach log item to owner item 1035c3d2f6cbSMauro Carvalho Chehab Attach log item to transaction 1036c3d2f6cbSMauro Carvalho Chehab 5. Modify item 1037c3d2f6cbSMauro Carvalho Chehab Record modifications in log item 1038c3d2f6cbSMauro Carvalho Chehab 6. Transaction commit 1039c3d2f6cbSMauro Carvalho Chehab Pin item in memory if not pinned in CIL 1040c3d2f6cbSMauro Carvalho Chehab Format item into log vector + buffer 1041c3d2f6cbSMauro Carvalho Chehab Attach log vector and buffer to log item 1042c3d2f6cbSMauro Carvalho Chehab Insert log item into CIL 1043c3d2f6cbSMauro Carvalho Chehab Write CIL context sequence into transaction 1044c3d2f6cbSMauro Carvalho Chehab Unlock item 1045c3d2f6cbSMauro Carvalho Chehab 1046c3d2f6cbSMauro Carvalho Chehab <next log force> 1047c3d2f6cbSMauro Carvalho Chehab 1048c3d2f6cbSMauro Carvalho Chehab 7. CIL push 1049c3d2f6cbSMauro Carvalho Chehab lock CIL flush 1050c3d2f6cbSMauro Carvalho Chehab Chain log vectors and buffers together 1051c3d2f6cbSMauro Carvalho Chehab Remove items from CIL 1052c3d2f6cbSMauro Carvalho Chehab unlock CIL flush 1053c3d2f6cbSMauro Carvalho Chehab write log vectors into log 1054c3d2f6cbSMauro Carvalho Chehab sequence commit records 1055c3d2f6cbSMauro Carvalho Chehab attach checkpoint context to log buffer 1056c3d2f6cbSMauro Carvalho Chehab 1057c3d2f6cbSMauro Carvalho Chehab <log buffer IO dispatched> 1058c3d2f6cbSMauro Carvalho Chehab <log buffer IO completes> 1059c3d2f6cbSMauro Carvalho Chehab 1060c3d2f6cbSMauro Carvalho Chehab 8. Checkpoint completion 1061c3d2f6cbSMauro Carvalho Chehab Mark log item committed 1062c3d2f6cbSMauro Carvalho Chehab Insert item into AIL 1063c3d2f6cbSMauro Carvalho Chehab Write commit LSN into log item 1064c3d2f6cbSMauro Carvalho Chehab Unpin log item 1065c3d2f6cbSMauro Carvalho Chehab 9. AIL traversal 1066c3d2f6cbSMauro Carvalho Chehab Lock item 1067c3d2f6cbSMauro Carvalho Chehab Mark log item clean 1068c3d2f6cbSMauro Carvalho Chehab Flush item to disk 1069c3d2f6cbSMauro Carvalho Chehab <item IO completion> 1070c3d2f6cbSMauro Carvalho Chehab 10. Log item removed from AIL 1071c3d2f6cbSMauro Carvalho Chehab Moves log tail 1072c3d2f6cbSMauro Carvalho Chehab Item unlocked 1073c3d2f6cbSMauro Carvalho Chehab 1074c3d2f6cbSMauro Carvalho ChehabFrom this, it can be seen that the only life cycle differences between the two 1075c3d2f6cbSMauro Carvalho Chehablogging methods are in the middle of the life cycle - they still have the same 1076c3d2f6cbSMauro Carvalho Chehabbeginning and end and execution constraints. The only differences are in the 1077c3d2f6cbSMauro Carvalho Chehabcommitting of the log items to the log itself and the completion processing. 1078c3d2f6cbSMauro Carvalho ChehabHence delayed logging should not introduce any constraints on log item 1079c3d2f6cbSMauro Carvalho Chehabbehaviour, allocation or freeing that don't already exist. 1080c3d2f6cbSMauro Carvalho Chehab 1081c3d2f6cbSMauro Carvalho ChehabAs a result of this zero-impact "insertion" of delayed logging infrastructure 1082c3d2f6cbSMauro Carvalho Chehaband the design of the internal structures to avoid on disk format changes, we 1083c3d2f6cbSMauro Carvalho Chehabcan basically switch between delayed logging and the existing mechanism with a 1084c3d2f6cbSMauro Carvalho Chehabmount option. Fundamentally, there is no reason why the log manager would not 1085c3d2f6cbSMauro Carvalho Chehabbe able to swap methods automatically and transparently depending on load 1086c3d2f6cbSMauro Carvalho Chehabcharacteristics, but this should not be necessary if delayed logging works as 1087c3d2f6cbSMauro Carvalho Chehabdesigned. 1088