7 ms·

About Flat vs. Object stores I wrote this piece, frustrated by, what looks to me, like the entire semiconductor industry is only exploring one single computer

by phkamp 4y ago

About Flat vs. Object stores I wrote this piece, frustrated by, what looks to me, like the entire semiconductor industry is only exploring one single computer storage organization, despite the fact that recent inventions like flash practically begs for innovation. For instance few people realize that the Flash Adaptation Layer in the SSD devices means that we literally run two filesystems on top of each other, because nobody has seriously tried to get rid of the "a disk is an array of individually rewritable sectors" despite this literally being untrue both for modern disks and in particular for Flash based storage. Similarly, the "flat physical/flat virtual" MMU model is a relic from the days of IBM 360 and VAX 11/780 and utterly inefficient and unsuitable for what we do in userland these days. As Robert has shown with CHERI, there is plenty of space to innovate without breaking existing code. And yes, C can be object oriented, all you have to do is keep your hands from the primitives which are necessary to access hardware directly. Architectually GPU's are a superoptimized distraction, like the vector-units on Cray and Convex computers were 40-50 years ago, but those too can function in a non-flat address-space. But even C in OO-mode, and C++, Go, Rust, PHP and for that matter LISP and SmallTalk, would benefit from an HW/MMU architecture which focused on delivering fast object service, rather than flat address-spaces which software must then convert into objects. But to innovate, we must first realize that we are currently stuck in a box, and dare to look outside it.

eru 4y ago
Thanks for writing the article and explaining some background here. Are you familiar with exokernels? They were an attempt to remove abstractions from kernel land and leave that to applications. See https://www.classes.cs.uchicago.edu/archive/2019/winter/33100-1/papers/hotos-jeremiad.pdf https://www.classes.cs.uchicago.edu/archive/2019/winter/3310... That way innovation can be much faster, because applications can generally move quicker than kernels. Btw, I'm not a fan of object orientation; and I don't think our hardware design should be infected by that fad. But I think your criticism of the badly fitting abstraction of flat address spaces is still valid. I am just not sure that 'fast object service' is necessarily the remedy.
- phkamp 4y ago
  I'm not a fan of any archtectural radicalism, and tend to think that there are things best done in both hardware, kernel and libraries and applications :-) That is not to say that the boundaries should be cast in stone, they should obviously be flexible enough that you do not need a complete multi-user management system in a single-service jail or container nor a full-blown journaled COW storage-manager on a small embedded system. In other words: I am firmly for the "Software Tools" paradigm.
  - eru 4y ago
    From the paper: > The defining tragedy of the operating systems community has been the definition of an operating system as software that both multiplexes and abstracts physical resources. The view that the OS should abstract the hardware is based on the assumption that it is possible bath to define abstractions that are appropriate for all areas and to implement them to perform efficiently in all situations. We believe that the fallacy of this quixotic goal is self-evident, and that the operating system problems of the last two decades (poor performance, poor reliability, poor adaptability, and inflexibility) can be traced back to it. The solution we propose is simple: complete elimination of operating system abstractions by lowering the operating system interface to the hardware level. Basically, they say to let libraries do the abstraction. The source code of your applications will still mostly look the same as before. It's just that the libraries will do more of the work, and the kernel will do less.
    - 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).
