7 ms·

Revisiting Apple Notes (6): The Protobuf

132 points by LaSombra 6y ago

criddell 6y ago
Whenever I read about protocol buffers, it reminds me of Microsoft's OLE libraries. IIRC, MS Word's file format is (or was) a bunch of OLE streams.
- pjmlp 6y ago
  Now it just gets serialized as a bunch of XML files. However COM is pretty much alive and is the foundation of UWP.
  - tasogare 6y ago
    Pretty much alive and UWP, chose one.
    - pjmlp 6y ago
      Another one that doesn't get that after Longhorn, its ideas were reimplemented as COM and bare bones Win32 is frozen in XP style.
    - p_l 6y ago
      Pretty much all new Windows APIs for maybe two decades now are done through COM, including DirectX.
- mumblemumble 6y ago
  You may be thinking of the Compound File Binary Format[1], which is used by OLE applications. OLE itself is an API mechanism, not a serialization format. So when an application that speaks OLE finds a chunk in a compound file that needs to be handled by another application, it would use OLE to go ask that application for help. Compound formats, in and of themselves, aren't really all that special. One could make a case that this is a common use case for fairly prosaic technologies like XML and MIME, too, for example. [1]: https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-cfb/53989ce4-7b05-4f8d-829b-d08d6148375b https://docs.microsoft.com/en-us/openspecs/windows_protocols...
  - criddell 6y ago
    Yes! That's what I was thinking of.
  - tomcam 6y ago
    Excellent and accurate description. Username totally unjustified.
- pantulis 6y ago
  I reminds me of CORBA's IDL.
  - dekhn 6y ago
    And Sun XDR.
