Paging to the web?

[joshw]

Seems pretty quiet in here these days.

I know right now there's a limitation, like 48 bits or so actually useful for addressing in 64-bit, but say it's not far off being able to address 64 bits or more.

What if we paged to the web? Moreover, what if we gave every document or piece of data an address, and when you need something, you just reference that memory address, and it's downloaded, swapped in, and the OS lets you access it seamlessly as if it's always in memory?

Maybe things are content-addressable, grouped by similarity, or grouped by identity.

Being intentionally vague to see what comes up. Have you guys floated this idea around?

[iansjack]

what if we gave every document or piece of data an address, and when you need something, you just reference that memory address, and it's downloaded, swapped in, and the OS lets you access it seamlessly as if it's always in memory?

Isn't that what is called a URL?

(Note that the Internet is estimated to occupy more than 64 zetabytes - and growing. A zetabyte would need a 70-bit address space.)

[joshw]

Isn't that what is called a URL?

Sure, it's one form of addressing. But not a permanent pointer-based address. You can't get the resource with a permanent pointer in memory unless you devised a scheme to page it in. You could also write to it and (if you had access), it could be published by paging it out.

So, for example, file hashes could map to a memory region. Trim the bit length, and any file can be loaded.

(Note that the Internet is estimated to occupy more than 64 zetabytes - and growing. A zetabyte would need a 70-bit address space.)

64 bits is definitely not enough, much less 48. So, we use a 128-bit or arbitrary address space. The page tables would be too large, but a theoretical MMU could expect a hash map instead (or whatever may have been proposed). We only use as much page table space as we have addressable things currently in use.

[iansjack]

But a memory address is no good on its own; nobody can remember an address. You need some form of name to translate to that address. And a URL is pretty good for that purpose - far better than a simple hierarchical directory would be with such a large amount of data. And you are going to need some form of distributed database to keep track of all those addresses and their updates - exactly what we already have; just think of the volumes of updates if your computer had to know all those addresses upfront without doing the equivalent of DNS queries.

It is already possible for data providers to allow their web pages to be written to (this page for example). But I suspect that most data providers would prefer to keep most of their data as read-only.

I don't really see any point in permanently mapping every available piece of data to a fixed numerical address. It's just too complicated and would require too much maintenance. I guess my question is what would be the point of the scheme you posit? It seems to me to be a solution looking for a requirement.

One thing you can be sure of - however large an address space you allocate for this purpose, this time next year you'll need an address space twice as large. All those pictures of cute kittens.

[joshw]

Here is an example setup that addresses those things. The hypothetical OS could join the IPFS network, tracking file identifiers using the Kademlia Distributed Hash Table. Your file system is just a big mapping of full path names to file identifiers. Just like IPFS, there's a scheme for local caching, and one for indexing the network. This would also add a scheme to map files into memory, e.g. by taking the first 96 bits of the file hash and leaving 4gb address space for the contents of the file (32 bits).

If you try to read or write to a file that's not present, the OS would just pull it from IPFS instead of from disk, by decoding the memory address and mapping it back to the network address.

Since 96 bits is probably not enough to reconstruct the full file hash to look it up, a similar KDHT would probably have to be modified to include something derived from the 96 bits.

No practical use in mind, just an interesting thought experiment. Could spark ideas for some other uses for large address spaces.

[eekee]

I think I've found a problem where the simple solution is to just not do this, but you do get to mmap(url) by the end of this paragraph. It goes like this: If you want an integer to address any byte on the web (HTTP), you'd need a database mapping address ranges to URLs. The content at any URL may change size at any time without notification to the database. When it grows longer than the address range allocated in the database, it needs to be moved to a new address. On the client side, this looks like realloc(); all pointers will have to be updated. Thus, if you address any byte of any web content at any time and expect parts to be paged in automatically, you have to make allowances for content changing during a program's run; you have to be ready to change the base address of the region you're accessing at any time. It would be better if the system required some sort of open or map function to be called before access, downloading the content to cache, mapping the cache into memory, and returning the base address. It would entirely make sense for the function to take a URL instead of an address, obviating the single web address space.

This is the first I've heard of IPFS, and all a quick look didn't give me enough to comment on.

I don't know half as much about content stores as I'd like; only 1 concrete example which was designed for an arbitrary number of users freely uploading content. It gave every uploaded item a uuid. Replacement content got a new uuid. Theoretically, such a store could be simply addressed as uuid_bits + bits(max_file_size). Let's say bits(max_file_size) = 64; that means 192 bit addresses, woof! You'd need layers and layers of caching to get any sort of performance out of it because even decoding 32 bits down to byte addresses runs into performance limits. Also, now we're hardcoding max_file_size, this is technically not future-proof.

Honestly, this all reaffirms my belief that large single-address spaces create deceptively complex conditions. Simple memory management for all but the simplest programs requires arbitrary limits or yield fragmentation, leakage and worse. Complex memory management code inevitably becomes very complex for performance. Every time this comes up, I get one step closer to coding an OS for the 8086

[joshw]

The content at any URL may change size at any time without notification to the database.

That's true! I guess the content-addressable space would be better for immutable files, and read-write stuff would be better represented by uuids, which can retain their address. For outgrowth, I'm sure there could be a method that can e.g. compute a derived uuid for subsequent blocks. Complicated, but not much moreso than current file sharing protocols.

Every time this comes up...

heh... must be a popular thought!

...one step closer to coding an OS for the 8086

I'm all about it!

