A region based abstraction of StableMemory

[crusso]

The Motoko StableMemory libraries bother me since they allow direct access to stable memory, using absolute addresses, are non-modular and will prevent us from moving to a better world where stable variables are maintained in memory throughout computation.

I've been wondering if we should at least consider moving to a more region based api, where programs allocate abstract isolation regions, where either all or, to simplify, perhaps just the last allocated region is growable.

Implemented as a class, Region, on top of the Raw API, this would look something like this:

https://m7sm4-2iaaa-aaaab-qabra-cai.raw.ic0.app/?tag=3279634825

import SM "mo:base/ExperimentalStableMemory";
import Debug "mo:base/Debug";
import Nat32 "mo:base/Nat32";

actor {
  class Region(pages : Nat32) {
      let base = SM.size() << 16;
      var end = base;

      public func grow(pages : Nat32) : Bool {
         if ((SM.size() << 16) == end) {
           let oldsize = SM.grow(pages);
           if (oldsize == 0xFFFFFFF) return false;
           end += pages << 16;
           return true;
         };
         return pages == 0;
      };

      assert (grow(pages));

      private func rebase(offset : Nat32, bytes : Nat32) : Nat32 {
          let address = base + offset;
          assert(address + bytes < end);
          base + offset;
      };

      public func loadNat8(offset : Nat32) : Nat8 {
          SM.loadNat8(rebase(offset, 1));
      };

      public func storeNat8(offset : Nat32, value : Nat8) : () {
          SM.storeNat8(rebase(offset, 1), value);
      };

      // etc.

      // perhaps also
      public func toBlob() : Blob {
          // may trap if region too large on StableMemory 64
          SM.loadBlob(base, Nat32.toNat(end - base));
      };

      public func size() : Nat32 {
          end - base;
      };

  };

}
;

However, I think we should not do this as a library, to prevent breaking the abstraction, but present regions as a new, opaque primitive type that is stable (and can be stored in stable data structures), with a lighter weight functional API, in which each operation is a known function that takes its region as first argument. The lower-level StableMemory.mo library would now be safely hidden underneath this abstraction. That would also avoid the overhead of record indexing and indirect functions calls and the problem with objects being non-stable.

E.g. something like (for 64 bit SM):

module Regions {
     type Region; // opaque but stable and not shared.
     region : (pages : Nat64) -> Region
     size : Region -> Nat64
     grow : (Region, pages : Nat64) -> Bool
     loadNat8: (Region, offset : Nat64) -> Nat8
     storeNat8 : (Region, offset : Nat64, value : Nat8) -> ()
}

