Multi tier load balancing with Linux

Multi-tier load-balancing with Linux

Summary in my words:
 

Multiple L7 load balancers talk to multiple backend servers. Backend servers don't have to worry about path MTU discovery, TCP congestion control algorithms, avoidance of the TIME-WAIT state and various other low-level details. But how do you load balance the L7 LBs?

L3 load balancing can help. All L7 LBs can advertise the same IP to their nearby routers. With a combination of ECMP and BGP protocols, routers can load balance the packets to L7 LBs. But adding/removing an L7 LB in this setup breaks existing connections(which is problematic for long connections like downloads) since routers don't use consistent hashing. Also, if one router becomes unavailable, other routers may forward the packets to a different LB since every router decides individually.

To mitigate this, use L4 LBs between L3 and L7. The purpose of this tier is to ensure that all members take same scheduling decision for an incoming packet based on destination IP and port. Consistent hashing is used to route packets to L7 LBs so removal/addition of an L7 LB isn't problematic. Additionally L7 LBs return response directly to L3 routers(DSR) to improve perf.

So, routers use ECMP + BGP to route packets to L4 LBs(all of which advertise the same IP). L4 LBs use consistent hashing scheme to talk to L7 LBs. And L7 LBs return the response directly to L3.

Actual Snippets from the article:

A combination of:
 

1. ECMP routing
2. Stateless L4 load-balancing
3. Stateful L7 load-balancing

L7 (Last Tier): 

Working in the highest layers of the OSI model, it can also offer additional services, like TLS-termination, HTTP routing, header rewriting, rate-limiting of unauthenticated users, and so on. Being stateful, it can leverage complex load-balancing algorithm. Being the first point of contact with backend servers, it should ease maintenances and minimize impact during daily changes.

It also terminates client TCP connections. This introduces some loose coupling between the load-balancing components and the backend servers with the following benefits:

1. connections to servers can be kept open for lower resource use and latency,
2. requests can be retried transparently in case of failure,
3. clients can use a different IP protocol than servers,
4. and servers do not have to care about path MTU discovery, TCP congestion control algorithms, avoidance of the TIME-WAIT state and various other low-level details.

As is, this solution is not complete. We have just moved the availability and scalability problem somewhere else. How do we load-balance the requests between the load-balancers?

First tier: ECMP routing (L3)
 

On most modern routed IP networks, redundant paths exist between clients and servers. For each packet, routers have to choose a path. When the cost associated to each path is equal, incoming flows are load-balanced among the available destinations. This characteristic can be used to balance connections among available load-balancers.

If we assume you already have BGP-enabled routers available, ExaBGP is a flexible solution to let the load-balancers advertise their availability.

Unfortunately, this solution is not resilient when an expected or unexpected change happens. Notably, when adding or removing a load-balancer, the number of available routes for a destination changes. The hashing algorithm used by routers is not consistent and flows are reshuffled among the available load-balancers, breaking existing connections.

Moreover, each router may choose its own routes. When a router becomes unavailable, the second one may route the same flows differently which again breaks existing connections.

If you think this is not an acceptable outcome, notably if you need to handle long connections like file downloads, video streaming or websocket connections, you need an additional tier. Keep reading!

Second tier: L4 load-balancing

The second tier is the glue between the stateless world of IP routers and the stateful land of L7 load-balancing. It is implemented with L4 load-balancing. The terminology can be a bit confusing here: this tier routes IP datagrams (no TCP termination) but the scheduler uses both destination IP and port to choose an available L7 load-balancer. The purpose of this tier is to ensure all members take the same scheduling decision for an incoming packet. There are two options:

1. stateful L4 load-balancing with state synchronization across the members,
2. or stateless L4 load-balancing with consistent hashing.

The first option increases complexity and limits scalability. We won’t use it. The second option is less resilient during some changes but can be enhanced with a hybrid approach using a local state.

We use IPVS, a performant L4 load-balancer running inside the Linux kernel, with Keepalived, a frontend to IPVS with a set of healthcheckers to kick out an unhealthy component. IPVS is configured to use the Maglev scheduler, a consistent hashing algorithm from Google. Among its family, this is a great algorithm because it spreads connections fairly, minimizes disruptions during changes and is quite fast at building its lookup table. Finally, to improve performance, we let the last tier—the L7 load-balancers—sends back answers directly to the clients without involving the second tier—the L4 load-balancers. This is referred to as direct server return (DSR) or direct routing (DR).
   

With such a setup, we expect packets from a flow to be able to move freely between the components of the first two tiers while sticking to the same L7 load-balancer.

