5 ms·

Stepping up an abstraction level in this discussion...does anyone have any insight into _why_ an encoding format wouldn't want to have length prefixes standardi

by saghm 3y ago

Stepping up an abstraction level in this discussion...does anyone have any insight into _why_ an encoding format wouldn't want to have length prefixes standardized as part of the expected header of a message? From what I can tell, there isn't a strong argument against it; assuming you're comfortable with limiting messages to under 2^32 bits, prefixing an unsigned length should only take four bytes per message, which doesn't seem like it would ever be a bottleneck, and it allows the receiving side of a message to know up front exactly how much memory to allocate, and it makes it much easier to write correct parsing code that also handles edge cases (e.g. making it obvious to explicitly handle a message that's much larger than the amount of memory you're willing to allocate). The fact that there are formats out there that don't mandate length prefixing makes me think I might be missing something though, so I'd be interested to hear counterarguments.

lifthrasiir 3y ago
The length should be known in advance in order to be written, so the message cannot be incrementally written. You need more complex framing scheme like Consistent Overhead Byte Stuffing for that. And many applications do want a variable number of length bytes because i) 4 bytes is actually too long for short messages and ii) some message can exceed 2^32 bytes. Not to say the generic varint encoding is good for this purpose, though [1]. [1] If you ever have to design one, make sure that reading the first byte is enough to determine the number of subsequent length bytes.
- saghm 3y ago
  > 4 bytes is actually too long for short messages Would it ever be an actual bottleneck though? If it's not actually impeding throughput, I feel like this is more of an aesthetic argument than a technical one, and one where I'd happily sacrifice aesthetics to make the code simpler. > some message can exceed 2^32 bytes Fair enough, but that just makes the question "would 8 bytes per message ever actually be a bottleneck", which I'm still not convinced would ever be the case
  - lifthrasiir 3y ago
    I agree that 4 byte overhead in a single item is not a big deal even when the item itself is short. But if you have multiple heterogeneous items, it becomes worthwhile to set an upper bound for the relative ratio of overhead over data. (SQLite, for example, makes extensive use of varints for this reason [1].) I personally think a single byte overhead is worthy for sub-100-byte data, while larger ones should use a fixed size prefix because the overhead is no longer significant. [1] https://www.sqlite.org/fileformat.html#record_format https://www.sqlite.org/fileformat.html#record_format
  - catiopatio 3y ago
    I work on an embedded OS where our IPC buffer is only about 140 bytes. Anything more requires multiple IPCs, with lots of expensive context switches. Wasting even one precious byte on a pointless header would absolutely be an issue in this environment.
    - saghm 3y ago
      That makes sense. I've probably been thinking more about remote network protocols, where the time it takes for a message to reach its destination will be so large that the overhead for a few extra bytes per message is negligible; for a protocol used solely within a given local system, there would be a much lower threshold of acceptable overhead.
