It is time... Move the filesystem off of disks

Bass said:

Dexter said:

*snip*

Ha ha, look who's talking. You're twisting my words yet you claim "losing argument".

 

Well I see you want to be on an equal footing with me on this. So I'll call you an insane person also. Insane person.

 

And how exactly does this relate to what I said? Or more generally, how exactly does this relate to caching?

 

This is the original point I am addressing:

Seriously, do you really want/expect a database system to move gigabytes or terrabytes of data around just to keep the kernel happy?

 

Okay I'm going to say this again. Please no more "NUH UHs" on this. I'm quite obviously right.

 

You can not write any explicit caching code to efficently cache things on an x86 processor. This algorithm is hardcoded into the control unit of the actual processor. The only way to get important data into cache (which is of course, what you want) is to "suggest" it to the proccessor by your data structures. This means working with the quirks of the branch predictor, and also localizing commonly accessed data.

 

Of course this is to keep the CPU happy and you are probably going to be like "well I didn't say CPU, so I am somehow correct, and you are wrong". Well buddy, you have to keep the CPU happy. A unhappy CPU is a cache missing CPU, and you MUST avoid this to have any reasonable performance.

 

And interestingly, by keeping the CPU happy, you also tend to make the kernel happy. Because the kernel isn't using some magical caching algorithm that Intel doesn't know about.

 

Kapeesh?

See --- this long post by Bass right here.

This is why I want Channel 9 forums to switch to something with a little bit more maturity like SMF or phpBB or something. The delays in bringing up posts, the times when you can't get to page 2 of a thread, and the over-AJAXification of the current Channel 9 forums interrupts and distracts from a steady stream of posts like this one which are both highly entertaining, yet educational. 

If I had succumbed to the urge to just not visit the site a few minute ago (an urge fueled mainly by the usability of these forums), I would not have read this post.

Thanks.

Bass said:

Dexter said:

*snip*

A system memory cache is a just a much slower and much bigger CPU cache.

 

In fact this is how the CPU sees the world:

 

Page fault: Geographical time

Cache miss: Snail time

In cache: Ferrari Enzo

 

You want your CPU to be riding that Ferrari as much as possible. That means NO DIRECT MEMORY ACCESS IF POSSIBLE. A big optimization thing (at least big as autovectorization) is to try to keep your working data on the cache, and never make the CPU explicitly access a piece of memory. Does that sound familiar? Isn't that exactly what you want to do with memory caching in general?

 

Oh wait, I can even make a fill in the blank:

The point of X caching is to keep as much working data in a fast memory store (in this case: Y) as possible.

 

I'm going to guess the reply: "irrelevant". LOLWUT?

So you have information cached in memory. Unfortunately, you can't have everything cached in memory, because you just don't have that much memory. So at some point, the DBMS is going to have to read something from disk, and, most importantly, something else is going to have to be removed from the cache to make room from the new information. Deciding what piece of information to remove from the cache when space runs out is probably the hardest and most performance critical part of cache algorithms.

Now ask yourself: who has more information by which to decide what should be dropped from the cache? The OS kernel, or the DBMS itself?

Sven Groot said:

Bass said:

*snip*

So you have information cached in memory. Unfortunately, you can't have everything cached in memory, because you just don't have that much memory. So at some point, the DBMS is going to have to read something from disk, and, most importantly, something else is going to have to be removed from the cache to make room from the new information. Deciding what piece of information to remove from the cache when space runs out is probably the hardest and most performance critical part of cache algorithms.

 

Now ask yourself: who has more information by which to decide what should be dropped from the cache? The OS kernel, or the DBMS itself?

The OS kernel has a lot of information here.

(1) It can figure out where the most commonly read information is, and store those pages in memory. I know this may seem silly but the most commonly read information is wait for it... exactly what you want to be in memory. Thus the kernel does a pretty good job of finding exactly what needs to be in memory. The DB's data structures MUST be written to be automatically cached anyway. You can not use unpredictably spread out data structures (see why heap sort performs poorly on x86), you are quite limited in how you structure your data for performance due to the CPU cache. But seriously, I in all honestly can not see what a DB's domain specific caching algorithm could do better. Since you are the so called DB expert perhaps you could enlighten me?

