13 ms·
The power of interning: making a time series database smaller
- lukeweston1234 2y agoGreat post, one of my more favorite reads in the last few weeks.
- jcgrillo 2y agoIt's really shocking to see how wasteful a big blob of JSON is. This is such a great illustration of how much room there is for improvement.
- deleted 2y ago[deleted]
- throitallaway 2y agoThe best thing that JSON is good at is human readability. I would say human composibility as well, but YAML and others are better for that. As a machine data exchange and storage format, JSON is extremely inefficient.
- travisjungroth 2y agoI really dislike writing YAML. It might be a skill issue (as the kids say), but it just never landed. I'd rather write JSON, even with all its verbosity.
- jcgrillo 2y agoIt never ceases to amaze me how good computer people are at solving problems which are not problems (readability of serialized representation) at the expense of multiple orders of magnitude more compute and storage.
- williamdclt 2y ago> problems which are not problems (readability of serialized representation) I don't know that I fully agree. A format that is both human- and machine-readable is very useful, for configuration and debuggability for example. It's indeed more expensive in compute and storage, but that's additional work _for machines_ rather than _for humans_ (having to compile/encode/decode data at the human/machine interface). Certainly doesn't mean it's always the right trade-off, but it's an appealing one, as the popularity of these formats shows, in particular JSON which isn't even that good for human-readability (eg no comments in standard JSON).
- vacuity 2y agoBut that's the thing: if we want to optimize both machine and human experience, we should create a 1:1 dual format, one which is machine-readable and one which is human-readable. A standard tool easily converts one to the other. This should not still be a problem. Yes, we have computers and should offload work onto them. But exactly what that work is is still important. Two approaches aren't equal because they both put the burden on the machine.
- addaon 2y ago> But that's the thing: if we want to optimize both machine and human experience, we should create a 1:1 dual format, one which is machine-readable and one which is human-readable. A standard tool easily converts one to the other. So… plists and plutil?
- Zezima 2y agoAn amazing example of Rust's abilities. More impressed by the relentless iterative approach taken by the author. Nicely done.
- henry700 2y agoAmazing doing this on a weekend and keeping enough track to write a great article about it within 3 weeks time.
- c-linkage 2y agoInterning strings saves a ton of space. I wish more programmers would use it. Back in the 32-bit days I was working on a large (multi GB) distributed Oracle database system but I couldn't use transaction log shipping (don't ask). Database A was the "main" system and database B was the "replica". To keep them in sync I needed a program that would compare the two databases and then generate an update script that would make B look like A. Complicating things was that, for some reason, floating point data in binary format would never match exactly between the two systems, so all floats had to be exported as text. The first attempt by a junior dev was implemented in C#. Not only was it terribly slow, but it also ran out of memory. I wrote a new version in C that interned all strings using a hash table and a custom bump-allocator. I also exported every field in the database as a string, so I didn't have to deal with native types. Using this technique meant that a database record could be represented as a plain array of pointers to the interned strings. Since each string was only recorded once, and every field was a pointer to a string, should two database records have the same values then they must by definition point to the same string. Comparing database rows was as easy as doing a memcmp() on the two pointer arrays, one being a record from database A and the other being a the record from database B. Not only was the system incredibly fast, but it never took more than 150MB of memory to run.
- gopalv 2y agoThis is mostly the real reason why interning gets used, to avoid long string comparisons over saving memory as such. Interned strings tend to not have a good cleanup mechanism, in a system where a lot of them are churned through. So often they tend to actually use more memory as data patterns evolve in a system. I use the same trick when parsing json, where a large set of rows tend to have the keys repeated & the conversion to columnar is easier if the keys are interned.
- kazinator 2y agoIn Lisp, interning is not only used for saving on string comparisons. It's the basis of the symbol abstraction. Or perhaps not the basis, but interning is the only way symbols can correspond to a printed representation. Without interning, we don't have it that A and A are the same object. A symbol being an object with a durable identity is important because it can have properties other than just the string which gives it a name.
- deleted 2y ago[deleted]
- 3abiton 2y agoVery fun read guillaume! I never find the courage to work on my "this seems to be interesting weekend idea" due to my fear of time commitment, but I often find these HN write up somehow fulfilling.
- Horffupolde 2y agoWhat about loading it into ClickHouse?
- wiredfool 2y agoYeah, I've got some clickhouse tables that store similar data (GBFS), and I've got an amortized size on the 1byte/row level.
- saghm 2y agoI did something similar to reduce the memory overhead of our Rust backend at a recent job; I noticed that when dealing with certain requests, we were using quite a lot of memory on duplicates of the same strings when processing things, so I made something I called an "alias cache" type that could be used to obtain an alias of an existing string if needed, and then introduced those to several places in the codebase where it was most helpful. This strategy also allowed some flexibility on how long strings were "cached" for, which let me tweak which layers of processing should share a cache versus creating their own (and letting the old one drop). Our use case definitely didn't have room for interning to use 2000x less memory, but I think in some of the pathological cases it reduced the max memory usage to around 50% of what it was before without significantly affecting runtime, which I was pretty pleased with!
- Diggsey 2y agoI have a Rust crate (ijson) which implements string interning and a generally much more efficient in-memory JSON representation. It probably doesn't compete with the author's specialized implementation, but if you just want a plug and play solution it's pretty good.
- valand 2y agoFun fact, V8 interns strings! But it doesn't seem to intern big ones.
- nostrademons 2y agoMany VMs do. The JVM was one of the first to do this extensively - all strings are in a "constant pool" as part of the .class format, and then they're referenced by index in instructions. Python does it for strings that appear in source code, and you can force it for runtime data with sys.intern().
- hu3 2y agoFrom the looks of it it seems that interning here is creating references to strings that repeat. Strings are large so if you can store a reference to it, you save space.
- jessekv 2y agoIf you are curious about how Python's string interning works: https://github.com/python/cpython/blob/main/InternalDocs/string_interning.md https://github.com/python/cpython/blob/main/InternalDocs/str...
- Someone 2y agoA problem with explicit interning is that libraries, when creating objects, cannot make an informed decision whether to offer some runtime performance in exchange for the expectation of a decrease in memory usage. And it is even less than an expectation. Many interning libraries never free objects that they created, so they can keep lots of objects that never are needed again around, and thus increase memory usage. I think the ideal API would somehow a) be simple and b) have the program communicate with the system about what they desire from the system. As a first step, the system has to know how much memory the program is willing to use, how much longer it expects to run, and for how long the program plans to retain data it is creating now. Simple examples: - if the program is shutting down, and there’s a megabyte of memory available, it’s likely detrimental to intern any new data. - in a “json grep” tool, interning json keys likely isn’t worth it, as most data will be discarded soon. That’s probably at least a dozen of ph.d’s of research, and likely not attainable, though.
- wdb 2y agoAs its already in Rust. Next step, is leveraging Apache DataFusion?
- trevor-e 2y agoGreat write-up! Apologies if this side-tracks the conversation, but why do we as an industry complicate the naming of such techniques? I don't remember what "string interning" is off the top of my head, but a "string lookup table" is immediately obvious. Maybe I'm wrong though and this is a commonly understood name. I guess interning captures both creating the lookup table + using the index in the related data structures. We used this technique at KAYAK to help efficiently construct the list of possible flight combinations for N x M depart/return legs.
- mannyv 2y agoSo interning is really just normalization/dictionarying your strings.
- cb321 2y ago"pointerizing" might be another name. It would be utterly unsurprising if the database/sql world had more than one other name as well. Usually, ideas that go back to the 1950s at the dawn of data representation have many names. Maybe worth noting, you only need the dictionary in one direction (converting an expanded string to a pointer by looking it up). In the other direction, you just need to indirect the pointer and most people don't call an address space indexed by integers a "dictionary" (though, I guess the OG Javascript did merge these two ideas). Also notable, how wide a pointer you need (8-bit..64-bit) and how often you do each direction just depends upon workload. This one-direction kind of matters since sometimes your data set is so static that you can just convert to pointers up-front. Then your data analysis doesn't even need the expanded->pointer dictionary. With larger pointers (like 16..64-bit offsets into a file), you just need the file (and whatever data &| files reference it via the pointers). Personally, I've run into many "enum-scale" scenarios where 8-bits was enough address space. E.g., there are <256 countries in the world, last I checked. You might need another layer of indirection if you cannot bound the length of per-country data, though. As mentioned else thread (at least here by nostrademons: https://news.ycombinator.com/item?id=43245421 https://news.ycombinator.com/item?id=43245421 but probably elsewhere), data compression algorithms just generalize this to not 8..64 bit, but " 'best' bits per token", but they need to measure up front what 'best' might mean. That domain of research/impl may also have its own terminology. I don't know what to do about "nobody talking to each other" either in this eentsy microcosm or more generally. Society can be tough. :-)
- vtuulos 2y agoif you want to see similar tricks applied in Python (with a JIT compiler for query-time optimization), take a look at this fun deck that I presented a long time ago: https://tuulos.github.io/sf-python-meetup-sep-2013 https://tuulos.github.io/sf-python-meetup-sep-2013 we were able to handle trillion+ datapoints with relatively modest machines - definitely a useful approach if you are ready to do some bit twiddling
- ciupicri 2y agoJust use `s = sys.intern(s)` for every string and be done with it. Or something like: _my_intern_dict = {} my_intern = lambda x: _my_intern_dict.setdefault(x, x) s = my_intern(s) Just make sure to delete _my_intern_dict when it's not needed anymore.
- uhgrippa 2y agoVery interesting, I particularly enjoyed the handling of memory reduction with the Interned<T> comparison. How do you go about finding open source projects which expose fascinating data such as this one?
- Aachen 2y agoI never heard of interning before (besides being an intern at a job perhaps) so I gave the post a read and... isn't this called deduplicating in plain English? I didn't understand what context the jargon adds; what makes this special
- coder543 2y agohttps://en.wikipedia.org/wiki/String_interning https://en.wikipedia.org/wiki/String_interning It's an established term in software. I would speculate that the word "intern" is short for "internalizing" here.
- olddustytrail 2y agoI think it's from the Lisp "intern" function, which creates an internal symbol if it doesn't already exist and there's no external symbol of the same name.
- vacuity 2y ago"Intern" (job) -> staying at a workplace for some time to be trained and do some work "Intern" (software) -> staying resident in memory to be referred to canonically I find that often words do come about with a surprising amount of sense.
- 6r17 2y agoFirst time I read about interning and this is really cool ; kudos for the article and the usage. Thanks for sharing !
- 658677646 2y ago[flagged]
- 658677646 2y ago[flagged]
- kajecounterhack 2y agoYears ago at Google, the permissions system (OG ganpati, for the googlers) was having major performance issues related to OOM in Java. IIRC there was an epic thread where folks discussed potential resolutions including, this being Java, GC tuning. But in the end, string interning was what helped a ton to defer the scaling issues until something else could be done (mostly a rewrite, smh). I mostly remember this as being a shocking solution to me. Part of me imagined there'd be some fancy scalable solution instead of single-binary optimization, but at the end of the day sometimes you just gotta intern some strings.
- xelxebar 2y agoMan, lately I've been amazed by how many performance tricks like these are just bog standard APL. For example, string interning looks like this: strs←∪input_strings ⍝ Build strs⍪←⊂'new string' ⍝ Append strs⍳⊂'some string' ⍝ Search f←strs∘⍳ ⍝ Hash table creation One extra advantage on top of standard interning is that this also uses an incarnation of tiny pointers[0], automatically saving 2X memory generally. Better yet, standard APL data design will often obviate the need for most string searches, letting you get away with integer comparisons instead. I'm starting to really see how data-oriented design tends to make straightforward code both parsimonious and highly performant. [0]:https://news.ycombinator.com/item?id=43023634 https://news.ycombinator.com/item?id=43023634
- est 2y agoDoes column store do this automatically?
- yencabulator 2y agoThat's a lot of manual effort for something a better format like Parquet could do automatically (dictionary encoding).
- mleonhard 2y agoWould it be simpler to use BTreeSet<Arc<Box<str>>>? use std::collections::BTreeSet; use std::sync::Arc; let mut set: BTreeSet<Arc<Box<str>>> = Default::default(); let s = Arc::new("abc".to_string().into_boxed_str()); if !set.contains(&s) { set.insert(s.clone()); } let s = set.get(&s).unwrap();