mirekrusin 3y ago
You may want to have yield/streaming senantics where length is not know in advance.
gizmo686 3y ago
In general, the issue is with composition. Your full message is someone else field. Having a header that only occurs in message initial position breaks this. For protobuffs in particular, I have no idea. If you look at the encoding [0], you will see that the notion of submessages are explicitly supported. However, submessages are preceeded by a length field, which makes the lack of a length field at the start of the top-level message a rather glaring omission. The best arguement I can see is that submessages use a tag-length-value scheme instead of length-value-tag. This is because in general protobufs use a tag-value scheme, and certain types have the begining of the value be a length field. This means that to have a consistent and composable format, you would need to message length to start at the second byte of the message. Still, that would probably be good enough for 90% of the instances where people want to apply a length header. [0] https://protobuf.dev/programming-guides/encoding/ https://protobuf.dev/programming-guides/encoding/
- lifthrasiir 3y ago
  Protobuf is sort of unique in the serialization format that it can be indefinitely extended in principle. (BSON is close, but has an explicit document size prefix.) For example, given the following definition: message Foo { repeated string bar = 1; } Any repetition of `09 03 41 42 43` (a value "ABC" for the field #1), including an empty sequence, is a valid protobuf message. In the other words there is no explicit encoding for "this is a message"! Submessages have to be delimited because otherwise they wouldn't be distinguishable from the parent message.
  - DougBTX 3y ago
    This is an interesting design decision between protobuf and cap’n proto, one has “repeated field of type X” while the other has “field of type list of X”. So one allows adding a repeated/optional field to a schema without re-encoding any messages, while the other supports “field of type list of lists of X” etc.
    - kentonv 3y ago
      > So one allows adding a repeated/optional field to a schema without re-encoding any messages, Hmm don't they both allow that? Or am I misunderstanding what you mean here? I guess the interesting (though only occasionally useful) thing about protobuf is if you concatenate two serialized messages of the same type and then parse the result, each repeated field in the first message will be concatenated with the same field in the second message.
throwaway8163 3y ago
Some compression formats such as gzip support encoding streams. This is useful when you don't know the size in advance, or if you compress on demand and want the receiver to start reading while the sender is still compressing. One example could be a web service where you request dynamic content (like a huge CSV file). The client can start downloading earlier, and the server doesn't need to create a temporary file. The web service will stream the results directly and encoding it in chunks.
- lifthrasiir 3y ago
  > Some compression formats such as gzip support encoding streams. More accurately speaking gzip (and many other compressed file formats) has the file size information, but that information should (or can, for others) be appended after the data. Protobuf doesn't have any such information, so a better analogue would be the DEFLATE compressed bytestream format.
  - mxmlnkn 3y ago
    Gzip in particular has more something akin to a size checksum appended at the end, i.e., decompressed size modulo 2^32. This is not very helpful, especially as the maximum compression ratio is ~1032, it means that this "size" could already overflow for a gzip file that is only 4 MiB in compressed size. https://stackoverflow.com/a/69353889/2191065 https://stackoverflow.com/a/69353889/2191065
jchw 3y ago
Among other things, length prefixing is annoying when streaming; it basically requires you to buffer the entire message, even if you could more efficiently stream it in chunks, because you need to know the length ahead of time, which you may very well not.
- cjbgkagh 3y ago
  If you have random access, you could leave some space and then go back and fill in the actual length value. Would work better with fixed size integer as you know ahead of time how much space to leave.
  - iainmerrick 3y ago
    If you’re streaming, you generally don’t have random access.
    - cjbgkagh 3y ago
      Somehow I missed the ‘streaming’ part… my bad
  - ahoka 3y ago
    Just leave some empty electromagnetic waves in the cables before your message, got it.
- Ginden 3y ago
  > length prefixing is annoying when streaming This can be avoided by magic number. If length is 0, then message length isn't known.
  - jchw 3y ago
    That does leave one problem: you still need a way to segment your stream. Most length-prefixed framing schemes do not have any way to segment the stream other than the length prefix. What you wind up wanting is something like chunked encoding. (Also, using zero as a sentinel is not necessarily a good idea, since it makes zero length messages more difficult. I'd go with -1 or ~0 instead.)
bloak 3y ago
Streaming has already been mentioned. Efficiency might be another argument. If your messages are typically being sent through a channel that already has a way of indicating the end of the message then having to express the length inside the message as well would be a useless overhead in bytes sent and code complexity.
- saghm 3y ago
  This assumes that only messages from controlled sources will be received though, right? If you're receiving messages over a TCP socket or something similar, that seems like a potentially flawed assumption; I'd think anything parsing messages coming from the network should be written in a way that explicitly accounts for malicious messages coming from the other side of a connection. EDIT: I'm also still not any more convinced that four bytes per message would ever be a bottleneck for any general purpose protocol, but I'd be curious to hear of a case where that would actually be an issue.
  - bloak 3y ago
    > This assumes that only messages from controlled sources will be received though, right? I don't think so. The question of whether you trust the length indication to be correct (you almost certainly shouldn't) seems to me to be independent of whether the length indication comes from inside the message or from some outside wrapper.
    - saghm 3y ago
      I might have misunderstood what you were suggesting; from rereading, it sounds like you're suggesting to rely on something like the end of a TCP packet rather than having an explicit length. If this is what you mean, my concern would be that requiring a protocol to map 1:1 to the transmission protocol's packets (or a similar construct) can be limiting; it would require all messages to fit in a single buffer, which could prevent it from working with clients or servers configured to use a different length and might make it difficult to use with other transmission protocols. My question in the beginning of this thread was intended to be specifically about general purpose formats like protobuf; I think relying on the semantics of TCP or something like that might be a good choose for a bespoke protocol, but it doesn't seem like a great idea for something expected to be used in a wide variety of cases.
catiopatio 3y ago
Framing is a distinct concern from payload serialization. Most protocols and serialization formats already define a form of length-prefixed framing; requiring that a protobuf payload also carry such a header would simply be a waste of bytes. Additionally, it ensures that protobuf can be serialized and streamed without first computing the payload length, which would require serializing the entire message first.
chrisdew 3y ago
Protobuf over UDP can use the UDP payload length. Likewise for the many variants of self-sychronising DLE framing (DLE,STX..DLE,ETX) used on serial links. A varint length field prepended to protobuf messages (sent over a reliable transport, such as TCP) seems sane.
throw0101c 3y ago
> and it allows the receiving side of a message to know up front exactly how much memory to allocate Not necessarily. Can you really trust the length given from a message? Couldn't a malicious sender put some fake length to fool around with memory allocation? I was under the impression that something like this caused Heartbleed (to use one example): * https://en.wikipedia.org/wiki/Heartbleed https://en.wikipedia.org/wiki/Heartbleed
- simiones 3y ago
  Heartbleed was caused by allowing the user to specify the length of the response, not that of a request. When receiving a message, if the user gives you a wrong length, you'll simply fail in parsing their message. Of course, it is up to you to protect against DOS attacks (like someone sending you a 5 TB message, or at least a message that claims it is 5TB) - but that is necessary regardless of whether they tell you the size ahead of time or not. With heartbleed, a user sent a message saying "please send me a 5MB large hearbeat message", and OpenSSL would send a 5MB re-used buffer, of which only the first few bytes were overwritten with the hearbeat content. The rest of the bytes were whatever remained out of a previous use of the buffer, which could be negotiated keys etc.
- saghm 3y ago
  I don't see how sending a bad length could cause a memory issue in this case; if a message has a length that's much longer than expected, the receiving side could just discard any future messages from that destination (or even immediately close the connection). If the message is much shorter than the data received, the bytes following it would be treated as the start of a new message, and the same logic would apply.
kentonv 3y ago
I'd say the main arguments are: 1. Many transports that you might use to transmit a Protobuf already have their own length tracking, making a length prefix redundant. E.g. HTTP has Content-Length. Having two lengths feels wrong and forces you to decide what to do if they don't agree. 2. As others note, a length prefix makes it infeasible to serialize incrementally, since computing the serialized size requires most of the work of actually serializing it. With that said, TBH the decision was probably not carefully considered, it just evolved that way and the protocol was in wide use in Google before anyone could really change their mind. In practice, this did turn out to be a frequent source of confusion for users of the library, who often expected that the parser would just know where to stop parsing without them telling it explicitly. Especially when people used the functions that parse from an input stream of some sort, it surprised them that the parser would always consume the entire input rather than stopping at the end of the message. People would write two messages into a file and then find when they went to parse it, only one message would come out, with some weird combination of the data from the two inputs. Based on that experience, Cap'n Proto chose to go the other way, and define a message format that is explicitly self-delimiting, so the parser does in fact know where the message ends. I think this has proven to be the right choice in practice. (I maintained protobuf for a while and created Cap'n Proto.)
- marcosdumay 3y ago
  About #2, it seems that every time someone creates some format with a prefix serialized size, the next required step is creating a chunked format without that prefix. What IMO is perfectly ok. Chunking things is a perfectly fine way to allow for incremental communication. Just do it up-front, and you will not need the complexity of 2 different sizing formats.
  - kentonv 3y ago
    In truth, the vast majority of protobuf users do not construct messages in a streaming way anyway; they have the whole message tree in memory upfront and the serialize it all at once. "Streaming" in gRPC (or Cap'n Proto) involves sending multiple messages. I think this is probably the right approach. Otherwise it seems very hard to use a message as its streaming in as you can never know which fields are not present vs. just haven't arrived yet. But representing a stream as multiple messages leaves it up to the application to decide what it wants in each chunk, which makes sense.
crabbone 3y ago
This is nothing general. Just someone who created Protobuf "forgot" to do it. There was no reason not to do it given how everything else is encoded in Protobuf. My guess is that Protobuf was first implemented then designed. And by the time it was designed, the designer felt too lazy to do anything about the top-level message's length. There are plenty of other technical bloopers that indicate lack of up-front design, so this wouldn't be very unlikely.

by saghm 3y ago

lifthrasiir 3y ago

The length should be known in advance in order to be written, so the message cannot be incrementally written. You need more complex framing scheme like Consistent Overhead Byte Stuffing for that. And many applications do want a variable number of length bytes because i) 4 bytes is actually too long for short messages and ii) some message can exceed 2^32 bytes. Not to say the generic varint encoding is good for this purpose, though [1]. [1] If you ever have to design one, make sure that reading the first byte is enough to determine the number of subsequent length bytes.