zasdffaa 4y ago
It's a rant and it's not information heavy. I've never heard of this processor (and provide a link, don't tell me to look it up). Other OO processors: Rekursiv (https://en.wikipedia.org/wiki/Rekursiv https://en.wikipedia.org/wiki/Rekursiv) and that famously slooow intel iAPX 432 (https://en.wikipedia.org/wiki/Intel_iAPX_432 https://en.wikipedia.org/wiki/Intel_iAPX_432) Interesting but neither (esp. the latter) were known as racehorses. I'd prefer to keep the hardware simple and fast and push the complexity into the software, and prove stuff. > would benefit from an HW/MMU architecture which focused on delivering fast object service, rather than flat address-spaces which software must then convert into objects. That conversion may not be cheap (edit: badly phrased, the object mapping process and hardware may not be cheaper (edit again: = faster) than that mapping done by the MMU for conventional memory) - can you exaplain how it would be done such that it would be cheaper in time than the current mapping in the common/hot/optimistic path, and how it would not be worse than it is now on the rare/cold/pessimistic path? And how it would behave on average, between those 2 extremes? And why objects everywhere would be better all-round?
- klelatti 4y ago
  On the subject of the iAPX 432 is anyone aware of an emulator? The only material I’ve seen is quite high level and doesn’t go down to ISA level.
- p_l 4y ago
  iAPX 432 arguably wasn't bad due to OOP orientation, but due to a bunch of several issues in how intel went about executing the idea. To the point that if they mismanaged a "normal" cpu this way they would have bungled it similarily.
- kragen 4y ago
  Probably if you haven't heard of CHERI and can't be bothered to Google it when one of the most respected systems architects around tells you it's worth looking at, you aren't going to put in the effort needed to read the CHERI tech reports so you can have an informed opinion on the performance cost of putting this kind of protection into hardware. And if the only historical "OO" processors you can think of are Rekursiv and iAPX432, and not the Dorado or the Symbolics line or the B5000/B5500/ClearPath line, it sounds like you have a lot of reading to do to get to having an informed opinion.
benreesman 4y ago
It’s a big thread (by virtue of being a cool piece), so maybe someone said this already, but isn’t there kind of a middle ground where we let existing software continue to run but acknowledge a changing hardware landscape by really cranking up (default) page sizes? Userland allocators already work pretty hard to hit in the TLB [1], but huge-page tuning and whatnot is, to your point, only hitting the sweet spot on modern gear via effort/luck. [1] https://engineering.fb.com/2011/01/03/core-data/scalable-memory-allocation-using-jemalloc/ https://engineering.fb.com/2011/01/03/core-data/scalable-mem...
- phkamp 4y ago
  I think that is a false dictomy. CHERI has shown that this kind of fundamental architectural improvements can happen with very little impact to running code.
  - benreesman 4y ago
    Not to be contradictory, but I’m having a hell of a time getting a toolchain put together that can reproducibly target Linux on x86_64 without liking glibc or libstdc++ and easily accommodate open-source libraries, and it’s not for want of knowing how the individual pieces work. If you’re promoting computer architecture and OS research, have at it, needs doing. But that’s a different game to running software on the architectures, operating systems, and tool chains we have today.
- Symmetry 4y ago
  Channeling my inner Linux, defaulting to larger pages means a drastic loss in memory efficiency when mmaping lots of small files as happens when someone compiles the Linux kernel. If you've got a 2kb file and 4kb pages then half the memory you allocate when the file is paged in is wasted. For larger pages that goes way up.
  - benreesman 4y ago
    Absolutely, but you also want a different scheduler for a low-latency server than you do for your desktop. One size almost never fits all, as I’m sure you’ll agree as someone who cares about compiling the kernel. With that said, the kernel is pretty good at reclaiming physical pages, so you’d most likely eat into the same disk cache you’re reading from in the scenario you’ve described.
FunnyBadger 4y ago
This is correct. A lot of this due to the hardware architecture itself. The software abstractions dictated/limited by the HW itself causes many of the risks! If you designed BOTH HW and SW up to and including the OS, you _might_ have a chance to control the risks better. But by the very separation of duties and roles, papered over by abstraction itself, you create problems. ALL abstractions throw away information and eventually those abstractions bite you in the ass. This was the case with digital logic once HW speeds rose to a critical level - suddenly the reality that digital is merely an abstraction upon analog and the very abstraction of lumped-model analog started failing which caused digital fail as well. We definitely can have and have had the same failure occurring with von Neumann architecture - there's NOTHING magical about it that immunizing against model abstraction failure and it can creation "intrinsic failures" that can never be fixed thanks to Gödel's incompleteness theorem.
titzer 4y ago
I am very sympathetic to this argument overall and trace the hardware industry's failure back to the spread of C, UNIX, and worse-is-better. With Wasm I see an opportunity to virtualize away the old world of C and linear address spaces. While we designed it to be low level and sandboxed to get C/C++ and Rust on board, I and others have always had in mind a future world where Wasm has managed (GC'd) data, first-class typed functions, and more. Those features should support a wide variety of source languages. Wasm should become the new, final ISA. It should become like Unicode; the final, most widely-supported[1] format for executable code. When all languages and programs can run easily on Wasm, then hardware can easily be swapped out. [1] Sure, Unicode has flaws, and it doesn't support everything equally as well. But it had the property that basically everyone dropped everything else in favor it, because it gained all the momentum.
- duped 4y ago
  As I understand it, wasm modules depend heavily on linear memory in growable buffers in each module.
  - titzer 4y ago
    Yes, because linear memory is the only game in town right now :)