(I'd even suggest putting the load/store operation under modules named by type, for uniformity).

Note that all offset are relative to the region and bounds checked. I would not allow region values (the handles) to be load/stored (or shared), so we eventually have the freedom to collect and maybe grow all regions, not just the last one.

This way, libraries can allocate their own isolated regions or be handed regions to work with. The only downside is that there is still some shared state that determines whether a given region can be grown.

Naive users could still use a single region and grow it incrementally, much as the current (Experimental)StableMemory library, but protected by a handle that must be explicitly passed to libraries that require them. A region is like a capability (good) while our StableMemory library is more like a global variable (terrible).

I'm open to better suggestions - there must be some. For example, the PalmPilot memory model was a much fancier version of something like this.

If we implemented this with some sort of page allocator for raw stable memory, then we might keep open the ability to separate the stable memory pages used for future in-flight stable variables and those used for regions.

[crusso]

@rossberg @nomeata @osa1 @ggreif @chenyan-dfinity @matthewhammer what do you think?

[nomeata]

The main thing I like about this is the last paragraph: not blocking out way to keeping stable data in stable memory while the program is running, which I think we should focus on. Otherwise I don't care too much, as I didn't care too much about the previous attempt to expose stable memory directly - both seem to be a bad fit for Motoko anyways. But I'm digressing…

[nomeata]

With the opaque interface above, it seems very inviting to have a page allocator below, and thus allow them all to grow. Essentially a memory multiplexer. But it's still a distraction from making stable variables work properly, IMHO. Although such a page allocator might be needed internally anyways, and then expositing growable arrays of bytes doesn't hurt.

Isn't this what this is? A data type similar to Buf<Nat8>? But then why not frame it like this, and add that as a data type and make it shared? At least once we keep stable variables in stable memory, there wouldn't be much difference, would there?

[crusso]

Yes it is similar to Buf, except that Buf grows implicitly and relies on the gc to cleanup. Supporting that would indeed need a page allocator or users would quickly churn through all stable memory... I too dislike the idea of raw access to SM, especially one that paints us into a corner.

[rossberg]

In the abstract, this looks fine, but how would you efficiently implement grow on a region?

[crusso]

The idea was to only allow growth of the last allocated region, as the implementation above does. However, Andreas and I discussed this offline.

Andreas is worried that adding grow to all regions, not just the last one, might lead to a unpredictable performance cliff when backed by a paging allocator and that it would be better to identify regions with wasm memories (as access to more than one of those come on-line).

Consequently, Andreas proposes to roughly keep the functional API, but remove the the dynamic region constructor for now, and have a single region handle passed in to the shared context pattern (along caller) of an actor class (but not methods).

That roughly gives us the capability based access, but for a single region.

If we ever move to multiple memory support in wasm then we might be able to generalize this , but since wasm has only static indexing of a finite set of known memories, I'm not sure how we'd actually do that - pass in an immutable array of memories, configured at installation only?

[rossberg]

Once we have multiple memories support in the IC, none of this would be needed anymore, since each module could just define its own memory and use it without interference from others. That should be our target, everything we're doing now is just a temporary backup plan, AFAIAC.

[crusso]

Hmm, I'm not sure I like the revision that much. If it's just a temporary hack, why extend the language with a stable, opaque region type and the class context with an additional field? That feel like even more of a language change... but I guess I can live with it and started down this path by suggesting the new region type.

Omer's basic page allocator doesn't look that complicated, but we'd have to save its state (the page freelists) n an upgrade as well which is yet more complexity.

[rossberg]

Yeah, the fact that it is temporary was my reason for foregoing extra boilerplate mechanisms.

I still don't see how a page allocator helps. The pages would have to be contiguous for addressing to work, which defeats their purpose. Alternatively, we would have to somehow enable representing fat pointers between multiple dynamically created pages, which means that pages require a handle that can itself be stored in a page, i.e., is transparent. At least if you want to avoid indirections through Motoko tables in stable vars, which would be a total bastard approach and add further to the coast.

[crusso]

Hmm,. why not just have a constructor (function 'region`) that can be invoked at most once. Since imports are pure, the main actor can always grab the region and pass it on if desired.

[rossberg]

We could do that, but in terms of capability-based access control, that's neither here nor there. As a permanent interface, it would be undesirable. As a temporary interface, does it provide a sufficiently relevant advantage to be worth it?

Btw, could we use the actors self principal instead of a separate token? That would save us from adding a new type and the extension to the context object.

[crusso]

Principals can be forged can't they? So no.

Do you have any preference on the name of the Region type, otherwise I'll just use that. The other obvious one is Memory

[crusso]

The other option is that we forget about ever using stable memory for in-flight stable vars and just a separate memory for that. I wish I'd insisted more on adding memory 64 as a separate memory....

[nomeata]

I'm a bit lost; what problem are we trying to solve with the existing or this direct memory access? And is that a step in the right direction, or a distraction?

It seems to me that raw memory access is quite an odd thing for language like Motoko, and I wonder if we should stop to beat around the bush and instead work towards making stable variables work properly and seamless, as originally intended, and using all available stable memory (instead of, what's it now, ~150MB before the cycle limits are hit and the canister becomes unupgradeable).

I'd rather have something quite slow that works (e.g.: uniform rep becomes 64 bits to address objects in stable memory, these are simply read from and written to there, writes to stable memory eagerly moves referenced objects there) and optimize later (e.g.. caching objects in main memory),

Or do we give up on stable variables?

[crusso]

That would be closer to the ideal solution, but in the meantime we need to povide users with way to store large amounts of data without stressing our first/second generation GC and without painting ourselves into a corner by hogging all of StableMemory for users.

[nomeata]

Or, put differently: if our surface semantics is fine as is, and our implementation is lacking, why are we discussing user-visible changes?

[nomeata]

Is anyone out there even using the ExperimentalStableMemory module? I am not sure if a stop-gap solution is needed, and worth the distraction.

[crusso]

I think because we don't have the budget to do the right thing in the short term, and need some stop-gap measure.

[nomeata]

Hmm, bummer. Since when have the perceived needs of our potential users guided our development? ;-)

Oh well, I'll focus on the beach again.

[crusso]

Several user were uploading large NFT sand the GC was struggling with this, though moving to a more recent scheduler alleviated that a bit. But we are still limited to less than 4GB this way unless we start utilizing stable memory.

[nomeata]

The upgrade cycle limit is so high now that it's no longer the bottleneck?

[crusso]

No idea. Is it?

[nomeata]

I would be surprised. But the fact that we don't know means nobody tried and complained, so people are not storing that much data in their canisters (yet). Or we don't hear them.

[rossberg]

The motivation is that we want to provide the ability to build efficient persistent abstractions that allow for zero-cost upgrades. Think emulating a key/value store, data base, or file system. Currently, you can only realistically do that in Rust.

We are a looooong way from being able to do that with stable vars. For one, an efficient implementation of stable vars directly in stable mem would require direct access to stable mem, which in turn would require Wasm multi-memory to be available on the IC. Then we'd need cross-memory GC, which would require a mature generational and incremental GC for Motoko. And even then it would not serve all use cases – for high performance, large data sets, you generally need more fine-grained control over data layout and memory management.

Thus the idea to provide a lower-level interface to stable memory that is more like accessing a large file.

It looks like users are already trying to store far more data in canisters than we anticipated, and I fear the first incident of an unupgradable canister is approaching fast. We can't afford to wait for that.

[rossberg]

Principals can be forged can't they? So no.

Yeah, crap. All these bad design decisions...

Do you have any preference on the name of the Region type, otherwise I'll just use that. The other obvious one is Memory

StableMemory? FWIW, if you prefer, I'm fine with the call-once constructor version.

[nomeata]

But we are providing stable variables now, so the first incident will happen eventually. Is it better to say “sorry, but you are using a beta product, and maybe missed yhr warning that you should keep it small for now while we make the changes to make the code you wrote scale” or to say “sorry, but you shouldn't have used stable variables, instead use this other new and less integrated feature, but because it's there it's your fault and not ours”?

If, for now, stable vars are definitely not for sizable data we should move the serialization code to the end of each message, so that our users wont run into non-upgradeable canisters. This will reduce the size even more, but it's safer and will judge them to use the low level interfaces (or libraries around them) before it's too late. Maybe restrict stable vars to 10M or something like that?

[rossberg]

Well, currently the first priority is to provide an alternative at all. We can consider additional restrictions on stable vars once that option is available.

Long-term, both options have their use cases – even if we manage to improve stable vars, they won't be adequate for everything.

[nomeata]

Isn't a capacity restriction to prevent non-upgradeable canisters much more urgent than providing new features (which don't prevent existing users from shooting themselves into the foot). It's supposed to be a safe language.

Also, we should clearly communicate where this is heading. If stable variables are a dead end, our users should know.