38
$\begingroup$

I am a software engineer and after a discussion with some colleagues, I realized I do not have a good grasp of the concept serialization. As I understand, serialization is the process of converting some entity, such as an object in OOP, to a sequence of bytes, so that the said entity can be stored or transmitted for subsequent access (the process of "deserialization").

The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes? (Of course they are, because they are stored in registers, memory, disk, etc.)

So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? What intricacies have I missed?

$\endgroup$
  • 21
    $\begingroup$ Serialization can be trivial for contiguous objects. When the object value is represented as a pointer graph, things become much more tricky, especially if said graph has loops. $\endgroup$ – chi Mar 27 '17 at 9:33
  • 1
    $\begingroup$ @chi: Your first sentence is a little misleading given contiguity is irrelevant. You might have a graph that happens to be continuous in memory and that still wouldn't help you with serializing it since you still have to (a) detect that it indeed happens to be contiguous, and (b) fix up the pointers inside. I'd just say the second part of what you said. $\endgroup$ – Mehrdad Mar 27 '17 at 12:11
  • $\begingroup$ @Mehrdad I agree my comment is not completely precise, for the reasons you mention. Perhaps pointer-free / pointer-using is a better distinction (even if not completely accurate, either) $\endgroup$ – chi Mar 27 '17 at 12:34
  • 7
    $\begingroup$ You also have to worry about representation on hardware. If I serialize an int 4 bytes on my PDP-11 and then try and read those same four bytes into memory on my macbook they are not the same number (because of Endianes). So you have to normalize the data to a representation you can de-code (this is serialization). How you serialize the data also has tradeoffs speed/flexibility human/machine readable. $\endgroup$ – Martin York Mar 28 '17 at 19:27
  • $\begingroup$ What if you're using Entity Framework with many deeply connected navigation properties? In one case, you might want to serialize a navigation property, but in another leave it null (because you will re-load that actual object from the database based on the ID that is in your serialized parent object). This is just one example. There are many. $\endgroup$ – ErikE Mar 28 '17 at 21:48
42
$\begingroup$

If you have a complicated data structure, its representation in memory might ordinarily be scattered throughout memory. (Think of a binary tree, for instance.)

In contrast, when you want to write it to disk, you probably want to have a representation as a (hopefully short) sequence of contiguous bytes. That's what serialization does for you.

$\endgroup$
29
$\begingroup$

The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes? (Of course they are, because they are stored in registers, memory, disk, etc.)

So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? What intricacies have I missed?

Consider an object graph in C with nodes defined as this:

struct Node {
    struct Node* parent;
    struct Node* someChild;
    struct Node* anotherLink;

    int value;
    char* label;
};

//

struct Node nodes[10] = {0};
nodes[5].parent = nodes[0];
nodes[0].someChild = calloc( 1, sizeof(struct Node) );
nodes[5].anotherLink = nodes[3];
for( size_t i = 3; i < 7; i++ ) {
    nodes[i].anotherLink = calloc( 1, sizeof(struct Node) );
}

At runtime the entire object Node graph would be scattered around the memory space, and the same node could be pointed-to from many different Nodes.

You can't simply dump memory to a file/stream/disk and call it serialized because the pointer values (which are memory addresses) couldn't be de-serialized (because those memory locations might already be occupied when you load the dump back into memory). Another problem with simply dumping memory is that you'll end up storing all kinds of irrelevant data and unused space - on x86 a process has up to 4GiB of memory space, and an OS or MMU only has a general idea of what memory is actually meaningful or not (based on the memory pages assigned to a process), so having Notepad.exe dump 4GB of raw bytes to my disk whenever I want to save a text file seems a bit wasteful.

Another problem is with versioning: what happens if you serialize your Node graph on day 1, then on day 2 you add another field to Node (such as another pointer value, or a primitive value), then on day 3 you de-serialize your file from day 1?

You also have to consider other things, like endianness. One of the main reasons why MacOS and IBM/Windows/PC files were incompatible with each other in the 1980s and 1990s despite ostensibly being made by the same programs (Word, Photoshop, etc) was because on x86/PC multi-byte integer values were saved in little-endian order, but big-endian order on the Mac - and the software wasn't built with cross-platform portability in mind. Nowadays things are better thanks to improved developer education and our increasingly heterogeneous computing world.

$\endgroup$
  • 2
    $\begingroup$ Dumping everything in the process memory space would also be horrible for security reasons. A program night have in memory both 1) some public data and 2) password, secret nonce or private key. When serializing the former, one does not want to reveal any information about the latter. $\endgroup$ – chi Mar 27 '17 at 9:31
  • 8
    $\begingroup$ A very interesting note on this topic: Why are the Microsoft Office file formats so complicated? $\endgroup$ – striking Mar 28 '17 at 23:30
