Hacker News Reader

Congrats :) you perfectly re-created the actual Protobuf stream format. [1]

https://protobuf.dev/reference/java/api-docs/com/google/prot...

> didn’t find any standard for separating protobuf messages

The fact that protobufs are not self-delimiting is an endless source of frustration, but I know of 2 standards for doing this:

- SerializeDelimited* is part of the protobuf library: https://github.com/protocolbuffers/protobuf/blob/main/src/go...

- Riegeli is "a file format for storing a sequence of string records, typically serialized protocol buffers. It supports dense compression, fast decoding, seeking, detection and optional skipping of data corruption, filtering of proto message fields for even faster decoding, and parallel encoding": https://github.com/google/riegeli

https://msgpack.org/

Huh? This is an entirely different serialization format altogether.

Just stick this in front of your frames:

    81 A2 70 62 C6 <32 bit be length> <protobuf data>

You got me. What's that format / magic number? At first I thought it was the zlib header for incompressible data, but that's not right. Is that just the MAC address of some NIC you own?

It's msgpack:

0x8n A map containing "n" key/value pairs -> 0x81 introduces a single key/value pair

b101XXXXX : A string where XXXXX is the string length -> 0xA2 introudces a 2 byte string

0xC6 followed by a 32-bit value N introduces an array of bytes of size N

0x70 0x62 "pb"

So it roughly corresponds to

  {"pb": <protobuf data> }

Poster is being cute.

Create a MessagePack message containing a byte array, put the protobuf in that. Of course, the enterprise solution would be to hex encode it and put it in a CDATA section in an XML document.

Doesn't have a Brainf*k implementation, disqualified.

/s

Prepending the message with a delimiter (size varint) is pretty common, even part of the reference Java implementation: https://protobuf.dev/reference/java/api-docs/com/google/prot...

> “I wanted to future proof this without wasting 64 goddamn bytes in front of each message”

64 bytes would be a 512-bit integer. That seems like excessive future proofing for the length of any message that would be transmitted before the Sun runs out of fuel.

Fun fact: just 103 more bits and it would be enough to address every point in the observable universe distinguishible by Planck length [1].

Not my thought originally, I heard it from somewhere else but can't find it. Possibly from Foone Turing.

[1] https://www.wolframalpha.com/input?i=log2%28+volume+of+unive...

Tbf though, I'm sure the number of cat pics floating about the internet dwarfs this number, so it depends on the data I suppose.

Plus rather simple things like pi could create rather a long message.

I suppose pi has a cheat code: if you made the largest possible circle in the universe you only need enough digits to distinguish points on its circumference that are a Planck distance apart. Then you can either ignore any digits beyond that or even simply make them up, as there would be no way to measure the difference.

I wonder whether there’s an upper bound on the largest number that can be expressed in the observable universe.

All digital representations rely on discrete states in hardware, and there’s a finite number of those in the observable universe, so there should a finite maximum number for computers.

Just as a quick example of why it's a bit absurd - I name that number you just defined $zeta$. Now I make $zeta'$ = zeta^zeta. Or whatever manipulation you like. Adding constraints is addressed in the link.

And zeta' can not be expressed by any state of the visible Universe.

The GP question was not about encoding, and thus is not subject to compression. The largest number we can measure of anything is a pretty well defined concept.

Depends on what you mean by “expressed”. E.g. you can represent a busy beaver that expresses the length of its output.

We don’t know if there is only a finite number of discrete states in the observable universe. The Planck length is not a discretization.

> Depends on what you mean by “expressed”

I'll have to think about this. I want a very physical meaning of the term using values rather than references. One where the largest number that can be expressed using up/down fingers with two hands is 1024, not a sign language reference to a googolplex.

all expression is reference

You might enjoy:

"Measuring the intelligence of an idealized mechanical knowing agent" https://philpapers.org/archive/ALEMTI-2.pdf

"Intuitive Ordinal Notations" https://github.com/semitrivial/IONs

If you are OK with a sum constants times powers of two, would you be ok with other hyperoperations on two?

https://en.m.wikipedia.org/wiki/Hyperoperation

I wonder if it would be helpful to restrict the question a bit, maybe something like: what is the largest number for which the number, and also all smaller magnitude integers, can be expressed.

A related point of fact is protobufs are limited to 2G anyway. You wouldn’t need 64 bits. Anything bigger than about 100MB is dangerously large anyway.

You can also define a wrapper message with a single repeated field. The resulting encoding would be `varint(field id * 8 + 1) varint(length)` plus the actual message, so it can be also easily generated from and parsed back into a raw byte sequence without protoc.

This approach is problematic because, as far as I know, all implementations expect to deserialize from a complete buffer -- at least all official implementations. That means the entire "stream" would have to be buffered in memory.

You can, of course, simply read field by field, but few libraries expose the ability to do that simply. And the naive operation then becomes quite problematic indeed.

This is the same as it's implemented in ClickHouse. In fact, it has two formats: `Protobuf` (with length-delimited messages) and `ProtobufSingle` (no delimiters, but only a single message can be read/written). And it is fairly common:

https://clickhouse.com/docs/en/sql-reference/formats#protobu...

Conforming implementations will fail to interoperate with their “protobuf” serialization; it’s absolutely incorrect for them to call their length-prefixed framing protobuf.

From my experimentation with writing my own push notification client for android, this is exactly what Google does with their push messages.

