Nice to see more people getting nerdsniped by the sh code. ;-)
Yes, associative arrays work well. I think it should even be possible to use bash associative arrays. But at that point you're no longer doing classic sh - awk is basically halfway to Perl. (And pretty awesome.)
Yeah, insisting on "only" shell is weird, shell is at heart a process orchestrater, and denying it it's processes is rejecting most of it's functionality. It is equivalent to saying "do this in python, but you are not allowed to use any modules"
Without processes shell is just a weird sad little language, with them it turns into this epic data flow language. With some real design stinkers, Most of these are due to it's interactive first focus, The features desirable for interactive use, often start to stink for stored program use, I will note that having the same language for interactive and scripting is pretty kick ass.
On the subject of dataflow languages has there been any research in this area? Something that can stitch together processes as well or better than shell? Perl may work in this role but I have to admit I really dislike it's syntax, and as such I never learned Perl enough to love it. and while most other scripting languages can technicaly create pipelines, it is very awkward compared to shell.
> On the subject of dataflow languages has there been any research in this area? Something that can stitch together processes as well or better than shell? Perl may work in this role but I have to admit I really dislike it's syntax, and as such I never learned Perl enough to love it. and while most other scripting languages can technicaly create pipelines, it is very awkward compared to shell.
I've been working on a design for a Python library to facilitate this sort of thing.
The general point is true, but the shell pipeline gets a lot more elegant if you use the sort-and-accumulate paradigm that the classic shell utilities were written for (which uses O(1) memory, by sorting on disk). Using mostly the author's own code, and adding --count to uniq:
(Where the final awk papers over the fact that we're mixing tabs and spaces here; obviously, awk is also good at doing the accumulation step, but uniq --count suffices here.)
(I originally posted the above as a comment on lobste.rs, on this same article.)
Very interesting solution, and in the spirit of the original article. If I understood the snippet right, you are sorting the input sequence on the first column (the words) and then on the second one (the frequencies)
It is nevertheless "complecting": the uniq assumes the data is sorted and the columns of your data structure move together. Maybe this algorithm is already complex regardless of the implementation.
The sort is on line numbers, as aozgaa said. Again, the paradigm here - and this is designed for a different time - is that your data most definitely does not fit in RAM, so you use sort(1) to sort on disk and run your software using only constant memory. (In modern software, databases can and do sort on disk, but few programs do.)
In detail, for input "foo bar FOO qux FOO foo", we convert to
[1 foo, 2 bar, 3 foo, 4 qux, 5 foo, 6 foo]
(with newlines instead of commas, obviously), then sort by word (then line number) to
[2 bar, 1 foo, 3 foo, 5 foo, 6 foo, 4 qux]
at which point the uniq invocation gives <count> <first_line> <word>, i.e.
[1 2 bar, 4 1 foo, 1 4 qux]
albeit with an ugly mix of tabs and spaces. One final sort by <first_line> gives us
[4 1 foo, 1 2 bar, 1 4 qux]
and then it's just a matter of formatting the output:
[foo 4, bar 1, qux 1]
The generally-useful point is that the classic shell utilities really do work pretty well if you're operating within their paradigm, which isn't "throw everything in a hash table". (That's the paradigm of later scripting languages.)
the point is to do a stable sort on (word, line number) lexicographically, then when we do "uniq" we can take the first line number.
In contrast to the "we need a frequency table" idea in the article, this solution trades off memory by transferring all the line numbers in the stream. This is very much in the spirit of the infamous McIlroy/Knuth "bakeoff"[1] -- tradeoff some efficiency (via extra book-keeping or sorts) in return for composability.
(Hopping in here because the discussion is interesting... feel very free to ignore.)
Thanks for writing this up! It was a very interesting read about a part of networking that I don't get to seriously touch.
That said: I'm sure you guys have thought about this a lot and that I'm just missing something, but "why can't every proxy probe every [worker, not application]?" was exactly one of the questions I had while reading.
Having the workers being the source-of-truth about applications is a nicely resilient design, and bruteforcing the problem by having, say 10k proxies each retrieve the state of 10k workers every second... may not be obviously impossible? Somewhat similar to sending/serving 10k DNS requests/s/worker? That's not trivial, but maybe not _that_ hard? (You've been working on modern Linux servers a lot more than I, but I'm thinking of e.g. https://blog.cloudflare.com/how-to-receive-a-million-packets...)
I did notice the sentence about "saturating our uplinks", but... assuming 1KB=8Kb of compressed critical state per worker, you'd end up with a peak bandwidth demand of about 80 Mbps of data per worker / per proxy; that may not be obviously impossible? (One could reduce _average_ bandwidth a lot by having the proxies mostly send some kind of "send changes since <...>" or "send all data unless its hash is <...>" query.)
(Obviously, bruteforcing the routing table does not get you out of doing _something_ more clever than that to tell the proxies about new workers joining/leaving the pool, and probably a hundred other tasks that I'm missing; but, as you imply, not all tasks are equally timing-critical.)
The other question I had while reading was why you need one failure/replication domain (originally, one global; soon, one per-region); if you shard worker state over 100 gossip (SWIM Corrosion) instances, obviously your proxies do need to join every sharded instance to build the global routing table - but bugs in replication per se should only take down 1/100th of your fleet, which would hit fewer customers (and, depending on the exact bug, may mean that customers with some redundancy and/or autoscaling stay up.) This wouldn't have helped in your exact case - perfectly replicating something that takes down your proxies - but might make a crash-stop of your consensus-ish protocol more tolerable?
Both of the questions above might lead to a less convenient programming model, which be enough reason on its own to scupper it; an article isn't necessarily improved by discussing every possible alternative; and again, I'm sure you guys have thought about this a lot more than I did (and/or that I got a couple of things embarassingly wrong). But, well, if you happen to be willing to entertain my questions I would appreciate it!
(I used to work at Fly, specifically on the proxy so my info may be slightly out of date, but I've spent a lot of time thinking about this stuff.)
> why can't every proxy probe every [worker, not application]?
There are several divergent issues with this approach (though it can have it's place). First, you still need _some_ service discovery to tell you where the nodes are, though it's easy to assume this can be solved via some consul-esque system. Secondly, there is a lot more data than you might be thinking at play here. A single proxy/host might have many thousands of VMs under its purview. That works out to a lot of data. As you point out there are ways to solve this:
> One could reduce _average_ bandwidth a lot by having the proxies mostly send some kind of "send changes since <...>" or "send all data unless its hash is <...>" query.
This is definitely an improvement. But we have a new issue. Lets say I have proxies A, B, and C. A and C lose connectivity. Optimally (and in fact fly has several mechanisms for this) A could send it's traffic to C via B. But in this case it might not even know that there is a VM candidate on C at all! It wasn't able to sync data for a while.
There are ways to solve this! We could make it possible for proxies to relay each others state. To recap:
- We have workers that poll each other
- They exchange diffs rather than the full state
- The state diffs can be relayed by other proxies
We have in practice invented something quite close to a gossip protocol! If we continued drawing the rest of the owl you might end up with something like SWIM.
As far as your second question I think you kinda got it exactly. A crash of a single corrosion does not generally affect anything else. But if something bad is replicated, or there is a gossip storm, isolating that failure is important.
You're commenting on an article about people consuming less than $3/day; Americans on food stamps (SNAP appears to be about $4-6/day alone, not counting any other benefits) are a distraction, simply not part of the population that the article is discussing.
Picking anything but PlantUML's default theme will make PlantUML look less 90's-Java. As a minimalistic solution, I already like "skinparam monochrome true" https://plantuml.com/skinparam#:~:text=Black%20and%20White. (You can go further with CSS and themes and...)
I really like this article. I do think it's useful to consider that the unit of isolation ("process") of the cloud era is a VM or container, and that the major clouds do have some sort of permissions model.
The error rate is given per bit, not per second, i.e. every few bars represents a distinct DRAM chip. That makes some sense, and the article explains quite well why DRAM would behave like that... but I agree that I had to read the article at least twice to figure out that the x-axis on the graph represents the lower bit of the address line!
Yes, associative arrays work well. I think it should even be possible to use bash associative arrays. But at that point you're no longer doing classic sh - awk is basically halfway to Perl. (And pretty awesome.)
reply