6 ms·

Reinventing backend subsetting at Google

110 points by yarapavan 4y ago

wilg 4y ago
I thought this was going to be Google automating shutting down their own products. Might be a good idea. Just start a clock for 18 months, shut down the service automatically, and reward the relevant executive with a bonus.
- postsantum 4y ago
  Sunsetting-based promotion cycle. Manager dies with the product only to be reborn at the higher step of the ladder
- sieabahlpark 4y ago
w0mbat 4y ago
- nobody9999 4y ago
  >"Wankadia" is an intriguing surname, combining as it does "Arcadia", the ancient Greek idea of a rural utopia and "Wank". This[0]: CALIFORNIA: From Latin 'calor', meaning "heat" (as in English 'calorie' or Spanish 'caliente'); and 'fornia', for "sexual intercourse" or "fornication." Hence: Tierra de California, "the land of hot sex." Should be right up your alley (yes, there's a double entendre there), friend. :) Sadly, your sense of humor (and mine, for that matter) isn't very popular around here. And more's the pity. [0] http://www.quotationspage.com/quote/23088.html http://www.quotationspage.com/quote/23088.html
  - smcameron 4y ago
    Huh, I'm pretty sure I first encountered this California joke from some variant of fortune[1] back in the '80s. Haven't thought of it in ages. ("fortune -m fornication" comes up empty on my linux system now though.) [1] https://linux.die.net/man/6/fortune https://linux.die.net/man/6/fortune
    - nobody9999 4y ago
      >Huh, I'm pretty sure I first encountered this California joke from some variant of fortune[1] back in the '80s. Haven't thought of it in ages. ("fortune -m fornication" comes up empty on my linux system now though.) Yep. That's where I remember that joke from too. A DDG search returned the link I used as the first result. I'd note that when looking for fortunes (ala fortune(6), to which you refer), the following sites are often useful: https://motd.ambians.com/ https://motd.ambians.com/ http://fortunes.cat-v.org/ http://fortunes.cat-v.org/ https://bsdfortune.com/ https://bsdfortune.com/ Edit: fixed man page section for fortune and formatting.
  - w0mbat 4y ago
    Thanks! I was lying when I said the original article was interesting. Once I saw that stunning surname I could think of nothing else, didn’t retain a word of the article at all.
kyrra 4y ago
Googler, options are my own. This is a great write-up. As someone who has had to deal with backend subsetting a bunch in the past, this is such an interesting read. One thing interesting about Google's scale and this architecture is that if you use classic firewalls that end up having connection tracking in them, you can easily overload that connection tracking table. M x k connections can balloon that connection count given the number of replicas some services have. If you like write-ups like this, there is a great 2016 acm paper by Google on how it does source control: https://cacm.acm.org/magazines/2016/7/204032-why-google-stores-billions-of-lines-of-code-in-a-single-repository/fulltext https://cacm.acm.org/magazines/2016/7/204032-why-google-stor...
- bushbaba 4y ago
  Conntrack tables filling up are also a challenge with k8s at very, very, very large scale.
  - jeffbee 4y ago
    Any kind of "smart" thing in your network will eventually hit a scaling limit. The end-to-end principle has to be given due respect. Only the edge of your system has the necessary resources to participate in it. As the scale becomes more extreme, even the kernel of a machine running 100s of k8s pods (or borg tasks) starts to look more like the center of your network and less like the edge of it. The trend is to move as many things as possible out of the kernel and into user processes, including network policy, quota, pacing, and the whole TCP stack too.
fh973 4y ago
> Google services run on Borg, the company's cluster management software. Thanks for confirming that this is still the case.
kerneis 4y ago
There are several points in the article where the examples didn't make sense at all to me. Overall an interesting article, but I'm either a bit dense this morning, or it's sloppy in the details and explanations For instance, in table 3, it looks like they excluded backend tasks {0,1} (for frontend tasks {0, 1}) then {2,3} (for frontend tasks {2,3}) in the N=10 case, but backend tasks {1,2} then {3,4} in the N=11. Why the discrepancy? I get that it helps them make the point about task 3 changing subset, but it's inconsistent with excluding left-overs in a round-robin fashion presented in the previous paragraph. Another sentence that I couldn't make sense of is: "If these [tasks 2 and 4] carry over to the subset of the next frontend task, you might get the shuffled backend tasks [7, 2, 0, 8, 9, 1, 4, 5, 3, 6], but you can't assign backend task 2 to the same frontend task. " The "same frontend task" as what? Obviously note the one task 2 was already assigned to (the most intuitive reading to me), since precisely task 2 was not assigned and is a left-over. But then again, what does this mean?
- kerneis 4y ago
  Other typos: Bbackend; missing math formula in "(for a frontend task m, this is )" — should be ⎣m/L⎦ I guess. Proofreading at ACM seems to be lacking.
- joatmon-snoo 4y ago
  > in table 3 Figure 3 is an (arbitrary) example of round-robin sunsetting with randomized sunset ordering. The point is to demonstrate how bad backend churn is with this algorithm, by inspecting a normal example of the decisions this algorithm makes. > The "same frontend task" as what? [...] what does this mean? It's not phrased great, but it's also tricky to communicate. My read is this: given backend shuffles [9, 1, 3, 0, 8, 6, 5, 7, 2, 4], [7, 2, 0, 8, 9, 1, 4, 5, 3, 6], if you combine these shuffles to choose a backend assignment, you end up with subsets {9, 1, 3, 0}, {8, 6, 5, 7}, {2, 4, 7, 2}, {0, 8, 9, 1}, {4, 5, 3, 6}. That third subset means the third frontend only has a subset of three backends, even though you want it to have four. The rest is reductio ad absurdum- reasoning through the ways you might fix this, and explaining why they in turn don't work. (I believe there's also an implicit assumption about the requirement that the final algorithm require no dynamic/runtime coordination, only static before-the-fact coordination amongst the front ends, i.e. agreement on a hash seed for a given subset, and say which hashing strategy the front ends would use).
