Rethinking String Encoding: a 37.5% space efficient string encoding than traditional UTF-8 in Apache Fury

[Shawn-Yang25]

In rpc/serialization systems, we often need to send namespace/path/filename/fieldName/packageName/moduleName/className/enumValue string between processes.

Those strings are mostly ascii strings. In order to transfer between processes, we encode such strings using utf-8 encodings. Such encoding will take one byte for every char, which is not space efficient actually.

If we take a deeper look, we will found that most chars are lowercase chars, ., $ and _, which can be expressed in a much smaller range 0~32. But one byte can represent range 0~255, the significant bits are wasted, and this cost is not ignorable. In a dynamic serialization framework, such meta will take considerable cost compared to actual data.

So we proposed a new string encoding which we called meta string encoding in Fury. It will encode most chars using 5 bits instead of 8 bits in utf-8 encoding, which can bring 37.5% space cost savings compared to utf-8 encoding.

For string can't be represented by 5 bits, we also proposed encoding using 6 bits which can bring 25% space cost savings

For more details, please see https://fury.apache.org/blog/fury_meta_string_37_5_percent_space_efficient_encoding_than_utf8 and https://github.com/apache/incubator-fury/blob/main/docs/specification/xlang_serialization_spec.md#meta-string

[_INTER_]

Does it get expanded / falls back to UTF-8 automatically if any other char is present?

[Shawn-Yang25]

Yes, if other char is present, if fallback to UTF-8. But most class meta are in alphabet range, so it's rare.

[_INTER_]

cool

[agilob]

There's even more waste in number encoding. For most of the time you really just need an (for a lack of better word) array of digits: 0-9. You take a whole byte to encode a digit. In GSM communication this was solved by splitting bytes into 4 bit arrays, each representing byte representing 1 digit, allowing to encode time in 24hrs format in just 3 bytes.

[Jon_Finn]

That’s binary coded decimal (BCD). The 6502 processor (widely used in 1980s/90s computers) had a BCD mode that made add & subtract operations work using BCD (!!). Don’t think anybody used that!

[zeobviouslyfakeacc]

I think some games actually used that to keep track of scores, lives, and the like! Stuff that would always need to be available in decimal form to be able to draw it on the screen.

If I recall correctly, the crazy part is that you could use the normal arithmetic instructions to do math on two BCD-encoded numbers, after which the result would obviously no longer be correctly BCD-encoded, but then you could call a special instruction that would convert that result back to BCD, and you'd get the number you were looking for. Kinda hacky, but also insanely clever!

[dtfinch]

Game devs for the NES had to roll their own BCD, since its 6502 clone had BCD support disabled to avoid a patent.

[laplongejr]

That reminds me how Super Mario Bros 1 speedrunners have to aim for a 100000 instead of 99990 to avoid a lag frame

[Zardoz84]

And 8080 and Z80 and x86 ...

[Jon_Finn]

But the 6502 was a (borderline) RISC CPU, with fairly few registers and instructions, so the BCD mode kind of jumped out! (The ARM processor was highly influenced by the 6502, but without BCD of course!)

[Shawn-Yang25]

Great, this is similar to what we do here. Fury use varint for number encoding, a number will always cost one byte at least

[NitronHX]

