-
Notifications
You must be signed in to change notification settings - Fork 12
Durable State Serialization
This document describes an alternative serialization strategy for a durable coroutine state.
The initial release of the coroutine package used a bespoke serialization format that was tightly coupled to Go’s type system and difficult to introspect. The serialized state was only valid for a particular program build (and coroutine library), so it was nearly impossible to deserialize and make sense of the state over time as changes were made to coroutines and the serialization layer.
We need a stable serialization format that supports introspection. We need a serialization format that we can evolve, such as being able to serialize multiple stacks (for if/when we support serializing the state of multiple goroutines), serialize data types from other languages (for if/when we support coroutines in different languages), serialize only the difference between the current state and previously serialized and persisted state (as a performance optimization), or serialize the state in such a way that complete or at least partial resumption is possible even when the underlying code changes (vs. the naive entire restart strategy we use today).
A serialization alternative must maintain serialization and deserialization performance and increase the size of the state relative to its in-memory form.
For these serialization problems, you’d usually reach for an off-the-shelf solution, such as protobuf. You get a small but valuable set of data types, a succinct encoding for your data, backward and forward compatibility, and a suite of tools for inspecting, transforming, and cataloging the data.
The problem is that these serialization formats were not really designed for encoding in-memory data structures. For example, they can’t natively handle references or more generally, pointers and aliasing. The expectation is that you would convert those data structures to a more amenable form to serialization (e.g., one without references, with only primitive and compound types). However, this is not possible when serializing a durable coroutine state because the user isn’t always in control of the data.
Another problem is that it’s difficult to encode pointers in general. Although it would be possible to create an approximate protobuf message for each object type in a Go program, pointers are required if references/aliases are to be preserved. You could create a message for each object on the stack or in the heap and then have your pointers be a simple reference to those objects (e.g., by object ID). However, this approach fails for a few reasons. Firstly, pointers can be to arbitrary locations in memory. They might point to totally different types of objects (Go is statically typed, but weakly so since anything can be cast to anything else via unsafe). They might point to a deeply nested object, so you must encode a root object ID and a path to the deeply nested field within that object. Secondly, pointers can point within an object. For example, two slices can point to different regions of the same array. Pointers would need to encode the fact that they point to an object but also the offset within that object. When aliasing is involved, there’s not necessarily an object that “owns” the underlying memory (i.e., includes a region that’s a superset of all aliased regions). In these cases, the underlying memory probably needs to be stored out of line. Thirdly, we’re working with a Von Neumann architecture so that pointers can point to data or instructions (i.e., functions). You would need a union to encode the two “types” of pointers. Finally, Go supports closures which are pointers to functions and data.
One solution is to use protobuf as a container but to encode the data in a way closer to its in-memory representation.
Memory looks like a contiguous array of bytes identified by a 64-bit offset (the address) to the running process. The bytes can be interpreted as either data or instructions or pointers to other parts of memory (which may contain data or instructions).
When serializing memory, there are a few considerations:
- we don’t need to serialize the entire address space. We only need a small subset of memory. The regions we’re interested in are not necessarily contiguous (we need to encode sparse memory)
- we cannot serialize memory addresses because these aren’t necessarily stable. The current approach to serializing function pointers is to encode the function name, which is stable across restarts. The name can be converted to a pointer at runtime
The solution is to do what linkers do: encode regions of memory as regions/segments and then store a list of relocations that must be applied at runtime (e.g., for a dynamic linker). When decoding this information, the segments can be loaded to arbitrary locations in memory, and then relocations can be applied to restore pointers. There are two types of relocations: a simple data relocation, where a data pointer is written to memory, and a function relocation, where a function name is resolved and its address written to memory.
message Memory {
repeated Segment segments = 1;
repeated Relocation relocations = 2;
}
message Segment {
bytes data = 1;
}
message Address {
uint32 segment_id = 1; // index into list of segments above
uint32 offset = 2;
}
message Relocation {
Address address = 1;
oneof { // points to:
Address data = 2;
uint32 function_id = 3; // index into list of functions below
}
}
repeated Function functions = 1;
message Function {
string name = 1;
}Note that this encoding scheme makes no distinction between bytes stored on the stack or in the heap; it’s all just bytes in memory.
Also, note that more succinct representations are possible. For example, you could encode an address as a uint64 (upper 32 bits encode segment ID, and lower 32 bits encode the offset).
This is probably the most contentious design choice here, but you don’t encode objects with this approach. You scan the object graph for two reasons: to find/merge the spans of memory that need to be serialized and to determine which parts of that memory are pointers (and whether they’re pointers to functions or data). You then serialize those memory regions as segments and generate the necessary relocations. Serialized objects have the same representation that they have in memory.
The upsides to this approach are that:
- serialization and deserialization is very fast
- all sorts of pointers, references, and aliasing are supported
The downsides to this approach are that:
- the serialized representation is closely tied to the program that generated it. Less so than snapshotting the memory directly since we’ve eliminated all addresses and can reload the memory into another address space. However, ABI concerns like struct padding/alignment and runtime implementation details like the layout of slices, strings, interfaces, maps, channels, etc., are preserved in the serialized representation
- the serialized state may be larger than an encoding scheme that attempts to pack all values (e.g., one that packs 64-bit integers as varints)
- to support introspection, it’s necessary to store auxiliary information to help with the interpretation of memory (see below)
To support introspection, consumers of the serialized state must be able to interpret memory.
The proposed approach is to do essentially what we’re doing in https://github.com/stealthrocket/coroutine/blob/main/types/types.go, which is to convert reflect.Type information into another form. Instead of a custom *typeinfo graph, which is serialized alongside data in memory, the types are instead encoded as protobuf messages. For example:
repeated Type types = 1;
message Type {
string name = 1; // fully-qualified name
oneof {
// TODO: store all info available on reflect.Type (e.g. https://github.com/stealthrocket/coroutine/blob/main/types/types.go#L28)
// TODO: refer to nested types by ID (index into list of types above)
}
}It’s necessary to encode not just type information but also ABI information when literal memory is involved (e.g., are pointers 32 or 64 bits? Are integers stored in little or big-endian form?). Although it’s possible to encode this information at the type level, it may be sufficient to encode higher-level information, such as the CPU architecture that the program was compiled for (or was running on at the time of serialization). The language/runtime may pad/align structs and fields in a particular way for a given arch or may do it in a type-specific manner. We need to preserve this information in some form so that consumers of the serialized state can successfully interpret memory.
How do users know which memory corresponds to which type and vice versa? Because Go is weakly typed, memory may have different interpretations. What’s needed are “roots” which let you access those interpretations of the type/data graph (see below).
The durable coroutine compiler generates a struct for each function/method (e.g. see this example). The struct contains the “instruction pointer” and all of the temporary variables used by the function:
struct {
IP int
X0 ...
X1 ...
}A stack is a collection of these “frames”, along with a “frame pointer” which tracks the position of the coroutine as stacks are rewound after a yield point. The frames themselves are stored in memory, and can be referenced by an Address (i.e. pointer).
The current serialization layer stores the stack and its frames in memory in a serializedCoroutine struct. With this approach, it’s not necessary to transform the stack after it has been deserialized; the deserialized Stack can be used directly. However, it complicates introspection.
To help with introspection, we instead encode the stack in an explicit Stack message with an explicit list of Frame's. Each frame has a data pointer which points to the frame struct, but also has the ID of the function the frame was taken from, and an ID for the type of the frame struct. The data pointer and function / type IDs are the introspection “roots” from which all other types and all other memory is reachable.
message Stack {
uint32 frame_pointer = 1;
repeated Frame frames = 2;
}
message Frame {
uint32 function_id = 1;
uint32 type_id = 2;
Address data = 3;
}There are cases where the in-memory representation of an object is not what the user wants to be serialized. For example, when serializing a database connection the user may want to serialize the connection details so that the connection can be recreated at deserialization time. Otherwise, unstable values like file descriptors may be serialized. To allow the user to control serialization for certain types, they’re able to register a serializer and deserializer for a particular type T.
The data model could be adjusted so that there’s an extra type of relocation:
repeated google.protobuf.Any objects = 1;
message Relocation {
Address address = 1;
oneof {
Address data = 2;
uint32 function_id = 3;
uint32 object_id = 4; // index into list of objects above
}
}At serialization time, the object T is converted to a proto.Message by the user’s routine. This opaque message is serialized via a google.protobuf.Any container (which also encodes a type URI) to help with introspection. All pointers/references to T are handled via the relocation facility, which adds a relocation that points to the serialized object’s ID. At deserialization time, the proto.Message is converted to a T by the user’s routine. The pointer to the deserialized T is used to resolve relocations.
In order for this to work, there must be indirection when embedding a T in an array, struct or map so that a pointer can be overridden (T must be a pointer, or interface, or a reference type like map/chan).
This serialization strategy means that it’s not possible to preserve references/aliases within a T, or outside of T that point to a region within a T. It’s assumed that there isn’t an overlap in use cases where you would want to register a custom serializer, and use cases where you would want to preserve references/aliases. It should be possible to detect and reject such cases at runtime.
Putting it all together:
message State {
Build build = 1;
Memory memory = 2;
repeated Type types = 3;
repeated Function functions = 4;
repeated google.protobuf.Any objects = 5;
Stack stack = 6;
}
message Build {
string id = 1; // github.com/stealthrocket/coroutine/pull/101
enum Arch arch = 2; // e.g. amd64, arm64
enum OS os = 3; // e.g. linux, darwin
string runtime = 4; // e.g. go1.21.4
}We could instead have repeated Stack stacks = 7; to encode the stacks of all threads/goroutines. Because data is stored in shared Memory, it may be possible to deserialize memory and stacks in a way which preserves things like shared channels, shared synchronization primitives, etc.
The proposed model translates well to lower level languages. For example, the model supports things that are not supported by or not allowed in Go but are seen in C, C++ and Rust, such as untagged unions and pointers into arbitrary data structures like maps. The function relocation strategy may need some minor modifications to get it to work more broadly, for example the ability to reference a location within a function rather than just the entry point, or the ability to reference executable memory created at runtime (e.g. JITs).
For higher level dynamic languages, it’s not clear whether the same representation Memory + types would be useful. The language may not support pointers and aliases, but may support references. In a dynamic language, values are often boxed such that the type information is stored alongside the data; storing memory and using relocations may be too heavy handed, and there may be no need to store a type graph separately when the types are present alongside the data. For cases like this, the nice thing about representing state with protobuf is that we can create new fields to hold graphs of objects rather than trying to find some common representation for state across high vs. low-level or static vs. dynamically typed languages.
The proposed scheme opens up some interesting possibilities in terms of enabling state diffs. Rather than serialize the full state each time a coroutine yields, it may be possible to encode just the changes to the state since the last serialized snapshot. The state may have been taken in a separate process, with a different OS/arch/runtime. This information is available in the serialized state, so it’s possible to determine at runtime whether a diff is possible in terms of OS/arch/runtime (and so syscall, endianness, runtime implementation details, etc) incompatibilities. Types could then be compared to determine if they’re compatible. It may then be possible to encode changes to memory since the previous snapshot; new segments, growing/shrinking segments, merging/splitting segments, new data, new relocations, etc. The stack could be scanned to determine if there’s a common prefix. The diff could include the length of the prefix, and then any new frames since.
Since https://github.com/stealthrocket/coroutine/pull/101, we err on the side of caution and include a build hash alongside the serialized state. If any part of the build changes — the user’s code, any dependencies, the runtime, the compiler, the linker, the OS/arch, etc — the hash changes and the state is rejected. In this case, the coroutine is restarted when running inside Ring.
If the build hash changes, but the OS/arch/runtime are identical, it may be possible to fully or partially resume a coroutine. You could scan the stack frames to determine the subset of types that are reachable in the type graph and subset of functions that are present on the call stack. If a type or function is changed, it may be possible to pop frames from the stack until the subset of reachable types and functions have not changed. That is, it may be possible to resume some prefix of the stack. The result is that the coroutine should either resume from where it left off, or resume from the first call to a function that changed (or that uses/accepts/returns a type that changed).
The Function and Type messages could include a hash field which can be used to quickly check whether it changed across state snapshots.