(2) It has access to a lot of information about the persistent store (eg: the position of the head). So it knows exactly when it can pull some piece of data off the disk (often measurable in nanoseconds), while at at best the DB could query the kernel for this information (zomg cache miss / context switch), but more likely simply guesses and then has blocking stuff all nicely queued for unpredictable times on the kernel's I/O scheduler.

(3) It has access to an array of modern caching technologies like DMA. Remember what I said about cache misses and all that? Well you are passing data in and out of the CPU like an idiot and that's BAD BAD BAD for performance. Unfortunately this is the only realistic way to implement a user-mode file cache is to pass data in and out of the CPU like an idiot. You really want to do that? Be my guest. I'll take DMA over that any day.

At best, if you want to implement a cache in a DB you should be subservient to the kernel, passing it the right information so it can do it's job via it's sheer awesome kernel powers. As I said before, there is ways to ask the kernel to cache something for you and there are ways to structure your data that is conductive to caching. But one thing you should never do the kernel's job for it, because you will never do it as well.

fknight said:

Bass said:

*snip*

See --- this long post by Bass right here.

 

This is why I want Channel 9 forums to switch to something with a little bit more maturity like SMF or phpBB or something. The delays in bringing up posts, the times when you can't get to page 2 of a thread, and the over-AJAXification of the current Channel 9 forums interrupts and distracts from a steady stream of posts like this one which are both highly entertaining, yet educational. 

 

If I had succumbed to the urge to just not visit the site a few minute ago (an urge fueled mainly by the usability of these forums), I would not have read this post.

 

Thanks.

 

 

This is why I want Channel 9 forums to switch to something with a little bit more maturity like SMF or phpBB

An open-source php BBS hosting Channel-9 ...somehow, I don’t think so.

In the “old days” I would have suggested Community Server, but these days, I can’t even figure out what the hell Telligent are trying to sell, let alone figure out the status of the product... it seems to be a very confused company with an even more confusing website.

fknight said:

Bass said:

*snip*

See --- this long post by Bass right here.

 

This is why I want Channel 9 forums to switch to something with a little bit more maturity like SMF or phpBB or something. The delays in bringing up posts, the times when you can't get to page 2 of a thread, and the over-AJAXification of the current Channel 9 forums interrupts and distracts from a steady stream of posts like this one which are both highly entertaining, yet educational. 

 

If I had succumbed to the urge to just not visit the site a few minute ago (an urge fueled mainly by the usability of these forums), I would not have read this post.

 

Thanks.

 

 

Thank you for the kind words.

Bass said:

Sven Groot said:

*snip*

The OS kernel has a lot of information here.

(1) It can figure out where the most commonly read information is, and store those pages in memory. I know this may seem silly but the most commonly read information is wait for it... exactly what you want to be in memory. Thus the kernel does a pretty good job of finding exactly what needs to be in memory. The DB's data structures MUST be written to be automatically cached anyway. You can not use unpredictably spread out data structures (see why heap sort performs poorly on x86), you are quite limited in how you structure your data for performance due to the CPU cache. But seriously, I in all honestly can not see what a DB's domain specific caching algorithm could do better. Since you are the so called DB expert perhaps you could enlighten me?

 

(2) It has access to a lot of information about the persistent store (eg: the position of the head). So it knows exactly when it can pull some piece of data off the disk (often measurable in nanoseconds), while at at best the DB could query the kernel for this information (zomg cache miss / context switch), but more likely simply guesses and then has blocking stuff all nicely queued for unpredictable times on the kernel's I/O scheduler.

 

(3) It has access to an array of modern caching technologies like DMA. Remember what I said about cache misses and all that? Well you are passing data in and out of the CPU like an idiot and that's BAD BAD BAD for performance. Unfortunately this is the only realistic way to implement a user-mode file cache is to pass data in and out of the CPU like an idiot. You really want to do that? Be my guest. I'll take DMA over that any day.

 

At best, if you want to implement a cache in a DB you should be subservient to the kernel, passing it the right information so it can do it's job via it's sheer awesome kernel powers. As I said before, there is ways to ask the kernel to cache something for you and there are ways to structure your data that is conductive to caching. But one thing you should never do the kernel's job for it, because you will never do it as well.

