Re: mmap (was First set of OSDL Shared Mem scalability results, some wierdness ...

>> pg to my mind is unique in not trying to avoid OS buffering. Other
>> dbmses spend a substantial effort to create a virtual OS (task
>> management, I/O drivers, etc.) both in code and support. Choosing mmap
>> seems such a limiting an option - it adds OS dependency and limits
>> kernel developer options (2G limits, global mlock serializations,
>> porting problems, inability to schedule or parallelize I/O, still
>> having to coordinate writers and readers).

2G limits? That must be a Linux limitation, not a limitation with
mmap(2). On OS-X and FreeBSD it's anywhere from 4GB to ... well,
whatever the 64bit limit is (which is bigger than any data file in
$PGDATA). An mlock(2) serialization problem is going to be cheaper
than hitting the disk in nearly all cases and should be no worse than a
context switch or semaphore (what we use for the current locking
scheme), of which PostgreSQL causes plenty of 'em because it's
multi-process, not multi-threaded. Coordination of data isn't
necessary if you mmap(2) data as a private block, which takes a
snapshot of the page at the time you make the mmap(2) call and gets
copied only when the page is written to. More on that later.

> I'm not sure I entirely agree with this. Whether you access a file
> via mmap() or via read(), the end result is that you still have to
> access it, and since PG has significant chunks of system-dependent
> code that it heavily relies on as it is (e.g., locking mechanisms,
> shared memory), writing the I/O subsystem in a similar way doesn't
> seem to me to be that much of a stretch (especially since PG already
> has the storage manager), though it might involve quite a bit of work.

Obviously you have to access the file on the hard drive, but you're
forgetting an enormous advantage of mmap(2). With a read(2) system
call, the program has to allocate space for the read(2), then it copies
data from the kernel into the allocated memory in the userland's newly
allocated memory location. With mmap(2) there is no second copy.

Let's look at what happens with a read(2) call. To read(2) data you
have to have a block of memory to copy data into. Assume your OS of
choice has a good malloc(3) implementation and it only needs to call
brk(2) once to extend the process's memory address after the first
malloc(3) call. There's your first system call, which guarantees one
context switch. The second hit, a much larger hit, is the actual
read(2) call itself, wherein the kernel has to copy the data twice:
once into a kernel buffer, then from the kernel buffer into the
userland's memory space. Yuk. Webserver's figured this out long ago
that read(2) is slow and evil in terms of performance. Apache uses
mmap(2) to send static files at performance levels that don't suck and
is actually quite fast (in terms of responsiveness, I'm not talking
about Apache's parallelism/concurrency performance levels... which in
1.X aren't great).

mmap(2) is a totally different animal in that you don't ever need to
make calls to read(2): mmap(2) is used in place of those calls (With
#ifdef and a good abstraction, the rest of PostgreSQL wouldn't know it
was working with a page of mmap(2)'ed data or need to know that it is).
Instead you mmap(2) a file descriptor and the kernel does some heavy
lifting/optimized magic in its VM. The kernel reads the file
descriptor and places the data it reads into its buffer (exactly the
same as what happens with read(2)), but, instead of copying the data to
the userspace, mmap(2) adjusts the process's address space and maps the
address of the kernel buffer into the process's address space. No
copying necessary. The savings here are *huge*!

Depending on the mmap(2) implementation, the VM may not even get a page
from disk until its actually needed. So, lets say you mmap(2) a 16M
file. The address space picks up an extra 16M of bits that the process
*can* use, but doesn't necessarily use. So if a user reads only ten
pages out of a 16MB file, only 10 pages (10 * getpagesize()), or
usually 40,960K, which is 0.24% the amount of disk access (((4096 * 10)
/ (16 *1024 * 1024)) * 100). Did I forget to mention that if the file
is already in the kernel's buffers, there's no need for the kernel to
access the hard drive? Another big win for data that's hot/frequently
accessed.

There's another large savings if the machine is doing network IO too...

> As for parallelization of I/O, the use of mmap() for reads should
> signficantly improve parallelization -- now instead of issuing read()
> system calls, possibly for the same set of blocks, all the backends
> would essentially be examining the same data directly. The
> performance improvements as a result of accessing the kernel's cache
> pages directly instead of having it do buffer copies to process-local
> memory should increase as concurrency goes up. But see below.

That's kinda true... though not quite correct. The improvement in IO
concurrency comes from zero-socket-copy operations from the disk to the
network controller. If a write(2) system call is issued on a page of
mmap(2)'ed data (and your operating system supports it, I know FreeBSD
does, but don't think Linux does), then the page of data is DMA'ed by
the network controller and sent out without the data needing to be
copied into the network controller's buffer. So, instead of the CPU
copying data from the OS's buffer to a kernel buffer, the network card
grabs the chunk of data in one interrupt because of the DMA (direct
memory access). This is a pretty big deal for web serving, but if
you've got a database sending large sets of data over the network,
assuming the network isn't the bottle neck, this results in a heafty
performance boost (that won't be noticed by most until they're running
huge, very busy installations). This optimization comes for free and
without needing to add one line of code to an application once mmap(2)
has been added to an application.

>> More to the point, I think it is very hard to effectively coordinate
>> multithreaded I/O, and mmap seems used mostly to manage relatively
>> simple scenarios.
>
> PG already manages and coordinates multithreaded I/O. The mechanisms
> used to coordinate writes needn't change at all. But the way reads
> are done relative to writes might have to be rethought, since an
> mmap()ed buffer always reflects what's actually in kernel space at the
> time the buffer is accessed, while a buffer retrieved via read()
> reflects the state of the file at the time of the read(). If it's
> necessary for the state of the buffers to be fixed at examination
> time, then mmap() will be at best a draw, not a win.

Here's where things can get interesting from a transaction stand point.
Your statement is correct up until you make the assertion that a page
needs to be fixed. If you're doing a read(2) transaction, mmap(2) a
region and set the MAP_PRIVATE flag so the ground won't change
underneath you. No copying of this page is done by the kernel unless
it gets written to. If you're doing a write(2) or are directly
scribbling on an mmap(2)'ed page[1], you need to grab some kind of an
exclusive lock on the page/file (mlock(2) is going to be no more
expensive than a semaphore, but probably less expensive). We already
do that with semaphores, however. So for databases that don't have
high contention for the same page/file of data, there are no additional
copies made. When a piece of data is written, a page is duplicated
before it gets scribbled on, but the application never knows this
happens. The next time a process mmap(2)'s a region of memory that's
been written to, it'll get the updated data without any need to flush a
cache or mark pages as dirty: the operating system does all of this for
us (and probably faster too). mmap(2) implementations are, IMHO, more
optimized that shared memory implementations (mmap(2) is a VM function,
which gets many eyes to look it over and is always being tuned, whereas
shared mem is a bastardized subsystem that works, but isn't integral to
any performance areas in the kernel so it gets neglected. Just my
observations from the *BSD commit lists. Linux it may be different).

[1] I forgot to mention earlier, you don't have to write(2) data to a
file if it's mmap(2)'ed, you can change the contents of an mmap(2)'ed
region, then msync(2) it back to disk (to ensure it gets written out)
or let the last munmap(2) call do that for you (which would be just as
dangerous as running without fsync... but would result in an additional
performance boost).

>> mmap doesn't look that promising.
>
> This ultimately depends on two things: how much time is spent copying
> buffers around in kernel memory, and how much advantage can be gained
> by freeing up the memory used by the backends to store the
> backend-local copies of the disk pages they use (and thus making that
> memory available to the kernel to use for additional disk buffering).

Someone on IRC pointed me to some OSDL benchmarks, which broke down
where time is being spent. Want to know what the most expensive part
of PostgreSQL is? *drum roll*

http://khack.osdl.org/stp/297960/profile/DBT_2_Profile-tick.sort

3967393 total 1.7735
2331284 default_idle 36426.3125
825716 do_sigaction 1290.1813
133126 __copy_from_user_ll 1040.0469
97780 __copy_to_user_ll 763.9062
43135 finish_task_switch 269.5938
30973 do_anonymous_page 62.4456
24175 scsi_request_fn 22.2197
23355 __do_softirq 121.6406
17039 __wake_up 133.1172
16527 __make_request 10.8730
9823 try_to_wake_up 13.6431
9525 generic_unplug_device 66.1458
8799 find_get_page 78.5625
7878 scsi_end_request 30.7734

Copying data to/from userspace and signal handling!!!! Let's hear it
for the need for mmap(2)!!! *crowd goes wild*

> The gains from the former are likely small. The gains from the latter
> are probably also small, but harder to estimate.

I disagree.

> The use of mmap() is probably one of those optimizations that should
> be done when there's little else left to optimize, because the
> potential gains are possibly (if not probably) relatively small and
> the amount of work involved may be quite large.

If system/kernel time is where most of your database spends its time,
then mmap(2) is a huge optimization that is very much worth pursuing.
It's stable (nearly all webservers use it, notably Apache), widely
deployed, POSIX specified (granted not all implementations are 100%
consistent, but that's an OS bug and mmap(2) doesn't have to be turned
on for those platforms: it's no worse than where we are now), and well
optimized by operating system hackers. I guarantee that your operating
system of choice has a faster VM and disk cache than PostgreSQL's
userland cache, nevermind using the OSs buffers leads to many
performance boosts as the OS can short-circuit common pathways that
would require data copying (ex: zero-socket-copy operations and copying
data to/from userland).

mmap(2) isn't a panacea or replacement for good software design, but it
certainly does make IO operations vastly faster, which is what
PostgreSQL does a lot of (hence its need for a userland cache).
Remember, back when PostgreSQL had its architecture thunk up, mmap(2)
hardly existed in anyone's eyes, nevermind it being widely used or a
POSIX function. It wasn't until Apache started using it that Operating
System vendors felt the need to implement it or make it work well. Now
it's integral to nearly all virtual memory implementations and a modern
OS can't live without it or have it broken in any way. It would be
largely beneficial to PostgreSQL to heavily utilize mmap(2).

A few places it should be used include:

*) Storage. It is a good idea to mmap(2) all files instead of
read(2)'ing files. mmap(2) doesn't fetch a page from disk until its
actually needed, which is a nifty savings. Sure it causes a fault in
the kernel, but it won't the second time that page is accessed.
Changes are necessary to src/backend/storage/file/, possibly
src/backend/storage/freespace/ (why is it using fread(3) and not
read(2)?), src/backend/storage/large_object/ can remain gimpy since
people should use BYTEA instead (IMHO), src/backend/storage/page/
doesn't need changes (I don't think), src/backend/storage/smgr/
shouldn't need any modifications either.

*) ARC. Why unmmap(2) data if you don't need to? With ARC, it's
possible for the database to coach the operating system in what pages
should be persistent. ARC's a smart algorithm for handling the needs
of a database. Instead of having a cache of pages in userland,
PostgreSQL would have a cache of mmap(2)'ed pages. It's shared between
processes, the changes are public to external programs read(2)'ing
data, and its quick. The needs for shared memory by the kernel drops
to nearly nothing. The needs for mmap(2)'able space in the kernel,
however, does go up. Unlike SysV shared mem, this can normally be
changed on the fly. The end result would be, if a page is needed, it
checks to see if its in the cache. If it is, the mmap(2)'ed page is
returned. If it isn't, the page gets read(2)/mmap(2) like it currently
is loaded (except in the mmap(2) case where after the data has been
loaded, the page gets munmap(2)'ed). If ARC decides to keep the page,
the page doesn't get munmap(2)'ed. I don't think any changes need to
be made though to take advantage of mmap(2) if the changes are made in
the places mentioned above in the Storage point.

A few other perks:

*) DIRECTIO can be used without much of a cache coherency headache
since the cache of data is in the kernel, not userland.

*) NFS. I'm not suggesting multiple clients use the same data
directory via NFS (unless read only), but if there were a single client
accessing a data directory over NFS, performance would be much better
than it is today because data consistency is handled by the kernel so
in flight packets for writes that get dropped or lost won't cause a
slow down (mmap(2) behaves differently with NFS pages) or corruption.

*) mmap(2) is conditional on the operating system's abilities, but
doesn't require any architectural changes. It does change the location
of the cache, from being in the userland, down in to the kernel. This
is a change for database administrators, but a good one, IMHO.
Previously, the operating system would be split 25% kernel, 75% user
because PostgreSQL would need the available RAM for its cache. Now,
that can be moved closer to the opposite, 75% kernel, 25% user because
most of the memory is mmap(2)'ed pages instead of actual memory in the
userland.

*) Pages can be protected via PROT_(EXEC|READ|WRITE). For backends
that aren't making changes to the DDL or system catalogs (permissions,
etc.), pages that are loaded from the catalogs could be loaded with the
protection PROT_READ, which would prevent changes to the catalogs. All
DDL and permission altering commands (anything that touches the system
catalogs) would then load the page with the PROT_WRITE bit set, make
their changes, then PROT_READ the page again. This would provide a
first line of defense against buggy programs or exploits.

*) Eliminates the double caching done currently (caching in PostgreSQL
and the kernel) by pushing the cache into the kernel... but without
PostgreSQL knowing it's working on a page that's in the kernel.

Please ask questions if you have them.

-sc

--
Sean Chittenden