tuananh 4y ago
why do they call it "subsetting" vs "load balancing"? is there difference between the 2 terms?
- kccqzy 4y ago
  Subsetting is literally part of load balancing. It literally means to ask the client to choose a subset of the available servers and load balance among them. At Google's scale of RPC systems, there would be way too many connections if every client connects to every server.
- detaro 4y ago
  See the linked chapter from the SRE book: https://sre.google/sre-book/load-balancing-datacenter/#limiting-the-connections-pool-with-subsetting-K7slUv https://sre.google/sre-book/load-balancing-datacenter/#limit...
  - tuananh 4y ago
    > limiting the pool of potential backend tasks with which a client task interacts. so it's like consistent hashing / hash ring?

110 points by yarapavan 4y ago

wilg 4y ago

I thought this was going to be Google automating shutting down their own products. Might be a good idea. Just start a clock for 18 months, shut down the service automatically, and reward the relevant executive with a bonus.

postsantum 4y ago
Sunsetting-based promotion cycle. Manager dies with the product only to be reborn at the higher step of the ladder
sieabahlpark 4y ago

w0mbat 4y ago

nobody9999 4y ago
>"Wankadia" is an intriguing surname, combining as it does "Arcadia", the ancient Greek idea of a rural utopia and "Wank". This[0]: CALIFORNIA: From Latin 'calor', meaning "heat" (as in English 'calorie' or Spanish 'caliente'); and 'fornia', for "sexual intercourse" or "fornication." Hence: Tierra de California, "the land of hot sex." Should be right up your alley (yes, there's a double entendre there), friend. :) Sadly, your sense of humor (and mine, for that matter) isn't very popular around here. And more's the pity. [0] http://www.quotationspage.com/quote/23088.html http://www.quotationspage.com/quote/23088.html
- smcameron 4y ago
  Huh, I'm pretty sure I first encountered this California joke from some variant of fortune[1] back in the '80s. Haven't thought of it in ages. ("fortune -m fornication" comes up empty on my linux system now though.) [1] https://linux.die.net/man/6/fortune https://linux.die.net/man/6/fortune
  - nobody9999 4y ago
    >Huh, I'm pretty sure I first encountered this California joke from some variant of fortune[1] back in the '80s. Haven't thought of it in ages. ("fortune -m fornication" comes up empty on my linux system now though.) Yep. That's where I remember that joke from too. A DDG search returned the link I used as the first result. I'd note that when looking for fortunes (ala fortune(6), to which you refer), the following sites are often useful: https://motd.ambians.com/ https://motd.ambians.com/ http://fortunes.cat-v.org/ http://fortunes.cat-v.org/ https://bsdfortune.com/ https://bsdfortune.com/ Edit: fixed man page section for fortune and formatting.
- w0mbat 4y ago
  Thanks! I was lying when I said the original article was interesting. Once I saw that stunning surname I could think of nothing else, didn’t retain a word of the article at all.

kyrra 4y ago

Googler, options are my own. This is a great write-up. As someone who has had to deal with backend subsetting a bunch in the past, this is such an interesting read. One thing interesting about Google's scale and this architecture is that if you use classic firewalls that end up having connection tracking in them, you can easily overload that connection tracking table. M x k connections can balloon that connection count given the number of replicas some services have. If you like write-ups like this, there is a great 2016 acm paper by Google on how it does source control: https://cacm.acm.org/magazines/2016/7/204032-why-google-stores-billions-of-lines-of-code-in-a-single-repository/fulltext https://cacm.acm.org/magazines/2016/7/204032-why-google-stor...

bushbaba 4y ago
Conntrack tables filling up are also a challenge with k8s at very, very, very large scale.
- jeffbee 4y ago
  Any kind of "smart" thing in your network will eventually hit a scaling limit. The end-to-end principle has to be given due respect. Only the edge of your system has the necessary resources to participate in it. As the scale becomes more extreme, even the kernel of a machine running 100s of k8s pods (or borg tasks) starts to look more like the center of your network and less like the edge of it. The trend is to move as many things as possible out of the kernel and into user processes, including network policy, quota, pacing, and the whole TCP stack too.

fh973 4y ago

> Google services run on Borg, the company's cluster management software. Thanks for confirming that this is still the case.

kerneis 4y ago

There are several points in the article where the examples didn't make sense at all to me. Overall an interesting article, but I'm either a bit dense this morning, or it's sloppy in the details and explanations For instance, in table 3, it looks like they excluded backend tasks {0,1} (for frontend tasks {0, 1}) then {2,3} (for frontend tasks {2,3}) in the N=10 case, but backend tasks {1,2} then {3,4} in the N=11. Why the discrepancy? I get that it helps them make the point about task 3 changing subset, but it's inconsistent with excluding left-overs in a round-robin fashion presented in the previous paragraph. Another sentence that I couldn't make sense of is: "If these [tasks 2 and 4] carry over to the subset of the next frontend task, you might get the shuffled backend tasks [7, 2, 0, 8, 9, 1, 4, 5, 3, 6], but you can't assign backend task 2 to the same frontend task. " The "same frontend task" as what? Obviously note the one task 2 was already assigned to (the most intuitive reading to me), since precisely task 2 was not assigned and is a left-over. But then again, what does this mean?

kerneis 4y ago
Other typos: Bbackend; missing math formula in "(for a frontend task m, this is )" — should be ⎣m/L⎦ I guess. Proofreading at ACM seems to be lacking.
joatmon-snoo 4y ago
> in table 3 Figure 3 is an (arbitrary) example of round-robin sunsetting with randomized sunset ordering. The point is to demonstrate how bad backend churn is with this algorithm, by inspecting a normal example of the decisions this algorithm makes. > The "same frontend task" as what? [...] what does this mean? It's not phrased great, but it's also tricky to communicate. My read is this: given backend shuffles [9, 1, 3, 0, 8, 6, 5, 7, 2, 4], [7, 2, 0, 8, 9, 1, 4, 5, 3, 6], if you combine these shuffles to choose a backend assignment, you end up with subsets {9, 1, 3, 0}, {8, 6, 5, 7}, {2, 4, 7, 2}, {0, 8, 9, 1}, {4, 5, 3, 6}. That third subset means the third frontend only has a subset of three backends, even though you want it to have four. The rest is reductio ad absurdum- reasoning through the ways you might fix this, and explaining why they in turn don't work. (I believe there's also an implicit assumption about the requirement that the final algorithm require no dynamic/runtime coordination, only static before-the-fact coordination amongst the front ends, i.e. agreement on a hash seed for a given subset, and say which hashing strategy the front ends would use).

tuananh 4y ago

why do they call it "subsetting" vs "load balancing"? is there difference between the 2 terms?

kccqzy 4y ago
Subsetting is literally part of load balancing. It literally means to ask the client to choose a subset of the available servers and load balance among them. At Google's scale of RPC systems, there would be way too many connections if every client connects to every server.
detaro 4y ago
See the linked chapter from the SRE book: https://sre.google/sre-book/load-balancing-datacenter/#limiting-the-connections-pool-with-subsetting-K7slUv https://sre.google/sre-book/load-balancing-datacenter/#limit...
- tuananh 4y ago
  > limiting the pool of potential backend tasks with which a client task interacts. so it's like consistent hashing / hash ring?