It can figure out where the most commonly read information is, and store those pages in memory.

But that just plainly isn't true. The kernel can figure out only what was the most common information in the past, and then hope that this will still be true in the future. But there are many access patterns where this simply isn't true. The kernel cannot know if an application is going to have an access pattern for which this strategy doesn't work. Only the application can know that. Hence, the application can do better.

And CPU caching isn't relevant to this discussion for several reasons: 1. The timing gap between memory and disk is greater than that between CPU cache and memory. 2. CPU cache is a few MB at best, file cache is typically multiple GB. 3. The kernel does not manage the CPU cache, the CPU does that.

And the simple fact is that SQL Server and Oracle and other high-performance DB systems do in fact do their own caching. Are you saying the people who develop those databases are all wrong?

figuerres said:

magicalclick said:

*snip*

magicalclick:  yeah this has went back and forth and i can see why you are lost....

 

the start of this was that the OP was talking about taking the NTFS "metadata" to a memory based system of some kind.

that he seemed to think that the raw data and the NTFS filesystem data could and should be handled differently.

at least that what i think the OP was saying.

 

then as the topic went on folks started talking about FS optimazation and how a DBMS might use the FS or might not.

 

so the term database has been used here 2 ways one as a normal database for say sql server and as the special data that a file system needs to manage.

Figuerres, Thanks for clearing that up.t

To TP: it would be cool if you can make a prototype and demonstrate how good it is.

To Bass. It is called NTFS. I guess you need a new stuff called DBFS.

For FS, I think I will list out some of the things we want in the future:

1) DB in mind.

2) Faster directory lookup to reduce lattency. Ideally directory lookup in RAM.

3) Multi-user support. (need good sync to all users when directory lookup is in RAM)

4) Security. No external driver, or FS, or whatever can access/modify its content without the FS.

I am not really keen on this topic, so please don't laugh, hehe.

magicalclick said:

figuerres said:

*snip*

Figuerres, Thanks for clearing that up.t

 

To TP: it would be cool if you can make a prototype and demonstrate how good it is.

To Bass. It is called NTFS. I guess you need a new stuff called DBFS.

 

For FS, I think I will list out some of the things we want in the future:

1) DB in mind.

2) Faster directory lookup to reduce lattency. Ideally directory lookup in RAM.

3) Multi-user support. (need good sync to all users when directory lookup is in RAM)

4) Security. No external driver, or FS, or whatever can access/modify its content without the FS.

 

I am not really keen on this topic, so please don't laugh, hehe.

 

1) Depends what you mean by DB. You can consider NTFS as being a domain specific DB. It's not relational, it doesn't process SQL queries but it stores and retrieves data, a lot of data. Incidentaly NTFS uses B-Trees which are also commonly used in databases.

2) Already done. NTFS (and probably most other filesystems) caches file metdata in RAM. Go enumerate a directory containing a large number of files. You'll likely see a ton of disk activity. Do that again. No disk activity this time.

3) Already done. File metadata caching occurs in kernel, not in the application. This means that there's only one instance of that data so there's no need for some sort of "good sync".

4) Already done. Unless you're an administrator you cannot access the disk directly, you must go through the filesystem. Also if you're not an administrator you cannot load drivers. In general this has less to do with the filesystem, it's a generic kernel problem.

Bass said:

Sven Groot said:

*snip*

The OS kernel has a lot of information here.

(1) It can figure out where the most commonly read information is, and store those pages in memory. I know this may seem silly but the most commonly read information is wait for it... exactly what you want to be in memory. Thus the kernel does a pretty good job of finding exactly what needs to be in memory. The DB's data structures MUST be written to be automatically cached anyway. You can not use unpredictably spread out data structures (see why heap sort performs poorly on x86), you are quite limited in how you structure your data for performance due to the CPU cache. But seriously, I in all honestly can not see what a DB's domain specific caching algorithm could do better. Since you are the so called DB expert perhaps you could enlighten me?

 

(2) It has access to a lot of information about the persistent store (eg: the position of the head). So it knows exactly when it can pull some piece of data off the disk (often measurable in nanoseconds), while at at best the DB could query the kernel for this information (zomg cache miss / context switch), but more likely simply guesses and then has blocking stuff all nicely queued for unpredictable times on the kernel's I/O scheduler.

 

