Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nobody ever got fired for using a struct

feldera.com

Post reply on HN
Print view View original

131–140 of 140 posts

Re: Nobody ever got fired for using a struct

#131

Post by amluto »

vlovich123 wrote: post #58
amluto wrote: post #36

There are many systems that take a native data structure in your favorite language and, using some sort of reflection, makes an on-disk structure that resembles it. Python pickles and Java’s serialization system are infamous examples, and rkyv is a less alarming one. I am quite strongly of the opinion that one should essentially never use these for anything that needs to work well at any scale. If you need an industr…

Protobufs definitely doesn’t solve the problems described. Capnproto may solve it but I’m not 100% sure. JSON/XML/ASN.1 definitely don’t. It’s like you listed a bunch of serialization technologies without grokking the problem outlined in the post doesn’t have much to do with rkyv itself.

Even completely ignoring the issues of language-centric vs data-format-centric serializers, your list is missing two very notable entries from my list: Arrow and Parquet. Both of them go to quite some lengths to efficiently handle optional/missing data efficiently. (I haven’t personally used either one for large data sets, but I have played with them. I think you’ll find that Arrow IPC / Feather (why can’t they just pick one name?) has excellent performance for the actual serialization and deserialization part as long as you do several rows at a time, but Parquet might win for table scans depending on the underlying storage medium.). Both of them are, quite specifically, the result of years of research into storing longish arrays of wide structures with potentially complex shapes and lots of missing data efficiently. (Logical arrays. They’re really struct-of-arrays formats, and I personally have a use case I kind of want to use Feather for except that Feather is not well tuned for emitting one row at a time.)

Re: Nobody ever got fired for using a struct

#132

Post by gz09 »

SigmundA wrote: post #110
gz09 wrote: post #26

Earlier quoted context omitted.