saghm 3y ago
> 4 bytes is actually too long for short messages Would it ever be an actual bottleneck though? If it's not actually impeding throughput, I feel like this is more of an aesthetic argument than a technical one, and one where I'd happily sacrifice aesthetics to make the code simpler. > some message can exceed 2^32 bytes Fair enough, but that just makes the question "would 8 bytes per message ever actually be a bottleneck", which I'm still not convinced would ever be the case
- lifthrasiir 3y ago
  I agree that 4 byte overhead in a single item is not a big deal even when the item itself is short. But if you have multiple heterogeneous items, it becomes worthwhile to set an upper bound for the relative ratio of overhead over data. (SQLite, for example, makes extensive use of varints for this reason [1].) I personally think a single byte overhead is worthy for sub-100-byte data, while larger ones should use a fixed size prefix because the overhead is no longer significant. [1] https://www.sqlite.org/fileformat.html#record_format https://www.sqlite.org/fileformat.html#record_format
- catiopatio 3y ago
  I work on an embedded OS where our IPC buffer is only about 140 bytes. Anything more requires multiple IPCs, with lots of expensive context switches. Wasting even one precious byte on a pointless header would absolutely be an issue in this environment.
  - saghm 3y ago
    That makes sense. I've probably been thinking more about remote network protocols, where the time it takes for a message to reach its destination will be so large that the overhead for a few extra bytes per message is negligible; for a protocol used solely within a given local system, there would be a much lower threshold of acceptable overhead.