Tier 0: DNS load-balancing

Optionally, you can add DNS load-balancing to the mix. This is useful either if your setup is spanned across multiple datacenters, or multiple cloud regions, or if you want to break a large load-balancing cluster into smaller ones. It is not intended to replace the first tier as it doesn’t share the same characteristics: load-balancing is unfair (it is not flow-based) and recovery from a failure is slow.

Interview Questions

Counting sort

https://leetcode.com/problems/campus-bikes/

https://leetcode.com/problems/height-checker/

DSU
https://leetcode.com/problems/sentence-similarity-ii/ (DFS as well)

https://leetcode.com/problems/number-of-islands-ii/

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

Searching in Sorted 2-D array
1. https://leetcode.com/problems/search-a-2d-matrix-ii/
2. https://leetcode.com/problems/search-a-2d-matrix/
3. https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

DAG/Topological sort
4. https://leetcode.com/problems/course-schedule/
5. https://leetcode.com/problems/course-schedule-ii
6. https://leetcode.com/problems/alien-dictionary/

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/ (OR DFS with memo/DP)

https://leetcode.com/problems/all-paths-from-source-lead-to-destination/

https://leetcode.com/problems/network-delay-time/

(diagram gives the impression of DAG, but it's DG => Directed and cyclic, find the shortest path from source to all)

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/

Trie or other string match
7. https://leetcode.com/problems/add-and-search-word-data-structure-design/
8. https://leetcode.com/problems/wildcard-matching/ 

https://leetcode.com/problems/stream-of-characters/

https://leetcode.com/problems/design-search-autocomplete-system/
Similar:
https://leetcode.com/problems/word-ladder/
https://leetcode.com/problems/implement-magic-dictionary/

Heap
9. https://leetcode.com/problems/top-k-frequent-elements/
10. https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/

https://leetcode.com/problems/mean-of-array-after-removing-some-elements/

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/

non heap approach as well

Graph
11. DFS => https://leetcode.com/problems/accounts-merge/
12. 2D Matrix BFS => https://leetcode.com/problems/walls-and-gates/
13. DFS => https://leetcode.com/problems/is-graph-bipartite
14. DFS => https://leetcode.com/problems/similar-string-groups/
15. BFS => https://leetcode.com/problems/word-ladder/
16. BFS => https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
17. DFS => https://leetcode.com/problems/delete-nodes-and-return-forest/

https://leetcode.com/problems/android-unlock-patterns/  (And permutation generation)

BFS https://leetcode.com/problems/sliding-puzzle/

BFS https://leetcode.com/problems/evaluate-division/

Modified BFS https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
DFS => https://leetcode.com/problems/path-with-maximum-gold/ (backtracking)

DFS => https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/

https://leetcode.com/problems/find-root-of-n-ary-tree/

DFS => https://leetcode.com/problems/letter-tile-possibilities/

https://leetcode.com/problems/flower-planting-with-no-adjacent/

Matrix
18. https://leetcode.com/problems/range-sum-query-2d-immutable/

build upon this https://leetcode.com/problems/matrix-block-sum/
19. https://leetcode.com/problems/diagonal-traverse/
20. BFS => https://leetcode.com/problems/shortest-path-in-binary-matrix/
21. BFS => https://leetcode.com/problems/swim-in-rising-water
22. BFS => https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/
23. BFS => https://leetcode.com/problems/shortest-distance-from-all-buildings/

https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/

https://leetcode.com/problems/toeplitz-matrix/

Linked Lists
24. https://leetcode.com/problems/next-greater-node-in-linked-list/
25. https://leetcode.com/problems/merge-two-sorted-lists/
26. https://leetcode.com/problems/reorder-list/
27. https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/
28. https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

https://leetcode.com/problems/print-immutable-linked-list-in-reverse/

Stack
29. https://leetcode.com/problems/simplify-path/
30. Parentheses => https://leetcode.com/problems/valid-parentheses/

 https://leetcode.com/problems/brace-expansion/
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

https://leetcode.com/problems/remove-outermost-parentheses/

Interval merging/intersection/Task Scheduling
31. https://leetcode.com/problems/task-scheduler/

32. https://leetcode.com/problems/non-overlapping-intervals/ - sort by end time ascending, maximize number of tasks finished
33. https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons - same as above, sort by end time

34. https://leetcode.com/problems/interval-list-intersections/
35. https://leetcode.com/problems/merge-intervals/ - start time ascending sort, keep merging with top of the stack
36. https://leetcode.com/problems/meeting-rooms/
https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/description/

sort by start day + minHeap OR sort by end day and iterate over day interval.

These 4 problems have exact same solution:
37. https://leetcode.com/problems/meeting-rooms-ii/
38. https://leetcode.com/problems/my-calendar-i/
39. https://leetcode.com/problems/my-calendar-ii/
40. https://leetcode.com/problems/my-calendar-iii/

41. https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Binary Tree/Binary Search Tree
https://leetcode.com/problems/binary-tree-coloring-game/

https://leetcode.com/problems/all-possible-full-binary-trees/

https://leetcode.com/problems/peak-index-in-a-mountain-array/
https://leetcode.com/problems/find-in-mountain-array/

https://leetcode.com/problems/correct-a-binary-tree/

42. Inorder Traversal => https://leetcode.com/problems/binary-search-tree-iterator/
43. Inorder Traversal => https://leetcode.com/problems/validate-binary-search-tree/
44. InOrder => https://leetcode.com/problems/kth-smallest-element-in-a-bst
45. InOrder => https://leetcode.com/problems/increasing-order-search-tree

46. PostOrder => https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
47. PostOrder => https://leetcode.com/problems/range-sum-of-bst/
48. PostOrder => https://leetcode.com/problems/flatten-binary-tree-to-linked-list
49. DFS (backtracking) https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
50. DFS => https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves
51. DFS https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
52. BFS => https://leetcode.com/problems/check-completeness-of-a-binary-tree/
53. BFS => https://leetcode.com/problems/binary-tree-right-side-view/
54. https://leetcode.com/problems/binary-tree-vertical-order-traversal/
55. https://leetcode.com/problems/closest-binary-search-tree-value/
56. https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
57. https://leetcode.com/problems/minimum-depth-of-binary-tree/
58. https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
59. https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/
60. https://leetcode.com/problems/split-bst/
61. https://leetcode.com/problems/populating-next-right-pointers-in-each-node
62. https://leetcode.com/problems/univalued-binary-tree
63. https://leetcode.com/problems/diameter-of-binary-tree

Binary Search
64. https://leetcode.com/problems/missing-element-in-sorted-array/
65. https://leetcode.com/problems/random-pick-with-weight/
66. https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
67. https://leetcode.com/problems/first-bad-version/
68. https://leetcode.com/problems/fixed-point/
69. https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix

https://leetcode.com/problems/find-peak-element/


Continuous SubArray/SubString/SubSequence
70. https://leetcode.com/problems/subarray-sum-equals-k/
71. https://leetcode.com/problems/continuous-subarray-sum/
72. https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
73. https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

similar to https://leetcode.com/problems/fruit-into-baskets/
74. https://leetcode.com/problems/find-all-anagrams-in-a-string/solution/
75. https://leetcode.com/problems/permutation-in-string/
76. https://leetcode.com/problems/max-consecutive-ones-iii/
77. https://leetcode.com/problems/longest-consecutive-sequence

https://leetcode.com/problems/sliding-window-maximum/

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

https://leetcode.com/problems/shortest-way-to-form-string/

DP
78. https://leetcode.com/problems/partition-equal-subset-sum
79. https://leetcode.com/problems/minimum-cost-for-tickets/
80. https://leetcode.com/problems/longest-arithmetic-sequence/
81. https://leetcode.com/problems/decode-ways/
82. https://leetcode.com/problems/minimum-knight-moves/
83. https://leetcode.com/problems/target-sum/
84. https://leetcode.com/problems/maximal-square
85. https://leetcode.com/problems/word-break/
86. https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix
87. https://leetcode.com/problems/knight-probability-in-chessboard/
88. https://leetcode.com/problems/valid-palindrome-iii/
89. https://leetcode.com/problems/longest-palindromic-subsequence
90. https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/

91. https://leetcode.com/problems/how-many-apples-can-you-put-into-the-basket
92. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ (Check i, ii as well)
93. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

https://leetcode.com/problems/perfect-squares/

https://leetcode.com/problems/campus-bikes-ii/

https://leetcode.com/problems/cherry-pickup-ii/

https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/

https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/

https://leetcode.com/problems/odd-even-jump/

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

contrast with https://leetcode.com/problems/count-submatrices-with-all-ones/

Array/List manipulation
94. https://leetcode.com/problems/move-zeroes/
95. https://leetcode.com/problems/nested-list-weight-sum-ii/ - also do (i)
96. https://leetcode.com/problems/squares-of-a-sorted-array/
97. https://leetcode.com/problems/product-of-array-except-self/

similar to https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/
98. https://leetcode.com/problems/maximum-swap/
99. https://leetcode.com/problems/intersection-of-three-sorted-arrays/
100. https://leetcode.com/problems/remove-duplicates-from-sorted-array
101. https://leetcode.com/problems/single-row-keyboard/
102. https://leetcode.com/problems/decompress-run-length-encoded-list/
103. https://leetcode.com/problems/sort-array-by-parity-ii/
104. https://leetcode.com/problems/monotonic-array/

https://leetcode.com/problems/wiggle-sort/

Deep Copy
105. https://leetcode.com/problems/clone-graph/
106. https://leetcode.com/problems/copy-list-with-random-pointer/

Arithmetic operations/Math
107. https://leetcode.com/problems/multiply-strings/
108. https://leetcode.com/problems/divide-two-integers/ (Read the Solution section, quite good)
109. https://leetcode.com/problems/bulb-switcher/
110. https://leetcode.com/problems/fraction-to-recurring-decimal/
111. https://leetcode.com/problems/basic-calculator-ii/
112. Geometry => https://leetcode.com/problems/minimum-area-rectangle
113. https://leetcode.com/problems/largest-number/
114. https://leetcode.com/problems/projection-area-of-3d-shapes/
115. https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero
116. https://leetcode.com/problems/plus-one/

https://leetcode.com/problems/add-to-array-form-of-integer/

Generating permutations/combinations
117. https://leetcode.com/problems/next-permutation/
118. https://leetcode.com/problems/letter-combinations-of-a-phone-number/ (cross product of lists)
119. https://leetcode.com/problems/subsets (power set)

https://leetcode.com/problems/di-string-match/

String manipulation

120. https://leetcode.com/problems/camelcase-matching/
121. https://leetcode.com/problems/goat-latin/
122. https://leetcode.com/problems/custom-sort-string/
123. https://leetcode.com/problems/add-bold-tag-in-string/
124. Parentheses => https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

125. https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
126. Parentheses => https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
127. https://leetcode.com/problems/remove-invalid-parentheses/
128. Parentheses => https://leetcode.com/problems/generate-parentheses/
129. https://leetcode.com/problems/reorganize-string/
130. https://leetcode.com/problems/find-and-replace-in-string/
131. https://leetcode.com/problems/implement-magic-dictionary/
132. https://leetcode.com/problems/group-shifted-strings/
133. https://leetcode.com/problems/subdomain-visit-count/
134. https://leetcode.com/problems/jewels-and-stones/
135. https://leetcode.com/problems/is-subsequence/
136. https://leetcode.com/problems/string-transforms-into-another-string/

similar to https://leetcode.com/problems/isomorphic-strings/

https://leetcode.com/problems/decode-string/

https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/

https://leetcode.com/problems/long-pressed-name/

https://leetcode.com/problems/repeated-substring-pattern/

Others
137. https://leetcode.com/problems/exam-room/

start from https://leetcode.com/problems/maximize-distance-to-closest-person/
138. https://leetcode.com/problems/next-closest-time
139. https://leetcode.com/problems/validate-ip-address/
140. https://leetcode.com/problems/unique-email-addresses/
141. https://leetcode.com/problems/flatten-nested-list-iterator/
142. https://leetcode.com/problems/logger-rate-limiter/
143. https://leetcode.com/problems/random-pick-index/
144. https://leetcode.com/problems/find-the-celebrity

145. https://leetcode.com/problems/3sum/

https://leetcode.com/problems/sentence-screen-fitting/

https://leetcode.com/problems/alphabet-board-path/

https://leetcode.com/problems/shortest-distance-to-target-color/

https://leetcode.com/problems/positions-of-large-groups/

https://leetcode.com/problems/robot-return-to-origin/

https://leetcode.com/problems/expressive-words/

https://leetcode.com/problems/rearrange-spaces-between-words/

https://leetcode.com/problems/confusing-number-ii/

https://leetcode.com/problems/bulls-and-cows/

https://leetcode.com/problems/design-phone-directory/

https://leetcode.com/problems/snapshot-array/

https://leetcode.com/problems/longest-absolute-file-path/

https://leetcode.com/problems/license-key-formatting/

https://leetcode.com/problems/k-empty-slots/

permutation combination generation

n choose k from array
https://stackoverflow.com/a/16256122/49560

all permutations of a string
https://stackoverflow.com/a/4240323/49560

all permutations of an array
https://stackoverflow.com/a/14444037/49560