2.4.20-ck3 / aa / rmap with contest
Here are a set of contest benchmarks for 2.4.20-ck3 comparing it to vanilla 2.4.20
ck3a is with the default aa vm
ck3r is with the rmap vm option
no_load:
Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 78 93.6 0.0 0.0 1.00 2420ck3a 1 78 94.9 0.0 0.0 1.00 2420ck3r 1 80 93.8 0.0 0.0 1.00 cacherun: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 74 98.6 0.0 0.0 0.95 2420ck3a 1 75 98.7 0.0 0.0 0.96 2420ck3r 1 76 97.4 0.0 0.0 0.95 process_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 123 56.1 105.0 41.5 1.58 2420ck3a 1 115 63.5 88.0 35.7 1.47 2420ck3r 1 120 61.7 94.0 35.8 1.50 ctar_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 98 79.6 2.0 5.1 1.26 2420ck3a 1 92 82.6 1.0 2.2 1.18 2420ck3r 1 97 80.4 1.0 3.1 1.21 xtar_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 130 59.2 2.0 4.6 1.67 2420ck3a 1 116 65.5 2.0 5.2 1.49 2420ck3r 1 127 60.6 2.0 3.9 1.59 io_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 297 25.3 95.5 15.5 3.81 2420ck3a 1 124 61.3 32.9 12.9 1.59 2420ck3r 1 152 51.3 35.7 12.5 1.90 io_other: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 100 74.0 32.8 15.8 1.28 2420ck3a 1 93 81.7 26.6 14.0 1.19 2420ck3r 1 110 70.0 29.7 13.6 1.38 read_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 200 39.5 16.8 5.5 2.56 2420ck3a 1 93 82.8 6.1 5.4 1.19 2420ck3r 1 121 65.3 7.2 5.0 1.51 list_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 95 78.9 0.0 5.3 1.22 2420ck3a 1 82 91.5 0.0 3.7 1.05 2420ck3r 1 94 80.9 0.0 3.2 1.18 mem_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 91 84.6 50.0 1.1 1.17 2420ck3a 1 104 73.1 51.0 1.9 1.33 2420ck3r 1 105 76.2 54.0 3.8 1.31 dbench_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.4.20 1 354 21.2 4.0 38.4 4.54 2420ck3a 1 135 61.5 0.0 0.0 1.73 2420ck3r 1 180 45.0 0.0 0.0 2.25
Con
http://greetings.yahoo.com.au - Yahoo! Greetings
- Send your seasons greetings online this year!
stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
The troughput/latency curve has only a few points where the throughput incrase while latency decrease. The miniumum latency doesn't necessairly mean minimal throughput as maxmium latency doesn't necessairly imply maximal throughput.
But clearly maximum throughput likely implys not minium latency and the other way around.
I described my idea to Jens a few days ago and he's working on it right now AFIK, incidentally he had an equivalent idea in the past and he had some old code that he's starting with. For the details on how it works you can read the stochastic fair queueing in the network packet scheduler (net/sched/sch_sfq.c).
The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the task->pid that is sumbitting the bh/bio. You'll have to apply an hash to the pid and you probably want a perturbation timer that will change the hash function every 30 sec or so. Plus I want a special queue for everything asynchronoys. So that the asynchronoys queue will be elevated and reordered like today since it's not latency critical. I suggeted Jens to differentiate it by checking current->mm, all the async stuff is normally submitted by the kernel daemons. A more finegrined way is to add a bitflag that you have to set between the bh lock and the submit_bh and that will be cleared by unlock_buffer (or equivalent one for the bio in 2.5). But the current->mm will take care of async-io with keventd too so it should be just fine (modulo the first aio submit but it's a minor issue).
Then the lowlevel drivers will pick requests from these queues in round robin (other variations may be possible too, like two requests per queue or stuff like that, but 1 request per queue should give an unbelieveable responsiveness to the system, something that we never experienced before).
This stochastic fair queueing I/O scheduling algorithm will be the best for desktop/multimedia, i.e. when your priority is that xmms or mplayer never skips no matter how many cp /dev/zero . you're running in background. Or also for a multiuser system. There is no other possible definitive fix IMHO. The only other possible fix would be to reduce the I/O queue to say 512kbytes and to take advantage of the FIFO behaviour of the queue wakeups, I tried that, it works so well, you can trivially test it with my elevator-lowlatency by just changing a line, but the problem is 512k is a too small I/O pipeline, i.e. it is not enough to guarantee the maximal throughput during contigous I/O. 2M of queue is the miniumum for using at best 100Mbyte arrays like my raid box.
Also the elevator-lowlatency patch right now has an unplug race that can hang the box under some workload, it's not a fatal bug (i.e. no risk of corruption and hard to trigger) and I need to fix it, like I need to limit the number of requests too or the seeking workloads get huge latencies with no throughput advantage (very well shown by tiobench in the great bigbox.html effort from Randy).
The stochastic fair queueing will allow us to keep a rasonable sized queue to avoid hurting workloads like bonnie, while still providing the maximum possible fariness across different tasks.
However it has to be optional, I suggested to use the b_max ioctl (currently unused) to select the scheduler mode, because dbench and other workloads really want the max reodering task-against-task to get the maximal throughput, not matter how long a certain dbench task is delayed. It is really up to the user to choose the I/O scheduling algorithm, just like it happens today in the network stack. Desktop users will want the stochastic fair queuing, people running workloads ala dbench must avoid it.
the stochastic fair queueing will also make the anticipatory scheduling a very low priority to have. Stochasting fair queueing will be an order of magnitude more important than anticipatory scheduling IMHO.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 3 lines · Andrea Arcangeli
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
Sounds nice. I would like to see per process disk distribution.
Quoted 31 lines
The troughput/latency curve has only a few points where the throughput incrase while latency decrease. The miniumum latency doesn't necessairly mean minimal throughput as maxmium latency doesn't necessairly imply maximal throughput.
But clearly maximum throughput likely implys not minium latency and the other way around.
I described my idea to Jens a few days ago and he's working on it right now AFIK, incidentally he had an equivalent idea in the past and he had some old code that he's starting with. For the details on how it works you can read the stochastic fair queueing in the network packet scheduler (
net/sched/sch_sfq.c).The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the
task->pidthat is sumbitting the bh/bio. You'll have to apply an hash to the pid and you probably want a perturbation timer that will change the hash function every 30 sec or so. Plus I want a special queue for everything asynchronoys. So that the asynchronoys queue will be elevated and reordered like today since it's not latency critical. I suggeted Jens to differentiate it by checkingcurrent->mm, all the async stuff is normally submitted by the kernel daemons. A more finegrined way is to add a bitflag that you have to set between the bh lock and thesubmit_bhand that will be cleared byunlock_buffer(or equivalent one for the bio in 2.5). But thecurrent->mmwill take care of async-io with keventd too so it should be just fine (modulo the first aio submit but it's a minor issue).
Quoted 5 lines
Then the lowlevel drivers will pick requests from these queues in round robin (other variations may be possible too, like two requests per queue or stuff like that, but 1 request per queue should give an unbelieveable responsiveness to the system, something that we never experienced before).
However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.
Quoted 14 lines
This stochastic fair queueing I/O scheduling algorithm will be the best for desktop/multimedia, i.e. when your priority is that xmms or mplayer never skips no matter how many cp
/dev/zero. you're running in background. Or also for a multiuser system. There is no other possible definitive fix IMHO. The only other possible fix would be to reduce the I/O queue to say 512kbytes and to take advantage of the FIFO behaviour of the queue wakeups, I tried that, it works so well, you can trivially test it with my elevator-lowlatency by just changing a line, but the problem is 512k is a too small I/O pipeline, i.e. it is not enough to guarantee the maximal throughput during contigous I/O. 2M of queue is the miniumum for using at best 100Mbyte arrays like my raid box.
But your solution also does nothing for sequential IO throughput in the presence of more than one submitter. Two sequential readers on different parts of the disk for example. Submit 128K request (4ms), seek (5ms), submit 128K request (4ms), so your 30MB/s disk gets less than 15MB/s here. Same with writes.
I think you should be giving each process a timeslice, that way you don't need to try to account for request size or seek vs IO time and is easily tunable. This should solve the above problem with say 50ms timeslices.
It also does little to help dependant reads vs writes or streaming reads.
For reads, anticipatory scheduling can be very helpful in theory however it remains to be seen if I can make it work without adding too much complexity. Your fair queueing should go nicely on top if I can make it work. I do like your idea though!
Nick
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 6 lines · Nick Piggin
Quoted 2 lines · Andrea Arcangeli
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
Sounds nice. I would like to see per process disk distribution.
Sounds like the easiest way to get that fair, indeed. Manage every disk as a separately scheduled resource...
Quoted 2 lines
However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.
Considering that one medium/far disk seek counts for about 400 kB of data read/write, I suspect we'll just want to merge requests or put adjacant requests next to each other into the elevator up to a fairly large size. Probably about 1 MB for a hard disk or a cdrom, but much less for floppies, opticals, etc...
Quoted 4 lines
But your solution also does nothing for sequential IO throughput in the presence of more than one submitter.
I think you should be giving each process a timeslice,
That is the anticipatory scheduler. A good complement to the SFQ part of the IO scheduler. I'd really like to see both ideas together in one scheduler, they sound like a winning pair.
Quoted 4 lines
For reads, anticipatory scheduling can be very helpful in theory however it remains to be seen if I can make it work without adding too much complexity. Your fair queueing should go nicely on top if I can make it work. I do like your idea though!
The anticipatory scheduler can just remain "on" while the priority difference of the requests of the current process aren't too big when compared to the priority of the other requests. Once the SFQ part of the scheduler sends down requests with a really big priority difference the anticipatory scheduler can "skip a beat" and switch to another process.
Note that Andrea's distinction between synchronous and asynchronous requests may be more appropriate than the distinction between read and write requests ...
The only remaining question is how do we know which requests are
synchronous and which are asynchronous ? Ie. which requests have
a process waiting on their completion and which requests don't have a process waiting on their completion ?
regards,
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 5 lines · Rik van Riel
Quoted 3 lines · Nick Piggin
Andrea Arcangeli wrote:
Quoted 9 lines
Quoted 5 lines
Quoted 3 lines
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
Sounds nice. I would like to see per process disk distribution.
Sounds like the easiest way to get that fair, indeed. Manage every disk as a separately scheduled resource...
I hope this option becomes available one day.
Quoted 6 lines
Quoted 5 lines
However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.
Quoted 6 lines
Considering that one medium/far disk seek counts for about 400 kB of data read/write, I suspect we'll just want to merge requests or put adjacant requests next to each other into the elevator up to a fairly large size. Probably about 1 MB for a hard disk or a cdrom, but much less for floppies, opticals, etc...
Yes, but the point is _dependant reads_. This is why Andrea's approach alone can't solve dependant read vs write or nondependant read - while maintaining a good throughput.
Quoted 6 lines
Quoted 5 lines
But your solution also does nothing for sequential IO throughput in the presence of more than one submitter.
Quoted 7 lines
Quoted 2 lines
I think you should be giving each process a timeslice,
That is the anticipatory scheduler. A good complement to the SFQ part of the IO scheduler. I'd really like to see both ideas together in one scheduler, they sound like a winning pair.
No, anticipatory scheduling just "pauses for a bit after some reads" I am talking about all this nonsense about trying to measure seek vs throughput vs rotational latency, etc. We don't process schedule by how many memory accesses a process makes * processor speed / memory speed + instruction jumps.....
If you want a fair disk scheduler, just give each process a disk timeslice, and all your seek, stream, settle, track buffer, etc accounting is magically done for you... For any device, and is 100% tunable. The point is, account by _time_.
Nick
usbaudio.c 2.5.59
I am compiling 2.5.59 with the latest BK patch applied, and get the following compile error when compiling sound/usb/usbaudio.c:
sound/usb/usbaudio, in function 'create composite quirk'
warning: initialization from incompatiable pointer type, line 2219 structure has no member named 'interface' line 2226
This error did not occur in early 2.5.5X versions, but has in 2.5.59, 2.5.58 and at least a few before that.P.S. I am testing a machine with a CMI8330 sound card and HiFi-Link usb audio device.
.config follows:
#
# Automatically generated make config: don't edit
#CONFIG_X86=yCONFIG_MMU=yCONFIG_SWAP=yCONFIG_UID16=yCONFIG_GENERIC_ISA_DMA=y
#
# Code maturity level options
#CONFIG_EXPERIMENTAL=y
#
# General setup
#CONFIG_SYSVIPC=yCONFIG_BSD_PROCESS_ACCT=yCONFIG_SYSCTL=yCONFIG_LOG_BUF_SHIFT=14
#
# Loadable module support
#CONFIG_MODULES=yCONFIG_MODULE_UNLOAD=y
# CONFIG_MODULE_FORCE_UNLOAD is not setCONFIG_OBSOLETE_MODPARM=yCONFIG_MODVERSIONS=yCONFIG_KMOD=y
#
# Processor type and features
#CONFIG_X86_PC=y
# CONFIG_X86_VOYAGER is not set
# CONFIG_X86_NUMAQ is not set
# CONFIG_X86_SUMMIT is not set
# CONFIG_X86_BIGSMP is not set
# CONFIG_M386 is not set
# CONFIG_M486 is not set
# CONFIG_M586 is not set
# CONFIG_M586TSC is not set
# CONFIG_M586MMX is not set
# CONFIG_M686 is not setCONFIG_MPENTIUMII=y
# CONFIG_MPENTIUMIII is not set
# CONFIG_MPENTIUM4 is not set
# CONFIG_MK6 is not set
# CONFIG_MK7 is not set
# CONFIG_MK8 is not set
# CONFIG_MELAN is not set
# CONFIG_MCRUSOE is not set
# CONFIG_MWINCHIPC6 is not set
# CONFIG_MWINCHIP2 is not set
# CONFIG_MWINCHIP3D is not set
# CONFIG_MCYRIXIII is not setCONFIG_X86_CMPXCHG=yCONFIG_X86_XADD=yCONFIG_X86_L1_CACHE_SHIFT=5CONFIG_RWSEM_XCHGADD_ALGORITHM=yCONFIG_X86_WP_WORKS_OK=yCONFIG_X86_INVLPG=yCONFIG_X86_BSWAP=yCONFIG_X86_POPAD_OK=yCONFIG_X86_TSC=yCONFIG_X86_GOOD_APIC=yCONFIG_X86_INTEL_USERCOPY=yCONFIG_X86_USE_PPRO_CHECKSUM=y
# CONFIG_HUGETLB_PAGE is not set
# CONFIG_SMP is not setCONFIG_PREEMPT=y
# CONFIG_X86_UP_APIC is not setCONFIG_X86_MCE=y
# CONFIG_X86_MCE_NONFATAL is not set
# CONFIG_TOSHIBA is not set
# CONFIG_I8K is not setCONFIG_MICROCODE=mCONFIG_X86_MSR=mCONFIG_X86_CPUID=m
# CONFIG_EDD is not set
# CONFIG_NOHIGHMEM is not setCONFIG_HIGHMEM4G=y
# CONFIG_HIGHMEM64G is not setCONFIG_HIGHMEM=y
# CONFIG_HIGHPTE is not set
# CONFIG_MATH_EMULATION is not setCONFIG_MTRR=yCONFIG_HAVE_DEC_LOCK=y
#
# Power management options (ACPI, APM)
#CONFIG_PM=y
# CONFIG_SOFTWARE_SUSPEND is not set
#
# ACPI Support
#
# CONFIG_ACPI is not set
# CONFIG_APM is not set
# CONFIG_CPU_FREQ is not set
#
# Bus options (PCI, PCMCIA, EISA, MCA, ISA)
#CONFIG_PCI=y
# CONFIG_PCI_GOBIOS is not set
# CONFIG_PCI_GODIRECT is not setCONFIG_PCI_GOANY=yCONFIG_PCI_BIOS=yCONFIG_PCI_DIRECT=y
# CONFIG_SCx200 is not set
# CONFIG_PCI_LEGACY_PROC is not setCONFIG_PCI_NAMES=yCONFIG_ISA=y
# CONFIG_EISA is not set
# CONFIG_MCA is not setCONFIG_HOTPLUG=y
#
# PCMCIA/CardBus support
#CONFIG_PCMCIA=mCONFIG_CARDBUS=yCONFIG_I82092=mCONFIG_I82365=m
# CONFIG_TCIC is not set
#
# PCI Hotplug Support
#
# CONFIG_HOTPLUG_PCI is not set
#
# Executable file formats
#CONFIG_KCORE_ELF=y
# CONFIG_KCORE_AOUT is not setCONFIG_BINFMT_AOUT=mCONFIG_BINFMT_ELF=yCONFIG_BINFMT_MISC=m
#
# Memory Technology Devices (MTD)
#
# CONFIG_MTD is not set
#
# Parallel port support
#CONFIG_PARPORT=mCONFIG_PARPORT_PC=mCONFIG_PARPORT_PC_CML1=m
# CONFIG_PARPORT_SERIAL is not set
# CONFIG_PARPORT_PC_FIFO is not set
# CONFIG_PARPORT_PC_SUPERIO is not setCONFIG_PARPORT_PC_PCMCIA=m
# CONFIG_PARPORT_OTHER is not setCONFIG_PARPORT_1284=y
#
# Plug and Play support
#CONFIG_PNP=yCONFIG_PNP_NAMES=yCONFIG_PNP_CARD=yCONFIG_PNP_DEBUG=y
#
# Protocols
#CONFIG_ISAPNP=yCONFIG_PNPBIOS=y
#
# Block devices
#CONFIG_BLK_DEV_FD=y
# CONFIG_BLK_DEV_XD is not set
# CONFIG_PARIDE is not set
# CONFIG_BLK_CPQ_DA is not set
# CONFIG_BLK_CPQ_CISS_DA is not set
# CONFIG_BLK_DEV_DAC960 is not setCONFIG_BLK_DEV_UMEM=mCONFIG_BLK_DEV_LOOP=yCONFIG_BLK_DEV_NBD=mCONFIG_BLK_DEV_RAM=yCONFIG_BLK_DEV_RAM_SIZE=4096CONFIG_BLK_DEV_INITRD=y
# CONFIG_LBD is not set
#
# ATA/ATAPI/MFM/RLL device support
#CONFIG_IDE=y
#
# IDE, ATA and ATAPI Block devices
#CONFIG_BLK_DEV_IDE=y
#
# Please see Documentation/ide.txt for help/info on IDE drives #
# CONFIG_BLK_DEV_HD_IDE is not set
# CONFIG_BLK_DEV_HD is not set CONFIG_BLK_DEV_IDEDISK=yCONFIG_IDEDISK_MULTI_MODE=y
# CONFIG_IDEDISK_STROKE is not set CONFIG_BLK_DEV_IDECS=mCONFIG_BLK_DEV_IDECD=y
C
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Nick PigginQuoted 30 lines · Nick Piggin
Quoted 5 lines · Rik van Riel
Quoted 3 lines · Nick Piggin
Andrea Arcangeli wrote:
Quoted 9 lines
Quoted 5 lines
Quoted 3 lines
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
Sounds nice. I would like to see per process disk distribution.
Sounds like the easiest way to get that fair, indeed. Manage every disk as a separately scheduled resource...
I hope this option becomes available one day.
Quoted 6 lines
Quoted 5 lines
However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.
Quoted 6 lines
Considering that one medium/far disk seek counts for about 400 kB of data read/write, I suspect we'll just want to merge requests or put adjacant requests next to each other into the elevator up to a fairly large size. Probably about 1 MB for a hard disk or a cdrom, but much less for floppies, opticals, etc...
Quoted 3 lines
Yes, but the point is
_dependantreads_. This is why Andrea's approach alone can't solve dependant read vs write or nondependant read - while maintaining a good throughput.
note that for soem workloads the _dependant reads_ can have _dependant writes_ in between. I know it's not the most common case though, but I don't love too much to make reads that much special. But again, it makes perfect sense to have it as a feature, but I wouldn't like it to be only option, I mean there must always be a way to disable anticipatory scheduling like there must be a way to disable SFQ (infact for SFQ it makes sense to leave it disabled by default, it's only a few people that definitely only cares to have the lowest possible latency for mplayer or xmms, or for multiuser system doing lots of I/O, but those guys can't live without it)
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 54 lines · Andrea Arcangeli
Quoted 36 lines · Nick Piggin
Quoted 11 lines · Rik van Riel
Quoted 8 lines · Nick Piggin
Quoted 4 lines · Andrea Arcangeli
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
Quoted 7 lines
Quoted 3 lines
Sounds nice. I would like to see per process disk distribution.
Sounds like the easiest way to get that fair, indeed. Manage every disk as a separately scheduled resource...
I hope this option becomes available one day.
Quoted 5 lines
Quoted 5 lines
However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.
Quoted 7 lines
Considering that one medium/far disk seek counts for about 400 kB of data read/write, I suspect we'll just want to merge requests or put adjacant requests next to each other into the elevator up to a fairly large size. Probably about 1 MB for a hard disk or a cdrom, but much less for floppies, opticals, etc...
Quoted 4 lines
Yes, but the point is
_dependantreads_. This is why Andrea's approach alone can't solve dependant read vs write or nondependant read - while maintaining a good throughput.note that for soem workloads the
_dependantreads_can have_dependantwrites_in between. I know it's not the most common case though, but I don't love too much to make reads that much special. But again, it makes perfect sense to have it as a feature, but I wouldn't like it to be only option, I mean there must always be a way to disable anticipatory scheduling like there must be a way to disable SFQ (infact for SFQ it makes sense to leave it disabled by default, it's only a few people that definitely only cares to have the lowest possible latency for mplayer or xmms, or for multiuser system doing lots of I/O, but those guys can't live without it)
Quoted 2 lines
Andrea
If you pass the information down, the IO scheduler can easily put a lower expiry time on sync writes for example, or a higher one on async reads. This isn't what the anticipatory scheduler patch is about.
The point is that it is very easy to get a huge backlog of writes for the purpose of disk head schedule optimising, but this is difficult with reads, anticipatory scheduling helps address this. Thats all really.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliQuoted 2 lines · Andrea Arcangeli
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
"The only way" ? That sounds like a lack of fantasy ;))
Having said that, I like the idea of using SFQ for fairness, since it seems to work really well for networking... I'll definately try such a patch.
Quoted 6 lines
The only other possible fix would be to reduce the I/O queue to say 512kbytes and to take advantage of the FIFO behaviour of the queue wakeups, I tried that, it works so well, you can trivially test it with my elevator-lowlatency by just changing a line, but the problem is 512k is a too small I/O pipeline, i.e. it is not enough to guarantee the maximal throughput during contigous I/O.
Maybe you want to count the I/O pipeline size in disk seeks and not in disk blocks ?
In the time of one disk seek plus half rotational latency (12 ms) you can do a pretty large amount of reading (>400kB). This means that for near and medium disk seeks you don't care all that much about how large the submitted IO is. Track buffers further reduce this importance.
OTOH, if you're seeking to the track next-door, or have mixed read and write operations on the same track, the seek time goes to near-zero and only the rotational latency counts. In that case the size of the IO does have an influence on the speed the request can be handled.
Quoted 3 lines
the stochastic fair queueing will also make the anticipatory scheduling a very low priority to have. Stochasting fair queueing will be an order of magnitude more important than anticipatory scheduling IMHO.
On the contrary, once we have SFQ to fix the biggest elevator problems the difference made by the anticipatory scheduler should be much more visible.
Think of a disk with 6 track buffers for reading and a system with 10 active reader processes. Without the anticipatory scheduler you'd need to go to the platter for almost every OS read (because each process flushes out the track buffer for the others), while with the anticipatory scheduler you've got a bigger chance of having the data you want in one of the drive's track buffers, meaning that you don't need to go to the platter but can just do a silicon to silicon copy.
If you look at the academic papers of an anticipatory scheduler, you'll find that it gives as much as a 73% increase in throughput. On real-world tasks, not even on specially contrived benchmarks.
The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.
regards,
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 4 lines · Rik van Riel
The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.
Forget that I said that, we don't have the infrastructure to get this right. The definition of "synchronous" is "some process is waiting on this request to complete", but processes wait on other objects instead.
A normal sequence (probably the most common) is:
1) submit request
(request is now asynchronous)
2) wait_on_page
(request should now magically become synchronous)
The infrastructure to get this working is probably too big a change for 2.5/2.6, at this point, so chances are that we're better off using the (90% accurate?) distinction between reads and writes.
regards,
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
David Lang
Quoted 45 lines · Rik van Riel
Date: Mon, 10 Feb 2003 02:15:10 -0200 (BRST)
From: Rik van Riel <[email protected]>
To: Andrea Arcangeli <[email protected]>
Cc: Con Kolivas <[email protected]>, lkml <[email protected]>,
Jens Axboe <[email protected]>
Subject: Re: stochastic fair queueing in the elevator [Re: [BENCHMARK]2.4.20-ck3 / aa / rmap with contest]Quoted 4 lines · Rik van Riel
The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.
Forget that I said that, we don't have the infrastructure to get this right. The definition of "synchronous" is "some process is waiting on this request to complete", but processes wait on other objects instead.
A normal sequence (probably the most common) is:
1) submit request
(request is now asynchronous)
2)wait_on_page
(request should now magically become synchronous)The infrastructure to get this working is probably too big a change for 2.5/2.6, at this point, so chances are that we're better off using the (90% accurate?) distinction between reads and writes.
regards,
Rik
--
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/ http://guru.conectiva.com/
Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a> -
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 3 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
Exactly. This is nasty with our current data structures; probably not something to do during the current code slush.
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 8 lines · Rik van Riel
Quoted 3 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
Exactly. This is nasty with our current data structures; probably not something to do during the current code slush.
as I said, you can consider asychronous all requests submitted with current->mm, this will be 90% accurate. This whole thing is an heuristic, if the heuristic fails the behaviour become like w/o SFQ so no regression. Also the latency of fsync is less critical than the latency of a read() syscall, again, this is statistically, sometime it can be the other way around.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to David LangQuoted 4 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
It's still approximate. An exact solution would involve only marking I/O as synchronous when some process actually waits on its completion. I do not believe that all the extra lookup and locking infrastructure and storage which this would require is justified. Certainly not in a first iteration.
The Rice Uni researchers did implement controls which attempted to learn IO submission patterns on a per-process basis, and I believe these were also used to avoid undesirable starvations. We have only briefly played with process-aware logic.
The first thing to do is to get the anticipatory scheduler working properly. Nick has been tied down for a week chasing generic bugs in the request layer. He seems to have nailed the important ones now.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 8 lines · Andrew Morton
Quoted 4 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
An fsync might change already submitted asynchronous writes into synchronous writes, but this is not something I'm going to lose sleep over. ;)
Quoted 4 lines
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
It's still approximate.
Sounds like a good enough approximation to me.
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 7 lines · Rik van Riel
Quoted 6 lines · Andrew Morton
Quoted 4 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
Quoted 6 lines
Quoted 2 lines
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
An fsync might change already submitted asynchronous writes into synchronous writes, but this is not something I'm going to lose sleep over. ;)
correct.
Quoted 7 lines
Quoted 5 lines
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
It's still approximate.
Sounds like a good enough approximation to me.
yes, the approximation should be more than enough IMHO
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrew MortonQuoted 11 lines · Andrew Morton
Quoted 4 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
This may be a terribly stupid question, if so pls. just tell me :)
I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?
If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).
Quoted 4 lines
It's still approximate. An exact solution would involve only marking I/O as synchronous when some process actually waits on its completion. I do not believe that all the extra lookup and locking infrastructure and storage which this would require is justified. Certainly not in a first iteration.
Just a quirk; NFS file servers.
The client does read-ahead - the nfsd on the server-side will wait for the read request, thus the read is synchronous... But it's not.
Signature · 6 lines
................................................................ : [email protected] : And I see the elder races, : :.........................: putrid forms of man : : Jakob Østergaard : See him rise and claim the earth, : : OZ9ABN : his downfall is at hand. : :.........................:............{Konkhra}...............:
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 16 lines · Jakob Oestergaard
Quoted 11 lines · Andrew Morton
Quoted 4 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
This may be a terribly stupid question, if so pls. just tell me :)
Quoted 8 lines
I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?
If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).
Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.
Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.
Nick
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
On Mon, Feb 10, 2003 at 03:58:26PM +1100, Nick Piggin wrote:
...
Quoted 8 lines
Quoted 5 lines
If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).
Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.
I buy the sequential-argument - very good point.
Thanks,
Quoted 3 lines
Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.
I'm curious as to how these things will interact in the NFS server<->client situation :)
Time will show, I guess.
Random data-point (not meant as a rant - I'm happy for all I got ;)
In stock 2.4.20 the interaction is horrible - whatever was done there is
not optimal. A 'tar xf' on the client will neither load the network
nor the server - it seems to be network latency bound (readahead not doing it's job - changing min-readahead and max-readahead on the client doesn't seem to make a difference). However, my desktop (running on the client) can hang for 10 seconds straight every half hour or so, when the nightly backup runs on the server (local disk reads streaming at around 2 MB/sec from an array capable of at least 40 MB/sec).
Signature · 6 lines
................................................................ : [email protected] : And I see the elder races, : :.........................: putrid forms of man : : Jakob Østergaard : See him rise and claim the earth, : : OZ9ABN : his downfall is at hand. : :.........................:............{Konkhra}...............:
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 5 lines · Jakob Oestergaard
In stock 2.4.20 the interaction is horrible - whatever was done there is
not optimal. A 'tar xf' on the client will neither load the network
nor the server - it seems to be network latency bound (readahead not doing it's job - changing min-readahead and max-readahead on the client doesn't seem to make a difference). However, my desktop (running on the
This sounds like the traditional NFS suckage that has been there for decades. The problem is that 'tar xf' ends up doing a *LOT* of NFS calls - a huge stream of stat()/open()/chmod()/utime() calls. On a local disk, most of this gets accelerated by the in-core inode cache, but on an NFS mount, you're looking at lots and lots of synchronous calls.
In 'man 5 exports':
async This option allows the NFS server to violate the NFS protocol
and reply to requests before any changes made by that request have been committed to stable storage (e.g. disc drive).
Using this option usually improves performance, but at the cost that an unclean server restart (i.e. a crash) can cause data to be lost or corrupted.
In releases of nfs-utils upto and including 1.0.0, this option
was the default. In this and future releases, sync is the
default, and async must be explicit requested if needed. To
help make system adminstrators aware of this change, 'exportfs' will issue a warning if neither sync nor async is specified.
Does this address your NFS issue?
Signature · 3 lines
Valdis Kletnieks Computer Systems Senior Engineer Virginia Tech
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 24 lines · On Mon, Feb 10, 2003 at 01:06:27AM -0500, [email protected] wrote:
Quoted 5 lines · Jakob Oestergaard
In stock 2.4.20 the interaction is horrible - whatever was done there is
not optimal. A 'tar xf' on the client will neither load the network
nor the server - it seems to be network latency bound (readahead not doing it's job - changing min-readahead and max-readahead on the client doesn't seem to make a difference). However, my desktop (running on theThis sounds like the traditional NFS suckage that has been there for decades. The problem is that 'tar xf' ends up doing a *LOT* of NFS calls - a huge stream of stat()/open()/chmod()/utime() calls. On a local disk, most of this gets accelerated by the in-core inode cache, but on an NFS mount, you're looking at lots and lots of synchronous calls.
In 'man 5 exports':
async This option allows the NFS server to violate the NFS protocol
and reply to requests before any changes made by that request have been committed to stable storage (e.g. disc drive).Using this option usually improves performance, but at the cost that an unclean server restart (i.e. a crash) can cause data to be lost or corrupted.
Quoted 7 lines
In releases of nfs-utils upto and including 1.0.0, this option
was the default. In this and future releases, sync is the
default, and async must be explicit requested if needed. To
help make system adminstrators aware of this change, 'exportfs' will issue a warning if neither sync nor async is specified.Does this address your NFS issue?
No. Tried it in the past, just tried it again to make sure.
The caching should be done client-side, I guess, to be effective. Even if the server acknowledges operations before they hit the disks, the client is still bound by the RPC call latency.
I'm sure there are problems preventing such caching... Hmm... Seems
like the only way out is a multi-threaded tar ;) Or tar using AIO.
Btw. nocto on the client doesn't really seem to help matters much either.
Thanks for the suggestion,
Signature · 6 lines
................................................................ : [email protected] : And I see the elder races, : :.........................: putrid forms of man : : Jakob Østergaard : See him rise and claim the earth, : : OZ9ABN : his downfall is at hand. : :.........................:............{Konkhra}...............:
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Nick PigginQuoted 28 lines · Nick Piggin
Quoted 18 lines · Jakob Oestergaard
Quoted 7 lines · Andrew Morton
Quoted 5 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous'
as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.Quoted 6 lines
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
This may be a terribly stupid question, if so pls. just tell me :)
Quoted 8 lines
I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?
If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).
Quoted 7 lines
Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.
Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.
the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 37 lines · Andrea Arcangeli
Quoted 35 lines · Nick Piggin
Quoted 19 lines · Jakob Oestergaard
Quoted 8 lines · Andrew Morton
Quoted 5 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
Quoted 6 lines
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
This may be a terribly stupid question, if so pls. just tell me :)
Quoted 9 lines
I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?
If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).
Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.
Quoted 9 lines
Quoted 4 lines
Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.
the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.
You seem to be forgetting things like seek time.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 47 lines · Nick Piggin
Quoted 45 lines · Andrea Arcangeli
Quoted 42 lines · Nick Piggin
Quoted 22 lines · Jakob Oestergaard
Quoted 10 lines · Andrew Morton
Quoted 7 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous'
as should writes to any partition mounted with the sync option, or writes
to a directory with the S flag set.Quoted 7 lines
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
This may be a terribly stupid question, if so pls. just tell me :)
Quoted 9 lines
I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?
If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).
Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.
Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.
Quoted 5 lines
Quoted 4 lines
the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.
You seem to be forgetting things like seek time.
I didn't say it's the only purpose. Of course there's no hope for merging in the metadata dependent reads of the fs where anticipatory scheduling does its best, and infact they don't even attempt to do any readhaead. BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 5 lines · Andrea Arcangeli
BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.
Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.
And neither fs performs inode table readahead.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 9 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli
BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.
Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.
At least for big directories it should be at least a quite obvious microoptimization, if you do it at the logical level. Maybe it wasn't worthwhile in the past (like in ext3) because it was done at the block layer with a dumb reada rather than with proper read of the next logical block before wait_on_buffer. Also keep in mind the max readahead generated by the block layer is nothing compared to the true readahead that the logical layer is able to generate.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 12 lines · Andrea Arcangeli
Quoted 9 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli
BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.
Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.
Quoted 8 lines
At least for big directories it should be at least a quite obvious microoptimization, if you do it at the logical level. Maybe it wasn't worthwhile in the past (like in ext3) because it was done at the block layer with a dumb reada rather than with proper read of the next logical block before
wait_on_buffer. Also keep in mind the max readahead generated by the block layer is nothing compared to the true readahead that the logical layer is able to generate.
No, it's doing the directory readahead against the correct blocks (it calls ext3_getblk() to find them).
Large directories tend to be spread all around the disk anyway. And I've never explicitly tested for any problems which the loss of readahead might have caused ext2. Nor have I tested inode table readahead. Guess I should.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 22 lines · Andrew Morton
Quoted 12 lines · Andrea Arcangeli
Quoted 9 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli
BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.
Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.
Quoted 8 lines
At least for big directories it should be at least a quite obvious microoptimization, if you do it at the logical level. Maybe it wasn't worthwhile in the past (like in ext3) because it was done at the block layer with a dumb reada rather than with proper read of the next logical block before
wait_on_buffer. Also keep in mind the max readahead generated by the block layer is nothing compared to the true readahead that the logical layer is able to generate.
Quoted 2 lines
No, it's doing the directory readahead against the correct blocks (it calls
ext3_getblk()to find them).
yes, sorry.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrew MortonQuoted 6 lines · Andrew Morton
Large directories tend to be spread all around the disk anyway. And I've never explicitly tested for any problems which the loss of readahead might have caused ext2. Nor have I tested inode table readahead. Guess I should.
Quoted 9 lines
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.
For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.
Signature · 1 line
Hans
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 18 lines · Hans Reiser
Quoted 7 lines · Andrew Morton
Large directories tend to be spread all around the disk anyway. And I've never explicitly tested for any problems which the loss of readahead might have caused ext2. Nor have I tested inode table readahead. Guess I should.
Quoted 9 lines
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 1 line
readahead seems to be less effective for non-sequential objects. Or at
yes, this is why I said readahead matters mostly to generate the big dma commands, so if the object is sequential it will be served by the lowlevel with a single dma using SG. this is also why when I moved the high dma limit of scsi to 512k (from 128k IIRC) I got such a relevant throughput improvement. Also watch the read speed in my tree compared to 2.4 and 2.5 in bigbox.html from Randy (bonnie shows it well).
Quoted 3 lines
least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.
Agreed.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 23 lines · Andrea Arcangeli
Quoted 18 lines · Hans Reiser
Quoted 5 lines · Andrew Morton
Large directories tend to be spread all around the disk anyway. And I've never explicitly tested for any problems which the loss of readahead might have caused ext2. Nor have I tested inode table readahead. Guess I should.
Quoted 10 lines
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/Quoted 2 lines
readahead seems to be less effective for non-sequential objects. Or at
Quoted 7 lines
yes, this is why I said readahead matters mostly to generate the bigdma commands, so if the object is sequential it will be served by the lowlevel with a single dma using SG. this is also why when I moved the high dma limit of scsi to 512k (from 128k IIRC) I got such a relevant throughput improvement. Also watch the read speed in my tree compared to 2.4 and 2.5 in bigbox.html from Randy (bonnie shows it well).
...AND readahead matters mostly to disk head scheduling when there is other IO competing with the streaming read...
A big throughput improvement would have seen would be all to do with better disk head scheduling due to the larger request sizes, yeah? And this would probably be to do with the elevator accounting being based on requests and/or seeks. You shouldn't notice much difference with the elevator stuff in Andrew's mm patches.
I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.
Nick
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 3 lines · Nick Piggin
I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.
I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 6 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin
I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.
Quoted 8 lines
I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)
I thought scsi in 2.5 was doing 512k I/O's at present???
Doesn't Randy attribute the differences there to an updated
qlogic driver? (Or was the update to allow 512k I/O's? ;))
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 16 lines · Andrew Morton
Quoted 6 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin
I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.
Quoted 8 lines
I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)
Quoted 4 lines
I thought scsi in 2.5 was doing 512k I/O's at present???
Doesn't Randy attribute the differences there to an updated
qlogic driver? (Or was the update to allow 512k I/O's? ;))
The special case of the qlogic that Randy is using does 256k commands with the new driver.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliQuoted 7 lines · Andrea Arcangeli
Quoted 4 lines · Nick Piggin
I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.
Quoted 8 lines
I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)
Yes it is very clear from the numbers that your tree is more than 150% the speed for reads. As I said I don't know too much about SCSI, but it is very interesting that writes don't get a noticable improvement although they would be using the bigger request sizes too, right? Something is causing this but the cpu, bus, wire overhead of using small requests does not seem to be it.
Nick
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 17 lines · Nick Piggin
Quoted 7 lines · Andrea Arcangeli
Quoted 4 lines · Nick Piggin
I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.
Quoted 8 lines
I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)
Quoted 2 lines
Yes it is very clear from the numbers that your tree is more than 150% the speed for reads. As I said I don't know too much about
correct, that's the huge improvement I get in the read sequential case (i.e. bonnie), which is a crucial common workload.
Quoted 3 lines
SCSI, but it is very interesting that writes don't get a noticable improvement although they would be using the bigger request sizes too, right? Something is causing this but the cpu, bus, wire
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
writes don't need readahead to use the max command size, they always used it since the first place, so they can't go even faster, they never had a problem.
It's by fixing readahead that reads gets boosted. this has nothing to do with writes or the max_sectors itself.
You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.
Quoted 4 lines
overhead of using small requests does not seem to be it.
Nick
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 22 lines · Andrea Arcangeli
Quoted 20 lines · Nick Piggin
Quoted 17 lines · Andrea Arcangeli
Quoted 5 lines · Nick Piggin
I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.
I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)
Quoted 7 lines
Quoted 3 lines
Yes it is very clear from the numbers that your tree is more than 150% the speed for reads. As I said I don't know too much about
correct, that's the huge improvement I get in the read sequential case (i.e. bonnie), which is a crucial common workload.
Yep
Quoted 7 lines
Quoted 6 lines
SCSI, but it is very interesting that writes don't get a noticable improvement although they would be using the bigger request sizes too, right? Something is causing this but the cpu, bus, wire
Quoted 8 lines
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
writes don't need readahead to use the max command size, they always used it since the first place, so they can't go even faster, they never had a problem.
Yes I am an idiot, I don't know why I said that :P
Quoted 10 lines
It's by fixing readahead that reads gets boosted. this has nothing to do with writes or the
max_sectorsitself.You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.
Look at the few simple tests I have been posting - it clearly indicates the need is decreased. I did say however that it would be subject to CPU/bus/device overheads. I did not realiase SCSI setups would behave like this. From a purely disk head perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 2 lines · Nick Piggin
perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).
I'm guessing that physically it may be needed from a head prospective too, I doubt it only has to do with the in-core overhead. Seeing it all before reaching the seek point might allow the disk to do smarter things and to keep the head at the right place for longer, dunno. Anyways, whatever is the reason it doesn't make much difference from our point of view ;), but I don't expect this hardware behaviour changing in future high end storage.
NOTE: just to be sure, I'm not at all against anticpiatory scheduling, it's clearly a very good feature to have (still I would like an option to disable it especially in heavy async environments like databases, where lots of writes are sync too) but it should be probably be enabled by default, especially for the metadata reads that have to be synchronous by design.
Infact I wonder that it may be interesting to also make it optionally controlled from a fs hint (of course we don't pretend all fs to provide the hint), so that you stall I/O writes only when you know for sure you're going to submit another read in a few usec, just the time to parse the last metadata you read. Still a timeout would be needed for scheduling against RT etc..., but it could be a much more relaxed timeout with this option enabled, so it would need less accurate timings, and it would be less dependent on hardware, and it would be less prone to generate false positive stalls. The downside is having to add the hints.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 6 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin
perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).
Quoted 8 lines
I'm guessing that physically it may be needed from a head prospective too, I doubt it only has to do with the in-core overhead. Seeing it all before reaching the seek point might allow the disk to do smarter things and to keep the head at the right place for longer, dunno. Anyways, whatever is the reason it doesn't make much difference from our point of view ;), but I don't expect this hardware behaviour changing in future high end storage.
I don't understand it at all. I mean there is no other IO going on so there would be no reason for the disk head to move anyway. Rotational latency should be basically non-existant due to track buffers, and being FC RAID hardware you wouldn't expect them to skimp on anything.
Quoted 9 lines
NOTE: just to be sure, I'm not at all against anticpiatory scheduling, it's clearly a very good feature to have (still I would like an option to disable it especially in heavy async environments like databases, where lots of writes are sync too) but it should be probably be enabled by default, especially for the metadata reads that have to be synchronous by design.
Yes it definately has to be selectable (in fact, in my current version, setting antic_expire = 0 disables it), and Andrew has been working on tuning the non anticipatory version into shape.
Quoted 13 lines
Infact I wonder that it may be interesting to also make it optionally controlled from a fs hint (of course we don't pretend all fs to provide the hint), so that you stall I/O writes only when you know for sure you're going to submit another read in a few usec, just the time to parse the last metadata you read. Still a timeout would be needed for scheduling against RT etc..., but it could be a much more relaxed timeout with this option enabled, so it would need less accurate timings, and it would be less dependent on hardware, and it would be less prone to generate false positive stalls. The downside is having to add the hints.
It would be easy to anticipate or not based on hints. We could anticipate sync writes if we wanted, lower expire time for sync writes, increase it for async reads. It is really not very complex (although the code needs tidying up).
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 16 lines · Nick Piggin
Quoted 6 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin
perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).
Quoted 8 lines
I'm guessing that physically it may be needed from a head prospective too, I doubt it only has to do with the in-core overhead. Seeing it all before reaching the seek point might allow the disk to do smarter things and to keep the head at the right place for longer, dunno. Anyways, whatever is the reason it doesn't make much difference from our point of view ;), but I don't expect this hardware behaviour changing in future high end storage.
Quoted 1 line
I don't understand it at all. I mean there is no other IO going
Unfortunately I can't help you understand it, but this is what I found with my pratical experience, I found it the first time in my alpha years ago when I increased the sym to 512k in early 2.4 then since it could break stuff we added the max_sectors again in 2.4. But of course if you don't fix readahead there's no way reads can take advantage of these lowlevel fixes. I thought I fixed readahead too but I felt it got backed out and when I noticed I resurrected it in my tree (see the name of the patch ;)
Quoted 10 lines
Quoted 7 lines
NOTE: just to be sure, I'm not at all against anticpiatory scheduling, it's clearly a very good feature to have (still I would like an option to disable it especially in heavy async environments like databases, where lots of writes are sync too) but it should be probably be enabled by default, especially for the metadata reads that have to be synchronous by design.
Yes it definately has to be selectable (in fact, in my current version, setting
antic_expire= 0 disables it), and Andrew has been working on tuning the non anticipatory version into shape.
Great.
Quoted 11 lines
Quoted 11 lines
Infact I wonder that it may be interesting to also make it optionally controlled from a fs hint (of course we don't pretend all fs to provide the hint), so that you stall I/O writes only when you know for sure you're going to submit another read in a few usec, just the time to parse the last metadata you read. Still a timeout would be needed for scheduling against RT etc..., but it could be a much more relaxed timeout with this option enabled, so it would need less accurate timings, and it would be less dependent on hardware, and it would be less prone to generate false positive stalls. The downside is having to add the hints.
Quoted 1 line
It would be easy to anticipate or not based on hints. We could
yep.
Quoted 3 lines
anticipate sync writes if we wanted, lower expire time for sync writes, increase it for async reads. It is really not very complex (although the code needs tidying up).
this is not the way I thought at it. I'm interested to give an hint only to know for sure which are the intermediate sync dependent reads (the obvious example is when doing the get_block and walking the 3 level of inode indirect metadata blocks with big files, or while walking the balanced tree in reiserfs), and I'm not interested at all about writes. And I would just set an higher timeout when a read that I know for sure (thanks to the hint) is "intermdiate" is completed. We can use high timeouts there because we know they won't trigger 90% of the time, a new dependent read will be always submitted first.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 5 lines · Andrea Arcangeli
Quoted 2 lines · Nick Piggin
I don't understand it at all. I mean there is no other IO going
Quoted 9 lines
Unfortunately I can't help you understand it, but this is what I found with my pratical experience, I found it the first time in my alpha years ago when I increased the sym to 512k in early 2.4 then since it could break stuff we added the
max_sectorsagain in 2.4. But of course if you don't fix readahead there's no way reads can take advantage of these lowlevel fixes. I thought I fixed readahead too but I felt it got backed out and when I noticed I resurrected it in my tree (see the name of the patch ;)
Fair enough. I accept it is important. Still think its odd ;)
[snip]
Quoted 11 lines
Quoted 2 lines
It would be easy to anticipate or not based on hints. We could
yep.
Quoted 4 lines
anticipate sync writes if we wanted, lower expire time for sync writes, increase it for async reads. It is really not very complex (although the code needs tidying up).
Quoted 10 lines
this is not the way I thought at it. I'm interested to give an hint only to know for sure which are the intermediate sync dependent reads (the obvious example is when doing the
get_blockand walking the 3 level of inode indirect metadata blocks with big files, or while walking the balanced tree in reiserfs), and I'm not interested at all about writes. And I would just set an higher timeout when a read that I know for sure (thanks to the hint) is "intermdiate" is completed. We can use high timeouts there because we know they won't trigger 90% of the time, a new dependent read will be always submitted first.
This is a lot of nitty gritty stuff. It will all help, especially in corner cases. Luckily it seems you don't need such infrastructure to demonstrate most anticipatory scheduler gains.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 2 lines · Nick Piggin
in corner cases. Luckily it seems you don't need such infrastructure to demonstrate most anticipatory scheduler gains.
sure. I guess it would be most important to be allowed to leave anticipatory scheduling enabled *always* even with very async-io intensive workloads, so when you read a file with normal fileutiles you still can take advantage of it for the most important places. Ideally in this case where w/o the hint we might have to disable anticipatory scheduling completely to get peak async-io performance, the non-hint timeout could be zero (i.e. no stall at all) and the kernel would understand and do the right thing
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliQuoted 9 lines · Andrea Arcangeli
Quoted 2 lines · Nick Piggin
perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).
I'm guessing that physically it may be needed from a head prospective too, I doubt it only has to do with the in-core overhead. Seeing it all before reaching the seek point might allow the disk to do smarter things
NOTE: just to be sure, I'm not at all against anticpiatory scheduling,
Most disks seem to have a large cache, but with the cache unit for most of the cache being one _track_ at a time.
This has the effect of the disk reading one track in at a time, but only being able to cache a few of these tracks in its cache.
Anticipatory scheduling should reduce any thrashing of this disk cache.
regards,
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliQuoted 4 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
- *max_ra++ = vm_max_readahead;
+ *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.
Quoted 5 lines
You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.
The anticipatory scheduler can easily permit 512k of reading before seeking away to another file. In fact it can allow much more, without requiring that readhead be cranked up.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 13 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
(quoted diff) +1
-1- *max_ra++ = vm_max_readahead; + *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 4 lines
Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.
Though Andrea did say it is a "single threaded" streaming read. That is what I can't understand. Movement of the disk head should be exactly the same in either situation and 128K is not exactly a pitiful request size - so it suggests a quirk somewhere. It is not as if the disk has to be particularly smart or know a lot about the data in order to optimise the head movement for a load like this.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 15 lines · Nick Piggin
Quoted 13 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
(quoted diff) +1
-1- *max_ra++ = vm_max_readahead; + *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 5 lines
Quoted 4 lines
Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.
Though Andrea did say it is a "single threaded" streaming read.
yes, I pointed you to bonnie read sequential in bigbox.html, not tiobench.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 24 lines · Andrea Arcangeli
Quoted 22 lines · Nick Piggin
Quoted 19 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
(quoted diff) +1
-1- *max_ra++ = vm_max_readahead; + *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.
Quoted 6 lines
Quoted 2 lines
Though Andrea did say it is a "single threaded" streaming read.
yes, I pointed you to bonnie read sequential in bigbox.html, not tiobench.
The same pattern is also observed with single threaded tiobench anyway.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 27 lines · Nick Piggin
Quoted 25 lines · Andrea Arcangeli
Quoted 23 lines · Nick Piggin
Quoted 20 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
(quoted diff) +1
-1- *max_ra++ = vm_max_readahead; + *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;Well of course that will get bigger bonnie numbers, for exactly the reasons
I've explained. It will seek between files after every 512k rather than after every 128k.
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
Though Andrea did say it is a "single threaded" streaming read.
yes, I pointed you to bonnie read sequential in bigbox.html, not tiobench.
The same pattern is also observed with single threaded tiobench anyway.
yes, of course.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Nick PigginQuoted 16 lines · Nick Piggin
Quoted 13 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
(quoted diff) +1
-1- *max_ra++ = vm_max_readahead; + *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 5 lines
Quoted 4 lines
Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.
Though Andrea did say it is a "single threaded" streaming read.
Oh sorry, I missed that.
Quoted 6 lines
That is what I can't understand. Movement of the disk head should be exactly the same in either situation and 128K is not exactly a pitiful request size - so it suggests a quirk somewhere. It is not as if the disk has to be particularly smart or know a lot about the data in order to optimise the head movement for a load like this.
Yes, that's a bit odd. Some reduction in CPU cost and bus
traffic, etc would be expected. Could be that sending out a
request which is larger than a track is saving a rev of the disk for some reason.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 3 lines · Andrew Morton
traffic, etc would be expected. Could be that sending out a
request which is larger than a track is saving a rev of the disk for some reason.
I'm guessing something on those lines yes, I doubt it's purerely in core overhead that makes that much difference. Just for completeness, I never read this in literature or data sheets, this is all out of pratical experience, so we can't exclude something odd in the scsi layer, but I very much doubt, the only thing that might explain it is to waste cpu and we know it's not wasting it.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrew MortonQuoted 10 lines · Andrew Morton
Quoted 7 lines · Nick Piggin
That is what I can't understand. Movement of the disk head should be exactly the same in either situation and 128K is not exactly a pitiful request size - so it suggests a quirk somewhere. It is not as if the disk has to be particularly smart or know a lot about the data in order to optimise the head movement for a load like this.
Quoted 5 lines
Yes, that's a bit odd. Some reduction in CPU cost and bus
traffic, etc would be expected. Could be that sending out a
request which is larger than a track is saving a rev of the disk for some reason.
Shouldn't be. Even at 128KB readahead we should always have outstanding requests against the disk in a streaming read scenario, right? Maybe if the track buffers are bigger than 128K?
Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 2 lines · Nick Piggin
Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?
I recall more than 512k wasn't worthwhile anymore
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 8 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin
Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?
I recall more than 512k wasn't worthwhile anymore
Behaviour between 128 and 512 would be interesting then
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 11 lines · Nick Piggin
Quoted 8 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin
Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?
I recall more than 512k wasn't worthwhile anymore
Behaviour between 128 and 512 would be interesting then
this is exactly what is shown by Randy's bonnie ;)
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 20 lines · Andrea Arcangeli
Quoted 17 lines · Nick Piggin
Quoted 13 lines · Andrea Arcangeli
Quoted 5 lines · Nick Piggin
Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?
I recall more than 512k wasn't worthwhile anymore
Quoted 6 lines
Quoted 3 lines
Behaviour between 128 and 512 would be interesting then
this is exactly what is shown by Randy's bonnie ;)
I don't see it... I mean eg 192, 256, 320...
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrew MortonQuoted 2 lines · Andrew Morton
Could be that sending out a request which is larger than a track is saving a rev of the disk for some reason.
I guess disks are optimised for the benchmarks that are run by popular PC magazines ...
After all, those benchmarks and the sales price are the main factors determining sales ;)
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 7 lines · ext Rik van Riel
Quoted 2 lines · Andrew Morton
Could be that sending out a request which is larger than a track is saving a rev of the disk for some reason.
I guess disks are optimised for the benchmarks that are run by popular PC magazines ...
Yes, absolutely they are (I used to work for one such company that no longer exists). However, there's a catch -- the disk drive companies are optimizing for the test as currently constituted, but the test keeps changing. So they're optimizing for version N-1 while the magazine is publishing N. Can't help it. Ever heard of the Nyquist frequency?
Quoted 4 lines
After all, those benchmarks and the sales price are the main factors determining sales ;)
Yup. In general, it's capacity first, then reliability, then performance. No, wait, not quite; the FIRST criterion is the ability to ship when you say you will. If you make Dell late on shipping a bunch of machines, you WILL feel the pain.
--Rod
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrew MortonQuoted 12 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
(quoted diff) +1
-1- *max_ra++ = vm_max_readahead; + *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 3 lines
Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.
NOTE: first there is no seek at all in the benchmark we're talking about, no idea why you think there are seeks. This is not tiobench, this is bonnie sequential read.
Second I increased it to 4 times 128k very recently, it was used to be exactly 128k and 512k for scsi. Infact the difference happens in SCSI not IDE, where going past 128k is helpful, on ide as said the limit of the command is limited by the hardware anyways.
the only thing you can argue is that the qla is capable of max 256k per command, and I'm doing readahead of 512k at once, but I don't think it can matter, like it doesn't matter now that I increased it even more, all it matters is not to stop at 128k, and to submit the 256k commands.
Quoted 10 lines
Quoted 6 lines
You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.
The anticipatory scheduler can easily permit 512k of reading before seeking away to another file. In fact it can allow much more, without requiring that readhead be cranked up.
This has nothing to do with "the other file". There is a single task in the system, it is in replacement of /sbin/init, it never forks and it never opens more than 1 single file called /myfile. Nothing else nothing more.
anticipatory scheduling can't help in any way that benchmark, period. If you destroy readahead you won't be able to build the scsi command of the optimal size and this will hurt. Waiting can't help this.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 14 lines · Andrea Arcangeli
Quoted 12 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
(quoted diff) +1
-1- *max_ra++ = vm_max_readahead; + *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 9 lines
Quoted 4 lines
Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.
NOTE: first there is no seek at all in the benchmark we're talking about, no idea why you think there are seeks. This is not tiobench, this is bonnie sequential read.
Yes, Andrew obviously missed this... Anyway, could it be due to a big stripe size and hitting more disks in the RAID? How does a single SCSI disk perform here, Andrea?
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 22 lines · Nick Piggin
Quoted 20 lines · Andrea Arcangeli
Quoted 17 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli
It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.
Oh bah.
(quoted diff) +1
-1- *max_ra++ = vm_max_readahead; + *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;Well of course that will get bigger bonnie numbers, for exactly the reasons
I've explained. It will seek between files after every 512k rather than after every 128k.
Quoted 7 lines
Quoted 4 lines
NOTE: first there is no seek at all in the benchmark we're talking about, no idea why you think there are seeks. This is not tiobench, this is bonnie sequential read.
Yes, Andrew obviously missed this... Anyway, could it be due to a big stripe size and hitting more disks in the RAID? How does a single SCSI disk perform here, Andrea?
Actually I increased readahead to more than just 512k in my last tree, especially to take care of RAID :) so that both lowlevel will get the 512k, instead of being limited to 256k command each 8) This might apply to hardware raid too.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliIs the following a fair summary?
There is a certain minimum size required for the IOs to be cost effective. This can be determined by single reader benchmarking. Only readahead and not anticipatory scheduling addresses that.
Anticipatory scheduling does not address the application that spends one minute processing every read that it makes. Readahead does.
Anticipatory scheduling does address the application that reads multiple files that are near each other (because they are in the same directory), and current readahead implementations (excepting reiser4 in progress vaporware) do not.
Anticipatory scheduling can do a better job of avoiding unnecessary reads for workloads with small time gaps between reads than readahead (it is potentially more accurate for some workloads).
Is this a fair summary?
Signature · 1 line
Hans
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 14 lines · Hans Reiser
Is the following a fair summary?
There is a certain minimum size required for the IOs to be cost effective. This can be determined by single reader benchmarking. Only readahead and not anticipatory scheduling addresses that.
Anticipatory scheduling does not address the application that spends one minute processing every read that it makes. Readahead does.
Anticipatory scheduling does address the application that reads multiple files that are near each other (because they are in the same directory), and current readahead implementations (excepting reiser4 in progress vaporware) do not.
Quoted 5 lines
Anticipatory scheduling can do a better job of avoiding unnecessary reads for workloads with small time gaps between reads than readahead (it is potentially more accurate for some workloads).
Is this a fair summary?
I would also add what I feel the most important thing, that is anticipatory scheduling can help decreasing a lot the latencies of filesystem reads in presence of lots of misc I/O, by knowing which are the read commands that are intermediate-dependent-sync, that means knowing a new dependent read will be submitted very quickly as soon as the current read-I/O is completed. In such a case it makes lots sense to wait for the next read to be submitted instead of start processing immediatly the rest of the I/O queue. This way when you read a file and you've to walk the indirect blocks before being able to read the data, you won't be greatly peanalized against the writes or reads that won't need to pass through metadata I/O before being served.
This doesn't obviate the need of SFQ for the patological multimedia cases where I/O latency is the first prio, or for workloads where sync-write latency is the first prio.
BTW, I'm also thinking that the SFQ could be selected not system wide, but per-process basis, with a prctl or something, so you could have all the I/O going into the single default async-io queue, except for mplayer that will use the SFQ queues. This may not even need to be privilegied since SFQ is fair and if an user can write a lot it can just hurt latency, with SFQ could hurt more but still not deadlock. This SFQ prctl for the I/O scheduler, would be very similar to the RT policy for the main process scheduler. Infact it maybe the best to just have SFQ always enabled, and selectable only via the SFQ prctl, and to enable the functionaltiy only per-process basis rather than global. We can still add a sysctl to enable it globally despite nobody set the per-process flag.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 17 lines · Andrea Arcangeli
Quoted 4 lines · Hans Reiser
Is the following a fair summary?
There is a certain minimum size required for the IOs to be cost effective. This can be determined by single reader benchmarking. Only readahead and not anticipatory scheduling addresses that.
Quoted 9 lines
Anticipatory scheduling does not address the application that spends one minute processing every read that it makes. Readahead does.
Anticipatory scheduling does address the application that reads multiple files that are near each other (because they are in the same directory), and current readahead implementations (excepting reiser4 in progress vaporware) do not.
Anticipatory scheduling can do a better job of avoiding unnecessary reads for workloads with small time gaps between reads than readahead (it is potentially more accurate for some workloads).
Is this a fair summary?
Quoted 7 lines
I would also add what I feel the most important thing, that is anticipatory scheduling can help decreasing a lot the latencies of filesystem reads in presence of lots of misc I/O, by knowing which are the read commands that are intermediate-dependent-sync, that means knowing a new dependent read will be submitted very quickly as soon as the current read-I/O is completed.
Ah.... yes... I have seen that be a problem, and reiserfs suffers from it more than ext2....
maybe we should simply have an explicit protocol for that... I would be quite willing to have reiserfs use some flag that says WILL_READ_NEARBY_NEXT whenever it reads an internal node to get the location of its children.... that might be a lot cleaner than trying to do it all in your layer... what do you guys think...
Perhaps it will be both less code, and a better result in that it avoids some unnecessary lingering....
Quoted 24 lines
In such a case it makes lots sense to
wait for the next read to be submitted instead of start processing immediatly the rest of the I/O queue. This way when you read a file and you've to walk the indirect blocks before being able to read the data, you won't be greatly peanalized against the writes or reads that won't need to pass through metadata I/O before being served.This doesn't obviate the need of SFQ for the patological multimedia cases where I/O latency is the first prio, or for workloads where sync-write latency is the first prio.
BTW, I'm also thinking that the SFQ could be selected not system wide, but per-process basis, with a prctl or something, so you could have all the I/O going into the single default async-io queue, except for mplayer that will use the SFQ queues. This may not even need to be privilegied since SFQ is fair and if an user can write a lot it can just hurt latency, with SFQ could hurt more but still not deadlock. This SFQ prctl for the I/O scheduler, would be very similar to the RT policy for the main process scheduler. Infact it maybe the best to just have SFQ always enabled, and selectable only via the SFQ prctl, and to enable the functionaltiy only per-process basis rather than global. We can still add a sysctl to enable it globally despite nobody set the per-process flag.
Quoted 5 lines
Andrea
I still don't really understand your SFQ design, probably because I haven't studied recent networking algorithms that your description assumed I understand.
Signature · 1 line
Hans
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Hans ReiserQuoted 3 lines · Hans Reiser
Is the following a fair summary?
There is a certain minimum size required for the IOs to be cost effective. This can be determined by single reader benchmarking. Only readahead and not anticipatory scheduling addresses that.
Well as a rule you would gain efficiency the larger your request size gets. There will be a point where you make the trade off. And no, anticipatory scheduling will not make read request sizes bigger.
Quoted 3 lines
Anticipatory scheduling does not address the application that spends one minute processing every read that it makes. Readahead does.
In the presence of other IO, anticipatory scheduling would help here. In the absense of other IO, readahead would not help (past the efficiency problem above). However anticipatory scheduling _would_ mean you don't need as much RAM tied up doing nothing (or being discarded) for one minute before it is needed.
Quoted 3 lines
Anticipatory scheduling does address the application that reads multiple files that are near each other (because they are in the same directory), and current readahead implementations (excepting reiser4 in progress vaporware) do not.
File readahead would not help. Anticipatory scheduling can.
Quoted 3 lines
Anticipatory scheduling can do a better job of avoiding unnecessary reads for workloads with small time gaps between reads than readahead (it is potentially more accurate for some workloads).
It avoids seeks mainly, but the lesser need for readahead should mean the readahead algorithm doesn't need to be very smart.
Quoted 3 lines
Is this a fair summary?
Well I don't see it so much as readahead vs anticipatory scheduling. I know readahead is important.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.
In reply to Andrew MortonQuoted 10 lines
Quoted 6 lines
You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.
The anticipatory scheduler can easily permit 512k of reading before seeking away to another file. In fact it can allow much more, without requiring that readhead be cranked up.
IMHO anticipatory scheduling and readahead address different problems. RA is simpler and cheaper. Reading a few more KB comes almost for free and that helps a lot sequential reads. AS is useful for random i/o (fs metadata, executables, ...), but it wastes time if the timer expires, or if the new request wants data which is far away the previous one. AS is useful for sequential reads too, but only if the application reads large chunks of data, otherwise RA is better. I we need both RA and AS to address the largest variety of workloads.
Bye.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.
Quoted 11 lines · Giuliano Pochini
Quoted 10 lines
Quoted 6 lines
You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.
The anticipatory scheduler can easily permit 512k of reading before seeking away to another file. In fact it can allow much more, without requiring that readhead be cranked up.
Quoted 5 lines
IMHO anticipatory scheduling and readahead address different problems. RA is simpler and cheaper. Reading a few more KB comes almost for free and that helps a lot sequential reads. AS is useful for random i/o (fs metadata, executables, ...), but it wastes time if the timer expires, or if the new request wants data which is far away the previous one. AS is useful for
Yep.
Quoted 2 lines
sequential reads too, but only if the application reads large chunks of data, otherwise RA is better. I we need both RA and AS to address the
actually even if the app reads large chunks of data RA is needed, the size of the read/io_submit syscalls won't reach the readpage/wait_on_page at the pagecache layer, w/o readahead we would read PAGE_SIZE per dma and not more (ignoring PAGE_CACHE_SIZE of course, which isn't going to be enough anyways due mem fragmentation issues)
Quoted 3 lines
largest variety of workloads.
Bye.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliIs it true that there is no manpage available anywhere for fadvise?
For the benefit of others reading this thread, anticipatory scheduling is described at:
http://lwn.net/Articles/21274/
Signature · 1 line
Hans
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 3 lines · Hans Reiser
Is it true that there is no manpage available anywhere for fadvise?
It's pretty simple.
http://www.opengroup.org/onlinepubs/007904975/functions/posix_fadvise.html
It's also basically unimplementable without the radix tree, so I don't how other systems can be doing it. Maybe they just lock up for a day when someone does fadvise64(fd, 0, -1, FADV_DONTNEED) ;)
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 8 lines · Andrew Morton
Quoted 4 lines · Hans Reiser
Is it true that there is no manpage available anywhere for fadvise?
Quoted 12 lines
It's pretty simple.
http://www.opengroup.org/onlinepubs/007904975/functions/posix_fadvise.html
It's also basically unimplementable without the radix tree, so I don't how other systems can be doing it. Maybe they just lock up for a day when someone does
fadvise64(fd, 0, -1, FADV_DONTNEED);)
Andrew, don't you think you should write a linux manpage and/or other documentation when you add system calls like fadvise to linux? Also, Andrew, your measurements would be a lot more understandable if you did not use programs written by you and not present in any linux distro (do I understand that correctly?) without defining what they do. Yes? ;-)
Signature · 1 line
Hans
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Hans ReiserQuoted 6 lines · Hans Reiser
readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.
Quoted 6 lines
For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.
The biggest place where readahead helps is when there are several files being read at the same time. Without readahead the disk will seek from one file to the next after having performed a 4k I/O. With readahead, after performing a (say) 128k I/O. It really can make a 32x difference.
Readahead is brute force. The anticipatory scheduler solves this in a smarter way.
Yes, device readahead helps. But I believe the caches are only 4-way segmented or thereabouts, so it is easy to thrash them. Let's test:
vmm:/mnt/hda6> dd if=/dev/zero of=file1 bs=1M count=100 100+0 records in
100+0 records out
vmm:/mnt/hda6> dd if=/dev/zero of=file2 bs=1M count=100 100+0 records in
100+0 records out
vmm:/mnt/hda6> fadvise file1 0 9999999999 dontneed vmm:/mnt/hda6> fadvise file2 0 9999999999 dontneed vmm:/mnt/hda6> time cat file1 > /dev/null & time cat file2 > /dev/null cat 2 > /dev/null 0.00s user 0.11s system 0% cpu 21.011 total cat 1 > /dev/null 0.00s user 0.14s system 0% cpu 23.011 total vmm:/mnt/hda6> 0 blockdev --setra 4 /dev/hda
vmm:/mnt/hda6> fadvise file1 0 9999999999 dontneed vmm:/mnt/hda6> fadvise file2 0 9999999999 dontneed vmm:/mnt/hda6> time cat file1 > /dev/null & time cat file2 > /dev/null cat 2 > /dev/null 0.07s user 0.43s system 1% cpu 31.431 total cat 1 > /dev/null 0.01s user 0.27s system 0% cpu 31.430 total
OK, so there's a 50% slowdown on a modern IDE disk from not using readahead.
vmm:/mnt/hda6> for i in $(seq 1 8)
for> do
for> dd if=/dev/zero of=file$i bs=1M count=10
for> sync
for> fadvise file$i 0 999999999 dontneed
for> done
vmm:/home/akpm> 0 blockdev --setra 240 /dev/hda1
for i in $(seq 1 8)
do
time cat file$i >/dev/null&
done
cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 4.422 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 5.801 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.012 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.261 total cat file$i > /dev/null 0.00s user 0.02s system 0% cpu 6.401 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.494 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.754 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.757 total
vmm:/mnt/hda6> for i in $(seq 1 8)
do
fadvise file$i 0 999999999 dontneed
done
vmm:/home/akpm> 0 blockdev --setra 4 /dev/hda1
vmm:/mnt/hda6> for i in $(seq 1 8)
do
time cat file$i >/dev/null&
done
cat file$i > /dev/null 0.00s user 0.02s system 0% cpu 13.373 total cat file$i > /dev/null 0.00s user 0.04s system 0% cpu 14.849 total cat file$i > /dev/null 0.00s user 0.02s system 0% cpu 15.816 total cat file$i > /dev/null 0.00s user 0.04s system 0% cpu 16.808 total cat file$i > /dev/null 0.00s user 0.05s system 0% cpu 17.824 total cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 19.004 total cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 19.274 total cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 19.301 total
So with eight files, it's a 300% drop from not using readahead.
With 16 files, readahead enabled:
cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 9.887 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 10.925 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 11.033 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 11.146 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 11.381 total cat file$i > /dev/null 0.00s user 0.02s system 0% cpu 11.640 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 11.907 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 12.262 total
....
Readahead disabled:
cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 39.307 total cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 39.378 total cat file$i > /dev/null 0.00s user 0.04s system 0% cpu 39.679 total cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 39.888 total cat file$i > /dev/null 0.00s user 0.02s system 0% cpu 40.261 total
Still only 300%. I'd expect to see much larger differences on some older SCSI disks I have here.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 13 lines · Andrew Morton
Quoted 5 lines · Hans Reiser
readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.
For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.
The biggest place where readahead helps is when there are several files being read at the same time. Without readahead the disk will seek from one file to the next after having performed a 4k I/O. With readahead, after performing a (say) 128k I/O. It really can make a 32x difference.
Quoted 6 lines
Readahead is brute force. The anticipatory scheduler solves this in a smarter way.
Yes, device readahead helps. But I believe the caches are only 4-way segmented or thereabouts, so it is easy to thrash them. Let's test:
[snip results]
Quoted 5 lines
Still only 300%. I'd expect to see much larger differences on some older SCSI disks I have here.
It would be interesting to see numbers with and without anticipatory scheduling as well. I have tried two streaming readers. Speed with default readahead 13MB/s
Speed with no readahead, no anticipation 7MB/s
Speed with no readahead, anticipation 11.8MB/s
I suspect more readers will simply favour the anticipatory scheduler more.
Nick
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrew MortonQuoted 14 lines · Andrew Morton
Quoted 6 lines · Hans Reiser
readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.
Quoted 6 lines
For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.
Quoted 4 lines
The biggest place where readahead helps is when there are several files being read at the same time. Without readahead the disk will seek from one file to the next after having performed a 4k I/O. With readahead, after performing a (say) 128k I/O. It really can make a 32x difference.
definitely, but again the most important by far is to submit big commands, if you get the 512k commands interleaved by different task it isn't a panic situation.
Quoted 2 lines
Readahead is brute force. The anticipatory scheduler solves this in a smarter way.
If you decrease readahead with anticipatory scheduler you will submit the small commands, if you decrease the readahead you can stall 10 minutes any write in the queue, and still you won't grow the command in the head of the queue.
Quoted 5 lines
vmm:/mnt/hda6> for i in $(seq 1 8)
for> do
for> dd if=/dev/zero of=file$i bs=1M count=10
for> sync
for> fadvise file$i 0 999999999 dontneed
what is this fadvise doing?
Quoted 35 lines
for> done
vmm:/home/akpm> 0 blockdev --setra 240
/dev/hda1for i in $(seq 1 8)
do
time cat file$i >/dev/null&
donecat file$i > /dev/null 0.00s user 0.01s system 0% cpu 4.422 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 5.801 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.012 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.261 total cat file$i > /dev/null 0.00s user 0.02s system 0% cpu 6.401 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.494 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.754 total cat file$i > /dev/null 0.00s user 0.01s system 0% cpu 6.757 totalvmm:/mnt/hda6> for i in $(seq 1 8)
do
fadvise file$i 0 999999999 dontneed
done
vmm:/home/akpm> 0 blockdev --setra 4/dev/hda1
vmm:/mnt/hda6> for i in $(seq 1 8)
do
time cat file$i >/dev/null&
donecat file$i > /dev/null 0.00s user 0.02s system 0% cpu 13.373 total cat file$i > /dev/null 0.00s user 0.04s system 0% cpu 14.849 total cat file$i > /dev/null 0.00s user 0.02s system 0% cpu 15.816 total cat file$i > /dev/null 0.00s user 0.04s system 0% cpu 16.808 total cat file$i > /dev/null 0.00s user 0.05s system 0% cpu 17.824 total cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 19.004 total cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 19.274 total cat file$i > /dev/null 0.00s user 0.03s system 0% cpu 19.301 total
Quoted 1 line
So with eight files, it's a 300% drop from not using readahead.
yes, and anticipatory scheduler isn't going to fix it. furthmore with IDE the max merging is 64k so you can see little of the whole picture.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 2 lines · Andrea Arcangeli
what is this fadvise doing?
Invoking fadvise64(). Dropping the pagecache.
Quoted 2 lines
yes, and anticipatory scheduler isn't going to fix it. furthmore with IDE the max merging is 64k so you can see little of the whole picture.
124k. (Or is it 128k now?)
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 10 lines · Andrew Morton
Quoted 2 lines · Andrea Arcangeli
what is this fadvise doing?
Invoking
fadvise64(). Dropping the pagecache.Quoted 2 lines
yes, and anticipatory scheduler isn't going to fix it. furthmore with IDE the max merging is 64k so you can see little of the whole picture.
124k. (Or is it 128k now?)
sure, sorry, the ide limit is 128k
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliQuoted 15 lines · Andrea Arcangeli
Quoted 4 lines · Andrew Morton
Quoted 2 lines · Hans Reiser
readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.
Quoted 8 lines
Quoted 3 lines
For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.
The biggest place where readahead helps is when there are several files being read at the same time. Without readahead the disk will seek from one file to the next after having performed a 4k I/O. With readahead, after performing a (say) 128k I/O. It really can make a 32x difference.
Quoted 4 lines
definitely, but again the most important by far is to submit big commands, if you get the 512k commands interleaved by different task it isn't a panic situation.
Well the most important by far is to minimise seeks - you may be able to achieve that by submitting big commands, but you can also do it by accounting by time (not number of requests) and anticipating reads. I'm not saying your way doesn't work.
Quoted 11 lines
Quoted 5 lines
Readahead is brute force. The anticipatory scheduler solves this in a smarter way.
If you decrease readahead with anticipatory scheduler you will submit the small commands, if you decrease the readahead you can stall 10 minutes any write in the queue, and still you won't grow the command in the head of the queue.
Not sure exactly what you mean here, however no big starvation occurs with the scheduler you will find in 2.5.59-mm10 + experimental.
A streaming reader and streaming writer total 14MB/s in agregate throughput, with 2.23 bytes read per write with default settings.
This goes to 11.4MB/s and a ratio of 1.6 with 0 readahead.
When I turn off anticipatory scheduling however, I get a good 17MB/s throughput with a ratio of 0.00 reads per write (actually some small positive epsilon less than one over one hundred).
[snipped]
Quoted 6 lines
Quoted 3 lines
So with eight files, it's a 300% drop from not using readahead.
yes, and anticipatory scheduler isn't going to fix it. furthmore with
I am guessing it will do a pretty good job.
Quoted 3 lines
IDE the max merging is 64k so you can see little of the whole picture.
The disk can't but the io scheduler obviously can. We can give the disk a lot of help.
Quoted 7 lines
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrew MortonQuoted 13 lines · Andrew Morton
Quoted 6 lines · Andrea Arcangeli
BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.
Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.
Quoted 10 lines
And neither fs performs inode table readahead.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
reiser4 does directory readahead. It gets a lot of gain from it.
Signature · 1 line
Hans
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 2 lines · Hans Reiser
reiser4 does directory readahead. It gets a lot of gain from it.
What is "a lot"?
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 12 lines · Andrew Morton
Quoted 3 lines · Hans Reiser
reiser4 does directory readahead. It gets a lot of gain from it.
What is "a lot"?
I'll need a bit of time to answer your question. I must confess that I am speaking based on vague memories.
Signature · 1 line
Hans
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrew MortonQuoted 12 lines · Andrew Morton
Quoted 3 lines · Hans Reiser
reiser4 does directory readahead. It gets a lot of gain from it.
What is "a lot"?
Vladimir Saveliev had the numbers ready at hand after all, and said:
The most noticeable gain is found in the folowing test (not sure that it can be considered as effective readahead though): ls -l over directory containing 30000 files (named numerically) created in random order :
4.87 with no readahead
2.99 with readahead (which is limited by 25% of ram or by directory and all its stat data)
Signature · 1 line
Hans
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliQuoted 7 lines · Andrea Arcangeli
Quoted 5 lines · Nick Piggin
Quoted 2 lines · Andrea Arcangeli
On Mon, Feb 10, 2003 at 03:58:26PM +1100, Nick Piggin wrote:
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.
Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.
What I mean by this is: if we have >1 sequential readers (eg. ftp server), lets say 30MB/s disk, 4ms avg seek+settle+blah time, submitting reads in say 128KB chunks alternating between streams will cut throughput in half... At 1MB readahead we're at 89% throughput. At 2MB, 94%
With anticipatory scheduling, we can give each stream say 100ms so thats 96% with, say... 8K readahead if you like. (Yes, I am aware that CPU/PCI/IDE efficiency also mandates a larger request size).
Anyway that is the theory. It remains to be seen if we can make it work.
Quoted 23 lines
Quoted 9 lines
Quoted 7 lines
Quoted 2 lines
the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.
You seem to be forgetting things like seek time.
I didn't say it's the only purpose. Of course there's no hope for merging in the metadata dependent reads of the fs where anticipatory scheduling does its best, and infact they don't even attempt to do any readhaead. BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 25 lines · Nick Piggin
Quoted 7 lines · Andrea Arcangeli
Quoted 5 lines · Nick Piggin
Quoted 2 lines · Andrea Arcangeli
On Mon, Feb 10, 2003 at 03:58:26PM +1100, Nick Piggin wrote:
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.
Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.
What I mean by this is: if we have >1 sequential readers (eg. ftp server), lets say 30MB/s disk, 4ms avg seek+settle+blah time, submitting reads in say 128KB chunks alternating between streams will cut throughput in half... At 1MB readahead we're at 89% throughput. At 2MB, 94%
Quoted 4 lines
With anticipatory scheduling, we can give each stream say 100ms so thats 96% with, say... 8K readahead if you like. (Yes, I am aware that CPU/PCI/IDE efficiency also mandates a larger request size).
the way things works, if you give 8k readahead, you'll end submitting 8k requests no matter how long you wait and it will kill throughput to 10% of what was possible to achieve, very especially with scsi, max coalescing of ide is 64k and btw that is its main weakness IMHO.
It doesn't make any sense to me your claim that you can decrease the readahead by adding anticipatory scheduling, if you do you'll run so slow at 8k per request in all common workloads.
Quoted 28 lines
Anyway that is the theory. It remains to be seen if we can make it work.
Quoted 23 lines
Quoted 9 lines
Quoted 7 lines
Quoted 2 lines
the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.
You seem to be forgetting things like seek time.
I didn't say it's the only purpose. Of course there's no hope for merging in the metadata dependent reads of the fs where anticipatory scheduling does its best, and infact they don't even attempt to do any readhaead. BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.
Andrea
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 37 lines · Andrea Arcangeli
Quoted 29 lines · Nick Piggin
Quoted 14 lines · Andrea Arcangeli
Quoted 11 lines · Nick Piggin
Quoted 7 lines · Andrea Arcangeli
Quoted 4 lines · Nick Piggin
Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.
What I mean by this is: if we have >1 sequential readers (eg. ftp server), lets say 30MB/s disk, 4ms avg seek+settle+blah time, submitting reads in say 128KB chunks alternating between streams will cut throughput in half... At 1MB readahead we're at 89% throughput. At 2MB, 94%
Quoted 5 lines
With anticipatory scheduling, we can give each stream say 100ms so thats 96% with, say... 8K readahead if you like. (Yes, I am aware that CPU/PCI/IDE efficiency also mandates a larger request size).
Quoted 9 lines
the way things works, if you give 8k readahead, you'll end submitting 8k requests no matter how long you wait and it will kill throughput to 10% of what was possible to achieve, very especially with scsi, max coalescing of ide is 64k and btw that is its main weakness IMHO.
It doesn't make any sense to me your claim that you can decrease the readahead by adding anticipatory scheduling, if you do you'll run so slow at 8k per request in all common workloads.
I mean you kill throughput by submitting non linear requests. OK with such small requests you probably would lose some throughtput due to much greater ratio of overheads to work done, but in general we are talking about disk head positioning. 10 1MB requests should be much quicker than 1000 10K requests, for disk performance.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliQuoted 4 lines · Andrea Arcangeli
On Mon, Feb 10, 2003 at 07:27:51PM +1100, Nick Piggin wrote:
It doesn't make any sense to me your claim that you can decrease the readahead by adding anticipatory scheduling, if you do you'll run so slow at 8k per request in all common workloads.
Readahead kills seeks and command overhead at the expense of maybe transfering data needlessly over the bus and consuming RAM.
AS kills seeks. (At the expense of delaying some IO a tiny bit.)
If unecessary seeks are the main problem, with AS smaller READA is possible. If command overhead is a problem, READA needs to be large.
Regards,
Signature · 3 lines
Kurt Garloff <[email protected]> Eindhoven, NL GPG key: See mail header, key servers SuSE Labs (Head) SuSE Linux AG, Nuernberg, DE SCSI, Security
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 7 lines · Kurt Garloff
Readahead kills seeks and command overhead at the expense of maybe transfering data needlessly over the bus and consuming RAM.
AS kills seeks. (At the expense of delaying some IO a tiny bit.)
If unecessary seeks are the main problem, with AS smaller READA is possible. If command overhead is a problem, READA needs to be large.
Think about reading inode blocks or a bunch of related .h files. We can't nicely do readahead in either of these scenarios, but AS should take care of them nicely...
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Jakob OestergaardQuoted 11 lines · Jakob Oestergaard
Quoted 9 lines · Andrew Morton
Quoted 4 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
Quoted 7 lines
Quoted 2 lines
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
This may be a terribly stupid question, if so pls. just tell me :)
I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?
Yes, they are treated the same. If any part of the request is to be waited upon then the whole request should be treated as synchronous.
And if no part of a readahead request is waited upon, we should never have submited it anyway.
Quoted 4 lines
If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).
The simplified assumption that "reads are waited upon and writes are not" is highly accurate.
I want to see the Linux I/O scheduler work as well as possible with workloads which make that assumption 100% true. Once we have done that, then we can start worrying about corner cases like AIO, O_SYNC, truncate, etc.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Jakob OestergaardQuoted 10 lines · Jakob Oestergaard
Quoted 9 lines · Andrew Morton
Quoted 4 lines · David Lang
note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.
We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.
Quoted 7 lines
Quoted 2 lines
That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.
This may be a terribly stupid question, if so pls. just tell me :)
I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?
readahead is meant for merging. So in short normally there is no additional request generated by readhaead. Inter-process merging must not be forbidden by SFQ.
We also have to choose if to forbid or not outer-process merging. In theory SFQ would tell us to avoid it, and to only merge in the context of the same pid, in the common case it should just take care of most merging, things like dbench aren't going to run well with SFQ no matter if we do global merging or only per-process merging. Optimizing for throughput is not the object here.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Rik van RielQuoted 6 lines · Rik van Riel
Quoted 2 lines · Andrea Arcangeli
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
"The only way" ? That sounds like a lack of fantasy ;))
Took about 30 minutes, but here is an alternative algorithm. One that doesn't suffer from SFQ's "temporary unfairness due to unlucky hashing" problem, which can be made worse with SQF's "rehashing once every N seconds" policy, where N is too big for the user, say 30 seconds.
It requires 2 extra fields in the struct files_struct:
->last_request and ->request_priority
where ->last_request is the time (jiffies value) when a process associated with this files_struct last submitted an IO request and ->request_priority is a floating average of the time between IO requests, which can be directly used to determine the request priority.
The floating priority is kept over (1 << RQ_PRIO_SHIFT) requests, maybe 32 would be a good value to start ? Maybe 128 ?
The request priority of the files_struct used by the current process can be calculated in a simple O(1) way every time a request is submitted:
{
struct files_struct *files = current->files;
unsigned long interval = jiffies - files->last_request;
files->request_priority -= (files->request_priority >> RQ_SHIFT_PRIO);
files->request_priority += interval;
}The request_priority gets assigned as the priority of the currently submitted request (or the request gets submitted in the queue belonging to this priority range). We don't change the priority of already submitted requests, except maybe when merging requests.
This idea should adapt faster to changing IO usage of tasks and is O(1) scalable. Dunno if it'll be better than SFQ in practice too, but it just shows that SFQ isn't the only way. ;)
have fun,
Rik
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://guru.conectiva.com/ Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a>
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 45 lines · Rik van Riel
Quoted 6 lines · Rik van Riel
Quoted 2 lines · Andrea Arcangeli
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
"The only way" ? That sounds like a lack of fantasy ;))
Took about 30 minutes, but here is an alternative algorithm. One that doesn't suffer from SFQ's "temporary unfairness due to unlucky hashing" problem, which can be made worse with SQF's "rehashing once every N seconds" policy, where N is too big for the user, say 30 seconds.
It requires 2 extra fields in the struct
files_struct:->last_request and ->request_prioritywhere ->last_request is the time (jiffies value) when a process associated with this
files_structlast submitted an IO request and ->request_priority is a floating average of the time between IO requests, which can be directly used to determine the request priority.The floating priority is kept over (1 <<
RQ_PRIO_SHIFT) requests, maybe 32 would be a good value to start ? Maybe 128 ?The request priority of the
files_structused by the current process can be calculated in a simple O(1) way every time a request is submitted:{ struct files_struct *files = current->files; unsigned long interval = jiffies - files->last_request; files->request_priority -= (files->request_priority >> RQ_SHIFT_PRIO); files->request_priority += interval; }The
request_prioritygets assigned as the priority of the currently submitted request (or the request gets submitted in the queue belonging to this priority range). We don't change the priority of already submitted requests, except maybe when merging requests.
Quoted 3 lines
This idea should adapt faster to changing IO usage of tasks and is O(1) scalable. Dunno if it'll be better than SFQ in practice too, but it just shows that SFQ isn't the only way. ;)
The file level is worthless IMHO, you have no idea of what is going on in the I/O queue from there, the queue can be filled with 64M in some msec. If you really thing the above can be nearly as good at SFQ at the queue level, implement your alternate solution, benchmark it against SFQ with a seeking tiotest 1 with a cp /dev/zero . in background, if it works better than SFQ we'll use it.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Rik van RielQuoted 6 lines · Rik van Riel
Quoted 2 lines · Andrea Arcangeli
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
"The only way" ? That sounds like a lack of fantasy ;))
you can do more but you'd need to build additional APIs, to allow the highlevel (possibly userspace too) to give hints to the lowlevel.
This only requires the pid and checking current->mm which is trivial. So without adding a complex API I think this is the best/only thing you can do to get close to the minimal possible I/O latency from a process point of view.
Quoted 12 lines
On the contrary, once we have SFQ to fix the biggest elevator problems the difference made by the anticipatory scheduler should be much more visible.
Think of a disk with 6 track buffers for reading and a system with 10 active reader processes. Without the anticipatory scheduler you'd need to go to the platter for almost every OS read (because each process flushes out the track buffer for the others), while with the anticipatory scheduler you've got a bigger chance of having the data you want in one of the drive's track buffers, meaning that you don't need to go to the platter but can just do a silicon to silicon copy.
Quoted 8 lines
If you look at the academic papers of an anticipatory scheduler, you'll find that it gives as much as a 73% increase in throughput. On real-world tasks, not even on specially contrived benchmarks.
The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.
I'm not saying anticipatory scheduling is going to be obsoleted by SFQ, especially because SFQ has to be an option to use only when absolutely your only care to get the lowest possible I/O latency from a per-process point of view (like while playing an mpeg or mp3).
But I still definitely think that if you run an anticipatory scheduling benchmark w/ and w/o SFQ, the effect w/o SFQ (i.e. right now) is going to be much more visible than w/ SFQ enabled. The reason is the size of the queue that w/o SFQ can be as large as several seconds in time and several dozen mbytes in bytes.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 47 lines · Andrea Arcangeli
Quoted 8 lines · Rik van Riel
Quoted 3 lines · Andrea Arcangeli
The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.
"The only way" ? That sounds like a lack of fantasy ;))
you can do more but you'd need to build additional APIs, to allow the highlevel (possibly userspace too) to give hints to the lowlevel.
This only requires the pid and checking
current->mmwhich is trivial. So without adding a complex API I think this is the best/only thing you can do to get close to the minimal possible I/O latency from a process point of view.Quoted 12 lines
On the contrary, once we have SFQ to fix the biggest elevator problems the difference made by the anticipatory scheduler should be much more visible.
Think of a disk with 6 track buffers for reading and a system with 10 active reader processes. Without the anticipatory scheduler you'd need to go to the platter for almost every OS read (because each process flushes out the track buffer for the others), while with the anticipatory scheduler you've got a bigger chance of having the data you want in one of the drive's track buffers, meaning that you don't need to go to the platter but can just do a silicon to silicon copy.
Quoted 9 lines
If you look at the academic papers of an anticipatory scheduler, you'll find that it gives as much as a 73% increase in throughput. On real-world tasks, not even on specially contrived benchmarks.
The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.
I'm not saying anticipatory scheduling is going to be obsoleted by SFQ, especially because SFQ has to be an option to use only when absolutely your only care to get the lowest possible I/O latency from a per-process point of view (like while playing an mpeg or mp3).
Quoted 6 lines
But I still definitely think that if you run an anticipatory scheduling benchmark w/ and w/o SFQ, the effect w/o SFQ (i.e. right now) is going to be much more visible than w/ SFQ enabled. The reason is the size of the queue that w/o SFQ can be as large as several seconds in time and several dozen mbytes in bytes.
You are addressing a fundamentally different problem. In the 2.5 elevator we can have whatever queue size we like. I get great contest results with a 8192 request queue size. We track each request submission time so we can impose a soft upper limit on service times which provides fine latency, and the sync nature of reads ensures pretty good fairness.
What your scheduler is good for obviously is providing a much stronger per process fairness solution which is obviously very useful for some tasks.
The problems each are trying to solve are different. I don't think your idea solves anything that anticipatory scheduling solves (tries to).
Nick
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.
In reply to Rik van RielQuoted 6 lines
In the time of one disk seek plus half rotational latency (12 ms) you can do a pretty large amount of reading (>400kB). This means that for near and medium disk seeks you don't care all that much about how large the submitted IO is. Track buffers further reduce this importance.
This isn't always true. Removable devices usually have a quite low seek time compared to their raw transfer rate.
Bye.
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliHi!
Quoted 6 lines
The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the
task->pidthat is sumbitting the bh/bio. You'll have to apply an hash to the pid and you probably want a perturbation timer that will change the hash function every 30 sec or so. Plus I want a special queue for everything asynchronoys. So that the asynchronoys queue will be elevated and
What about adding speicial queue (queues?) for niced things? That way nice -20 job would not interfere with normal processes, not even for I/O.
Pavel
Signature · 2 lines
Worst form of spam? Adding advertisment signatures ala sourceforge.net. What goes next? Inserting advertisment *into* email?
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 9 lines · Pavel Machek
Hi!
Quoted 6 lines
The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the
task->pidthat is sumbitting the bh/bio. You'll have to apply an hash to the pid and you probably want a perturbation timer that will change the hash function every 30 sec or so. Plus I want a special queue for everything asynchronoys. So that the asynchronoys queue will be elevated and
Quoted 3 lines
What about adding speicial queue (queues?) for niced things? That way nice -20 job would not interfere with normal processes, not even for I/O.
Once you have per-process queues, it's fairly trivial to add stuff like that.
Signature · 1 line
Jens Axboe
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
In reply to Andrea ArcangeliHi!
Quoted 4 lines
The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the
task->pidthat is sumbitting the bh/bio. You'll have to apply an hash to the pid and you
Well, if you want *fair* scheduler, as in "fair between users", I guess you should base it on task->uid.
That should solve your dbench problems, too, as you are very unlikely to see two tasks working over same data with different uids.
Pavel
Signature · 2 lines
Worst form of spam? Adding advertisment signatures ala sourceforge.net. What goes next? Inserting advertisment *into* email?
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 9 lines · Pavel Machek
Hi!
Quoted 4 lines
The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the
task->pidthat is sumbitting the bh/bio. You'll have to apply an hash to the pid and youWell, if you want *fair* scheduler, as in "fair between users", I guess you should base it on
task->uid.
Good idea. All these cases should be optional, and they make plenty of sense to me.
Quoted 2 lines
That should solve your dbench problems, too, as you are very unlikely to see two tasks working over same data with different uids.
yes, but the main reason we do this isn't for multiuser systems. For multiuser systems it's true it would solve dbench, but there must be an option to go with task->pid and being able to specify the latency criticak tasks from userspace would be a good idea too.
Andrea
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 8 lines · Andrea Arcangeli
Quoted 7 lines · Pavel Machek
Hi!
Quoted 4 lines
The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the
task->pidthat is sumbitting the bh/bio. You'll have to apply an hash to the pid and you
Quoted 5 lines
Quoted 2 lines
Well, if you want *fair* scheduler, as in "fair between users", I guess you should base it on
task->uid.Good idea. All these cases should be optional, and they make plenty of sense to me.
Coolest would to simply stack these schedulers any way you want. Sneak the uid based fairness scheduler in front of the pid based one, and you have per-user with per-process fairness.
Lets lego.
Signature · 1 line
Jens Axboe
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 3 lines · [email protected] said:
Coolest would to simply stack these schedulers any way you want. Sneak the uid based fairness scheduler in front of the pid based one, and you have per-user with per-process fairness.
Which again reminds us of the network queueing. You all seem to be reinventing alexey's wheel here. The above reminds me of HTB with SFQ leaf nodes.
By all means, do the same thing with disk i/o. It's been a smashing success with packet queueing.
Jason
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 8 lines · Jason Lunz
Quoted 3 lines · [email protected] said:
Coolest would to simply stack these schedulers any way you want. Sneak the uid based fairness scheduler in front of the pid based one, and you have per-user with per-process fairness.
Which again reminds us of the network queueing. You all seem to be reinventing alexey's wheel here. The above reminds me of HTB with SFQ leaf nodes.
There's no wheel reinventing here, just applying the goodies from network scheduling to disk scheduling.
Quoted 2 lines
By all means, do the same thing with disk i/o. It's been a smashing success with packet queueing.
Well, that's the point.
Signature · 1 line
Jens Axboe
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 4 lines · [email protected] said:
Quoted 2 lines
By all means, do the same thing with disk i/o. It's been a smashing success with packet queueing.
Well, that's the point.
Yes, what you've done with cbq is great. What I was referring to, though, is the user configurability of network frame queueing. It's possible to do really complex things for very specialized needs, yet also easy to put in a simple tweak if there's just one type of traffic you need to prioritize. It'd be nice to have that kind of configurability for unusual i/o loads, and the arbitrary queue stacking is a whole different beast than having a couple of tunables to tweak.
Jason
Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
Quoted 6 lines · Jason Lunz
Quoted 4 lines · [email protected] said:
Quoted 2 lines
By all means, do the same thing with disk i/o. It's been a smashing success with packet queueing.
Well, that's the point.
Quoted 7 lines
Yes, what you've done with cbq is great. What I was referring to, though, is the user configurability of network frame queueing. It's possible to do really complex things for very specialized needs, yet also easy to put in a simple tweak if there's just one type of traffic you need to prioritize. It'd be nice to have that kind of configurability for unusual i/o loads, and the arbitrary queue stacking is a whole different beast than having a couple of tunables to tweak.
That is indeed the goal. We'll see how much is doable within the 2.6 time frame, though.
Signature · 1 line
Jens Axboe