kazinator 4y ago
Re: flash. A flash adaptation layer solves the following problem: I have M filesystems, that I'd like to use on any one of N different flash technologies. I don't want to complicate each M filesystem with support for N flashes. I don't think both layers are "filesystem" in the same sense. We don't need the lower filesystem to provide permissions, ownerships, time stamps, directories, symbolic links and such. Re: linear A machine address is a word of bits. A word of bits always has a linear interpretation as a binary number. For instance if we have a 16 bit segment ID, and a 32 bit offset, then we can still pretend that it's a 48 bit linear address. We can compare two pointers for inequality, for instance: p0 < p1, as 48 bit words. That space may be sparsely populated, but that doesn't make it nonlinear; the spaces you are calling linear can also be sparsely populated and have numeric conventions about regions. You say physical memories are linear, but they are also sparsely populated in the same way: such and such a range is a ROM, such and such a range is certain memory mapped registers, DRAM is over there. Generally speaking, hardware treats some part of an address as an ID that it recognizes, and then the bits below that as an offset. When there is a bus read or write, if the ID part matches that hardware device, then it selects itself for that I/O operation, and uses the offset bits to provide access to the right thing. So physical memory is arguably nonlinear; it is like a subclassed IP address space. Physical addresses can have bits which are not used for addressing; e.g. a certain range of memory might be available as uncached if you enable a certain upper bit in the address. That looks like linear, but with aliasing between distant regions. Linear virtual memory is sparsely populated; there are mapped pages and unmapped pages. Pages can alias: the same object can be mapped in multiple places, so a write here can be read there. If you want to split an address into an object ID and offset, you have to gamble about how many bits you need for each one. One application has hundreds of millions of tiny objects: it wants a big object ID part of the address, and a small offset. Another one has a small number of huge objects: it doesn't care for large object ID, but wants big offsets. Either you make that configurable (slow gets even slower), or else waste bits on making both spaces larger at the same time, perhaps ending up with wasteful 128 bit pointers on a system where 64 is more than enough. All interpretations of the bits of an address above and beyond "pure binary number" add complication and overhead. The hardware (e.g. DMA bus master) isn't going to understand objects; it will always want a simple address. Re: C, C++, Go, Rust, PHP, Lisp, Smalltalk No two implementations of these can agree with each other on what exactly is an object. Implementations will just carry their existing respective portable object representations into the non-linear model. Architectures without flat memory, like the JVM and WebAssembly, tend to only cause pain for Lisp and its ilk. A Lisp is not going to want some weird object model from the operating system; it will want to do things like packing cons cells tightly together into one larger heap object. That heap object could be a segment. We had those; they are also from the 1960's. Operating systems started ignoring them, opting for just the demand paging support the VM hardware.

by phkamp 4y ago

eru 4y ago

Thanks for writing the article and explaining some background here. Are you familiar with exokernels? They were an attempt to remove abstractions from kernel land and leave that to applications. See https://www.classes.cs.uchicago.edu/archive/2019/winter/33100-1/papers/hotos-jeremiad.pdf https://www.classes.cs.uchicago.edu/archive/2019/winter/3310... That way innovation can be much faster, because applications can generally move quicker than kernels. Btw, I'm not a fan of object orientation; and I don't think our hardware design should be infected by that fad. But I think your criticism of the badly fitting abstraction of flat address spaces is still valid. I am just not sure that 'fast object service' is necessarily the remedy.

phkamp 4y ago
I'm not a fan of any archtectural radicalism, and tend to think that there are things best done in both hardware, kernel and libraries and applications :-) That is not to say that the boundaries should be cast in stone, they should obviously be flexible enough that you do not need a complete multi-user management system in a single-service jail or container nor a full-blown journaled COW storage-manager on a small embedded system. In other words: I am firmly for the "Software Tools" paradigm.
- eru 4y ago
  From the paper: > The defining tragedy of the operating systems community has been the definition of an operating system as software that both multiplexes and abstracts physical resources. The view that the OS should abstract the hardware is based on the assumption that it is possible bath to define abstractions that are appropriate for all areas and to implement them to perform efficiently in all situations. We believe that the fallacy of this quixotic goal is self-evident, and that the operating system problems of the last two decades (poor performance, poor reliability, poor adaptability, and inflexibility) can be traced back to it. The solution we propose is simple: complete elimination of operating system abstractions by lowering the operating system interface to the hardware level. Basically, they say to let libraries do the abstraction. The source code of your applications will still mostly look the same as before. It's just that the libraries will do more of the work, and the kernel will do less.
  - 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).