mirekrusin 3y ago

You may want to have yield/streaming senantics where length is not know in advance.

gizmo686 3y ago

In general, the issue is with composition. Your full message is someone else field. Having a header that only occurs in message initial position breaks this. For protobuffs in particular, I have no idea. If you look at the encoding [0], you will see that the notion of submessages are explicitly supported. However, submessages are preceeded by a length field, which makes the lack of a length field at the start of the top-level message a rather glaring omission. The best arguement I can see is that submessages use a tag-length-value scheme instead of length-value-tag. This is because in general protobufs use a tag-value scheme, and certain types have the begining of the value be a length field. This means that to have a consistent and composable format, you would need to message length to start at the second byte of the message. Still, that would probably be good enough for 90% of the instances where people want to apply a length header. [0] https://protobuf.dev/programming-guides/encoding/ https://protobuf.dev/programming-guides/encoding/

lifthrasiir 3y ago
Protobuf is sort of unique in the serialization format that it can be indefinitely extended in principle. (BSON is close, but has an explicit document size prefix.) For example, given the following definition: message Foo { repeated string bar = 1; } Any repetition of `09 03 41 42 43` (a value "ABC" for the field #1), including an empty sequence, is a valid protobuf message. In the other words there is no explicit encoding for "this is a message"! Submessages have to be delimited because otherwise they wouldn't be distinguishable from the parent message.
- DougBTX 3y ago
  This is an interesting design decision between protobuf and cap’n proto, one has “repeated field of type X” while the other has “field of type list of X”. So one allows adding a repeated/optional field to a schema without re-encoding any messages, while the other supports “field of type list of lists of X” etc.
  - kentonv 3y ago
    > So one allows adding a repeated/optional field to a schema without re-encoding any messages, Hmm don't they both allow that? Or am I misunderstanding what you mean here? I guess the interesting (though only occasionally useful) thing about protobuf is if you concatenate two serialized messages of the same type and then parse the result, each repeated field in the first message will be concatenated with the same field in the second message.

throwaway8163 3y ago

Some compression formats such as gzip support encoding streams. This is useful when you don't know the size in advance, or if you compress on demand and want the receiver to start reading while the sender is still compressing. One example could be a web service where you request dynamic content (like a huge CSV file). The client can start downloading earlier, and the server doesn't need to create a temporary file. The web service will stream the results directly and encoding it in chunks.

lifthrasiir 3y ago
> Some compression formats such as gzip support encoding streams. More accurately speaking gzip (and many other compressed file formats) has the file size information, but that information should (or can, for others) be appended after the data. Protobuf doesn't have any such information, so a better analogue would be the DEFLATE compressed bytestream format.
- mxmlnkn 3y ago
  Gzip in particular has more something akin to a size checksum appended at the end, i.e., decompressed size modulo 2^32. This is not very helpful, especially as the maximum compression ratio is ~1032, it means that this "size" could already overflow for a gzip file that is only 4 MiB in compressed size. https://stackoverflow.com/a/69353889/2191065 https://stackoverflow.com/a/69353889/2191065

jchw 3y ago

Among other things, length prefixing is annoying when streaming; it basically requires you to buffer the entire message, even if you could more efficiently stream it in chunks, because you need to know the length ahead of time, which you may very well not.

cjbgkagh 3y ago
If you have random access, you could leave some space and then go back and fill in the actual length value. Would work better with fixed size integer as you know ahead of time how much space to leave.
- iainmerrick 3y ago
  If you’re streaming, you generally don’t have random access.
  - cjbgkagh 3y ago
    Somehow I missed the ‘streaming’ part… my bad
- ahoka 3y ago
  Just leave some empty electromagnetic waves in the cables before your message, got it.
Ginden 3y ago
> length prefixing is annoying when streaming This can be avoided by magic number. If length is 0, then message length isn't known.
- jchw 3y ago
  That does leave one problem: you still need a way to segment your stream. Most length-prefixed framing schemes do not have any way to segment the stream other than the length prefix. What you wind up wanting is something like chunked encoding. (Also, using zero as a sentinel is not necessarily a good idea, since it makes zero length messages more difficult. I'd go with -1 or ~0 instead.)

bloak 3y ago

Streaming has already been mentioned. Efficiency might be another argument. If your messages are typically being sent through a channel that already has a way of indicating the end of the message then having to express the length inside the message as well would be a useless overhead in bytes sent and code complexity.

saghm 3y ago
This assumes that only messages from controlled sources will be received though, right? If you're receiving messages over a TCP socket or something similar, that seems like a potentially flawed assumption; I'd think anything parsing messages coming from the network should be written in a way that explicitly accounts for malicious messages coming from the other side of a connection. EDIT: I'm also still not any more convinced that four bytes per message would ever be a bottleneck for any general purpose protocol, but I'd be curious to hear of a case where that would actually be an issue.
- bloak 3y ago
  > This assumes that only messages from controlled sources will be received though, right? I don't think so. The question of whether you trust the length indication to be correct (you almost certainly shouldn't) seems to me to be independent of whether the length indication comes from inside the message or from some outside wrapper.
  - saghm 3y ago
    I might have misunderstood what you were suggesting; from rereading, it sounds like you're suggesting to rely on something like the end of a TCP packet rather than having an explicit length. If this is what you mean, my concern would be that requiring a protocol to map 1:1 to the transmission protocol's packets (or a similar construct) can be limiting; it would require all messages to fit in a single buffer, which could prevent it from working with clients or servers configured to use a different length and might make it difficult to use with other transmission protocols. My question in the beginning of this thread was intended to be specifically about general purpose formats like protobuf; I think relying on the semantics of TCP or something like that might be a good choose for a bespoke protocol, but it doesn't seem like a great idea for something expected to be used in a wide variety of cases.

catiopatio 3y ago

Framing is a distinct concern from payload serialization. Most protocols and serialization formats already define a form of length-prefixed framing; requiring that a protobuf payload also carry such a header would simply be a waste of bytes. Additionally, it ensures that protobuf can be serialized and streamed without first computing the payload length, which would require serializing the entire message first.

chrisdew 3y ago

Protobuf over UDP can use the UDP payload length. Likewise for the many variants of self-sychronising DLE framing (DLE,STX..DLE,ETX) used on serial links. A varint length field prepended to protobuf messages (sent over a reliable transport, such as TCP) seems sane.

throw0101c 3y ago

> and it allows the receiving side of a message to know up front exactly how much memory to allocate Not necessarily. Can you really trust the length given from a message? Couldn't a malicious sender put some fake length to fool around with memory allocation? I was under the impression that something like this caused Heartbleed (to use one example): * https://en.wikipedia.org/wiki/Heartbleed https://en.wikipedia.org/wiki/Heartbleed

simiones 3y ago
Heartbleed was caused by allowing the user to specify the length of the response, not that of a request. When receiving a message, if the user gives you a wrong length, you'll simply fail in parsing their message. Of course, it is up to you to protect against DOS attacks (like someone sending you a 5 TB message, or at least a message that claims it is 5TB) - but that is necessary regardless of whether they tell you the size ahead of time or not. With heartbleed, a user sent a message saying "please send me a 5MB large hearbeat message", and OpenSSL would send a 5MB re-used buffer, of which only the first few bytes were overwritten with the hearbeat content. The rest of the bytes were whatever remained out of a previous use of the buffer, which could be negotiated keys etc.
saghm 3y ago
I don't see how sending a bad length could cause a memory issue in this case; if a message has a length that's much longer than expected, the receiving side could just discard any future messages from that destination (or even immediately close the connection). If the message is much shorter than the data received, the bytes following it would be treated as the start of a new message, and the same logic would apply.

kentonv 3y ago

I'd say the main arguments are: 1. Many transports that you might use to transmit a Protobuf already have their own length tracking, making a length prefix redundant. E.g. HTTP has Content-Length. Having two lengths feels wrong and forces you to decide what to do if they don't agree. 2. As others note, a length prefix makes it infeasible to serialize incrementally, since computing the serialized size requires most of the work of actually serializing it. With that said, TBH the decision was probably not carefully considered, it just evolved that way and the protocol was in wide use in Google before anyone could really change their mind. In practice, this did turn out to be a frequent source of confusion for users of the library, who often expected that the parser would just know where to stop parsing without them telling it explicitly. Especially when people used the functions that parse from an input stream of some sort, it surprised them that the parser would always consume the entire input rather than stopping at the end of the message. People would write two messages into a file and then find when they went to parse it, only one message would come out, with some weird combination of the data from the two inputs. Based on that experience, Cap'n Proto chose to go the other way, and define a message format that is explicitly self-delimiting, so the parser does in fact know where the message ends. I think this has proven to be the right choice in practice. (I maintained protobuf for a while and created Cap'n Proto.)

marcosdumay 3y ago
About #2, it seems that every time someone creates some format with a prefix serialized size, the next required step is creating a chunked format without that prefix. What IMO is perfectly ok. Chunking things is a perfectly fine way to allow for incremental communication. Just do it up-front, and you will not need the complexity of 2 different sizing formats.
- kentonv 3y ago
  In truth, the vast majority of protobuf users do not construct messages in a streaming way anyway; they have the whole message tree in memory upfront and the serialize it all at once. "Streaming" in gRPC (or Cap'n Proto) involves sending multiple messages. I think this is probably the right approach. Otherwise it seems very hard to use a message as its streaming in as you can never know which fields are not present vs. just haven't arrived yet. But representing a stream as multiple messages leaves it up to the application to decide what it wants in each chunk, which makes sense.

crabbone 3y ago

This is nothing general. Just someone who created Protobuf "forgot" to do it. There was no reason not to do it given how everything else is encoded in Protobuf. My guess is that Protobuf was first implemented then designed. And by the time it was designed, the designer felt too lazy to do anything about the top-level message's length. There are plenty of other technical bloopers that indicate lack of up-front design, so this wouldn't be very unlikely.