- cryptonector 6y ago
  MS-RPC NDR IDL, ONC/RPC XDR, ASN.1, and many, many others. There aren't too many variations. You can have "self-describing" formats, which is generally short for tag-length-value (TLV) formats where the tag identifies the type of the encoded value, and the value is an octet string of the given length encoding a value of the given type tag. This includes ASN.1's BER/DER/CER. Protobufs is a TLV encoding. Or you can have a more "binary" format with no tags and lengths elided for fields with fixed-sized encodings or fields whose variable-length value encodings are self-describing as to length (e.g., various varint formats). This includes NDR, XDR, ASN.1's PER and OER. Flatbuffers is a variation on this theme. Or you can have textual encodings like XML and JSON. There's not a lot of other options. Each has its pros and cons, but, really, the packed encoding type (NDR, XDR, PER, OER, flatbuffers) is generally superior. That's because TLV schemes are redundant and therefore bloated, and because you really need to have the schema at hand (or have code generated from the schema, which is a different way of having the schema at hand) no matter what, so "self-describing" just isn't terribly useful. If you've ever seen the output of "asn1print" type programs you'll understand that you still need to know the schema in your head to understand the output, so might as well have a dumper/pretty-printer that can use a schema to really pretty-print... Textual encodings generally end up getting binary / optimized variants. E.g., XML has FastInfoSet (which is essentially a transcoding to ASN.1 with PER!). JSON has many binary formats, including several "JSONB" schemes (e.g., PostgreSQL's), and CBOR. This is because at the end of the day, textual formats are hard to parse -- they really suck. No one needs to build a SIMD parser for NDR/XDR/PER/OER/flatbuffers/CBOR/JSONB, but JSON is so hard to parse quickly that SIMD parsers for it exist. Besides the many standards, I've seen quite a few ad-hoc schemes, such as Lustre's RPC format (basically flatbuffers, but without an IDL compiler and code generator), many Perl5 DataDumper-type modules, Lisp S-expressions (the grand-daddy of data encoding formats!), and many others. In a few years we might see a new round of bad reinventions of this wheel. This happens because inexperienced people find that scheme X "sucks" or there's no tooling for scheme X in the hot new programming language yet, and rather than read the specs for X and implement their own tooling they go off and make up a new scheme as they implement it. ASN.1 gets a lot of hate, but mostly the issue is with the TLV-type encoding rules, but there are many more encoding rules than just BER (and the DER and CER variants of BER): there's binary-style non-TLV ERs like PER and OER, there's XER (XML!), JER (JSON!), and even GSER (a textual encoding just for LDAP), and anyone can create new encoding rules if they really want to. Another reason ASN.1 gets hated on is lack of tooling, but every time anyone invents a new scheme... they have to write new tooling anyways -- what a waste. Note: I'm not saying we should only be using ASN.1 or anything of the sort. I'm saying we need to really understand what came before so we don't make the same mistakes again. Most importantly we need to understand that the T and often the L in TLV are just a lame crutch that bloats data on the wire and makes it easy to hand-roll bug-riddled codecs.
sigzero 6y ago
That was a fascinating breakdown.
herodotus 6y ago
If I understand the idea of protobufs correctly, the fundamental point is to start with a serialization specification and then generate reader/writer code for that spec in the programming language of your choice. If that is correct, it is very similar to the idea of pattern matching in functional programming compilers. See for example: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.257.6166&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25... The fundamental idea is that when you have a function definition like f(<pattern>) <- ..... instead of a runtime binary match(<pattern>,<expression>), the compiler generates a function (lets call it fmp) such that fmp(<expression>) = match(<pattern>,<expression>) for any <expression> Ever since I first used pattern matching compilation when I worked on the Hope compiler, I always though that the idea of precompiling static function parameters (or slowly changing ones) was a very under-used idea.
- cryptonector 6y ago
  Protobufs is just yet another structured data serialization format. There's nothing special to it other than "it's not one of the others". It's a bad reinvention of the wheel though. That's why there's new and better things like flatbuffers. The most important thing to take away from protobufs is that in a field full of literature and prior art, one should not ignore it.
  - mumblemumble 6y ago
    For the curious, here's my hot take on the details: Protocol buffers, being older, are far and away the more widely supported format. If you're looking for something like a wire format for RPC, or usability from basically any common language is important to you, protobuf will be the path of least resistance. However, there are some design warts to work around. The most notable one (IMO) is that varints make dealing with numbers a rather delicate subject. Flatbuffers are similar, but made some design decisions allow for a zero-copy implementation. This can be good for performance. Overall, flatbuffers have always struck me as being promising, but language and tooling support isn't nearly as comprehensive, which has always kept me from giving them a serious try at work.
jeffbee 6y ago
The author says "field 2 is clearly a message type" but does not support this deduction. Why did they conclude the second field was a message type rather than just a string? Strings and messages are isomorphic on the wire.
- scottlamb 6y ago
  > Why did they conclude the second field was a message type rather than just a string? Strings and messages are isomorphic on the wire. Presumably its contents. The included protobuf-inspector output shows it's a valid submessage, including length-delimited fields having valid lengths. A two-deep string matches the expected title. The tag numbers are also in order, which adds plausibility. (Tags aren't required to be in a particular order but IIRC the stock implementations in most languages output them in ascending tag number order for known fields.) This is pretty strong evidence. If it's not strong enough for you, reverse engineering might not be your thing. That's okay. Nit: message is isomorphic with bytes, not string. string has the additional restriction of being valid UTF-8. I didn't check, but I wouldn't be surprised if field 2 is not a valid string.
  - jeffbee 6y ago
    Right but the fact that a bytes can be decoded as a message doesn't mean that's how it's declared in the proto. Sometimes a message will have `bytes opaquemsg = 42;` when an application wants to proxy through a nested protocol message, but without caring about the contents. What I'm getting at is the article has arrived at one of many possible proto files that could be the one the app actually uses.
    - scottlamb 6y ago
      They're reverse engineering the program from its effects (the files it reads and writes). It's not possible to exactly duplicate the original program's source code in that manner, nor is it necessary. When there are two indistinguishable approaches—in this case representing something as a message in the .proto vs representing it as bytes and later decoding it separately as a message—it makes more sense to choose the simpler way.
