7 ms·

Yes, and I dont (quite) buy that argument, but I understand where it comes from. The problem starts when you, quite sensibly implement something like SHA256 in

by phkamp 4y ago

Yes, and I dont (quite) buy that argument, but I understand where it comes from. The problem starts when you, quite sensibly implement something like SHA256 in hardware. It is a perfect example of something hardware does better than software. But Dennis, Ken and Brian didn't think about cryptographic hash-algorithms when they created UNIX, and because UNIX no longer have a recognized architectural authority, nobody provides a timely architecture for such new features, and instead we end up with all sorts of hackery, some in kernels, some in libraries and some in applications. SHA256 should be a standard library API, and if the CPU has a HW implementation, the platforms library should spot that and use that, no need to get the kernel involved, it's just a fancy XOR on purely userland data. But SHA256 being a good example does not mean that we should throw out the baby with the bath-water. Things like file-systems are incredibly ill-suited for userland implementations. What they dont say in the article is that they will need monolithic "libraries" for things like filesystems, and to implement things like locking, atomicity, these libraries will have to coordinate amongst the processes which use the filesystem, and must do so without the control and power available to the kernel. There are ways to do that, see for instance MACH or the original MINIX. It transpires there are disadvantages. And that's what I mean by "archtectural radicalism": Try to use the right tool for the job, and sometimes the kernel is the right tool (filesystems) and sometimes it is not (SHA256).

