Messagepack-csharp: Support for circular references in object graph

[tsibelman]

I love this library but I tried to use it on class containing circular reference and it and it looks like it get stuck in infinite loop , but maybe I missing something ?

[neuecc]

No, many serializers does not supports circular reference, also MessagePack for C#.
In the future I may include options to support, but the possibilities are not high.

[SergeBerwert]

Support for circular reference would be highly appreciated. The Problem is we are working a lot with Objects from Entity Framework and there you often have a parent-child-parent connection. And also objects how are connected over multiple nodes. We would like to use MessagePack but for us that feature is a must.

[fanc-mso]

Hi, I second this request... Would like to serialize entities coming from an ORM for caching purposes... MsgPack offers the smallest and fastest serialization but circular references is preventing me from using it fully right now... JSON.NET can handle those with the option PreserveReferencesHandling.Objects so I'm sure there must be a similar way in MsgPack

[shamasis]

+1

We want to use it for transporting user code data in JS that we have no control over. If we have to process the variables to remove circular references before passing to msgpack, it defeats the whole purpose of reducing time complexity.

[rashidmirza]

i want to pack my data, and define what the data is, such as character, byte, etc, how can i do that using msgpackb (msgpack binary)?

[epsitec]

@neuecc any chance of getting circular references detected/handled?

[neuecc]

@epsitec Sorry, I have not yet how to handle(with keeping performance) circular reference.

[epsitec]

I can't see any solution other than having to track all references in a dictionary/look-up table (assign a unique key to every reference), and then emit already known references by using the key. Doing this in a very efficient way is not possible. So this should clearly be an opt-in mechanism.

By the way, this would not only resolve circular references, but also possibly object sharing.

[rikimaru0345]

+1 for this!

I hope this will be added eventually, we don't have many objects that require this in our networking stack, but some objects definitely need it. We were able to remove some of the circular references, but not for all objects. For some, we simply have to keep loops in the object-graph.

Maybe - to keep performance in the majority of cases - it can be activated for only some types?
When resolving a type, msgpack can set a bool to remember if that type needs to be serialized as a graph that can have circular references. (uses different serialization and deserialization methods)

[rikimaru0345]

@tsibelman @epsitec @SergeBerwert

Since there's no progress at all and this became an essential feature for one of the projects I'm working on, I wrote my own serializer.
Performance is comparable to message pack and it has quite a few extra features:
https://github.com/rikimaru0345/Ceras

At the moment I'm still working on version tolerance, but other than that it's ready.
Maybe you guys also like it or want to keep an eye on it.

[arivera12]

I just got stuck on this. 2 years from now and this haven't been resolved...

[urosberce]

@AArnott is this issue resolved in your latest merge? Thanks!

[AArnott]

No.

[urosberce]

That's a pitty, I've been testing multiple serializers and found out this one to be the best by far for my needs.....except for this - it's a dealbreaker for me:( Any hints on how this could be implemented? I am thinking about giving it a try, but I have no experience with serializers...

[AArnott]

It was just not in scope for the change I was making. But it is still a use case that interests me.

