Hacker News Reader

Comment by cperciva | Hacker News Reader

It's a bit humbling to think that my "quick hack" is yielding bandwidth savings measured in petabytes per day.

I wonder how it translates to the money savings for Google and end users.

A quick estimate based on prices quoted by Google Cloud Engine for Egress transfers ($0.08/GB) gives $183 million in yearly savings.

Surely Google pays much less than that for their own transfers, but even if we assume they are paying 1% of that price it is still respectable. Pretty sure they are paying more than that though.

EDIT: Found better estimates - Amazon Cloudfront is charging as low as $0.02/GB (on demand pricing), which translates to $46 million. Given very good knowledge Google has about their users and their vast infrastructure I'm guessing their costs are fraction of this. Anyone with domain knowledge that can comment on this?

I'm very much not in the know (my personal experience tops out at renting gigabit lines at 95th percentile), but it's my understanding that at extreme scale, you're doing peering arrangements directly with ISPs, and provisioning a fixed amount of bandwidth with them.

It wouldn't surprise me if Google was scheduling the majority of updates to take place in off peak times, when the bandwidth would simply be otherwise unused. If so, the cost to Google would be a rounding error of your estimate based on GCE traffic prices.

For end users: Google is well aware of how many android phones are being used in the developing world. Something like 97% of the smartphone market in Myanmar is on android 4.2 and later. 1GB of data paid via scratch card is a lot of money for some people.

I just tried bsdiff, and can I complain a little? I tried to diff two 1 GB files, and within a few seconds bsdiff was using enough memory to lock up my Ubuntu desktop. 10 minutes later I managed to get a text console and kill it. Maybe I should blame Ubuntu for letting a single process hose the system, but it was still annoying.

Edit: bsdiff is documented to use memory 17x the file size.

Interesting, I had assumed this (runaway process and unable to do anything) only happens on Windows. (speaking in general)

This happens to me quite often on Linux and I've always wondered if there's a way to fix it. Is there?

man ulimit?

ssh to the box then kill the process.

I've often been unable to connect to SSH on a host for lack of available CPU/memory to spawn the SSH receiver process + the shell.

It's especially a problem with AWS's tN.micro instances: when something thrashes them for long enough, they ratchet down to such a low CPU allocation that it will likely take hours before SSHD gets context-switched to enough times to start your process. By then, all sorts of timeouts will likely have killed your session.

That's worth making persistent noise about, I think. Because you just described something that can be accurately described as a type of DoS.

Considering the number of AWS credentials out there, I can see malicious users logging in, forkbombing the instance, getting it to throttle back, and then walking away whistling until the person with dashboard login wakes up and can reboot the machine.

Usually this happens on Linux because an application is using too much memory and the kernel is spending tons of resources reclaiming memory to prevent a system OOM.

The system can easily slow to a crawl as memory accesses and allocations are constantly triggering reclaim and causing the system to thrash. The kernel has no way to know that it should prioritize the terminal you are trying to open to kill things rather than try its hardest to keep the offending application running.

The best way to prevent this, if you know an application will use lots of memory, is to run it in a memory cgroup. With a memory cgroup you can limit the applications total allowed memory, reserving some for the rest of the system.