17
$\begingroup$

The tricky is actually already described in the word itself: "serialization".

The question is basically: how can I represent an arbitrarily complex interconnected cyclic directed graph of arbitrarily complex objects as a linear sequence of bytes?

Think about it: a linear sequence is kind-of like a degenerate directed graph where every vertex has exactly one incoming and outgoing edge (except the "first vertex" which has no incoming edge and the "last vertex" which has no outgoing edge). And a byte is obviously less complex than an object.

So, it seems reasonable that as we go from an arbitrarily complex graph to a much more restricted "graph" (actually just a list) and from arbitrarily complex objects to simple bytes, information will be lost, if we do this naively and don't encode the "extraneous" information in some way. And that's exactly what serialization does: encode the complex information into a simple linear format.

If you are familiar with YAML, you might have a look at the anchor and alias features which allow you to represent the idea that "the same object may appear in different places" in a serialization.

E.g. if you have following graph:

A → B → D
↓       ↑
C ––––––+

You could represent that as a list of linear paths in YAML like this:

- [&A A, B, &D D]
- [*A, C, *D]

You could also represent it as an adjacency list, or an adjacency matrix, or as a pair whose first element is a set of nodes and whose second element is a set of pairs of nodes, but in all of those representations, you need to have a way of referring backwards and forwards to existing nodes, i.e. pointers, which you generally don't have in a file or a network stream. All you have, in the end, is bytes.

(Which BTW means that the above YAML text file itself also needs to be "serialized", that's what the various character encodings and Unicode transfer formats are for … it's not strictly "serialization", just encoding, because the text file is already a serial / linear list of codepoints, but you can see some similarities.)

$\endgroup$
14
$\begingroup$

The other answers already address complex object graphs, but it's worth pointing out that serializing primitives is also non-trivial.

Using C primitive type names for concreteness, consider:

  1. I serialize a long. Some time later I de-serialize it, but ... on a different platform, and now long is int64_t rather than the int32_t I stored. So, I need to either be very careful about the exact size of every type I store, or store some metadata describing the type and size of every field.

    Note that this different platform could just be the same platform after a future recompile.

  2. I serialize an int32_t. Some time later I de-serialize it, but ... on a different platform, and now the value is corrupt. Sadly I saved the value on a big-endian platform, and loaded it on a little-endian one. Now I need to establish a convention for my format, or add more metadata describing the endiannness of each file/stream/whatever. And, of course, actually perform the appropriate conversions.

  3. I serialize a string. This time one platform uses char and UTF-8, and one wchar_t and UTF-16.

So, I'd claim that reasonable-quality serialization isn't trivial even for primitives in contiguous memory. There are lots of encoding decisions you need to either document, or describe with inline metadata.

Object graphs add another layer of complexity on top of that.

$\endgroup$
6
$\begingroup$

There are multiple aspects:

Readability by the same program

Your program has stored your data somehow as bytes in the memory. But it might be arbitrarily scattered across different registers, with pointers going back and forth between its smaller pieces [edit: As commented, physically the data is more likely in main memory than a data register, but that does not take away the pointer problem]. Just think of a linked integer list. Each list element might be stored at a totally different place and all that holds the list together are the pointers from one element to the next. If you were to take that data as is and tried to copy it on another machine running the same program, you would run into problems:

  1. First and foremost, the register adresses your data is stored in on one machine might already be used for something completely different on another machine (someone is browsing stack exchange and the browser ate all that memory already). So if you simply override those registers, good bye browser. Thus, you would need to re-arrange the pointers in the structure to fit the addresses you have free on the second machine. The same problem arises when you try to re-load the data on the same machine at a later time.
  2. What if some external component points into your structure or your structure has pointers to external data, you did not transmit? Segfaults everywhere! This would become a debugging nightmare.

Readability by another program

Let's say you manage to allocate just the right addresses on another machine, for your data to fit into. If your data is processed by a separate program on that machine (different language), that program might have a totally different basic understanding of data. Say you have C++ objects with pointers, but your target language does not even support pointers on that level. Again, you end up with no clean way to address that data in the second program. You end up with some binary data in memory, but then, you need to write extra code that wraps around the data and somehow translates it into something that your target language can work with. Sounds like deserialization, just that your starting point now is strange object scattered around your main memory, that is different for different source languages, instead of a file with a well-defined structure. Same thing, of course, if you try to directly interpret the binary file that includes pointers - you need to write parsers for every possible way another language might represent data in-memory.

Readability by a human