The way I was thinking of approaching the problem (and you'd be welcome to beat me to it 😄) is at the serializer/formatter level. The MessagePackReader/Writer structs are much too low-level. We should define a new object cache type. When beginning a (de)serialization and pass an instance of this to each formatter as we invoke it. The formatter, if it knows it will be serializing or deserializing an object (including a string, perhaps, but not including primitive value types like int), it should consult this cache. An example of the fields on this cache class can be found here.

When serializing objects, it will "store" the object in the cache and get an ID for the object back, which it will serialize first before writing out the object data. If upon storing the object the cache responds that the object is already present, the formatter should write _only_ the ID and not the object data.

Upon deserializing, when the ID is read, the cache should be consulted and if an object is returned for that given ID, the object data is _not_ deserialized (since it isn't there) and instead the existing object reference is used. But if no object is already in the cache then a new (uninitialized) object should be placed in the cache with the deserialized ID and then the object data should be read and used to initialize the object.

In this way, we should both optimize to avoid serializing the same object multiple times, and support circular references.

An example of such a feature is found in vs-mef.

Considering MsgPack's format spec, we'd probably need to define this object ID as part of the object itself, rather than an arbitrary leading integer to an object. That way, array or object map headers with counts will actually reflect the number of elements that follow rather than only half the elements (since the ID outside of the element would throw it off). So I'm thinking that each serialized object could include an __id__ field or something like that, which would be in addition to the object's regular fields (if serializing that object for the first time) or as the only field in the object if the ID had been seen before.

This would constitute either a breaking change to the formatter interface (which we'd want to include in the v2 breaking changes, probably) or an optional additional interface that formatters can implement to indicate that they support such a feature. At least some of the existing formatters would need to be updated to support this.

[urosberce]

Thank you Andrew for your elaboration. I agree with your idea, and will definitely give it a try sometime soon. I think it should not impact performance too badly if used only for specific types, which would be requested by user - there should be a setting to allow user to choose which types are eligible for reference checking. As I did a revision of my project, I realised that of many classes included in serialization, only a small fraction would actually need reference checking.

[msfredb7]

@AArnott

So I'm thinking that each serialized object could include an __id__ field or something like that, which would be in addition to the object's regular fields (if serializing that object for the first time) or as the only field in the object if the ID had been seen before.

Could we get the id from the object's address instead? Any reference-type object should technically have a unique one.

EDIT:
I guess a small downside would be that the ids change every time you reload / resave the data since the instances get recreated

[AArnott]

@msfredb7 I don't think we can make ID's that stay constant across serialization/deserialization runs. They will be effectively "random". But no, I wouldn't use the memory address of the object as that could change mid-serialization due to a compacting GC.

[rikimaru0345]

Edit: ah, I took too long to type :P I was talking to @msfredb7 in the text below.

I think he was only talking about the data, the binary representation of the serialized object.

There is no need to add an actual field to any class in your code!

In Ceras I solved this problem by using a dictionary. (I put in a lot of effort to investigate custom dictionary implementations as well, but it turns out the standard Dictionary<,> is already well optimized and pretty hard to beat!)

[msfredb7]

Oh right, I forgot the garbage collection did that. Good point.

Using a dictionary is indeed a good idea. Thanks for the replies :)

[AllanMichaelsen]

I'm definitely for this getting a push. I had to change away from MessagePack because of stack overflows, but I'd prefer to go back it due to the speed...

[github-actions[bot]]

This issue is stale because it has been open 90 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[jjxtra]

Need reference support so we can properly serialize and deserialize tree structures. Sticking with protobuf until it is available here.

[pCYSl5EDgo]

I'm working on this.

[pCYSl5EDgo]

I implemented the circular reference (de)serialization experimentally.

According to @AArnott 's previous comment

Reference Cache Type

List<object> is enough.
ValueTuple<object[], int> is more appropriate in order to take advantage of ArrayPool<object> to decrease memory allocation.
ValueTuple<object[], int> needs finalizer/Dispose().
ValueTuple<WeakReference[], int> is possibly more appropriate?

The cache list must not be shared among multiple (de)serialization.

MessagePack Representation

[StructLayout(LayoutKind.Explicit)]
struct Union<T> where T : class
{
    [FieldOffset(0)] uint id;
    [FieldOffset(0)] T value;
}

Circular Reference (de)serialization processes Type T value as above union struct.

| input value | messagepack kind |
| ---- | ---- |
| null | Nil |
| new object | messagepack array, map, extension type |
| object found in the cache list | unsigned integer |

Usual formatter does not serialize class object as unsigned integer.
Detecting whether the messagepack binary is unsigned integer or not is enough to represent the union.

[pCYSl5EDgo]

@AArnott

```csharp:common
[MessagePackObject(Circular = true)]
public class CR
{
[Key(0)] public CR Previous;
[Key(1)] public CR Next;
}

Provide that there was a Circular Reference class `CR`.

```csharp:v1
[MessagePackObject]
public class Hoge
{
    [Key(0)] public CR[] Array;
    [Key(1)] public CR Item;
}

And one programmer once defined Hoge class.
At that time, he/she could serilialize and deserialize Hoge properly.

csharp:v2 [MessagePackObject] public class Hoge { [Key(1)] public CR Item; }

Then, he/she changed the Hoge.
What should we do when Hoge.Item.Previous points to the element of Hoge.Array?

I think it should throw MessagePackSerializationException.

[AArnott]

We need a place to store the objects that may be referenced later (both while serializing and deserializing). Given the API we have to work with I was thinking this could be a derived type of MessagePackSerializationOptions that adds the collection that maps objects to IDs and back again. It looks like that's what you had in mind with #1065 as well, @pCYSl5EDgo. Or maybe instead of a derived class, maybe we should simply define an _interface_ so that other people's existing options-derived classes can add support without having to break their possibly public API by changing the base type of their Options class.

I'd like to see references to objects that appear earlier in the msgpack stream work without opting in a particular class type if possible. So I'd rather not see [MessagePackObject(Circular = true)] being required. Instead, opt-in should be by providing an instance of this MessagePackSerializationOptions-derived type.

In addition to circular references, this mechanism _can_ be used to 'compress' the data stream as well when serializing large structs by only serializing the struct once and then referencing it elsewhere. It doesn't produce reference equality during deserialization (since structs are values) but it would speed up deserialization and compress the stream. So while it certainly does not make sense to 'cache' int for example, we might want the ability to apply this logic to structs as well as classes. But that's a lower priority.

I feel like this feature would benefit from another feature that I've wanted for a while: support for a wrapper resolver/formatter. That is, given MessagePackFormatter<T>, I want to introduce another formatter which may get called instead but then can delegate to the 'inner' formatter. That would allow for your circular formatter to delegate deserialization to the proper formatter.

Another collection in this options-derived class might need to store what in the XmlSerializer we called 'fix-ups', which would allow one object to have one or more of its properties set "later" in deserialization once the value to be set is ready. For example if A and B reference each other, A.B will be set to B before B.A is set to A. This means B must be available in the cache before B is fully deserialized, but whose B.A property must later be set to A.

Now to @pCYSl5EDgo's scenario of referencing an object that was never deserialized because it was in part of the msgpack graph that was skipped: that's an interesting one. Your idea of throwing at that point seems reasonable. An alternative though is to index not by incrementing integers but rather by offset in the msgpack stream. It's still a unique number like an incrementing integer would be, but if the deserializer had for some reason skipped that area of the msgpack graph, it could 'rewind' back to that offset to deserialize that object.

[pCYSl5EDgo]

An alternative though is to index not by incrementing integers but rather by offset in the msgpack stream.

Very good idea!
In order to implement it, the MessagePackWriter's inner BufferWriter's BytesCommitted.BytesCommitted needs to be public.

So I'd rather not see [MessagePackObject(Circular = true)] being required. Instead, opt-in should be by providing an instance of this MessagePackSerializationOptions-derived type.

DataContactAttribute has IsReference property.
Supporting the way [MessagePackObject(Circular = true)] and [DataContract(IsReference = true)] seems reasonable.

Given the API we have to work with I was thinking this could be a derived type of MessagePackSerializationOptions that adds the collection that maps objects to IDs and back again.

Or we add the collection to the MessagePack(Writer|Reader).
I made another implementation for the Circular Reference support based on this idea.
The MessagePack(Writer|Reader) needs Dispose() method. And the users must Dispose them to avoid memory leak.
It works well for the array.

My Pull Request #1065 does not support the array well.