Add a manual page describing the LSI Fusion family of devices with a
[dragonfly.git] / share / doc / smm / 05.fastfs / 3.t
1 .\" Copyright (c) 1986, 1993
2 .\"     The Regents of the University of California.  All rights reserved.
3 .\"
4 .\" Redistribution and use in source and binary forms, with or without
5 .\" modification, are permitted provided that the following conditions
6 .\" are met:
7 .\" 1. Redistributions of source code must retain the above copyright
8 .\"    notice, this list of conditions and the following disclaimer.
9 .\" 2. Redistributions in binary form must reproduce the above copyright
10 .\"    notice, this list of conditions and the following disclaimer in the
11 .\"    documentation and/or other materials provided with the distribution.
12 .\" 3. All advertising materials mentioning features or use of this software
13 .\"    must display the following acknowledgement:
14 .\"     This product includes software developed by the University of
15 .\"     California, Berkeley and its contributors.
16 .\" 4. Neither the name of the University nor the names of its contributors
17 .\"    may be used to endorse or promote products derived from this software
18 .\"    without specific prior written permission.
19 .\"
31 .\"
32 .\"     @(#)3.t 8.1 (Berkeley) 6/8/93
33 .\"
34 .ds RH New file system
35 .NH
36 New file system organization
37 .PP
38 In the new file system organization (as in the
39 old file system organization),
40 each disk drive contains one or more file systems.
41 A file system is described by its super-block,
42 located at the beginning of the file system's disk partition.
43 Because the super-block contains critical data,
44 it is replicated to protect against catastrophic loss.
45 This is done when the file system is created;
46 since the super-block data does not change,
47 the copies need not be referenced unless a head crash
48 or other hard disk error causes the default super-block
49 to be unusable.
50 .PP
51 To insure that it is possible to create files as large as
52 .if n 2 ** 32
53 .if t $2 sup 32$
54 bytes with only two levels of indirection,
55 the minimum size of a file system block is 4096 bytes.
56 The size of file system blocks can be any power of two
57 greater than or equal to 4096.
58 The block size of a file system is recorded in the 
59 file system's super-block
60 so it is possible for file systems with different block sizes
61 to be simultaneously accessible on the same system.
62 The block size must be decided at the time that
63 the file system is created;
64 it cannot be subsequently changed without rebuilding the file system.
65 .PP
66 The new file system organization divides a disk partition
67 into one or more areas called
68 .I "cylinder groups".
69 A cylinder group is comprised of one or more consecutive
70 cylinders on a disk.
71 Associated with each cylinder group is some bookkeeping information
72 that includes a redundant copy of the super-block,
73 space for inodes,
74 a bit map describing available blocks in the cylinder group,
75 and summary information describing the usage of data blocks
76 within the cylinder group.
77 The bit map of available blocks in the cylinder group replaces
78 the traditional file system's free list.
79 For each cylinder group a static number of inodes
80 is allocated at file system creation time.
81 The default policy is to allocate one inode for each 2048
82 bytes of space in the cylinder group, expecting this
83 to be far more than will ever be needed. 
84 .PP
85 All the cylinder group bookkeeping information could be
86 placed at the beginning of each cylinder group.
87 However if this approach were used,
88 all the redundant information would be on the top platter.
89 A single hardware failure that destroyed the top platter
90 could cause the loss of all redundant copies of the super-block.
91 Thus the cylinder group bookkeeping information
92 begins at a varying offset from the beginning of the cylinder group.
93 The offset for each successive cylinder group is calculated to be
94 about one track further from the beginning of the cylinder group
95 than the preceding cylinder group.
96 In this way the redundant
97 information spirals down into the pack so that any single track, cylinder,
98 or platter can be lost without losing all copies of the super-block.
99 Except for the first cylinder group,
100 the space between the beginning of the cylinder group
101 and the beginning of the cylinder group information
102 is used for data blocks.\(dg
103 .FS
104 \(dg While it appears that the first cylinder group could be laid
105 out with its super-block at the ``known'' location,
106 this would not work for file systems
107 with blocks sizes of 16 kilobytes or greater.
108 This is because of a requirement that the first 8 kilobytes of the disk
109 be reserved for a bootstrap program and a separate requirement that
110 the cylinder group information begin on a file system block boundary.
111 To start the cylinder group on a file system block boundary,
112 file systems with block sizes larger than 8 kilobytes 
113 would have to leave an empty space between the end of
114 the boot block and the beginning of the cylinder group.
115 Without knowing the size of the file system blocks,
116 the system would not know what roundup function to use
117 to find the beginning of the first cylinder group.
118 .FE
119 .NH 2
120 Optimizing storage utilization
121 .PP
122 Data is laid out so that larger blocks can be transferred
123 in a single disk transaction, greatly increasing file system throughput.
124 As an example, consider a file in the new file system
125 composed of 4096 byte data blocks.
126 In the old file system this file would be composed of 1024 byte blocks.
127 By increasing the block size, disk accesses in the new file
128 system may transfer up to four times as much information per
129 disk transaction.
130 In large files, several
131 4096 byte blocks may be allocated from the same cylinder so that
132 even larger data transfers are possible before requiring a seek.
133 .PP
134 The main problem with 
135 larger blocks is that most UNIX
136 file systems are composed of many small files.
137 A uniformly large block size wastes space.
138 Table 1 shows the effect of file system
139 block size on the amount of wasted space in the file system.
140 The files measured to obtain these figures reside on
141 one of our time sharing
142 systems that has roughly 1.2 gigabytes of on-line storage.
143 The measurements are based on the active user file systems containing
144 about 920 megabytes of formatted space.
145 .KF
146 .DS B
147 .TS
148 box;
149 l|l|l
150 a|n|l.
151 Space used      % waste Organization
152 _
153 775.2 Mb        0.0     Data only, no separation between files
154 807.8 Mb        4.2     Data only, each file starts on 512 byte boundary
155 828.7 Mb        6.9     Data + inodes, 512 byte block UNIX file system
156 866.5 Mb        11.8    Data + inodes, 1024 byte block UNIX file system
157 948.5 Mb        22.4    Data + inodes, 2048 byte block UNIX file system
158 1128.3 Mb       45.6    Data + inodes, 4096 byte block UNIX file system
159 .TE
160 Table 1 \- Amount of wasted space as a function of block size.
161 .DE
162 .KE
163 The space wasted is calculated to be the percentage of space
164 on the disk not containing user data.
165 As the block size on the disk
166 increases, the waste rises quickly, to an intolerable
167 45.6% waste with 4096 byte file system blocks.
168 .PP
169 To be able to use large blocks without undue waste,
170 small files must be stored in a more efficient way.
171 The new file system accomplishes this goal by allowing the division
172 of a single file system block into one or more
173 .I "fragments".
174 The file system fragment size is specified
175 at the time that the file system is created;
176 each file system block can optionally be broken into
177 2, 4, or 8 fragments, each of which is addressable.
178 The lower bound on the size of these fragments is constrained
179 by the disk sector size,
180 typically 512 bytes.
181 The block map associated with each cylinder group
182 records the space available in a cylinder group
183 at the fragment level;
184 to determine if a block is available, aligned fragments are examined.
185 Figure 1 shows a piece of a map from a 4096/1024 file system.
186 .KF
187 .DS B
188 .TS
189 box;
190 l|c c c c.
191 Bits in map     XXXX    XXOO    OOXX    OOOO
192 Fragment numbers        0-3     4-7     8-11    12-15
193 Block numbers   0       1       2       3
194 .TE
195 Figure 1 \- Example layout of blocks and fragments in a 4096/1024 file system.
196 .DE
197 .KE
198 Each bit in the map records the status of a fragment;
199 an ``X'' shows that the fragment is in use,
200 while a ``O'' shows that the fragment is available for allocation.
201 In this example,
202 fragments 0\-5, 10, and 11 are in use,
203 while fragments 6\-9, and 12\-15 are free.
204 Fragments of adjoining blocks cannot be used as a full block,
205 even if they are large enough.
206 In this example,
207 fragments 6\-9 cannot be allocated as a full block;
208 only fragments 12\-15 can be coalesced into a full block.
209 .PP
210 On a file system with a block size of 4096 bytes
211 and a fragment size of 1024 bytes,
212 a file is represented by zero or more 4096 byte blocks of data,
213 and possibly a single fragmented block.
214 If a file system block must be fragmented to obtain
215 space for a small amount of data,
216 the remaining fragments of the block are made
217 available for allocation to other files.
218 As an example consider an 11000 byte file stored on
219 a 4096/1024 byte file system.
220 This file would uses two full size blocks and one
221 three fragment portion of another block.
222 If no block with three aligned fragments is
223 available at the time the file is created,
224 a full size block is split yielding the necessary
225 fragments and a single unused fragment.
226 This remaining fragment can be allocated to another file as needed.
227 .PP
228 Space is allocated to a file when a program does a \fIwrite\fP
229 system call.
230 Each time data is written to a file, the system checks to see if
231 the size of the file has increased*.
232 .FS
233 * A program may be overwriting data in the middle of an existing file
234 in which case space would already have been allocated.
235 .FE
236 If the file needs to be expanded to hold the new data,
237 one of three conditions exists:
238 .IP 1)
239 There is enough space left in an already allocated
240 block or fragment to hold the new data.
241 The new data is written into the available space.
242 .IP 2)
243 The file contains no fragmented blocks (and the last
244 block in the file
245 contains insufficient space to hold the new data).
246 If space exists in a block already allocated,
247 the space is filled with new data.
248 If the remainder of the new data contains more than
249 a full block of data, a full block is allocated and
250 the first full block of new data is written there.
251 This process is repeated until less than a full block
252 of new data remains.
253 If the remaining new data to be written will
254 fit in less than a full block,
255 a block with the necessary fragments is located,
256 otherwise a full block is located.
257 The remaining new data is written into the located space.
258 .IP 3)
259 The file contains one or more fragments (and the 
260 fragments contain insufficient space to hold the new data).
261 If the size of the new data plus the size of the data
262 already in the fragments exceeds the size of a full block,
263 a new block is allocated.
264 The contents of the fragments are copied
265 to the beginning of the block
266 and the remainder of the block is filled with new data.
267 The process then continues as in (2) above.
268 Otherwise, if the new data to be written will
269 fit in less than a full block,
270 a block with the necessary fragments is located,
271 otherwise a full block is located.
272 The contents of the existing fragments
273 appended with the new data
274 are written into the allocated space.
275 .PP
276 The problem with expanding a file one fragment at a
277 a time is that data may be copied many times as a 
278 fragmented block expands to a full block.
279 Fragment reallocation can be minimized
280 if the user program writes a full block at a time,
281 except for a partial block at the end of the file.
282 Since file systems with different block sizes may reside on
283 the same system,
284 the file system interface has been extended to provide
285 application programs the optimal size for a read or write.
286 For files the optimal size is the block size of the file system
287 on which the file is being accessed.
288 For other objects, such as pipes and sockets,
289 the optimal size is the underlying buffer size.
290 This feature is used by the Standard
291 Input/Output Library,
292 a package used by most user programs.
293 This feature is also used by
294 certain system utilities such as archivers and loaders
295 that do their own input and output management
296 and need the highest possible file system bandwidth.
297 .PP
298 The amount of wasted space in the 4096/1024 byte new file system
299 organization is empirically observed to be about the same as in the
300 1024 byte old file system organization.
301 A file system with 4096 byte blocks and 512 byte fragments
302 has about the same amount of wasted space as the 512 byte
303 block UNIX file system.
304 The new file system uses less space
305 than the 512 byte or 1024 byte
306 file systems for indexing information for
307 large files and the same amount of space
308 for small files.
309 These savings are offset by the need to use
310 more space for keeping track of available free blocks.
311 The net result is about the same disk utilization
312 when a new file system's fragment size
313 equals an old file system's block size.
314 .PP
315 In order for the layout policies to be effective,
316 a file system cannot be kept completely full.
317 For each file system there is a parameter, termed
318 the free space reserve, that
319 gives the minimum acceptable percentage of file system
320 blocks that should be free.
321 If the number of free blocks drops below this level
322 only the system administrator can continue to allocate blocks.
323 The value of this parameter may be changed at any time,
324 even when the file system is mounted and active.
325 The transfer rates that appear in section 4 were measured on file
326 systems kept less than 90% full (a reserve of 10%).
327 If the number of free blocks falls to zero,
328 the file system throughput tends to be cut in half,
329 because of the inability of the file system to localize
330 blocks in a file.
331 If a file system's performance degrades because
332 of overfilling, it may be restored by removing
333 files until the amount of free space once again
334 reaches the minimum acceptable level.
335 Access rates for files created during periods of little
336 free space may be restored by moving their data once enough
337 space is available.
338 The free space reserve must be added to the
339 percentage of waste when comparing the organizations given
340 in Table 1.
341 Thus, the percentage of waste in
342 an old 1024 byte UNIX file system is roughly
343 comparable to a new 4096/512 byte file system
344 with the free space reserve set at 5%.
345 (Compare 11.8% wasted with the old file system
346 to 6.9% waste + 5% reserved space in the
347 new file system.)
348 .NH 2 
349 File system parameterization
350 .PP
351 Except for the initial creation of the free list,
352 the old file system ignores the parameters of the underlying hardware.
353 It has no information about either the physical characteristics
354 of the mass storage device,
355 or the hardware that interacts with it.
356 A goal of the new file system is to parameterize the 
357 processor capabilities and
358 mass storage characteristics
359 so that blocks can be allocated in an
360 optimum configuration-dependent way. 
361 Parameters used include the speed of the processor,
362 the hardware support for mass storage transfers,
363 and the characteristics of the mass storage devices.
364 Disk technology is constantly improving and
365 a given installation can have several different disk technologies
366 running on a single processor.
367 Each file system is parameterized so that it can be
368 adapted to the characteristics of the disk on which
369 it is placed.
370 .PP
371 For mass storage devices such as disks,
372 the new file system tries to allocate new blocks
373 on the same cylinder as the previous block in the same file. 
374 Optimally, these new blocks will also be 
375 rotationally well positioned.
376 The distance between ``rotationally optimal'' blocks varies greatly;
377 it can be a consecutive block
378 or a rotationally delayed block
379 depending on system characteristics.
380 On a processor with an input/output channel that does not require
381 any processor intervention between mass storage transfer requests,
382 two consecutive disk blocks can often be accessed
383 without suffering lost time because of an intervening disk revolution.
384 For processors without input/output channels,
385 the main processor must field an interrupt and
386 prepare for a new disk transfer.
387 The expected time to service this interrupt and
388 schedule a new disk transfer depends on the
389 speed of the main processor.
390 .PP
391 The physical characteristics of each disk include
392 the number of blocks per track and the rate at which
393 the disk spins.
394 The allocation routines use this information to calculate
395 the number of milliseconds required to skip over a block.
396 The characteristics of the processor include
397 the expected time to service an interrupt and schedule a
398 new disk transfer.
399 Given a block allocated to a file,
400 the allocation routines calculate the number of blocks to
401 skip over so that the next block in the file will
402 come into position under the disk head in the expected
403 amount of time that it takes to start a new
404 disk transfer operation.
405 For programs that sequentially access large amounts of data,
406 this strategy minimizes the amount of time spent waiting for
407 the disk to position itself.
408 .PP
409 To ease the calculation of finding rotationally optimal blocks,
410 the cylinder group summary information includes
411 a count of the available blocks in a cylinder
412 group at different rotational positions.
413 Eight rotational positions are distinguished,
414 so the resolution of the
415 summary information is 2 milliseconds for a typical 3600
416 revolution per minute drive.
417 The super-block contains a vector of lists called
418 .I "rotational layout tables".
419 The vector is indexed by rotational position.
420 Each component of the vector
421 lists the index into the block map for every data block contained
422 in its rotational position.
423 When looking for an allocatable block,
424 the system first looks through the summary counts for a rotational
425 position with a non-zero block count.
426 It then uses the index of the rotational position to find the appropriate
427 list to use to index through
428 only the relevant parts of the block map to find a free block.
429 .PP
430 The parameter that defines the
431 minimum number of milliseconds between the completion of a data
432 transfer and the initiation of
433 another data transfer on the same cylinder
434 can be changed at any time,
435 even when the file system is mounted and active.
436 If a file system is parameterized to lay out blocks with
437 a rotational separation of 2 milliseconds,
438 and the disk pack is then moved to a system that has a
439 processor requiring 4 milliseconds to schedule a disk operation,
440 the throughput will drop precipitously because of lost disk revolutions
441 on nearly every block.
442 If the eventual target machine is known, 
443 the file system can be parameterized for it
444 even though it is initially created on a different processor.
445 Even if the move is not known in advance,
446 the rotational layout delay can be reconfigured after the disk is moved
447 so that all further allocation is done based on the
448 characteristics of the new host.
449 .NH 2
450 Layout policies
451 .PP
452 The file system layout policies are divided into two distinct parts.
453 At the top level are global policies that use file system
454 wide summary information to make decisions regarding
455 the placement of new inodes and data blocks.
456 These routines are responsible for deciding the
457 placement of new directories and files.
458 They also calculate rotationally optimal block layouts,
459 and decide when to force a long seek to a new cylinder group
460 because there are insufficient blocks left
461 in the current cylinder group to do reasonable layouts.
462 Below the global policy routines are
463 the local allocation routines that use a locally optimal scheme to
464 lay out data blocks.
465 .PP
466 Two methods for improving file system performance are to increase
467 the locality of reference to minimize seek latency 
468 as described by [Trivedi80], and
469 to improve the layout of data to make larger transfers possible
470 as described by [Nevalainen77].
471 The global layout policies try to improve performance
472 by clustering related information.
473 They cannot attempt to localize all data references,
474 but must also try to spread unrelated data
475 among different cylinder groups.
476 If too much localization is attempted,
477 the local cylinder group may run out of space
478 forcing the data to be scattered to non-local cylinder groups.
479 Taken to an extreme,
480 total localization can result in a single huge cluster of data
481 resembling the old file system.
482 The global policies try to balance the two conflicting
483 goals of localizing data that is concurrently accessed
484 while spreading out unrelated data.
485 .PP
486 One allocatable resource is inodes.
487 Inodes are used to describe both files and directories.
488 Inodes of files in the same directory are frequently accessed together.
489 For example, the ``list directory'' command often accesses 
490 the inode for each file in a directory.
491 The layout policy tries to place all the inodes of
492 files in a directory in the same cylinder group.
493 To ensure that files are distributed throughout the disk,
494 a different policy is used for directory allocation.
495 A new directory is placed in a cylinder group that has a greater
496 than average number of free inodes,
497 and the smallest number of directories already in it.
498 The intent of this policy is to allow the inode clustering policy
499 to succeed most of the time.
500 The allocation of inodes within a cylinder group is done using a
501 next free strategy.
502 Although this allocates the inodes randomly within a cylinder group,
503 all the inodes for a particular cylinder group can be read with
504 8 to 16 disk transfers.
505 (At most 16 disk transfers are required because a cylinder
506 group may have no more than 2048 inodes.)
507 This puts a small and constant upper bound on the number of
508 disk transfers required to access the inodes
509 for all the files in a directory.
510 In contrast, the old file system typically requires
511 one disk transfer to fetch the inode for each file in a directory.
512 .PP
513 The other major resource is data blocks.
514 Since data blocks for a file are typically accessed together,
515 the policy routines try to place all data
516 blocks for a file in the same cylinder group,
517 preferably at rotationally optimal positions in the same cylinder.
518 The problem with allocating all the data blocks
519 in the same cylinder group is that large files will
520 quickly use up available space in the cylinder group,
521 forcing a spill over to other areas.
522 Further, using all the space in a cylinder group
523 causes future allocations for any file in the cylinder group
524 to also spill to other areas.
525 Ideally none of the cylinder groups should ever become completely full.
526 The heuristic solution chosen is to
527 redirect block allocation
528 to a different cylinder group
529 when a file exceeds 48 kilobytes,
530 and at every megabyte thereafter.*
531 .FS
532 * The first spill over point at 48 kilobytes is the point
533 at which a file on a 4096 byte block file system first
534 requires a single indirect block.  This appears to be
535 a natural first point at which to redirect block allocation.
536 The other spillover points are chosen with the intent of
537 forcing block allocation to be redirected when a
538 file has used about 25% of the data blocks in a cylinder group.
539 In observing the new file system in day to day use, the heuristics appear
540 to work well in minimizing the number of completely filled
541 cylinder groups.
542 .FE
543 The newly chosen cylinder group is selected from those cylinder
544 groups that have a greater than average number of free blocks left.
545 Although big files tend to be spread out over the disk,
546 a megabyte of data is typically accessible before
547 a long seek must be performed,
548 and the cost of one long seek per megabyte is small.
549 .PP
550 The global policy routines call local allocation routines with 
551 requests for specific blocks.
552 The local allocation routines will
553 always allocate the requested block 
554 if it is free, otherwise it
555 allocates a free block of the requested size that is
556 rotationally closest to the requested block.
557 If the global layout policies had complete information,
558 they could always request unused blocks and
559 the allocation routines would be reduced to simple bookkeeping.
560 However, maintaining complete information is costly;
561 thus the implementation of the global layout policy 
562 uses heuristics that employ only partial information.
563 .PP
564 If a requested block is not available, the local allocator uses
565 a four level allocation strategy:
566 .IP 1)
567 Use the next available block rotationally closest
568 to the requested block on the same cylinder.  It is assumed
569 here that head switching time is zero.  On disk 
570 controllers where this is not the case, it may be possible
571 to incorporate the time required to switch between disk platters
572 when constructing the rotational layout tables.  This, however,
573 has not yet been tried.
574 .IP 2)
575 If there are no blocks available on the same cylinder,
576 use a block within the same cylinder group.
577 .IP 3)
578 If that cylinder group is entirely full, 
579 quadratically hash the cylinder group number to choose
580 another cylinder group to look for a free block.
581 .IP 4)
582 Finally if the hash fails, apply an exhaustive search
583 to all cylinder groups.
584 .PP
585 Quadratic hash is used because of its speed in finding
586 unused slots in nearly full hash tables [Knuth75].
587 File systems that are parameterized to maintain at least
588 10% free space rarely use this strategy.
589 File systems that are run without maintaining any free
590 space typically have so few free blocks that almost any
591 allocation is random;
592 the most important characteristic of
593 the strategy used under such conditions is that the strategy be fast.
594 .ds RH Performance
595 .sp 2
596 .ne 1i