If it was for fun and to learn how, that's fair. But are you aware of https://ntfy.sh?

Ah I was just experimenting with what was possible, essentially I wanted to intercept notifications from an app to use for an automation.

Can you share more?

You've basically got two ways of handling this:

Using a delimiter to mark end of packet. For text protocols we usually use "\n" to be the delimiter. This usually requires some escaping in the packet to make it unambiguous. Two standard protocols for this are SLIP and HDLC.

Length encoding - like what you did.

The downside of the delimiter approach is that it changes the length of the packet - when you are escaping one byte becomes two and that's sometimes a pain if you're doing it in place in memory (less of a problem if you're streaming byte by byte). The big advantage is that it allows for resynchronisation - if you lose a single byte from your stream, or your length byte ever gets corrupted then you're permanently out of sync - the receiver will never again know where the start or end of a packet is. With the delimiter approach, you just lose one packet. So if you're ever doing this for a UART or network stream or something, always do the delimiter approach!

> So if you're ever doing this for a UART or network stream or something, always do the delimiter approach!

I'm confused. I mean for UART, sure. But network streams is usually sent over a protocol that recovers lost data. Am I reckless for sending length-prefixed data chunks over TCP?

No, you're right that this approach is ok for TCP streams. I shouldn't have thrown that in there without clarification that I meant something more generic.

I actually use SLIP for packetisation over TCP anyway, because then syncing for any other logging or diagnostic thing that joins halfway through is easy. Basically I find it to just be a more robust system.

"I actually use SLIP for packetisation over TCP anyway"

Whoa, that's an acronym I haven't heard in a long time.

SLIP/TCP seems redundant. Your serial encoding IP then sending it over TCP/IP? Is this a tunnel?

TCP is a stream with no packet boundaries. If you want to separate that stream into a series of messages then you need to do packetisation. The SLIP delimiter approach is a pretty good one.

You're right that it was originally for segmenting a serial link to send separate IP packets (so you could theoretically have SLIP over TCP over IP over SLIP), but it works just as well in other contexts.

A TCP network stream will guarantee no missed bytes via behind-the-scenes retransmissions, no?

Yes, that's why it's very common to send length-prefixed messages over TCP.

(The TCP checksum is very weak at only 16 bits, but there's usually another layer like TLS that gives you integrity for free so nobody cares)

> isn’t a standard in that protobuf doesn’t care

Shove protobuf into Something Else that does packet delimitation for you. I'm fond of SQLite for offline cases as a richer alternative to sstable.

Oh who hasn’t written some LengthPrefixedProtobufRecord class. I get why Rachel would be annoyed if someone claimed it was protobuf, but even then it’s like, 8 seconds in xxd to see what’s going on.

I shudder to think how well shit must be going for this to merit a Rachel post.

Why not just define a higher level proto that contains all possible (maybe repeated) protos you might want to include? Then if one of the included protos is not present, the higher level proto will efficiently encode that, and nothing gets broken.

If you want to future proof it you need to version it. It sounds like you're trying to pack many things into a single file, so having the first few bits of the file represent a version allows you to use fixed length integers without fear of them being too small (in the future). You can reserve the "last" version for varint if you truly need it.

In general, I find adding versions to things allows for much more graceful future redesigns and that is, IMO, invaluable if you're concerned about longevity and are not confident in your ability to perfectly design something for the indefinite future.

YAGNI

The idea is so simple that any change would be a misfeature.

I'm a big YAGNI proponent but format version numbers are not something I would dare to YAGNI.

Even if it's varint separated messages?

You stick a magic number and a version number at the top of the file and call it done. It’s trivial and buys you a great deal.

The magic means it’s possible to identify the file type. Maybe you’ll add a tool later that operates on multiple types of files.

The version means you can evolve the contents in non-backwards-compatible ways, while maintaining the ability to read/parse the old version.

It’s a pain in the ass to add a magic or version number later; there’s a reason why nearly every file format on the planet has both.

> nearly every file format on the planet

XML

JSON

YML

TOML

  <?xml version="1.1" encoding="UTF-8" ?>

The others are serialization formats, like protobuf — they’re not file formats.

XML prolog is optional.

> they're not file formats

Brb, gonna delete all my files without file formats

If you prefer to ship fragile binary file formats for no reason other than finding it too onerous to define something as trivial as an eight-byte file header, that’s silly, but nobody is going to stop you.

If you’re going to use text-based serialization formats as your justification for the decision, however, I’d suggest you look into all the fun bugs, security issues, and weird edges cases that arise from parsers having to make a best guess at character encoding and file format when all you have to work with is the file extension, maybe a byte order mark, and heuristics over the file contents.

I don't see the point. As soon as you bump the version number, old versions of the software will refuse to read newer files. So you might as well use a new format and file extension for the newer files. Of course the new software will read both formats.

The way protobufs handles versioning (old software ignores unknown fields) is far superior and realistically everyone uses 64 bit fixed length sizes everywhere

Do you mean 64 bits I assume?

Because that's all you would need.

Your length-prefixed message frames represent a distinct serialization scheme that provides external framing for embedded messages; it’s a standalone format, and you can use whatever frame header you want without worrying about collision.

The only issue is if you were to ship a “protobuf” library that emits/consumes your (very much not protobuf) framing format.

Also, a 64 bit frame length would only be 8 bytes, not 64 :-)