zasdffaa 4y ago

It's a rant and it's not information heavy. I've never heard of this processor (and provide a link, don't tell me to look it up). Other OO processors: Rekursiv (https://en.wikipedia.org/wiki/Rekursiv https://en.wikipedia.org/wiki/Rekursiv) and that famously slooow intel iAPX 432 (https://en.wikipedia.org/wiki/Intel_iAPX_432 https://en.wikipedia.org/wiki/Intel_iAPX_432) Interesting but neither (esp. the latter) were known as racehorses. I'd prefer to keep the hardware simple and fast and push the complexity into the software, and prove stuff. > would benefit from an HW/MMU architecture which focused on delivering fast object service, rather than flat address-spaces which software must then convert into objects. That conversion may not be cheap (edit: badly phrased, the object mapping process and hardware may not be cheaper (edit again: = faster) than that mapping done by the MMU for conventional memory) - can you exaplain how it would be done such that it would be cheaper in time than the current mapping in the common/hot/optimistic path, and how it would not be worse than it is now on the rare/cold/pessimistic path? And how it would behave on average, between those 2 extremes? And why objects everywhere would be better all-round?

klelatti 4y ago
On the subject of the iAPX 432 is anyone aware of an emulator? The only material I’ve seen is quite high level and doesn’t go down to ISA level.
p_l 4y ago
iAPX 432 arguably wasn't bad due to OOP orientation, but due to a bunch of several issues in how intel went about executing the idea. To the point that if they mismanaged a "normal" cpu this way they would have bungled it similarily.
kragen 4y ago
Probably if you haven't heard of CHERI and can't be bothered to Google it when one of the most respected systems architects around tells you it's worth looking at, you aren't going to put in the effort needed to read the CHERI tech reports so you can have an informed opinion on the performance cost of putting this kind of protection into hardware. And if the only historical "OO" processors you can think of are Rekursiv and iAPX432, and not the Dorado or the Symbolics line or the B5000/B5500/ClearPath line, it sounds like you have a lot of reading to do to get to having an informed opinion.

benreesman 4y ago

It’s a big thread (by virtue of being a cool piece), so maybe someone said this already, but isn’t there kind of a middle ground where we let existing software continue to run but acknowledge a changing hardware landscape by really cranking up (default) page sizes? Userland allocators already work pretty hard to hit in the TLB [1], but huge-page tuning and whatnot is, to your point, only hitting the sweet spot on modern gear via effort/luck. [1] https://engineering.fb.com/2011/01/03/core-data/scalable-memory-allocation-using-jemalloc/ https://engineering.fb.com/2011/01/03/core-data/scalable-mem...

phkamp 4y ago
I think that is a false dictomy. CHERI has shown that this kind of fundamental architectural improvements can happen with very little impact to running code.
- benreesman 4y ago
  Not to be contradictory, but I’m having a hell of a time getting a toolchain put together that can reproducibly target Linux on x86_64 without liking glibc or libstdc++ and easily accommodate open-source libraries, and it’s not for want of knowing how the individual pieces work. If you’re promoting computer architecture and OS research, have at it, needs doing. But that’s a different game to running software on the architectures, operating systems, and tool chains we have today.
Symmetry 4y ago
Channeling my inner Linux, defaulting to larger pages means a drastic loss in memory efficiency when mmaping lots of small files as happens when someone compiles the Linux kernel. If you've got a 2kb file and 4kb pages then half the memory you allocate when the file is paged in is wasted. For larger pages that goes way up.
- benreesman 4y ago
  Absolutely, but you also want a different scheduler for a low-latency server than you do for your desktop. One size almost never fits all, as I’m sure you’ll agree as someone who cares about compiling the kernel. With that said, the kernel is pretty good at reclaiming physical pages, so you’d most likely eat into the same disk cache you’re reading from in the scenario you’ve described.

FunnyBadger 4y ago

This is correct. A lot of this due to the hardware architecture itself. The software abstractions dictated/limited by the HW itself causes many of the risks! If you designed BOTH HW and SW up to and including the OS, you _might_ have a chance to control the risks better. But by the very separation of duties and roles, papered over by abstraction itself, you create problems. ALL abstractions throw away information and eventually those abstractions bite you in the ass. This was the case with digital logic once HW speeds rose to a critical level - suddenly the reality that digital is merely an abstraction upon analog and the very abstraction of lumped-model analog started failing which caused digital fail as well. We definitely can have and have had the same failure occurring with von Neumann architecture - there's NOTHING magical about it that immunizing against model abstraction failure and it can creation "intrinsic failures" that can never be fixed thanks to Gödel's incompleteness theorem.

titzer 4y ago

I am very sympathetic to this argument overall and trace the hardware industry's failure back to the spread of C, UNIX, and worse-is-better. With Wasm I see an opportunity to virtualize away the old world of C and linear address spaces. While we designed it to be low level and sandboxed to get C/C++ and Rust on board, I and others have always had in mind a future world where Wasm has managed (GC'd) data, first-class typed functions, and more. Those features should support a wide variety of source languages. Wasm should become the new, final ISA. It should become like Unicode; the final, most widely-supported[1] format for executable code. When all languages and programs can run easily on Wasm, then hardware can easily be swapped out. [1] Sure, Unicode has flaws, and it doesn't support everything equally as well. But it had the property that basically everyone dropped everything else in favor it, because it gained all the momentum.