Two of the most prominent modern serialization languages for web based serialization (xml, json) are easily understandable by a human. Instead of a binary pile of goo, the actual structure and content of data is clear even without a program to read the data. This has multiple advantages:

  • easier debugging -> if there is a problem in your service pipeline, you just look at the data that comes out of one service and check if it makes sense (as a first step); you also directly see if the data looks like you think it should, when you write your export interface in the first place.
  • archivability: if you have your data as a pure binary goo pile, and you loose the program that is meant to interpret it, you loose the data (or you will have to spent quite some time to actually find something in there); if your serialized data is human readible, you can easily use it as an archive or program your own importer for a new program
  • the declarative nature of the data serialized in such a way, also means, it is totally independent of the computer system and its hardware; you could load it into a totally differently constructed quantum computer or infect an alien A.I. with alternative facts so it accidentally flies into the next sun (Emmerich if you read this, a reference would be nice, if you use that idea for the next 4th July movie)
$\endgroup$
  • $\begingroup$ My data's probably mostly in main memory, not in registers. If my data fits in registers, serialization is barely even an issue. I think you've misunderstood what a register is. $\endgroup$ – David Richerby Mar 27 '17 at 18:55
  • $\begingroup$ Indeed, I used the term register too loosely here. But the main point is that your data may contain pointers to the address space to identify its own components or to refer to other data. It does not matter if it is a physical register or a virtual address in main memory. $\endgroup$ – Frank Hopkins Mar 27 '17 at 22:22
  • $\begingroup$ No, you used the term "register" completely incorrectly. The things you are calling registers are in a completely different part of the memory hierarchy to actual registers. $\endgroup$ – David Richerby Mar 28 '17 at 8:07
6
$\begingroup$

In addition to what the other answers have said:

Sometimes you want to serialise things that are not pure data.

For instance, think of a file handle or a connection to a server. Even though the file handle or socket is an int, this number is meaningless the next time the program runs. To properly recreate objects that contain handles to such things, you need to reopen files and recreate connections, and decide what to do if this fails.