dunham 6y ago
If the author is here, thanks for writing this up. I did something similar years ago, but I neglected to write it up. My process was essentially the same as yours, although I used some thrown-together python code to analyze the protobuf data. After I finished, I found out that the raw .proto files were embedded in the web app, which would have have saved a bit of time, but also taken away some of the fun. So if you want the official schema, you can look there, but it might not be legal to redistribute as-is. Also, if anyone is poking around with protobuf forensics with ObjectiveC code, I once threw together a script to reverse engineer protobuf definitions from ObjectiveC executables. I haven't tested it recently, but it should work for ObjetiveC code generated by protoc (i.e. if _PBDataWriterWriteInt shows up in nm output): https://gist.github.com/dunhamsteve/224e26a7f56689c33cea4f0fa7632c3d https://gist.github.com/dunhamsteve/224e26a7f56689c33cea4f0f...
- alynn 6y ago
  I never would have thought to check the webapp. Grepping for loadProto or .proto" does it. Thanks for sharing.
  - jeremiahlee 6y ago
    Specifically, loadProto in https://www.icloud.com/applications/notes3/2017Project42/en-us/main.js https://www.icloud.com/applications/notes3/2017Project42/en-... looks promising.
- thesnarky1 6y ago
  I was not here, but wanted to create an account to thank you for the work you did years ago. Your work was really critical to my understanding of tables and I wish I had found it sooner! I keep meaning to go back and add in the drawing code, but since I can export the fallback image directly, I just use that for now in the parser. Glad you liked the article and really glad to see you specifically comment on it. Thank you!
  - dunham 6y ago
    That project sent me down a rabbit hole learning about CRDTs. I'd love to learn more about the history of the Notes implementation. Who did it? What background did they have? Their "topotext" construct is similar to RGA, but different from any paper that I can find. I think it was invented by the developers. The drawing thing I did because it was interesting - the kind of data that would be fun to have to play around with character / shape recognition. I export it as SVG for my "notes2html". But since my output doesn't take into account the pen angle, pressure, and velocity, it isn't going to be as good as Apple's PNG. The actual raw data for the stroke is a series of PKCompressedStrokePoint structures that contain timestamp, position, radius, aspectRatio, edgeWidth, force, azimuth (scaled radians), altitude, and opacity. I had to look at disassembled libraries to figure that part out. Peeking at PencilKit again with Hopper makes me think that the structure layout may have changed since I wrote that code.
oezi 6y ago
Did I miss it or did the author also discuss the strokes created with the Apple pencil?
- thesnarky1 6y ago
  You did not miss it. There is some other, helpful, prior work in that subject by another author: https://github.com/dunhamsteve/notesutils/blob/master/notes.md https://github.com/dunhamsteve/notesutils/blob/master/notes....
