-
Notifications
You must be signed in to change notification settings - Fork 12
Durable State Serialization
This document describes an alternative serialization strategy for durable coroutine state.
Today (2023/11/14), we’re using a bespoke serialization format that’s tightly coupled to Go’s type system and is difficult to introspect. The serialized state is only valid for a particular build of the program (and coroutine library), so it will be near impossible to deserialize and make sense of state over time as we make changes to coroutines and the serialization layer.
We need a stable serialization format that supports introspection. We need a serialization format that we can evolve over time, 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 other 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 full or at least partial resumption is possible even when the underlying code changes (vs. the naive complete restart strategy we use today).
A serialization alternative must not sacrifice serialization and deserialization performance, nor increase the size of the state too much relative to its in-memory form.
For these sorts of serialialization problems you’d usually reach for an off-the-shelf solution, such as protobuf. You get a small but useful set of data types, a succinct encoding for your data, backwards and forwards 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 form that’s more amenable to serialization (e.g. one without references, with only primitive and compound types), however this is not possible when serializing 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 would need to encode both a root object ID as well as a path to the field that’s deeply nested 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 would also need to encode 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). The underlying memory probably needs to be stored out of line in these cases. Thirdly, we’re working with a Von Neumman architecture so pointers could point to data or to 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 that’s closer to its in-memory representation.
To the running process, memory looks like a contiguous array of bytes identified by a 64-bit offset (the address). The bytes can be interpreted as either data or instructions, or as pointers to other parts of memory (which may contain data or instructions).
When serializing memory, there are 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, which is to 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 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 with this approach you don’t encode objects. 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 so 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. is 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 way. We just need to ensure that this information is preserved 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 {
string build_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
Memory memory = 5;
repeated Type types = 6;
repeated Function functions = 7;
repeated google.protobuf.Any objects = 8;
Stack stack = 9;
}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.