Many languages these days support storing anonymous functions within objects, for instance an onBlah() handler in Javascript. This is challenging because such code can contain references to additional pieces of data which in turn need to be serialised. (And then there's the issue of serialising code in a cross-platform way, which is obviously easier for interpreted languages.) Still, even if only a subset of the language can be supported, it can still prove quite useful. Not many serialisation mechanisms attempt to serialise code, but see serialize-javascript.

In cases where you want to serialise an object but it contains something that isn't supported by your serialisation mechanism, you need to rewrite the code in a way that works around this. For instance, you can use enums in place of anonymous functions when there are a finite number of possible functions.

Often you want serialised data to be terse.

If you're sending data over the network or even storing it on disk, it can be important to keep the size small. One of the easiest ways to achieve this is to throw away information that can be rebuilt (for instance, discarding caches, hash tables, and alternate representations of the same data).

Of course, the programmer has to manually select what is to be saved and what is to be discarded, and make sure things are rebuilt when the object is recreated.

Think about the act of saving a game. Objects may contain lots of pointers to graphics data, sound data, and other objects. But most of this stuff can be loaded from the game data files and doesn't need to be stored in a save file. Discarding it can be laborious so little things are often left in. I've hex-edited some save files in my time and discovered data that was clearly redundant, like textual item descriptions.

Sometimes space isn't important but readability is—in which case you might use an ASCII format (possibly JSON or XML) instead.

$\endgroup$
3
$\begingroup$

Let's define what a sequence of bytes actually is. A sequence of bytes consists of an non-negative integer called the length and some arbitrary function/correspondence that maps any integer i that is at least zero and less than length to a byte value (an integer from 0 to 255).

Many of the objects you deal with in a typical program are not in that form, because the objects are actually made up of many different memory allocations that are in different places in RAM, and could be separated from eachother by millions of bytes of stuff you don't care about. Just think of a basic linked list: each node in the list is a sequence of bytes, yes, but the nodes are in lots of different locations in your computer's memory, and they are connected with pointers. Or just think of a simple struct that has a pointer to a variable-length string.

The reason why we want to serialize data structures into a sequence of bytes is usually because we want to store them on disk or send them to a different system (e.g. over the network). If you try to store a pointer on disk or send it to a different system, it will be pretty useless because the program reading that pointer will have a different set of memory areas available.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure that's a great definition of a sequence. Most people would define a sequence to be, well, a sequence: a line of things one after another. By your definition, int seq(int i) { if (0 <= i < length) return i+1; else return -1;} is a sequence. So how am I going to store that on disk? $\endgroup$ – David Richerby Mar 27 '17 at 18:53
  • 1
    $\begingroup$ If the length is 4, I store a four byte file with contents: 1, 2, 3, 4. $\endgroup$ – David Grayson Mar 27 '17 at 20:01
  • 1
    $\begingroup$ @DavidRicherby His definition is equivalent to "a line of things one after another", it's just a more mathematical and precise definition than your intuitive definition. Note that your function is not a sequence because to have a sequence you need that function and another integer which is called the length. $\endgroup$ – immibis Mar 27 '17 at 22:57
  • 1
    $\begingroup$ @FreshAir My point is that the sequence is 1, 2, 3, 4, 5. The thing that I wrote down is a function. A function is not a sequence. $\endgroup$ – David Richerby Mar 28 '17 at 8:12
  • 1
    $\begingroup$ A simple way to write a function to disk is the one I already proposed: for every possible input, store the output. I think maybe you still don't get it but I'm not sure what to say. Did you know that in embedded systems it is common to convert expensive functions like sin into a lookup table, which is a sequence of numbers? Did you know your function is the same as this one for the inputs we care about? int seq(n) { int a[] = [1, 2, 3, 4]; return a[n]; } Why exactly do you say that my four-byte file is an inadequate representation? $\endgroup$ – David Grayson Mar 28 '17 at 13:50
2
$\begingroup$

The intricacies reflect the intricacies of data and objects themselves. These objects can be real world objects, or computer only objects. The answer is in the name. Serialisation is the linear representation of multi dimensional objects. There are many issues other than fragmented RAM.

If you can flatten 12 five dimensional arrays and some program code, serialisation also allows you to transfer an entire computer program (and data) between machines. Distributed computing protocols such as RMI /CORBA use serialisation extensively to transfer data and programs.

Consider your phone bill. It might be a single object, consisting of all your calls (list of strings), amount to pay (integer) and country. Or your phone bill could be inside out from the above and consist of discrete itemised phone calls linked to your name. Each flattened out will look different, reflect how your phone company wrote that version of it's software and the reason that object oriented databases never took off.

Some parts of a structure might not even be in memory at all. If you have lazy caching, some parts of an object might only be referenced to a disk file, and are only loaded when that part of that particular object is accessed. This is common in serious persistence frameworks. BLOBs are a good example. Getty Images might store a huge multi megabyte picture of Fidel Castro and some meta data like the image's name, rental cost and the image itself. You might not want to load the 200 MB picture into memory every time, unless you actually look at him. Serialised, the entire file would require over 200MB of storage.

Some objects can't even be serialised at all. In the land of Java programming, you can have a programming object representing the graphics screen or a physical serial port. There's no real concept of serialising either of them. How would you send your port to someone else over a network?

Some things like passwords /encryption keys shouldn't be stored or transmitted. They can be tagged as such (volatile /transient etc) and the serialisation process will skip them but they can live in RAM. Omitting these tags is how encryption keys inadvertently get sent /stored in plain ASCII.

This and the other answers is why it's complicated.

$\endgroup$
2
$\begingroup$

The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes?

Yes, they are. The problem here is the layout of those bytes. A simple int can be 2, 4 or 8 bits long. It can be in big or small endian. It can be unsigned, signed with 1's complement or even in some super exotic bit coding like negabinary.

If you just dump the int binarily from memory, and call it "serialized", you have to attach pretty much entire computer, operating system and your program for it to be deserializable. Or at least, a precise description of them.

So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? What intricacies have I missed?

Serialization of a simple object is pretty much writing it down according to some rules. Those rules are plenty and not always obvious. Eg an xs:integer in XML is written in base-10. Not base-16, not base-9, but 10. It's not a hidden assumption, it's an actual rule. And such rules make serialization a serialization. Because, pretty much, there are no rules about bit layout of your program in memory.

That was just a tip of an iceberg. Let's take an example of a sequence of those simplest primitives: a C struct. You could think that

struct {
short width;
short height;
long count;
}

has a defined memory layout on a given computer+OS? Well, it does not. Depending on current #pragma pack setting, the compiler will pad the fields. On default settings of 32-bit compilation, both shorts will be padded to 4 bytes so the struct will actually have 3 fields of 4 bytes in memory. So now, you not only have to specify that short is 16 bits long, it's an integer, written in 1's complement negative, big or little endian. You also have to write down the structure packing setting your program was compiled with.

That's pretty much what serialization is about: making a set of rules, and sticking to them.

Those rules can be then expanded to accept even more sophisticated structures (like variable length lists or nonlinear data), added features like human readability, versioning, backward compatibility and error correction, etc. But even writing down a single int is already complicated enough if you only want to make sure you'll be able to read it back reliably.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.