Unfortunately, I don't know of a super nice CLI, but here's an example using cgcreate/cgexec (https://packages.debian.org/stretch/cgroup-tools):

    $ # Create a memory cgroup named 'mygroup', allowing $USER to change the parameters and run tasks in the cgroup.
    $ sudo cgcreate -a $USER -t $USER -g memory:mygroup
    $ # Set the memory limit to 10MB
    $ echo 10000000 > /sys/fs/cgroup/memory/mygroup/memory.limit_in_bytes
    $ # Run a program in the cgroup
    $ cgexec -g memory:mygroup ls

> The kernel has no way to know that it should prioritize the terminal you are trying to open to kill things rather than try its hardest to keep the offending application running.

This is one of the problems multitask OS's were invented to solve. The answer is always let other tasks run too.

> Maybe I should blame Ubuntu for letting a single process hose the system

Speaking of: is there a good way to ask an OS to "reserve memory and CPU-time" for emergency interactive maintenance (e.g. spawning a console on a thrashing box), in a similar way to how ext2/3/4 "reserves space" for the root user for emergency maintenance?

The only real way I can think of to do this (that doesn't involve already knowing what processes could thrash and cgroup'ing them) is to run a hypervisor and treat the dom0 as the emergency console. That still doesn't let you get inside the thrashing instance to fix it, though.

It won't help with memory usage but you can nice a process to reduce its share of time in the process scheduler.

If you use systemd you can assign services to slices which can be assigned cgroup resource reservations / limits. I don't think any distro does too much with this out of the box yet (IIRC by default all services run under a single "system" slice, and user sessions under a user slice), but it should be possible to run an "emergency environment" slice in which the processes are always guaranteed some small amount of resources necessary to recover.

The LinkedIn people report that it's not that simple.

* https://engineering.linkedin.com/blog/2016/08/don_t-let-linu...

isn't "Ctrl + Alt + F1" to F7 essentially that? (on linux)

> I just tried bsdiff, and can I complain a little?

It's HN. Do you even have to ask?

Without even opening this article, I knew that they would be using bsdiff.

Thanks, truly, for creating such a tremendously useful tool.

I don't want to diminish your work, but today's improvement is not in using bsdiff (which they already did), but in using it file-by-file. That's where bsdiff can really shine, because both inputs looks way more similar.

Sure, but running file-by-file is how bsdiff was designed to operate. (I wrote it for FreeBSD Update, which operates on a file-by-file basis, because I was paranoid about the problem I'd seen on Windows systems where an update was registered as "installed" but the system had not in fact been properly updated.)

Ah, that's where it got its name :)

Really awesome utility.

I believe it stands for Byte Subtraction Diff, or something like that. As I remember, something like Bentley McIlroy diff is used to identify identical runs, and where there are short runs of bytes separating two runs that are identical between the two files, the bytewise subtraction of the short run is stored.

The key observation is that when performing updates, large runs of machine code will be identical, with only relative offsets and absolute addresses changing. Code changes tend to shift huge pieces of binary code in parallel (by the same offset), so the bytewise subtraction expresses these shifts as many repeats of the same bytewise difference, which is then more easily compressed by zlib DEFLATE (or maybe another compressor... I forget the details).

These programs were originally named bdiff and bpatch, but the large number of other programs using those names lead to confusion; I'm not sure if the "bs" in refers to "binary software" (because bsdiff produces exceptionally small patches for executable files) or "bytewise subtraction" (which is the key to how well it performs). Feel free to offer other suggestions.

Ah, thanks for the information. I must admit I have never used it and never looked at what makes it different from other diff algorithms. Will definitely have a look at it !

I find bsdiff works fine on concatenated files, because it searches for common sections over the whole file, rather than a traditional diff which just searches in order.

It can work on concatenated files (if you avoid compression, which screws up everything) but it's usually more efficient to run bsdiff on individual matched pairs. The heuristic bsdiff uses for identifying "mostly-matching" regions is just that -- a heuristic -- and the larger the amount of data you have the higher the chance that bsdiff will try to build a mostly-matching region out of a coincidental sequence of matching bytes.

If I'm not mistaken, an APK file is a zip archive, meaning that bsdiff was previously run on compressed stuff. As you can see in the article compressing content tends to make the output greatly differ (so much that gzip has a special option to make it more easily diffable, typically for rsync use). So bsdiff wasn't previously run on a concatenation of file; it was not used optimally.

The archive tools (like 7z) have a special flag to allow for diff over the entire archive by external tools.

The flag will modify the storage format, -kinda packing files/chunk together instead of just compressing into a huge block- so that tools can detect diff and same sections over the full archive.

It's not well know but it is an absolute must known. e.g. for backup archive that goes over rsync, and change little over time.

I looked in the 7z manual but couldn't find anything obviously related to this functionality. Would you mind giving a reference?

'gzip --rsyncable' for gzip.

I couldn't find the equivalent for 7z in a quick glance. It supports at least 5 compression algorithms so there is probably not a general option. Maybe one has to play with the advanced settings per algorithm, if they support it.

gzip --rsyncable does make gzip set boundaries so one change doesn't affect the entire rest of the file, just one block.

However, the resulting differences don't seem nearly as amenable to the bsdiff algorithm as the changes to the underlying uncompressed data. In almost all cases, you'll likely get better results with bsdiff on the uncompressed data (and bsdiff internally compresses its result).

Don't know about how bsdiff operate, maybe it's naive.

Good deduplication and diff algorithms have adaptive block size detection.

It should in theory work similarly on a tar file, no? (tar without compression)

Apple has also been using bsdiff for incremental app updates (on device). I discovered bsdiff while poking around in one of their update files.

One wonders how much more they'd save if they could use the more sophisticated version you developed. ;-)

Reply on news.ycombinator.com