News for hackers. Stuff that matters.
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jandrewrogers on Thursday April 03, 2014 @10:46AM (#7523156)
Issues like the ones raised are why all sufficiently advanced database engine designs tend to evolve toward a kernel bypass architecture. From the perspective of a database engine, operating systems do a lot of "dumb" things with resource management and scheduling in ways that are essentially impossible to avoid that the database engine has enough context to do intelligently on its own. OS bypass in a database can have substantial performance benefits and add robustness for many edge cases. The obvious downside is that you basically end up rewriting the operating system in userspace, minus the device drivers, which is an enormous amount of work. It is not an incremental kind of design approach and it makes portability difficult. PostgreSQL actually does a really good job trying to be fast and robust without going to bypass internals.

I've always asserted that the reason we've never seen a proper kernel bypass database engine in open source is that the Minimum Viable Product is too complex. A bare, stripped-down, low-level database engine that does full bypass of the operating system is usually at least 100kLoC of low-level C/C++, and that is before you add all the features a database user will actually want. That is a big initial investment by some people with fairly rare software design skills.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jeffdavis on Thursday April 03, 2014 @12:06PM (#7523777)
I assert that open source databases don't do it because it's a bad idea. It's the kind of you do when you have a lot of spare engineering resources and not many innovative ideas.

Not only is the initial devepment expensive, so is the maintenance burden. It makes every new idea cost more to implement.

Postgres has been extraordinarily innovative; offering things like transactional DDL, advanced indexing, first-class extensibility, serializable snapshot isolation, per-transaction durability, sophisticated constraints (e.g. non-overlapping ranges), etc. These features are possible because postgres didn't get bogged down reimplementing and maintaining a filesystem.

And what would all of that work gain, anyway? +25% single-node performance? Not a very strategic direction to go for databases. Better to improve JavaScript/json support and get a good logical replication solution in place.

That being said, there are some low level features that are really worth doing. Robert Haas (the author) did some great work with lockless algorithms, which has achieved great concurrency with a manageable maintenance burden.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jandrewrogers on Thursday April 03, 2014 @02:57PM (#7525154)
You both overestimate the engineering complexity and underestimate the benefits. I've both designed and worked on a couple different bypass kernels as well PostgreSQL internals over the years.

You are correct that the initial development is steep. However, once the infrastructure is there it really is not much different than working with the operating system infrastructure and you gain a level of predictability and stability in terms of behavior that saves engineering time. Also, bypass implementations have almost no locking internally (either "lock-free" types or heavier types) which reduces complexity considerably.

Some bypass kernel code bases allow you to compile with the bypass implementation disabled, using highly-optimized PostgreSQL-like internals. I've seen and run quite a few comparative benchmarks on the same design with and without bypass enabled, as well as absolute benchmarks against engines like PostgreSQL. We don't have to guess about single node performance.

Broadly speaking, a properly designed bypass kernel buys you 2-3x the throughput of a highly optimized non-bypass kernel in my experience. If it was only 25% no one would bother. Furthermore, for massively parallel databases, you essentially require a bypass kernel to design a well-behaved system due to the adaptive operation scheduling requirements.

I agree that it is a lot of work but it is also entirely worth it if you need to either (1) maximize throughput on a single node and (2) build a well-behaved massively parallel database kernel. The differences are not trivial.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jeffdavis on Thursday April 03, 2014 @05:26PM (#7526896)
Any number we have is going to be sensitive to the workload, so I think it's unfair to say 2-3x without a lot of context.

Also, you dismiss ideas that help the database and the OS work together better. For instance, I did "synchronized scans" for postgres. It coordinates sequential scans to start from the block another scan is already reading, improving cache behavior and dramatically reducing seeks. This could have been done by lots of extra code controlling the I/O very carefully (as at least one paper seemed to suggest was a good idea). But I chose to do it the simple way, just start the scan off in the same place as another scan, and concurrent scans got almost ideal behavior -- each ran in about the same time as if no other scan was in progress (with no overhead in the single scan case).

Linux is clearly interested in allowing more hooks and making them more useful. From an engineering standpoint, that makes more sense to me.

Two other points:

* I'm a little skeptical that such a bypass can easily be made resilient to some strange/degenerate cases.

* You say that the reason an open source system won't do it is because the MVP is too expensive. But the MVP for a cost-based optimizer is also very expensive, and postgres has one of those. I think that was a much better investment than investment in the filesystem/scheduling layer.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jandrewrogers on Thursday April 03, 2014 @10:42PM (#7528842)
Jeff, I am familiar with your work, I lurked on the PostgreSQL hackers mailing list for years when I was hacking on that database. :-) I am not dismissing the coordination of OS and database, it just has really deep limits because the OS must hide information critical to optimizing database throughput.

While the increased throughput is a complex function of hardware, workload, etc, it is also consistently substantial. The reason why it works is simple: the database processes have nearly omniscient view of hardware and state and there is only (in modern designs) a single process per core. Consequently, even if you have thousands of concurrent high-level database operations, each process can dynamically select and continuously reorder the low-level operations to (nearly) optimally maximize the throughput for the execution graph at that moment because the execution is completely cooperative. You can do the “synchronous scan” optimization for CPU caches that you do for disk systems. You can schedule around any conflicts in the execution graph and even the impact of outside CPU interrupts can be detected and optimized around. And it is easy to track the aggregate costs of these choices. To the extent possible, every clock cycle is spent on end-user database work instead of database internals overhead.

So minimal processing stalls, micro or macro, and no context-switching or coordination overhead. All combined with incredible locality knowledge (by inference) that is not available if you let the OS manage things for you.

On your other two points:

- Bypass is generally more resilient partly because the software has more explicit and immediate knowledge of the nature of the fault and can do something sensible about it. Obviously you have to handle faults when they occur. A lot of OS behavior when faults occur is pathological from the standpoint of optimizing databases. It is like memory management in C; it requires extra effort but also adds extra power if you handle it well.

- Postgres has expensive capability add-ons to an existing, useful system so it is more incremental in nature. The problem with OS bypass database kernels (and I learned this the hard way) is that (1) they are huge in terms of LoC long before rudimentary functionality is available and (2) it takes many years of atypical software design experience to be competent at trying to write one. It could be done, but it would require a critical mass of a tiny demographic willing to do a lot of work. My argument in this regard was less about inevitability and more about statistical probability.

I spent a lot of years hacking on and customizing Postgres. I recommend it to anyone and everyone that will listen because it is a great piece of engineering and would still use it for many OLTP systems. But it does leave a lot of performance on the table for a variety of reasons that probably make sense for a portable, open source project. The fact remains that I can design and have built bypass kernels that are substantially faster largely by exploiting the optimizations bypassing offers.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jeffdavis on Friday April 04, 2014 @11:48AM (#7532176)
Perhaps it's just because I've never seen a good implementation of a bypass, and I might agree if I had seen one. Like many things, maybe it just takes the right people to make it successful.

Postgres leaves a lot of performance on the table in much more basic ways, too, so I certainly am not suggesting that postgres is anywhere near optimal.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by deafbybeheading on Friday April 04, 2014 @03:47AM (#7529890)
Stupid (and somewhat tangential) question: how do bypass kernels work with virtualization, if at all?
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jurjenh on Thursday April 03, 2014 @04:30PM (#7526322)
Is there a middle ground here somewhere? In that the kernel developers create some sort of DB specific hooks that allow some of the kernel bypass mechanisms to be implemented?

What are the key things that a kernel bypass version does different? Can these be separated out in a concise way which would lead to multiple DB implementations being able to use these same interfaces? Essentially for any major DB system, you'd want the kernel tailored anyway - you're not going to be doing much else on your DB server (are you?)

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by kev009 on Thursday April 03, 2014 @04:05PM (#7526043)
Or you could, you know, fix the OS like they are trying to do in TFA.
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by cookiecaper on Friday April 04, 2014 @03:57AM (#7529924)
The argument is that "fix" is relative. Things that improves Postgres's performance may negatively impact other applications. The suggestion, therefore, is that Postgres takes control of these tasks for its own purposes, and then they don't have to worry about the implications for other systems or wait on anyone else.
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by hcarvalhoalves on Thursday April 03, 2014 @12:36PM (#7523978)
Maybe it's b possible to port a database to a model like OpenMirage's [1], building against all the runtime it requires but running on top of a hypervisor?

[1] http://www.openmirage.org/

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by mattzito on Thursday April 03, 2014 @11:08AM (#7523342)
And one of the reasons that software like Oracle is so complicated and expensive. Oracle spent years getting the OS kernels out of the way, partially for platform consistency/supportability sake and partially for performance. They obviously still depend on the kernel for a variety of things, but memory management, networking, filesystems, etc. can all be done in Oracle-space at this point.
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by beagle3 on Thursday April 03, 2014 @02:12PM (#7524806)
But what it buys Oracle is not performance, but rather bragging rights for being a little faster at a moment in time.

However 3-6 months later, you'll get comparable performance from improved kernel, CPU and disk speeds. Are those 20% in performance for 6 months worth the premium oracle is charging (which, in part, reflects their harder work)? For most customers most of the time the answer is no.

If you depend on performance, you don't use Oracle in the first place - Vyahu, OneTick, kdb, Vertica are the speed demons (as well as TimesTen which was acquired by Oracle - but is distinct from their "standard" offering)

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by dfox on Thursday April 03, 2014 @11:08AM (#7523337)
These two issues are actually perfect counterpoint to bypassing kernel caching and scheduling. There is no way to overcome first issue in userspace, second is trigered by what amounts to too agressive caching in userspace, and third is something that you should not be doing anyway (I'm not exactly sure if there is something better that kernel can do in that case, except doing write-thru caching on writes which has it's own performance implications for other users of O_DIRECT).
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jandrewrogers on Thursday April 03, 2014 @03:14PM (#7525319)
I think you aren't understanding what a bypass kernel does. It literally takes control of the physical resources to the extent kernel interfaces exist that allow it to do so and, at least in the case of Linux, the level of control possible is quite high. That means taking control of the CPU, physical memory, disk I/O, network I/O, etc so that they can be scheduled and managed from userspace. All at the same time starting with bypass kernel initialization. For obvious reasons, it is usually a bad idea to run other non-trivial processes on the same machine because they will tend to be resource starved.

Once you have these resources, you can organize them and use them as you see fit. Because it is not going to the kernel for any resources or buffering or scheduling or memory etc, there is little opportunity for the OS to do the wrong thing with resources that already are tightly controlled by the runtime. However, this is also why it is an "all or nothing" kind of situation.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by twoodfin on Thursday April 03, 2014 @04:57PM (#7526589)
Interesting. When I read your first comment, I didn't realize you meant "bypass kernel" in as wide a scope as you describe here. Usurping CPU scheduling, in particular, was something I didn't think was common practice. Can you name a (presumably commercial) DBMS that represents this kind of "self-manage everything" architecture?
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jandrewrogers on Thursday April 03, 2014 @10:54PM (#7528902)
Most of the big "enterprise" OLTP databases are designed this way; the less portable they are, the more likely they are doing deep bypass optimizations. DB2, SQL Server, and similar are bypass designs. Oracle used to be a weird hybrid, due to portability requirements, but since they took control of the hardware I would assume recent versions are mostly pure bypass.

Most commercial analytical databases are not bypass, due in large part to the fact that most of them are based on Postgres, ironically.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by drzaiusapelord on Thursday April 03, 2014 @11:18AM (#7523419)
How does this work? I don't see how its possible to fight the scheduler or how caching works via userspace.

Maybe I don't understand this stuff, but maybe the kernel should have some bypass API for high performance applications, instead of coders finding curious ways to fight it.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by usefulcat on Thursday April 03, 2014 @01:27PM (#7524445)
You can bypass filesystem caching on Linux using O_DIRECT. The tradeoff (besides the obvious lack of caching) is that there are specific alignment restrictions on the length and address of the userspace buffers and file offsets, and these restrictions may vary by filesystem and by kernel.
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by dap on Thursday April 03, 2014 @11:29AM (#7523487)
You can bypass the scheduler by binding processes to processors. Some runtimes do this -- and sometimes get much worse performance as a result. My colleagues and I have seen many programs that think they know better than the OS do much worse for trying.
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by jandrewrogers on Thursday April 03, 2014 @03:20PM (#7525411)
The kernel does have bypass APIs, or APIs that can be used for that purpose. However, you can't use just a little; once you start down that path you need to bypass everything.

To be clear, while the bypass APIs are simple to use you actually have to know what you are doing since you become responsible for doing things the OS used to do for you. I/O scheduling, disk caching, process scheduling, memory management, etc all have to be reimplemented in userspace.

It is why I mentioned that the skill set required to do bypass kernels is fairly rarified. You can't just reimplement what the OS already does, you need to implement something that is different than the OS design but also better at providing functionality the OS provides for the use case. You are essentially writing a purpose-optimized OS without the device drivers.

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by ape4 on Thursday April 03, 2014 @12:59PM (#7524181)
How about a special filesystem api for databases?
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by pekk on Thursday April 03, 2014 @01:29PM (#7524470)
At this point why aren't you just building the database on top of a minimal OS? Then run that in a VM, say
Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by ori_b on Thursday April 03, 2014 @02:23PM (#7524901)
> Then run that in a VM

You think that VMs aren't subject to the host OS scheduler, caching, and memory allocation quirks?

Re: Subtly Bad Things Linux May Be Doing To PostgreSQL by Dylan16807 on Saturday April 05, 2014 @01:43AM (#7536107)
>scheduler

eh, it could pin threads at realtime priority

>caching

vm wouldn't use the OS cache

>memory allocation

it can easily allocate memory up front