(3) It has access to an array of modern caching technologies like DMA. Remember what I said about cache misses and all that? Well you are passing data in and out of the CPU like an idiot and that's BAD BAD BAD for performance. Unfortunately this is the only realistic way to implement a user-mode file cache is to pass data in and out of the CPU like an idiot. You really want to do that? Be my guest. I'll take DMA over that any day.

 

At best, if you want to implement a cache in a DB you should be subservient to the kernel, passing it the right information so it can do it's job via it's sheer awesome kernel powers. As I said before, there is ways to ask the kernel to cache something for you and there are ways to structure your data that is conductive to caching. But one thing you should never do the kernel's job for it, because you will never do it as well.

Eh, more crap. You're calling a 30 years old (or maybe even older) technology like DMA a modern thing. Sure, 30 years ago there was no CPU cache but it's not like CPU cache is extremly new either.

And you have no clue about how non cached file I/O works and you claim that it's not possible to implement user mode caching because of lack of DMA?

And you call people idiots for moving data in and out of the CPU cache. Do you perhaps have a wonder CPU with 1 terrabyte of cache so people can stop acting like idiots while moving their database in and out of the CPU cache?

You might as well throw in the kitchen sink. It will probably weight more than flawed arguments.

PS:

Technical notes for people unfamiliar with x86 hardware and file caching (at least on Windows):

PCs included DMA since the early days. Back then it was used to transfer data from the floppy disk to memory and for a couple of other things. AFAIR it was even possible to progam it to transfer from memory to memory.

It is certainly possible to use DMA to transfer data directly from disk to application memory. There are some restriction to the size, memory address and file offset (basically they need to be multiple of disk sector size) but that's hardly a problem for databases because they organize data in pages and th page size is a multiple of sector size (at least on SQL Server).

It should also be noted that kernel file caching does not always come for free. For example if you're reading a file by using a "read" style call then the kernel has no choice but to copy the file data from its cache to the application provided buffer. Not extremly slow but certainly not free either.

Sven Groot said:

Bass said:

*snip*

But that just plainly isn't true. The kernel can figure out only what was the most common information in the past, and then hope that this will still be true in the future. But there are many access patterns where this simply isn't true. The kernel cannot know if an application is going to have an access pattern for which this strategy doesn't work. Only the application can know that. Hence, the application can do better.

 

And CPU caching isn't relevant to this discussion for several reasons: 1. The timing gap between memory and disk is greater than that between CPU cache and memory. 2. CPU cache is a few MB at best, file cache is typically multiple GB. 3. The kernel does not manage the CPU cache, the CPU does that.

 

And the simple fact is that SQL Server and Oracle and other high-performance DB systems do in fact do their own caching. Are you saying the people who develop those databases are all wrong?

But that just plainly isn't true. The kernel can figure out only what was the most common information in the past, and then hope that this will still be true in the future.

If you design your data structures correctly, it SHOULD be true in the future.

But there are many access patterns where this simply isn't true.

And they don't belong in databases.

The kernel cannot know if an application is going to have an access pattern for which this strategy doesn't work. Only the application can know that. Hence, the application can do better.

I don't think that's actually true. For many data structures, you can not reliably predict where an element will be located on a restructure. If you can, you can ask the kernel to cache that part of the file for you anyway. See the readahead syscall. Which is exactly how readahead daemons like preload work! They don't go around implementing their own file caching, that would be stupid. They let the kernel do it for them, as any good DB implementation would.

And CPU caching isn't relevant to this discussion for several reasons: 1. The timing gap between memory and disk is greater than that between CPU cache and memory. 2. CPU cache is a few MB at best, file cache is typically multiple GB. 3. The kernel does not manage the CPU cache, the CPU does that.

1. It may be, but having too many direct memory accesses with effect system performance in a very bad way.

2. CPU Cache is a few MB at best, so lets ignore it? That sounds like a plan chief.