PostThisTooFast 6y ago
My favorite part of protobufs is how Google, their inventor, hasn't bothered to create a generator for Google's own language: Kotlin. Apparently Google doesn't think Android developers want to use protobufs. Oh well.
lostdog 6y ago
It's been interesting to see how many places protocol buffers are now used by. I'm guessing a large fraction of companies use them internally without being too public about it, which is unfortunate because I've often shied away from using them as a Google-only thing. It's remarkable that nothing better has replaced them, since they're a little old and crufty, but I guess most of the web startup community was happy enough with JSON. Plus, it's still hard to tell if proto2 or proto3 is the right version to build on long term.
- halflings 6y ago
  The biggest issue in proto3 is the missing "has_<field>" functions (e.g no distinction between a field's default value, and a special <missing> state). There are suggested workarounds for this, but I'd just stick with proto2 for the time being as proto3 is still WIP.
mevorah 6y ago
One question I’ve had about Protobufs is, what about function definitions? If Protobufs handle my objects, do I have to use a separate tool for my API?

132 points by LaSombra 6y ago

Whenever I read about protocol buffers, it reminds me of Microsoft's OLE libraries. IIRC, MS Word's file format is (or was) a bunch of OLE streams.

pjmlp 6y ago
Now it just gets serialized as a bunch of XML files. However COM is pretty much alive and is the foundation of UWP.
- tasogare 6y ago
  Pretty much alive and UWP, chose one.
  - pjmlp 6y ago
    Another one that doesn't get that after Longhorn, its ideas were reimplemented as COM and bare bones Win32 is frozen in XP style.
  - p_l 6y ago
    Pretty much all new Windows APIs for maybe two decades now are done through COM, including DirectX.
mumblemumble 6y ago
You may be thinking of the Compound File Binary Format[1], which is used by OLE applications. OLE itself is an API mechanism, not a serialization format. So when an application that speaks OLE finds a chunk in a compound file that needs to be handled by another application, it would use OLE to go ask that application for help. Compound formats, in and of themselves, aren't really all that special. One could make a case that this is a common use case for fairly prosaic technologies like XML and MIME, too, for example. [1]: https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-cfb/53989ce4-7b05-4f8d-829b-d08d6148375b https://docs.microsoft.com/en-us/openspecs/windows_protocols...
- criddell 6y ago
  Yes! That's what I was thinking of.
- tomcam 6y ago
  Excellent and accurate description. Username totally unjustified.
pantulis 6y ago
I reminds me of CORBA's IDL.
- dekhn 6y ago
  And Sun XDR.
cryptonector 6y ago
MS-RPC NDR IDL, ONC/RPC XDR, ASN.1, and many, many others. There aren't too many variations. You can have "self-describing" formats, which is generally short for tag-length-value (TLV) formats where the tag identifies the type of the encoded value, and the value is an octet string of the given length encoding a value of the given type tag. This includes ASN.1's BER/DER/CER. Protobufs is a TLV encoding. Or you can have a more "binary" format with no tags and lengths elided for fields with fixed-sized encodings or fields whose variable-length value encodings are self-describing as to length (e.g., various varint formats). This includes NDR, XDR, ASN.1's PER and OER. Flatbuffers is a variation on this theme. Or you can have textual encodings like XML and JSON. There's not a lot of other options. Each has its pros and cons, but, really, the packed encoding type (NDR, XDR, PER, OER, flatbuffers) is generally superior. That's because TLV schemes are redundant and therefore bloated, and because you really need to have the schema at hand (or have code generated from the schema, which is a different way of having the schema at hand) no matter what, so "self-describing" just isn't terribly useful. If you've ever seen the output of "asn1print" type programs you'll understand that you still need to know the schema in your head to understand the output, so might as well have a dumper/pretty-printer that can use a schema to really pretty-print... Textual encodings generally end up getting binary / optimized variants. E.g., XML has FastInfoSet (which is essentially a transcoding to ASN.1 with PER!). JSON has many binary formats, including several "JSONB" schemes (e.g., PostgreSQL's), and CBOR. This is because at the end of the day, textual formats are hard to parse -- they really suck. No one needs to build a SIMD parser for NDR/XDR/PER/OER/flatbuffers/CBOR/JSONB, but JSON is so hard to parse quickly that SIMD parsers for it exist. Besides the many standards, I've seen quite a few ad-hoc schemes, such as Lustre's RPC format (basically flatbuffers, but without an IDL compiler and code generator), many Perl5 DataDumper-type modules, Lisp S-expressions (the grand-daddy of data encoding formats!), and many others. In a few years we might see a new round of bad reinventions of this wheel. This happens because inexperienced people find that scheme X "sucks" or there's no tooling for scheme X in the hot new programming language yet, and rather than read the specs for X and implement their own tooling they go off and make up a new scheme as they implement it. ASN.1 gets a lot of hate, but mostly the issue is with the TLV-type encoding rules, but there are many more encoding rules than just BER (and the DER and CER variants of BER): there's binary-style non-TLV ERs like PER and OER, there's XER (XML!), JER (JSON!), and even GSER (a textual encoding just for LDAP), and anyone can create new encoding rules if they really want to. Another reason ASN.1 gets hated on is lack of tooling, but every time anyone invents a new scheme... they have to write new tooling anyways -- what a waste. Note: I'm not saying we should only be using ASN.1 or anything of the sort. I'm saying we need to really understand what came before so we don't make the same mistakes again. Most importantly we need to understand that the T and often the L in TLV are just a lame crutch that bloats data on the wire and makes it easy to hand-roll bug-riddled codecs.

sigzero 6y ago

That was a fascinating breakdown.

herodotus 6y ago

If I understand the idea of protobufs correctly, the fundamental point is to start with a serialization specification and then generate reader/writer code for that spec in the programming language of your choice. If that is correct, it is very similar to the idea of pattern matching in functional programming compilers. See for example: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.257.6166&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25... The fundamental idea is that when you have a function definition like f(<pattern>) <- ..... instead of a runtime binary match(<pattern>,<expression>), the compiler generates a function (lets call it fmp) such that fmp(<expression>) = match(<pattern>,<expression>) for any <expression> Ever since I first used pattern matching compilation when I worked on the Hope compiler, I always though that the idea of precompiling static function parameters (or slowly changing ones) was a very under-used idea.

cryptonector 6y ago
Protobufs is just yet another structured data serialization format. There's nothing special to it other than "it's not one of the others". It's a bad reinvention of the wheel though. That's why there's new and better things like flatbuffers. The most important thing to take away from protobufs is that in a field full of literature and prior art, one should not ignore it.
- mumblemumble 6y ago
  For the curious, here's my hot take on the details: Protocol buffers, being older, are far and away the more widely supported format. If you're looking for something like a wire format for RPC, or usability from basically any common language is important to you, protobuf will be the path of least resistance. However, there are some design warts to work around. The most notable one (IMO) is that varints make dealing with numbers a rather delicate subject. Flatbuffers are similar, but made some design decisions allow for a zero-copy implementation. This can be good for performance. Overall, flatbuffers have always struck me as being promising, but language and tooling support isn't nearly as comprehensive, which has always kept me from giving them a serious try at work.

jeffbee 6y ago

The author says "field 2 is clearly a message type" but does not support this deduction. Why did they conclude the second field was a message type rather than just a string? Strings and messages are isomorphic on the wire.

scottlamb 6y ago
> Why did they conclude the second field was a message type rather than just a string? Strings and messages are isomorphic on the wire. Presumably its contents. The included protobuf-inspector output shows it's a valid submessage, including length-delimited fields having valid lengths. A two-deep string matches the expected title. The tag numbers are also in order, which adds plausibility. (Tags aren't required to be in a particular order but IIRC the stock implementations in most languages output them in ascending tag number order for known fields.) This is pretty strong evidence. If it's not strong enough for you, reverse engineering might not be your thing. That's okay. Nit: message is isomorphic with bytes, not string. string has the additional restriction of being valid UTF-8. I didn't check, but I wouldn't be surprised if field 2 is not a valid string.
- jeffbee 6y ago
  Right but the fact that a bytes can be decoded as a message doesn't mean that's how it's declared in the proto. Sometimes a message will have `bytes opaquemsg = 42;` when an application wants to proxy through a nested protocol message, but without caring about the contents. What I'm getting at is the article has arrived at one of many possible proto files that could be the one the app actually uses.
  - scottlamb 6y ago
    They're reverse engineering the program from its effects (the files it reads and writes). It's not possible to exactly duplicate the original program's source code in that manner, nor is it necessary. When there are two indistinguishable approaches—in this case representing something as a message in the .proto vs representing it as bytes and later decoding it separately as a message—it makes more sense to choose the simpler way.

dunham 6y ago

If the author is here, thanks for writing this up. I did something similar years ago, but I neglected to write it up. My process was essentially the same as yours, although I used some thrown-together python code to analyze the protobuf data. After I finished, I found out that the raw .proto files were embedded in the web app, which would have have saved a bit of time, but also taken away some of the fun. So if you want the official schema, you can look there, but it might not be legal to redistribute as-is. Also, if anyone is poking around with protobuf forensics with ObjectiveC code, I once threw together a script to reverse engineer protobuf definitions from ObjectiveC executables. I haven't tested it recently, but it should work for ObjetiveC code generated by protoc (i.e. if _PBDataWriterWriteInt shows up in nm output): https://gist.github.com/dunhamsteve/224e26a7f56689c33cea4f0fa7632c3d https://gist.github.com/dunhamsteve/224e26a7f56689c33cea4f0f...

alynn 6y ago
I never would have thought to check the webapp. Grepping for loadProto or .proto" does it. Thanks for sharing.
- jeremiahlee 6y ago
  Specifically, loadProto in https://www.icloud.com/applications/notes3/2017Project42/en-us/main.js https://www.icloud.com/applications/notes3/2017Project42/en-... looks promising.
thesnarky1 6y ago
I was not here, but wanted to create an account to thank you for the work you did years ago. Your work was really critical to my understanding of tables and I wish I had found it sooner! I keep meaning to go back and add in the drawing code, but since I can export the fallback image directly, I just use that for now in the parser. Glad you liked the article and really glad to see you specifically comment on it. Thank you!
- dunham 6y ago
  That project sent me down a rabbit hole learning about CRDTs. I'd love to learn more about the history of the Notes implementation. Who did it? What background did they have? Their "topotext" construct is similar to RGA, but different from any paper that I can find. I think it was invented by the developers. The drawing thing I did because it was interesting - the kind of data that would be fun to have to play around with character / shape recognition. I export it as SVG for my "notes2html". But since my output doesn't take into account the pen angle, pressure, and velocity, it isn't going to be as good as Apple's PNG. The actual raw data for the stroke is a series of PKCompressedStrokePoint structures that contain timestamp, position, radius, aspectRatio, edgeWidth, force, azimuth (scaled radians), altitude, and opacity. I had to look at disassembled libraries to figure that part out. Peeking at PencilKit again with Hopper makes me think that the structure layout may have changed since I wrote that code.

oezi 6y ago

Did I miss it or did the author also discuss the strokes created with the Apple pencil?

thesnarky1 6y ago
You did not miss it. There is some other, helpful, prior work in that subject by another author: https://github.com/dunhamsteve/notesutils/blob/master/notes.md https://github.com/dunhamsteve/notesutils/blob/master/notes....

PostThisTooFast 6y ago

My favorite part of protobufs is how Google, their inventor, hasn't bothered to create a generator for Google's own language: Kotlin. Apparently Google doesn't think Android developers want to use protobufs. Oh well.

lostdog 6y ago

It's been interesting to see how many places protocol buffers are now used by. I'm guessing a large fraction of companies use them internally without being too public about it, which is unfortunate because I've often shied away from using them as a Google-only thing. It's remarkable that nothing better has replaced them, since they're a little old and crufty, but I guess most of the web startup community was happy enough with JSON. Plus, it's still hard to tell if proto2 or proto3 is the right version to build on long term.

halflings 6y ago
The biggest issue in proto3 is the missing "has_<field>" functions (e.g no distinction between a field's default value, and a special <missing> state). There are suggested workarounds for this, but I'd just stick with proto2 for the time being as proto3 is still WIP.

mevorah 6y ago

One question I’ve had about Protobufs is, what about function definitions? If Protobufs handle my objects, do I have to use a separate tool for my API?