kragen 4y ago
Which of the disadvantages of microkernel userland filesystems do you think are most important and essential to the concept, and which do you think are a matter of bad implementations? I thought L4 and QNX had pretty reasonable filesystem stories, and even on poor old Linux I've been using FUSE with things like NTFS for years without much trouble. Is it just a matter of the cost of context switching between userland processes when you don't have enough cores? If it's a question of performance, with enough cores and shared memory that's accessible for atomic operations, I'd think talking to a userland filesystem would just* be a matter of pushing requests onto a lock-free request queue in shared memory from your application process and reading the responses from a lock-free response queue. Of course each application needs its own shared-memory area for talking to the filesystem to get fault isolation. Even if it's a matter of IPC message-passing cost on a single core, I think L4 has shown how to make that cheap enough that we should regard putting the filesystem in the kernel as a dubious optimization, and at that one that's second-best to granting the application mappings on an NVDIMM or something. Perhaps this is stating the obvious, but I don't think you can get much fault isolation with a pure library filesystem; if all the processes participating in the filesystem are faulty then there's no way to protect the filesystem from fatal corruption from faults. You might be able to reduce the presumed-correct filesystem core process to something like a simplified Kafka: a process that grants other processes read-only access to an append-only log and accepts properly delimited and identified blocks of data from them to append to it. If we're interested in efficiency and simplicity of mechanism, though, a library filesystem is likely faster and might be simpler than a conventional monolithic filesystem server, particularly a single-threaded one, because you can rely on blocking I/O. And the library might be able to wrap updates to the persistent store in lock-free transactions to reduce the frequency of filesystem corruption. The Xerox Alto famously used a single-tasking library filesystem similar to MS-DOS, but each sector was sufficiently self-describing that filesystem corruption was usually minor and easy to recover from. The filesystem directory could be reconstructed from the data blocks when required. Neither the Alto nor MS-DOS had to worry about locking, though! KeyKOS, as you know, took a lot of the ideas from the CAP machine and similar capability machines (and languages like Smalltalk), and implemented them on IBM 370 hardware using its regular MMU, with L4-like lightweight IPCs through the kernel for capability invocations. It went to the opposite extreme from having a library filesystem: each directory and each file was a "domain" of its own, which is to say a single-threaded process. Persistence was handled by a systemwide copy-on-write snapshot of the whole system state, plus a journal-sync call their database used to provide durable transactions. EUMEL and L3 took similar approaches; L4 instead takes persistence and even virtual memory out of the kernel. I wrote some somewhat sketchy notes on how Flash performance suggests rearchitecting things the other day at https://news.ycombinator.com/item?id=31902551 https://news.ycombinator.com/item?id=31902551; I know you have a very substantial amount of experience with this as a result of Varnish and your involvement with Fastly. What do you think? ______ * "Just" may be a loaded term here.
- eru 4y ago
  Keep in mind that (conventional) micro-kernels are not the same as exokernels. FUSE is fun, I've written my own filesystems with it, but it's basically a micro-kernel idea, not an exokernel one. (L4 is also great! But I don't think it qualifies as an exokernel?) https://pdos.csail.mit.edu/6.828/2019/lec/faq-exokernel.txt https://pdos.csail.mit.edu/6.828/2019/lec/faq-exokernel.txt explains a lot about exokernels that's not mentioned in the papers. Exokernels never caught on, at least not under that name. The closest equivalent in widespread use today are actually hypervisors for running virtual machines. (Especially if you are running a so called 'unikernel' on them.) About filesystems: if you just want the kinds of abstractions that conventional filesystems already give you, you won't get too much out of using an exokernel. (As you mention, perhaps you can get a bit of extra performance?) From the FAQ I linked above: > Q: In what kind of applications is an exokernel operating system preferable? There are naturally tradeoffs with the extra flexibility provided e.g. it is easier to make a mistake in user code. > A: An exokernel is most attractive to an application that needs to do something that is possible with an exokernel, but not possible with other kernels. The main area in which the 1995 exokernel paper increased flexibility was virtual memory. It turns out there are a bunch of neat techniques applications can use if they have low-level access to virtual memory mappings; the Appel and Li paper (citation [5]) discusses some of them. Examples include distributed shared memory and certain garbage collection tricks. Many operating systems in 1995 didn't give enough low-level access to virtual memory mappings to implement such techniques, but the exokernel did. The exokernel authors wrote a later paper (in SOSP 1997) that describes some examples in much more depth, including a web server that uses a customized file system layout to provide very high performance. The HN submission we are nominally discussing here is also about memory, so that might be applicable. An example for filesystems I could envision: direct low-level hardware access to an SSD's internals for a database. Databases don't really care about files, and might also want to deal with SSD's peculiar writing processes in a way that's different from the abstractions typical file systems give you. > Perhaps this is stating the obvious, but I don't think you can get much fault isolation with a pure library filesystem; if all the processes participating in the filesystem are faulty then there's no way to protect the filesystem from fatal corruption from faults. You might be able to reduce the presumed-correct filesystem core process to something like a simplified Kafka: a process that grants other processes read-only access to an append-only log and accepts properly delimited and identified blocks of data from them to append to it. That might be possible, but wouldn't really be faster than letting a kernel handle it, I'd guess? (But it would perhaps be more flexible to develop, since it's all userland.) You can also take inspiration from how eBPF allows you to upload user level logic into the Linux kernel and run them securely. Instead of uploading them into the kernel, you could also upload them into your filesystem service, I guess? Some of the original exokernel papers had some more interesting ideas sketched out. > I know you have a very substantial amount of experience with this as a result of Varnish and your involvement with Fastly. What do you think? I'm afraid you are mixing me up with someone else?

by phkamp 4y ago

kragen 4y ago

Which of the disadvantages of microkernel userland filesystems do you think are most important and essential to the concept, and which do you think are a matter of bad implementations? I thought L4 and QNX had pretty reasonable filesystem stories, and even on poor old Linux I've been using FUSE with things like NTFS for years without much trouble. Is it just a matter of the cost of context switching between userland processes when you don't have enough cores? If it's a question of performance, with enough cores and shared memory that's accessible for atomic operations, I'd think talking to a userland filesystem would just* be a matter of pushing requests onto a lock-free request queue in shared memory from your application process and reading the responses from a lock-free response queue. Of course each application needs its own shared-memory area for talking to the filesystem to get fault isolation. Even if it's a matter of IPC message-passing cost on a single core, I think L4 has shown how to make that cheap enough that we should regard putting the filesystem in the kernel as a dubious optimization, and at that one that's second-best to granting the application mappings on an NVDIMM or something. Perhaps this is stating the obvious, but I don't think you can get much fault isolation with a pure library filesystem; if all the processes participating in the filesystem are faulty then there's no way to protect the filesystem from fatal corruption from faults. You might be able to reduce the presumed-correct filesystem core process to something like a simplified Kafka: a process that grants other processes read-only access to an append-only log and accepts properly delimited and identified blocks of data from them to append to it. If we're interested in efficiency and simplicity of mechanism, though, a library filesystem is likely faster and might be simpler than a conventional monolithic filesystem server, particularly a single-threaded one, because you can rely on blocking I/O. And the library might be able to wrap updates to the persistent store in lock-free transactions to reduce the frequency of filesystem corruption. The Xerox Alto famously used a single-tasking library filesystem similar to MS-DOS, but each sector was sufficiently self-describing that filesystem corruption was usually minor and easy to recover from. The filesystem directory could be reconstructed from the data blocks when required. Neither the Alto nor MS-DOS had to worry about locking, though! KeyKOS, as you know, took a lot of the ideas from the CAP machine and similar capability machines (and languages like Smalltalk), and implemented them on IBM 370 hardware using its regular MMU, with L4-like lightweight IPCs through the kernel for capability invocations. It went to the opposite extreme from having a library filesystem: each directory and each file was a "domain" of its own, which is to say a single-threaded process. Persistence was handled by a systemwide copy-on-write snapshot of the whole system state, plus a journal-sync call their database used to provide durable transactions. EUMEL and L3 took similar approaches; L4 instead takes persistence and even virtual memory out of the kernel. I wrote some somewhat sketchy notes on how Flash performance suggests rearchitecting things the other day at https://news.ycombinator.com/item?id=31902551 https://news.ycombinator.com/item?id=31902551; I know you have a very substantial amount of experience with this as a result of Varnish and your involvement with Fastly. What do you think? ______ * "Just" may be a loaded term here.

eru 4y ago
Keep in mind that (conventional) micro-kernels are not the same as exokernels. FUSE is fun, I've written my own filesystems with it, but it's basically a micro-kernel idea, not an exokernel one. (L4 is also great! But I don't think it qualifies as an exokernel?) https://pdos.csail.mit.edu/6.828/2019/lec/faq-exokernel.txt https://pdos.csail.mit.edu/6.828/2019/lec/faq-exokernel.txt explains a lot about exokernels that's not mentioned in the papers. Exokernels never caught on, at least not under that name. The closest equivalent in widespread use today are actually hypervisors for running virtual machines. (Especially if you are running a so called 'unikernel' on them.) About filesystems: if you just want the kinds of abstractions that conventional filesystems already give you, you won't get too much out of using an exokernel. (As you mention, perhaps you can get a bit of extra performance?) From the FAQ I linked above: > Q: In what kind of applications is an exokernel operating system preferable? There are naturally tradeoffs with the extra flexibility provided e.g. it is easier to make a mistake in user code. > A: An exokernel is most attractive to an application that needs to do something that is possible with an exokernel, but not possible with other kernels. The main area in which the 1995 exokernel paper increased flexibility was virtual memory. It turns out there are a bunch of neat techniques applications can use if they have low-level access to virtual memory mappings; the Appel and Li paper (citation [5]) discusses some of them. Examples include distributed shared memory and certain garbage collection tricks. Many operating systems in 1995 didn't give enough low-level access to virtual memory mappings to implement such techniques, but the exokernel did. The exokernel authors wrote a later paper (in SOSP 1997) that describes some examples in much more depth, including a web server that uses a customized file system layout to provide very high performance. The HN submission we are nominally discussing here is also about memory, so that might be applicable. An example for filesystems I could envision: direct low-level hardware access to an SSD's internals for a database. Databases don't really care about files, and might also want to deal with SSD's peculiar writing processes in a way that's different from the abstractions typical file systems give you. > Perhaps this is stating the obvious, but I don't think you can get much fault isolation with a pure library filesystem; if all the processes participating in the filesystem are faulty then there's no way to protect the filesystem from fatal corruption from faults. You might be able to reduce the presumed-correct filesystem core process to something like a simplified Kafka: a process that grants other processes read-only access to an append-only log and accepts properly delimited and identified blocks of data from them to append to it. That might be possible, but wouldn't really be faster than letting a kernel handle it, I'd guess? (But it would perhaps be more flexible to develop, since it's all userland.) You can also take inspiration from how eBPF allows you to upload user level logic into the Linux kernel and run them securely. Instead of uploading them into the kernel, you could also upload them into your filesystem service, I guess? Some of the original exokernel papers had some more interesting ideas sketched out. > I know you have a very substantial amount of experience with this as a result of Varnish and your involvement with Fastly. What do you think? I'm afraid you are mixing me up with someone else?