3. The fact that the CPU manages the CPU cache is exactly why it's important. You can not program a CPU cache, because that is a right reserved only for the immortals who design hardware, and you are but a mortal software developer. The best you could do is structure your data in a way that is conductive to CPU caching. If you are going to do this anyway, why not structure your data in a way that is conductive to the kernel caching? Hmm? The kernel is like the CPU's prophet to software. Like most prophets, he is mortal and software like all other software, but is bestowed on by the immortals with certain miracles. But you shouldn't ignore his powers, for he speakiths directly to the hardware, and knows it's demands. You do not.

Dexter said:

Bass said:

*snip*

Eh, more crap. You're calling a 30 years old (or maybe even older) technology like DMA a modern thing. Sure, 30 years ago there was no CPU cache but it's not like CPU cache is extremly new either.

 

And you have no clue about how non cached file I/O works and you claim that it's not possible to implement user mode caching because of lack of DMA?

 

And you call people idiots for moving data in and out of the CPU cache. Do you perhaps have a wonder CPU with 1 terrabyte of cache so people can stop acting like idiots while moving their database in and out of the CPU cache?

 

You might as well throw in the kitchen sink. It will probably weight more than flawed arguments.

 

PS:

Technical notes for people unfamiliar with x86 hardware and file caching (at least on Windows):

 

PCs included DMA since the early days. Back then it was used to transfer data from the floppy disk to memory and for a couple of other things. AFAIR it was even possible to progam it to transfer from memory to memory.

 

It is certainly possible to use DMA to transfer data directly from disk to application memory. There are some restriction to the size, memory address and file offset (basically they need to be multiple of disk sector size) but that's hardly a problem for databases because they organize data in pages and th page size is a multiple of sector size (at least on SQL Server).

 

It should also be noted that kernel file caching does not always come for free. For example if you're reading a file by using a "read" style call then the kernel has no choice but to copy the file data from its cache to the application provided buffer. Not extremly slow but certainly not free either.

Welcome back Dexter!

I didn't say it was impossible to implement caching without DMA, I just said it was incredibly stupid. Since your entire argument is based on a false premise, there is little more I can say.

Bass said:

Dexter said:

*snip*

Welcome back Dexter!

 

I didn't say it was impossible to implement caching without DMA, I just said it was incredibly stupid. Since your entire argument is based on a false premise, there is little more I can say.

Well, it seems that you failed to read the "technical notes" part of the post. I guess you consider yourself familiar with inner kernel/hardware details. In that case you should also know that it is possible to use DMA even if caching is not done in kernel.

Unfortunately this is the only realistic way to implement a user-mode file cache is to pass data in and out of the CPU like an idiot.

Did you say "false premises"?

Dexter said:

Bass said:

*snip*

 

Did you say "false premises"?

You give a reasonable explination for how DMA works, and it's history. I'm not aware of any user-mode way of doing DMA, that's something that seems to be reserved to kernel space (as virtually any hardware control). If you know a way feel free to enlighten me.

But as so far as it makes any difference to the argument, using DMA is far better then not. If you start taking memory management in your own hands, if you are implementing your own cache by memcpy'ing things around you are effectively not using DMA so any data you write to this cache has to go through the CPU. If you let the kernel handle this file caching for you, this is not a problem.

Bass said:

Dexter said:

*snip*

You give a reasonable explination for how DMA works, and it's history. I'm not aware of any user-mode way of doing DMA, that's something that seems to be reserved to kernel space (as virtually any hardware control). If you know a way feel free to enlighten me.

 

But as so far as it makes any difference to the argument, using DMA is far better then not. If you start taking memory management in your own hands, if you are implementing your own cache by memcpy'ing things around you are effectively not using DMA so any data you write to this cache has to go through the CPU. If you let the kernel handle this file caching for you, this is not a problem.

seems to be reserved to kernel space

So you make a bunch of claims but you actually don't have a clue how this works? You have some nerve.

Of course one's going to use DMA. Not only that using PIO mode would be terrible inefficient but AFAIK it's not even possible with adapters like AHCI. Or SCSI.

And there's no reason why DMA cannot be used to transfer data to user mode space. Note that I'm talking about data tranfer and not about DMA programming. All the application has to do is to issue a properly aligned, non cached, asynchronous read request. The kernel will take care of programming the DMA (or the disk adapter which in turn will program the DMA) with the memory address and size specified by the application and that's all there is to it. There's no memcpy, no CPU cache trashing and no requirement for the application to have low level access to the hardware.