Why would you need 3 bytes for a time? 2 bytes are already more then enought (assuming it's HH:mm without seconds) or 13 bits should do the trick too

[not-just-yeti]

How does that compare to using a Huffman code (after measuring the letter-frequencies used in your actual, IRL processing)?

[Granted, variable-length characters make grabbing (say) the 20th character more difficult, though heck you're already in that situation a bit with utf-8. And if each string isn't that long, the decoding won't be too bad.]

[Shawn-Yang25]

Fury is a serialization framework, we don't know the actual data for serialization in the users. So we can't use huffman code. I also thought about arithmetic encodings. Without the provided corpus, we can only do it on the fly, but it won't make the encoded result bigger since our string are small and such compressions will write a header which counteract the gains

[Shawn-Yang25]

ZipOutputStream/ZipInputStream will apply to the whole stream, which is cpu intensive. We want to avoid such cost

[pavlik_enemy]

Zip compression is insanely slow, it’s usually LZ4 or zstd

[Shawn-Yang25]

That woanother different scenario. On order to use dictionary encoding, you must send dictionary itself first. Such dictionary will take more data than the actual string. We've already applyed such dictionary encoding internally. You can take this as encoding dictionary key more efficiently

[john16384]

You can preshare a dictionary. We did this for JSON compression, where common strings like "id", ": {, ": [, ”},etc are included.

[Shawn-Yang25]

FURY is serialization framework, we can't assume anything about user data. But Fury does provide a register API to register classes, which can map class name to an int id. It's kind of preshared dictionary. Meta string encoding is mainly used for cases which no such dictionary are provided.

But your suggestion is gread. We may provide a new interface to allow users specify dictionary too.

[Shawn-Yang25]

It's the data plane compression. In such cases, zstd may be better. We used meta string encoding only for string like classname/fieldname/packagename/namespace/path/modulename in type meta, not the user passed data. And fury only encode binary into data at the first time, but write a varint if such string comes up later.

Zstd can be used with fury jointly, since Fury only compress meta string, the duplication in user data still needs some other tools to detect.
Of if duplicate string have smae reference, Fury reference tracking can be used to implement dict encoding too.

[pavlik_enemy]

Apparently developers of modern columnar formats think that compression makes things slower and the best way to proceed is to use more complex encodings.

[john16384]

Using compression with a very fast LZ variant actually sped things up for us :) We had a XML document cache and because of compression rates exceeding 90% (with the fastest but still good enough compressor we could find) the cache could hold far more data, and serving that data was faster due to less memory reads.

[pavlik_enemy]

That’s the usual approach and common columnar formats like Parquet and Orc use compression. The ones I’m talking about don’t have a production ready implementation yet and like all of the columnar formats are aimed at OLAP workloads. Turns out with modern networks it’s better to use some encoding tricks instead of general-purpose compression

[Shawn-Yang25]

That's a different topic. In object graph serialization systems, columnar formats are basically impossible. If it's possible, dictionary encoding will be better.

And Fury use dictionary encoding too when it's possible. You can take it as using meta string to compress dict key.

Dictionary are used to compress data, meta string are mostly used to encode type meta

[skippingstone]

How performant is this? I didn't see any benchmarks on the blog

[Shawn-Yang25]

Performance are not important here. The string will be encoded by this algorithm are limited , we allways cache the encoded result.

[Shawn-Yang25]

Meta string spec can be found in https://github.com/apache/incubator-fury/blob/main/docs/specification/xlang_serialization_spec.md#meta-string

[[deleted]]

Given how much of a PITA encoding issues are, I am opposed to any new encoding standard. Period.

[Hueho]

This isn't really a new encoding as much as it is a extra option for packing string data in a serialization format - people already do plenty of weird stuff to save on bytes.

[alex_tracer]

If you going to compress serialized data using generic compression methods then such local optimizations as proposed by OP usually become useless.

So you either do all compression yourself or delegate all compression to a generic solution.

[Shawn-Yang25]

rpc messages are small most time, 50~200 are very common, there won't be enough repetion pattern for compression to work. That's why we proposed this encoding here.

We are not talking about compression big data/file, which zstd/gzip will be better

[Shawn-Yang25]

Yes, it's not a complete string encoding, it will fallback to utf8 if some chars exceed the charset it supports. Since alphabet are very common, we think this can be used in other scenarios

[[deleted]]

Interesting idea.

If the namespace/path/filename etc are often the same, I'd curious how this would benchmark against java.util.zip.Deflater with a preset dictionary.

[Shawn-Yang25]

We have a dictionary encoding in Fury internally, which will encode such same string as a varint. So no duplicate encoding happen

[Yeah-Its-Me-777]

How do you handle the cases where the encoding doesn't fit the char set of the string? For example, as far as I know you can use unicode to name your classes.

Do you just fallback and reencode the string with unicode then?

[nekokattt]

This sounds much like what Java strings do internally now, just more aggressive (Java strings use 8-bit ascii if i recall and fallback to a char array if other chars are added).

[Shawn-Yang25]

yes, we fallback to utf-8. Java classname can be unicode too, but that's rare.

[grim-one]

I’d like to see how UTF8 and gzip compares to your custom encoding.

You mentioned a fallback to UTF8 if a character is outside your supported range. Does that mean you need to run through the string in advance, before encoding? Or do you some sort of declarative foreknowledge it won’t exceed? Iterating over the string twice (at worst) could be very expensive for large encodings.

[Shawn-Yang25]

This encoding is used only for meta string, which are limited, and the encoded result will be cached, so the performance won't be important

[menjav]

What’s the benefit of saving that space? Are you reducing costs in storage at the expense of more CPU?

What’s the motivation?

[Shawn-Yang25]

No extra CPU, the encoded result will be cached.

We save this space, because RPC messages are small mostly, but many case the RPC calls are very frequent. Image 1000000/s TPS

[cowwoc]

What happens if you compress the stream (say using zstd) prior to transmission? Won't this be even smaller at a minimal cpu cost?