Alright, well good exercise. How about this idea (barring program isolation, etc.): memory and storage are unified, and files are objects referencing each other with pointers. You just map to your local storage or home network, and wire paging to that. Of course, this doesn't preclude you from having to write an efficient data store or sensible layout. But it does potentially make it simpler to open and read files. Could be fun to code for

[joshw]

All those pictures of cute kittens.

Given the number of combinations possible, could a generative AI be trained to map a given cat image into n-dimensional bit space and back?

[iansjack]

Alright, well good exercise. How about this idea (barring program isolation, etc.): memory and storage are unified, and files are objects referencing each other with pointers.

Ah - IBM i (aka OS/400).

[Demindiro]

It can be practical if you also add immutability to the mix.

If the data you fetch is immutable, then you can use a cryptographic hash as address, which does not need to be more than 256 bits (32 bytes).
You can also keep the data in a read-only cache, as it is immutable, mitigating issues with latency. Even more: you can make as many copies as you want without worries about desynchronization, as there is no such thing with immutable data.

Updating data would involve making whatever changes you want, calculating a new hash, then publishing that hash to whatever needs it. As well as the modified data to an appropriate location, of course.

===

I've spent a fair amount of time (and ongoing) on figuring this out, as I'll need such a system for some of my projects. I'm confident the mechanism I described is practical to implement, I mainly have been getting bogged down in details.

One particular distraction was when from a earlier language experiment I figured I could represent all data as either:

• "nil"
• pairs, each element either "nil" or another pair.

Combine that with hashing and you can form a minimal acyclic graph representing any data you can think of. You just need to agree on some conventions how to represent certain things, like binary "1" and "0".

But then I discovered the Iota combinator. This gave me the silly idea to instead make all data representable by combinators. Specifically: you wouldn't look at the combinators directly, but instead give it two special combinators "0" and "1" which would then get reduced to a bitstream. You can find my code here (the second version of it).
You may find the definitions file the most interesting.

In the meantime, I've learned a bit about Forth and I'm writing my own dialects now. Forth made me realize I don't need to construct a tree/graph right away. Instead one can be constructed using a bitstream. I.e. any binary blob in any format can be converted to a graph, as long as you know how to parse it. This will be significantly easier too, as all (mainstream) cryptographic hashes are designed to operate on plain binary data.

Once I wrap up work on some of my other projects I'm going to take a look at it again.

[evaristo]

What if we paged to the web? Moreover, what if we gave every document or piece of data an address, and when you need something, you just reference that memory address, and it's downloaded, swapped in, and the OS lets you access it seamlessly as if it's always in memory?

Isn't that an URL? Furthermore, for the and the OS lets you access it seamlessly as if it's always in memory part, you are just referring to 9P

[VincentVL85]

This is something I've been writing about on the MAD blog recently (honestly kind of banging my head against the wall writing about part of this right now), but it's kind of funny how it is and isn't so much harder than it sounds. As soon as you stop talking about local memory a lot of things stop being even remotely guaranteed. For instance, if a live memory object is stored remotely and you pull the plug on your computer, then update the application that was using it before starting that app again, it's possible the app will go looking for that external memory, but the code that manages that object type will have changed. At the very least, you will need some mechanism to detect the program has stopped running and invalidate its remote memory, which may not be as simple as the application telling you that it is quitting. Also... memory leaks now spread across multiple computers; lovely.

Likewise, if you want to use this "paging to the web" to transfer live data blocks from one app to another, suddenly not only do you need to coordinate the object's theoretical type between the two programs, but you need to coordinate the library version metadata, otherwise the code that reads it and the code that wrote it may not be in perfect alignment. Obviously we do that now for file types, but any data object that might get stored remotely now needs to be managed the same way. Depending on what exactly gets paged away and how much control the programmer has, you never know but some internal data structure used by a library will change. It's essentially making it possible to hotplug the library code while the data remains untouched - sort of like updating your kernel without rebooting, but for any and every software update. All of that kind of takes away from the idea that it is useful as just a low-level paging mechanism.

Because of my whole project thing, my answer to a challenge like this is pretty much "go big", as in standardized systems for tracking data types and library versions. If you're not keen on giving yourself an aneurism, it might make more sense to treat foreign memory as data-at-rest instead of live, serialized and deserialzed into fixed formats instead of just blitting back and forth. That would be a lot more flexible than trying to keep immaculate track of the in-memory representation to ensure that the library's bits didn't get tweaked because of a compiler optimization or similar.

I'd also like to point out that paging to the web per se, is an absolutely horrific idea as a matter of security and dependability - no offense to Web3, but it's generally unwise, even if you're pretty confident that it won't cause a fault, and I know that the math of Web3 theoretically checks out. As far as I'm concerned, it's much more managable is to have a multi-computer system that is entirely under your control, on a local network, VPN, or similar, in which all nodes in that system expose their resources to each other. In that kind of distributed system, if you need more memory and it exists somewhere else, use it - it belongs to you anyway.

But if you have all that extra hardware under your control and only use it to page memory, you are wasting nearly all of the gestalt system's potential. Every resource you fetch over the network is really just the output of a program - you can have that server do whatever you want, because you control it. Trying to reach the full potential of a distributed system is the point of MAD, and it's not simple, in part because our extant networking model is two separate programs, client and server, instead of a single program broken up into pieces that live on different sides of the network. If you had that, if you could simply take an axe to your program and toss one half of it somewhere else and it would still work, then the task of accessing the memory that is over there, is no different than accessing the memory anywhere else in your program.

THAT would be interesting. Just having more paging space... what's the real benefit to that over paging to disk?