Dexter said:

Bass said:

*snip*

 

So you make a bunch of claims but you actually don't have a clue how this works? You have some nerve.

 

Of course one's going to use DMA. Not only that using PIO mode would be terrible inefficient but AFAIK it's not even possible with adapters like AHCI. Or SCSI.

 

And there's no reason why DMA cannot be used to transfer data to user mode space. Note that I'm talking about data tranfer and not about DMA programming. All the application has to do is to issue a properly aligned, non cached, asynchronous read request. The kernel will take care of programming the DMA (or the disk adapter which in turn will program the DMA) with the memory address and size specified by the application and that's all there is to it. There's no memcpy, no CPU cache trashing and no requirement for the application to have low level access to the hardware.

 

So you make a bunch of claims but you actually don't have a clue how this works? You have some nerve.

Well I am not like you Dexter. I don't act like I know everything, and I actually value input from others. And this I apologize for. 

And there's no reason why DMA cannot be used to transfer data to user mode space. Note that I'm talking about data tranfer and not about DMA programming.

But what you seem (oops I said "seem", I have some nerve!) to be saying is that you indeed need to make a syscall to do DMA, which is what I assumed ("assumed"? you must be raging by now). Thank you for proving yourself wrong once again.

Bass said:

Dexter said:

*snip*

So you make a bunch of claims but you actually don't have a clue how this works? You have some nerve.

Well I am not like you Dexter. I don't act like I know everything, and I actually value input from others. And this I apologize for. 

 

And there's no reason why DMA cannot be used to transfer data to user mode space. Note that I'm talking about data tranfer and not about DMA programming.

 

But what you seem (oops I said "seem", I have some nerve!) to be saying is that you indeed need to make a syscall to do DMA, which is what I assumed ("assumed"? you must be raging by now). Thank you for proving yourself wrong once again.

Well I am not like you Dexter.  I don't act like I know everything, and actually value input from others. And this I apologize for. 

I don't know everything either. But I keep my mouth shut when I have no clue about what people are talking about.

But what you seem to be saying is that you indeed need to make a syscall to do DMA, which is what I assumed. Thank you for proving yourself wrong once again.

And what exactly is wrong? The whole thing was about an application bypassing the kernel cache, not about an application bypassing the whole kernel.

Dexter said:

Bass said:

*snip*

 

And what exactly is wrong? The whole thing was about an application bypassing the kernel cache, not about an application bypassing the whole kernel.

 

No Dexter,

Here is my primary arguments:

• If you design a DB, you want to delegate as much responsibility to the kernel as possible (Sven was almost insulted by this.)
• An OS can accomplish a lot of the intelligent read caching by a paging algorithm, which keeps track of the most commonly read parts of a file.
• In a modern kernel, you can control the functionality of the paging algorithm in many many ways (eg: mmap and readahead in Linux), to the point where I am not sure what this magical "domain-specific" DB cache that neither of you explained can do better.
• It would be downright stupid for a DB to take all of this in it's own hands, but I am sure there is some legacy DBs out there who still do all of this, because they were written during a time where MS-DOS was considered advanced.
• Implementing a file cache entirely in userspace (eg. malloc + memcpy) is downright idiotic.

Dexter said:

magicalclick said:

*snip*

1) Depends what you mean by DB. You can consider NTFS as being a domain specific DB. It's not relational, it doesn't process SQL queries but it stores and retrieves data, a lot of data. Incidentaly NTFS uses B-Trees which are also commonly used in databases.

2) Already done. NTFS (and probably most other filesystems) caches file metdata in RAM. Go enumerate a directory containing a large number of files. You'll likely see a ton of disk activity. Do that again. No disk activity this time.

3) Already done. File metadata caching occurs in kernel, not in the application. This means that there's only one instance of that data so there's no need for some sort of "good sync".

4) Already done. Unless you're an administrator you cannot access the disk directly, you must go through the filesystem. Also if you're not an administrator you cannot load drivers. In general this has less to do with the filesystem, it's a generic kernel problem.

Thanks for clearing that up. Now, I don't understand all the blah anymore. Well, better leave it to you guys.