Absolutely, it's a very common technique :) I wasn't sure about writing the article in the first place because of that, but I figured it may be interesting anyways because I was kind of happy with how simple it was to write this optimization when it was all done (when I started out with the task I wasn't sure if it would be hard because of how our code is structured, the libraries we use etc.). I originally posted th…

I think its a good article and I enjoyed learning a little more about rust, but would have been nice to point out this is a common technique used for tuple storage in databases for those not familiar. It comes off as being a novel solution rather than connecting it to a long tradition of DB design. I believe PG for instance has used a null bitmap since the beginning 40 years ago.

That would be surprising to me if anyone would think this is novel.

Using bitmaps to indicate whether things are in-use or not is very common in systems programming. Like you said PG does it, but most other systems do this too. It's not specific to databases: in an operating system, one of the first thing it needs is an allocator, the allocator most likely will use some bitmap trick somewhere to indicate what's free vs. what's available etc.

Re: Nobody ever got fired for using a struct

#133

Post by bombela »

amluto wrote: post #128
bombela wrote: post #126

Earlier quoted context omitted.

Ah, I see the confusion. rkyv_dyn doesn't serialize code. Rust is compiled to machine code. It would be quite a feat to accomplish. I was a bit confused when you compared it to Python pickle and assumed you were talking about general input validation somehow. I agree that pickle and similar are profoundly surprising and error prone. I struggle to find any reasonable reason one would want that. As for the man in middl…

> rkyv_dyn doesn't serialize code. Rust is compiled to machine code. Java is compiled to bytecode, and Obj-C is compiled to machine code. Yet both Android and iOS have had repeated severe vulnerabilities related to deserializing an object that contains a subobject of an unexpected type that pulls code along with it. It seems to be that rkyv_dyn has exactly the same underlying issue. Sure, Rust is “safe”, and if all t…

You know very well what I meant by "compile to machine code". But you decided to interpret it in a combative way. Even though you seem very knowledgeable, this makes me want to stop discussing with you.

Ultimately you should read the code of rkyv_dyn to understand what it does instead of making random claims.

It will be faster for you to read the code than for me to attempt explaining how it works. Especially since you will most likely choose the least charitable interpretation of everything I say. There is very little code, it won't take long.

Re: Nobody ever got fired for using a struct

#134

Post by SigmundA »

gz09 wrote: post #132
SigmundA wrote: post #110

Earlier quoted context omitted.

I think its a good article and I enjoyed learning a little more about rust, but would have been nice to point out this is a common technique used for tuple storage in databases for those not familiar. It comes off as being a novel solution rather than connecting it to a long tradition of DB design. I believe PG for instance has used a null bitmap since the beginning 40 years ago.

That would be surprising to me if anyone would think this is novel. Using bitmaps to indicate whether things are in-use or not is very common in systems programming. Like you said PG does it, but most other systems do this too. It's not specific to databases: in an operating system, one of the first thing it needs is an allocator, the allocator most likely will use some bitmap trick somewhere to indicate what's free…

Interesting so you don't find it odd that an article about the storage engine of a SQL database system explains the solution to problem without once mentioning that it is the way most other sql database engines solve it? It is mentioned several times sql table are typically sparse, but not that this is how its typically solved, only this is how you solved it...

>The fix is simple: we stop storing Option and instead we store a bitmap that records which fields are None.

Right here would have been the opportunity to let those not familiar with database internals know. Something like "This technique has been widely used in many RDBMS systems over the years, you can see the PG version of this in their documentation for page layout".

Instead you go into detail on what a null bitmap is and how to implement it, calling it a "trick". Which is strange if you think your target audience is assumed to already know this common technique.

I mean not one mention of the origin of the trick or even calling it a common solution to this problem...

Re: Nobody ever got fired for using a struct

#135

Post by amluto »

bombela wrote: post #133
amluto wrote: post #128

Earlier quoted context omitted.

> rkyv_dyn doesn't serialize code. Rust is compiled to machine code. Java is compiled to bytecode, and Obj-C is compiled to machine code. Yet both Android and iOS have had repeated severe vulnerabilities related to deserializing an object that contains a subobject of an unexpected type that pulls code along with it. It seems to be that rkyv_dyn has exactly the same underlying issue. Sure, Rust is “safe”, and if all t…

You know very well what I meant by "compile to machine code". But you decided to interpret it in a combative way. Even though you seem very knowledgeable, this makes me want to stop discussing with you. Ultimately you should read the code of rkyv_dyn to understand what it does instead of making random claims. It will be faster for you to read the code than for me to attempt explaining how it works. Especially since y…

> You know very well what I meant by "compile to machine code".

I really don't. I think you mean that Rust compiles to machine code and neither loads executable code at runtime nor contains a JIT, so you can't possibly open a file and deserialize it and end up with code or particularly code-like things from that file being executed in your process.

My point is that there's an open-ended global registry of objects that implement a given trait, and it's possible (I think) to deserialize and get an unexpected type out, and calling its methods may run code that was not expected by whoever wrote the calling code. And the set of impls and thus the set of actual methods may expand by the mere fact of linking something else into the project.

This probably won't blow up quite as badly as NSCoding does in ObjC because Rust is (except when unsafe is used) memory-safe, so use-after-free just from deserializing is pretty unlikely. But I would still never use a mechanism like this if there was any chance of it consuming potentially malicious input.

Re: Nobody ever got fired for using a struct

#136

Post by gz09 »

SigmundA wrote: post #134
gz09 wrote: post #132

Earlier quoted context omitted.

That would be surprising to me if anyone would think this is novel. Using bitmaps to indicate whether things are in-use or not is very common in systems programming. Like you said PG does it, but most other systems do this too. It's not specific to databases: in an operating system, one of the first thing it needs is an allocator, the allocator most likely will use some bitmap trick somewhere to indicate what's free…

Interesting so you don't find it odd that an article about the storage engine of a SQL database system explains the solution to problem without once mentioning that it is the way most other sql database engines solve it? It is mentioned several times sql table are typically sparse, but not that this is how its typically solved, only this is how you solved it... >The fix is simple: we stop storing Option and instead w…

> not one mention of the origin of the trick

And who or what would you say is the origin? The "trick" is so old I'm afraid it is lost to time to say who invented the bitmap. It was used in MULTICS or THE long before PostgreSQL was invented.

Re: Nobody ever got fired for using a struct

#137

Post by SigmundA »

gz09 wrote: post #136
SigmundA wrote: post #134

Earlier quoted context omitted.

Interesting so you don't find it odd that an article about the storage engine of a SQL database system explains the solution to problem without once mentioning that it is the way most other sql database engines solve it? It is mentioned several times sql table are typically sparse, but not that this is how its typically solved, only this is how you solved it... >The fix is simple: we stop storing Option and instead w…

> not one mention of the origin of the trick And who or what would you say is the origin? The "trick" is so old I'm afraid it is lost to time to say who invented the bitmap. It was used in MULTICS or THE long before PostgreSQL was invented.

There is a lot of space between no acknowledgment at all like this article and tracing down the exact origin of who and when invented to null bit map in what system.

Your version comes off as self promotion, going into detail how to implement a the technique with out once calling it a common technique or even mentioning its widely used in the industry to solve the problem you are solving.

It would be like saying finding rows in storage is slow so we implemented a b-tree in a separate structure for certain columns and go into detail how to create a b-tree, calling it a "trick" while never once acknowledging the is the most common form of indexing in RDBMS's, would you understand how this would seem strange?

Re: Nobody ever got fired for using a struct

#138

Post by p_v_doom »

Mikhail_Edoshin wrote: post #5
SoftTalker wrote: post #2

> But SQL schemas often look like this. Columns are nullable by default, and wide tables are common. Hard disagree. That database table was a waving red flag. I don't know enough/any rust so don't really understand the rest of the article but I have never in my life worked with a database table that had 700 columns. Or even 100.

I saw tables with more than a thousand columns. It was a law firm home-grown FileMaker tool. Didn't inspect it too closely, so don't know what was inside I remember a phrase from one of C. J. Date's books: every record is a logical statement. It really stood out for me and I keep returning to it. Such an understanding implies a rather small number of fields or the logical complexity will go through the roof.

> I saw tables with more than a thousand columns.

I used to work in a company that had all the tags in their SCADA system feed into SQL tables. They had multiple tables (as in tens of tables), because they ran out of columns ...

Re: Nobody ever got fired for using a struct

#139

Post by pmoati »

Great writeup !

The bitmap trick is elegant and I've seen similar patterns in other contexts. The core insight resonates beyond Rust and SQL: the data structure that's "obvious" at design time can become a bottleneck when the real-world usage pattern diverges from your assumptions. Most fields exist vs most fields might not exist is a subtil but critical distinction.

The fix being a simple layout change rather than a clever algorithm is also a good reminder. I've spent 20 years building apps and the most impactful optimizations were almost always about changing the shape of data, not adding complexity.

Re: Nobody ever got fired for using a struct

#140

Post by porise »

tialaramex wrote: post #89
porise wrote: post #63

Why is rust allowed to reorder fields? If I know that fields are going to be generally accessed together, this prevents me from ordering them so they fit in cache lines.

You can choose in Rust to explain the representation you want for your data type. Unlike C or C++ that's not a non-portable vendor extension it's just part of the language, look at the repr documentation: https://doc.rust-lang.org/nomicon/other-reprs.html So if you want "what C does" you can just repr(C) and that's what you get. For most people that's not a good trade unless they're doing FFI with a language that sha…

Rusts tradeoff is awful. People organize struct members in the logical ways in which they will be accessed. Rust just decides to do things different so they can say they do things different and "better" than the old C. The featured article is an extreme case but other normal cases would have the same issue. Packing structs should be the exception.
Post reply on HN