Alice and Bob in I/O Land

Alice, Bob And Their Race To Disk-Haven

Alice is a file-system write request.
Bob is a raw-device write request.
They both want to get to the haven of the disk drive - and fast...
...and yet not too fast - not if their friends are coming soon!
Let us follow their journey through Linux's file systems...
...page caches, block devices, elevators and other constructions.
Let us also discuss how to tune their journey, where we can.

Note: most images in these slides are courtesy of Liam Quin's "Alice adventures in wonderland" and his Through the looking glass pages.

Alice's Adventures In Wonderland - A Partial Recap

Alice chased the white rabbit (who was very late), and fell into a deep tree-hole.
Reaching the bottom, Alice saw the white rabbit run through a small door...
...drinking from a small bottle saying "drink me" made her small enough to pass through the door (after much crying).
Alice's tears made a flood which got everyone wet (including her)...
...so she joined all the birds in a drying caucus race.

Alice's Adventures In Wonderland - A Partial Recap - Cont.

At the white rabbit's house Alice ate another cake, which made her large again.
She then came by to the Mad Hatter's tea party.
Alice eventually came to the queen's house and joined a Crockett game.
Alice was put to trial, for being too big...
...during which the Mad Hatter gave testimony...
and eventually Alice woke up and found herself back at home.

Meet Alice - the 16KB "write" that could

Alice is an ordinary write to a file on a file-system.
Alice could be an attempt to write on an allocated part of the file...
...or an attempt to write to an un-allocated part.
Alice could be a synced operation - waiting until she gets to disk-haven...
...or an un-synced operation - getting into the page cache is enough.

Alice goes down the Rabbit hole

The programmer used 'write' to a normal file

(eventually, all the file-writing functions map to write(),
or one of its variants - pwrite(), writev(), etc.)

The system call crosses the boundary into kernel land - going
down the rabbit hole...

Alice wants to pass through the small door

Alice is big = 16KB big.
The page cache works small - page-size small (normally 4KB pages on x86 machines).
Alice cannot pass through the "door" to the page cache - so she needs to get smaller...
...and thus Alice is being cut into several Little Alices - 4KB each.

Little Alice joins the (page-cached) Caucus race

Little Alice is fresh and wet - she needs to dry before going on.
In page-cache-speak, Little Alice is too new to be sent to disk - perhaps
some of her friends will join soon.