duped 4y ago
As I understand it, wasm modules depend heavily on linear memory in growable buffers in each module.
- titzer 4y ago
  Yes, because linear memory is the only game in town right now :)

kazinator 4y ago

Re: flash. A flash adaptation layer solves the following problem: I have M filesystems, that I'd like to use on any one of N different flash technologies. I don't want to complicate each M filesystem with support for N flashes. I don't think both layers are "filesystem" in the same sense. We don't need the lower filesystem to provide permissions, ownerships, time stamps, directories, symbolic links and such. Re: linear A machine address is a word of bits. A word of bits always has a linear interpretation as a binary number. For instance if we have a 16 bit segment ID, and a 32 bit offset, then we can still pretend that it's a 48 bit linear address. We can compare two pointers for inequality, for instance: p0 < p1, as 48 bit words. That space may be sparsely populated, but that doesn't make it nonlinear; the spaces you are calling linear can also be sparsely populated and have numeric conventions about regions. You say physical memories are linear, but they are also sparsely populated in the same way: such and such a range is a ROM, such and such a range is certain memory mapped registers, DRAM is over there. Generally speaking, hardware treats some part of an address as an ID that it recognizes, and then the bits below that as an offset. When there is a bus read or write, if the ID part matches that hardware device, then it selects itself for that I/O operation, and uses the offset bits to provide access to the right thing. So physical memory is arguably nonlinear; it is like a subclassed IP address space. Physical addresses can have bits which are not used for addressing; e.g. a certain range of memory might be available as uncached if you enable a certain upper bit in the address. That looks like linear, but with aliasing between distant regions. Linear virtual memory is sparsely populated; there are mapped pages and unmapped pages. Pages can alias: the same object can be mapped in multiple places, so a write here can be read there. If you want to split an address into an object ID and offset, you have to gamble about how many bits you need for each one. One application has hundreds of millions of tiny objects: it wants a big object ID part of the address, and a small offset. Another one has a small number of huge objects: it doesn't care for large object ID, but wants big offsets. Either you make that configurable (slow gets even slower), or else waste bits on making both spaces larger at the same time, perhaps ending up with wasteful 128 bit pointers on a system where 64 is more than enough. All interpretations of the bits of an address above and beyond "pure binary number" add complication and overhead. The hardware (e.g. DMA bus master) isn't going to understand objects; it will always want a simple address. Re: C, C++, Go, Rust, PHP, Lisp, Smalltalk No two implementations of these can agree with each other on what exactly is an object. Implementations will just carry their existing respective portable object representations into the non-linear model. Architectures without flat memory, like the JVM and WebAssembly, tend to only cause pain for Lisp and its ilk. A Lisp is not going to want some weird object model from the operating system; it will want to do things like packing cons cells tightly together into one larger heap object. That heap object could be a segment. We had those; they are also from the 1960's. Operating systems started ignoring them, opting for just the demand paging support the VM hardware.