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 heads, file blocks or extents and journals.

Directory hierarchy traversal and the dentry cache

TODO

File heads and the inode cache

TODO

File Blocks And File Extents

TODO

File-System Journaling

TODO

Bob - the raw-"write"-er

TODO

Bob goes into I/O land

TODO

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

(dd with odirect and iostat)
TODO

What if Bob was sync(ing) harder?

TODO

boB - the reader from the "raw"

TODO

boB goes catching some ride

TODO

boB the cached Vs. boB the direct

TODO

Alice and Bob go picking an elevator

TODO

The "noop" elevator - quick and noisy

TODO

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

TODO

I/O Priority Using "ionice"

TODO

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

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

TODO

I/O and the court of law

(who's the owner)
TODO

Cartman (from South-park) looking for his father...

(tell the story)
TODO

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

TODO

/proc/<pid>/io and iotop

TODO

The I/O law of fatherhood

TODO

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

Originally written by guy keren