(these friends could be new writes that will over-write Little Alice,
or new writes adjacent to Little Alice,
or new reads that will want to query Little Alice's opinions).

pdflush is a kernel thread that decides when to push Little Alice down to the block device.
Memory pressure could also cause that to happen - if we're low on RAM, every cached item is a candidate for a flush.
for info on pdflush-related tuneables: G. Smiths's "The Linux Page Cache and pdflush"

Little Alice going down the (disk) elevator

When pdflush (or the writing process) sends Little Alice to the block device,
she enters the block device queue,
where everyone waits for the elevator.
The reasons for waiting are three:

Supporting flow-control
Supporting I/O priorities
Optimizing (disk) device IOPS/bandwidth/latency utilization

Little Alice grows again - the I/O scheduler dance

The I/O scheduler decides who goes into the elevator - and when.
It may do I/O re-ordering - to reduce seek time for the disk device.
It may do I/O merging (or coalescing) to increase disk bandwidth utilization, based on /sys/block/<device>/queue/ parameters:

max_sectors_kb - maximum number of sectors to send in a single request.
max_hw_sectors_kb - maximum number of sectors to that the (disk) driver can support in a single request.
nr_requests - maximum number of in-flight requests to the device.

We can use the "iostat" command to see what's going on during I/O.
For full details: iostat -k 1 -x.
See the iostat man-page for the details.
Of note: transaction sizes, queue sizes, average request wait time...

Example of "iostat" output

Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz avgqu-sz await svctm %util sda 0.00 3.00 0.00 4.00 0.00 28.00 14.00 0.01 2.50 2.50 1.00 scd0 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 explanations for some fields:
wrqm/s - the number of write requests merged per second.
w/s - the number of write requests that were sent to the device, per second.
wKB/s - number of KB of data written to the device in the last second.
avgrq-sz - average size (in sectors - typically 512 bytes long) of request that was sent to the device.
avgqu-sz - average size of the queue of requests waiting to be sent to the device.
await - average time (milli-seconds) to handle a request (includes time waiting in block-layer queue plus svctm)
svctm - average time (milli-seconds) it took the disk to service a request (not including time waiting in the block-layer queue)

Big Alice plays the disk Crockett - the basic elevator algorithm

When writing to a hard disk - size and location matters.
I/O time depends on seek time plus data transfer time.
The disk always rotates - so we need to schedule I/Os as close to the current read-head location as possible to reduce seek time.
The problem - the disk does not expose its physical geometry.
So the solution: ordering requests based on sector address
and making sure not to make the disk head "jump":

First move the elevator up: perform all I/Os from low address to high address.
If a request arrives, whose address is lower than the current I/O - it will wait for the elevator to come back down.
When there are no I/Os in the elevator's current direction - switch direction.

Original Alice Stands to Trial - ERR_SUCCESS or ERR_IO?

Eventually, we care whether Original Alice got an OK result or not.
This depends on the success or failure of all Little Alices and Big Alices that sprung out of Original Alice.
Note that for normal file-system writes, these errors are hidden by the page cache.

We will still need to put someone to trial - if there was a failure, someone must pay!
So we will keep the judgement results - and return them upon close()!

Mad Hatter testifies - the small bio-s joining in

Each I/O may have been split into several smaller I/O requests.
This could have been because the original I/O was too big, or due to being split across several devices (software-RAID, LVM), etc.
Each small I/O that returns - has a status.
The status of the original I/O will be "success" - only if all the underlying I/O requests succeeded.
Hopefully, the testimony accuracy is better than that of the Mad Hatter...

Original Alice wakes up from her write-full dream

Original Alice eventually wakes up.
If the cache had space - very quickly.
If the cache had lack of space - then after some free space is made.

Creating this free space might require just throwing away cached items (e.g. read-cache)...
...or it may require writing older cached writes back to disk - which is much slower.

In some cases (that we'll see later on) - original Alice wakes up only after all Little and Big Alices finished their race.

Ecila - the "read" that came back from the cold

Ecila is an ordinary read to a file on a file-system.
Ecila could be an attempt to read from an allocated part of the file...
...or an attempt to read from an un-allocated part (a hole in the middle of the file).
Ecila is Alice - through the looking glass.
The time - through the looking glass - goes backwards - and so does Ecila, as we will soon see...

Through The Looking Glass - A Partial Recap

"Through the looking glass" is a game of chess, where Alice is the white pawn, and wins in 11 moves.
Alice talked to her cat, Kitty, looked at the looking glass - and wondered what lies behind it...
Alice went in through the looking glass...
Behind the looking-glass house - everything is like a giant game of chess...
As she went out of the looking-glass house, she met the red queen, who took her to a motion-less run.

Through The Looking Glass - A Partial Recap - Cont.

She met the White Knight who saved her from the Red Knight - but needed much help staying on his horse.
She then met Humpty Dumpty, who sat on the wall (after she left him - he had a great fall...)
Alice met Twiddledee and Twiddledum who had a quarrel over a rattle and thus wanted to battle (and needed help getting dressed with their armors).
At the end of her journey across the chess-board, Alice becomes a queen!
...and eventually, Alice came back to her own home.

Ecila passes through the looking glass

The programmer used 'read' to a normal file

(eventually, all the file-reading functions map to read(),
or one of its variants - pread(), readv(), etc.)

The system call crosses the boundary into kernel land - going
through the looking glass...

Ecila meets the red queen and (page-cachely) runs nowhere

Ecila first tries to satisfy her needs (=data) from the page-cache.
If she can't - she'll go forward to the disk.
eventually when she comes back - she'll not be flushed - if she can...
Like the red queen - Ecila needs to run as fast as she can (i.e. have new reads) just in order to stay at the same place (in the page-cache).
Memory pressure could eventually cause Ecila's data to be flushed from the cache - if we're low on RAM, every cached item is a candidate for a flush.

What's in my cache?

The system call mincore() can be used to check if certain pages are mapped in memory or not.
The fincore utility uses this system-call to check what part of memory a file uses.
In combination with the lsof, we can check the entire contents of the cache:
#!/bin/bash lsof | grep REG | awk '{print($9)}' | while read fn; do echo $fn `fincore $fn -justsummarize` done

Example (very partial) output:
/usr/bin/gnome-keyring-daemon page size: 4096 bytes 56 pages, 224.0 kbytes in core for 1 file; 56.00 pages, 224.0 kbytes per file. /lib/libnss_files-2.11.1.so page size: 4096 bytes 12 pages, 48.0 kbytes in core for 1 file; 12.00 pages, 48.0 kbytes per file.

We can check this for the files used by a single process, by adding the '-p' flag to lsof.

Ecila meets the White Knight and goes to gather herself

When handling a read request - the data could be stored in different locations.
Part of the data might be in the cache.
Part of it might need to be retrieved from the disk.
We might have them in a "zebra" pattern:

page1 page2 page3 page4

cache disk cache disk

Thus, a read request might generate several different read requests, to different parts of the disk.

Ecila and Humpty Dumpty have a great elevated fall

If data needs to be retrieved from the disk, all the generated read requests go waiting for the (disk) elevator.
This is for the same reasons as for having write requests use the elevator.
Of-course, we don't want to wait too much:

unlike normal writes - for reads, the application is waiting.

Ecila meets Twiddledee and Twiddledum - and sends them ahead

One property of disks - is that they work better sequentially, fetching large amounts of data.
One property of applications - is their tendency to perform sequential I/O.
Thus, devices (and file-systems) are often configured to perform read-ahead.
The "read-ahead" is sent immediately after the application read...
...and returns quickly after.
Thus, when the application will want to read the next page - we'll find it in the cache.
If the application won't need the next pages - we wasted disk bandwidth...
...and possibly evicted other cached pages from memory.
Thus, for applications that perform random reads - read-ahead is a bad feature.

Tuning device-level read-ahead

For device "sda", the read-ahead value can be seen by:
# cat /sys/block/sda/queue/read_ahead_kb 128

This value is in KB.
We can change it to another value - lets try setting it to 256KB:
# echo 256 > /sys/block/sda/queue/read_ahead_kb # cat /sys/block/sda/queue/read_ahead_kb 256

To disable read-ahead - set the value to 0.

Ecila comes back through the mirror

When all I/O requests came from the disk (or earlier - if all data was in the cache), the read request copies the data to the user buffer(s).

A read() will copy into a single buffer.
A readv will copy into multiple buffers.

Note: it is allowed to return only partial data!

To simplify the code handling reads in the kernel (or the driver)
To simplify handling of signals received in the middle of the system call.

Thus: always check how many bytes were actually read, and don't assume a premature return is an error!
(the same is true for writes too!).

File-Systems and meta-data I/O

File systems differ from raw device access due to their handling of meta-data.
Whenever we open a file - a lot of meta-data reading and/or writing activity takes place.
During I/O operations to a file - some meta-data may also need to be managed.
Let us see what's going on behind the scenes.
We will encounter directory hierarchy traversals, file control blocks, file blocks or extents and journals.

Directory hierarchy traversal and the dentry cache

When we attempt to open a file, the system needs to check all the path components, one by one:

to verify their existence
to check our access permissions
to follow symbolic links

This requires bringing data from the disk (the directories data), in a random-access manner --> SLOW.
To speed up - fetched directory data is stored in the kernel's "dentry cache".

Checking dentry-cache statistics

To see statistics about the dentry-cache:
$ cat /proc/sys/fs/dentry-state 17782 9733 45 0 0 0

Entries are as follows:

nr_dentry - number of allocated dentries in the cache.
nr_unused - number of unused (=free) entries in the cache.
age_limit - the minimum age (in seconds) for a dentry, until the kernel may reclaim it due to memory pressure.
want_pages - non-zero when the kernel started a shrink dentry-cache operation that was not yet finished.
unused.
unused.

File control blocks and the inode cache

Each file has a control block, with information such as file size, last modification time, last access time, access permissions...
Since traveling a path requires checking permissions and file-types, the file control blocks are cached in the inode cache.

inode is the name of the object, on disk, that contains the file control-block.

Each dentry points to a matching entry in the inode-cache, allowing the path traversal code to quickly check for access permissions.

Checking inode-cache statistics

To see statistics about the inode-cache:
$ cat /proc/sys/fs/inode-state 68034 21738 0 0 0 0 0

Entries are as follows:

nr_inodes - number of allocated inodes in the cache.
nr_free_inodes - number of unused (=free) entries in the cache.
preshrink - nonzero when the number of allocated inodes is larger than inode-max (TODO - missing on Ubuntu 10.04?) - implying the system needs to clear inode cache entries.
unused
unused.
unused.
unused.

File Blocks And File Extents

The data of files is stored in disk blocks...

whose identities are stored in the file's inode...
...either directly, or indirectly (via indirect inode blocks)

On some file-systems (e.g. ext2, ext3) blocks are allocated only when there is a need to write into them.

Pros:

Good disk space utilization for small files and sparse files.

Cons:

Can cause file fragmentation - making large sequential data read/write operations require many disk seeks.
May cause a need to use more indirect inode blocks - making random file access work much worse.

File Blocks And File Extents - Cont.

Some file-systems (e.g. ext4, xfs) allocate larger extents.

Pros:

Reduces file fragmentation significantly.
Reduces need for indirect inode blocks - making random file access much faster.

Cons:

With small files and sparse files - disk space is wasted.

File-System Journaling

file systems (e.g. ext3, xfs, reiserfs) perform journaling - to avoid endless fsck times during a reboot after a system crash.
The basic idea: write the transaction into a journal, before doing the file-system updates.
On mount after a crash - replay the unfinished transactions from the journal.
Note: Linux has "jfs" support in the kernel - to support journals.

Journaling I/O

journals are not committed immediately to disk - they are batched in memory.
On ext3 - the journal is flushed to disk every 5 seconds (configurable)

This avoids too many seeks...
...at the price of potential transactions loss on system crash.

Journaling can be of several types:

full data journal - the data will be written to disk twice - to the journal and to the file system. Simpler to implement.
meta-data only - data won't be written to disk before entered into the journal - yet will be written to disk before the journal is written to disk.

Having an 'fsync()' call - requires flushing file-system blocks and journal blocks:

will cause seeks...
...unless the journal is kept on a separate disk (separate spindle).

Bob - the raw-"write"-er

Bob is a write to a block device.
Bob, unlike Alice, always writes onto an existing part of the device:

No block allocations needed.

Bob could be a direct operation - waiting until he gets to disk-haven...
...or an un-synced operation - getting into the buffer cache is enough.
Note: mixing I/O via the cache and bypassing the cache - is a bad idea.

Bob goes into I/O land

The programmer used 'write' (or its variants) to a block device file
Writing to a block device file implies writing into the device itself
Byte offsets map linearly into sector numbers on the block device.
TODO: can write to unaligned location if going via the cache?

To cache or not to cache - that is the D(irect) question

When doing I/O to a block device - we can still work with the buffer cache

From C, this is the normal consequence of writing into a file.
From the shell - one can zero-out a device file, using the buffer cache, as follows:
dd if=/dev/zero of=/dev/sdb bs=1MB
NOTE: be careful - do this on the wrong device - and your data is gone capoot!
Note: the above command will start very fast (writing into cache), and then slow down to disk speed.

But the more common use-case is using the block device to bypass the cache.

From C, This is done by using the O_DIRECT flag to the open() system call.
In this mode - file-offsets, buffer sizes and buffer addresses must be sector-aligned.
From the shell - one can zero-out a device file as follows:
dd if=/dev/zero of=/dev/sdb bs=1MB oflag=direct
NOTE: be careful - do this on the wrong device - and your data is gone capoot!

We can see the difference if we run "iostat" while these "dd" commands execute.

What if Bob was sync(ing) harder?

TODO

boB - the reader from the "raw"

boB is Bob's cousin, a read request.
boB just wants to get some data from the block device.
Like Bob, boB can choose to go via the cache, or bypass the cache.

boB goes catching some rie

TODO

boB the cached Vs. boB the direct

TODO

Alice and Bob go picking an elevator

Once there was a single type of elevator in the Linux "market".
Then several types of elevators were developed - but you had to choose only one for the entire system - as a kernel boot parameter.
And later on, a possibility was added to change the elevator per block device, during normal operation.
Linux elevators differ mostly in:

how they prioritize I/O requests
how aggressive they are in attempts to merge requests

Let us send Alice and Bob to the market, to pick an elevator.

The "noop" elevator - quick and noisy

The simplest elevator is the noop elevator.
noop does not re-order I/O requests - first-come, first-sent.
noop still may merge I/O requests if it happened to have several together in the queue when it scanned the queue.
noop is relevant when we have a better elevator inside the storage device (e.g. RAID, NCQ, SSD...)

The "CFQ" elevator - "no room! no room! (at the tea party)"

The default scheduler in most Linux distributions.
Attempts to give a "fair" share of I/O to all processes in the system.
The only scheduler that supports per-process I/O prioritization.

I/O Priority Using "ionice"

ionice allows us to give priority to I/O generated by certain processes.
There are 3 level classes - real-time, best-effort and Idle.

Real-time - gets absolute priorities above others. there are 8 real-time levels. CAN CHOKE ALL OTHER I/O!
Best-effort - the default class. A longer time-slice is defined for each level. Default level is 4. Time-slice also affected by process "nice" level.
Idle - will be allowed I/O access only when the other classes do not have any pending I/O.

Can change I/O priority of running processes, or start new processes with a given priority.

The "deadline" elevator - "I'm late! I'm late! I'm late!"

This scheduler attempts to delay I/O requests until "their friends" arrive...
...but with a deadline - don't let any single I/O wait too much.
As such, it should (theoretically) be better for latency-sensitive applications then CFQ.

The "anticipatory" elevator - "If you build it - they will come"

Anticipates that after some I/O - its friends will come.
In that respect - it is similar to the deadline scheduler.
However, it also avoids sending other I/O requests (from different "streams") for a certain amount of time.
In that sense, it does not push too many I/O requests simultaneously to the disk, except when there is a long stream of I/Os.
Which means it could be better for throughput, but worse for latency.

I/O and the court of law

The first problem is determining - who is the owner of a given I/O?
Consider these scenarios, and determine who is the owner:

Task A wrote to a file - into page-cache. Task B then wrote over the same file-offsets. Data was flushed to disk once
Task A read from a file. Task B read from the same file (via page-cache).
Task A wrote into a file - into page-cache. Task B read from the file - from the page-cache.

So who do we "blame" for the I/O operation - who is the scapegoat?

The one that happened to "be first to read" for whom disk access was done?
Anyone, regardless of whether disk I/O was needed or not?
Split the "blame" between all involved?

Cartman (from South-park) looking for his father...
Note: this is NOT politically-correct - this is southpark...

Cartman decided to look for his father.
The problem was - his mother had been involved with too many people
and it is impossible to know who it was.
(it took many seasons to find that out...)

Why is it so hard to perform per-process I/O accounting

Even if we avoid having the "multiple-suspects" situation - delayed-writes:

Process A wrote to a file - into page-cache.
pdflush eventually flushed it to disk - so process A didn't do any I/O.
We could mark the "data owner" in the page-cache - but this will break when we have multiple suspects.

Another case - partial-page reads:

Process A wants to read 512 bytes.
The file-system works at a block size of 4KB.
Thus the file system reads 4KB from disk - and returns 512 bytes to process A.
How much do we account for process A - 512 bytes or 4096 bytes?
What if process A wanted to read only 1 byte at offset 173?

/proc/<pid>/io and iotop

We look at the file "/proc/<pid>/io":
$ cat /proc/1275/io rchar: 1661777 wchar: 7431 syscr: 1240 syscw: 123 read_bytes: 7335936 write_bytes: 12288 cancelled_write_bytes: 0

The fields are:

rchar: number of bytes the process read, using any read-like system call (from files, pipes, tty...).
wchar: number of bytes the process wrote using any write-like system call.
syscr: number of read-like system call invocations that the process performed.
syscr: number of write-like system call invocations that the process performed.
read_bytes: number of bytes the process directly read from disk.
write_bytes: number of bytes the process originally dirtied in the page-cache (assuming they will go to disk later).
cancelled_write_bytes: number of bytes the process "un-dirtied" - e.g. using an "ftruncate" call that truncated pages from the page-cache.

One can use "iotop" to view the top I/O generators in real-time.

The Linux I/O law of fatherhood

Whenever a read bio is submitted to a block device - the active thread is accounted for it - regardless whether this is the originating process or pdflush.
Whenever (virtual) memory pages are marked dirty - the active thread is accounted for this as a write request.

Why not during sending the bio to the block device?
Because then we'll always think it was done by pdflush.

Whenever pages in the page-cache are truncated - the active thread is accounted for "cancelled write bytes" (i.e. "negative" I/O).

References

The Linux Page Cache and pdflush: Theory of Operation and Tuning for Write-Heavy Loads - http://www.westnet.com/~gsmith/content/linux-pdflush.htm
Page Cache, the Affair Between Memory and Files - http://duartes.org/gustavo/blog/post/page-cache-the-affair-between-memory-and-files
"fcoretools" source package in Ubuntu - https://launchpad.net/ubuntu/+source/fcoretools/1.0-1
Anatomy of the Linux virtual file system switch - http://www.ibm.com/developerworks/linux/library/l-virtual-filesystem-switch/

Originally written by guy keren