Multi-Leader Replication

Einsteinder — Thu, 18 Jul 2024 16:57:25 +0000

	single-leader	multi-leader
Performance	significant latency	network delay hidden from users
Tolerance of datacenter outages	failover	each datacenter operating independently

Solution for multi-leader confliction:

last write wins (LWW)
predefined the replica ranking
merge values together
record the conflict, resolve later

Problems with Replication Lag

Einsteinder — Thu, 18 Jul 2024 15:26:32 +0000

Here are some example problems and possible solutions for replication lag

1. Post not instantly show

when user post the comment under a passage, he want to see it immediately, otherwise, he would think something wrong. When we user asynchronous replication, the comment may not be replicated to follower nodes. So we need to implement the read-after-write consistency to avoid it.

we assume the leader node always be synchronized with the action, based on it we can expect user will read something they've edit. for example, a user will edit his own profile instead of others, they can always read it from the leader node to make sure the read-after-write consistency.
keep track of the last updated time, for example user edited on 3:15, during 3:15 - 3:16 we always read from leader node.
client can remember of timestamp of write, read from whoever has it or wait util it has

2. Monotonic Reads

Users may not expect to see something they've seen is disappeared.

It happens when user read from different replicas, one have small lag, and the other have a greater lag.

The solution for this would be ask user read from same replica always, it may not read the latest data, but they will see the data sequentially

DFS and BFS

Einsteinder — Mon, 15 Jul 2024 17:22:16 +0000

Today I will start refreshing my computer science knowledge by writing tech blogs.

Start from Leetcode 865.
It's exactly same with Leetcode 1123

read the question clearly before starting coding, I thought there was only one deepest node in the tree, so I didn't think this was a problem of the LCA. the key to solving this problem is to check the left and right subtrees if they have the same level, if yes that means their parent is the smallest subtree. There are two conditions: a) when the 2 nodes are at the same deepest level, then their parent node is the smallest subtree.

b) if there is only one node is the deepest level, then it self is the smallest subtree

The first way I can think of is recursive, here is the code:

class Solution:
    max_level = 0
    res = None

    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        level = 0
        self.dfs(root,level)
        return self.res


    def dfs(self,node,current_level):
        if not node:
            return current_level
        else:
            l_next_level = self.dfs(node.left,current_level+1)

            r_next_level = self.dfs(node.right,current_level+1)

            max_cur_level = max(l_next_level,r_next_level)

            self.max_level = max(self.max_level,max_cur_level)

            if self.max_level == l_next_level and self.max_level==r_next_level:
                self.res = node

            return  max_cur_level

Since we need to keep track of the same level of the deepest nodes and find their common ancestor, it seems hard to simulate it with a iterative dfs, if you can, please leave the comment.

I try to use BFS to solve the same problem:

    def bfs(self,node):
        leftmost_node = None
        rightmost_node = None
        q = [node]
        while q:
            q_size = len(q)
            for i in range(q_size):
                the_node = q.pop()
                if i == 0:leftmost_node = the_node
                if i == q_size - 1 : rightmost_node = the_node
                if the_node.left: q.insert(0,the_node.left)
                if the_node.right:q.insert(0,the_node.right)
        self.res = self.lca(node,leftmost_node,rightmost_node)
        return 
    def lca(self,root,p,q):
        if not root:return
        if root==p or root ==q: return root
        left = self.lca(root.left,p,q)
        right = self.lca(root.right,p,q)
        if not left:
            return right
        elif not right:
            return left
        else:
            return root

Based on this problem, let's explore more about dfs and bfs.

Let's see Leetcode 200
This is a classic problem that can be solved by dfs and bfs. For dfs, the idea is we need to start from all points on the map and explore all the islands that can be reached. The basic operation is to check the four directions around the point to see if there are "1", if yes go into that point and check its four directions, and repeat this until no "1" is found around. Here is the code:

class Solution:
    directions = [
        [0,1], #right
        [1,0], #down
        [-1,0],#up
        [0,-1],#left
    ]
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    grid[i][j] = "0"
                    count += 1
                    self.dfs(grid,i,j)
        return count


    def dfs(self,grid,i,j):
        for m,n in self.directions:
            if  0<= i+m < len(grid) and 0<= j+n <len(grid[0]) and grid[i+m][j+n] == "1":
                grid[i+m][j+n] = "0"
                self.dfs(grid,i+m,j+n)

In this code, we changed the visited points in place to "0", if we don't want to change the the given grid, we can also store the visited points like this:

    def numIslands_no_self(self, grid: List[List[str]]) -> int:
        def dfs(i,j):
            visited.add((i, j))
            for m,n in self.directions:
                if  0<= i+m < len(grid) and 0<= j+n <len(grid[0]) and grid[i+m][j+n] == "1" and (i+m,j+n) not in visited:
                    dfs(i+m,j+n)

        if not grid or not grid[0]: return 0    
        visited = set()        
        count = 0
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                print(54,visited)
                if grid[row][col] == "1" and (row,col) not in visited:
                    count += 1
                    dfs(row,col)

        return count

You may wonder why I named the function "no_self". At the very beginning, I used a global variable to save the visited points, logically speaking, it's no different from the local variable, but when I submitted it, it couldn't pass the test. I figured that caused by the global variable is long-lived in memory, when a new test case comes in, the old visited points are still there, and that's why it cannot go through. So I recommend we all use the local variable here.

Next, I will try to use BFS to solve the problem. The key of BFS will queue, and iteration will be like the wave spread from the middle.

    def numIslands(self, grid: List[List[str]]) -> int:
        def bfs():
            if not grid or not grid[0]: return 0
            count = 0
            q = []
            for row in range(len(grid)):
                for col in range(len(grid[0])):

                    if grid[row][col]=="1":
                        count += 1
                        q.insert(0,(row,col))


                    while q:
                        i,j = q. pop()
                        if grid[i][j] == "1":
                            grid[i][j] = "0"
                            for m,n in self.directions:
                                if  0<= i+m < len(grid) and 0<= j+n <len(grid[0]) and grid[i+m][j+n] == "1":
                                    q.insert(0,(i+m,j+n))
            return count
        return bfs()

Let's try another one Leetcode 130
the key to this problem is to find all O at the edge of the board and all O connected to them cannot be converted. All other O needs to convert to X, here is the implementation:

class Solution:
    directions = [
        [0,-1],
        [0,1],
        [1,0],
        [-1,0]
    ]
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def dfs(i,j):
            if board[i][j] in ["#","X"]: return
            board[i][j] = "#"
            for m,n in self.directions:
                if 0 <= i+m <len(board) and 0<= j+n <len(board[0]):
                    dfs(i+m,j+n)



        if not board or not board[0]: return
        for i in range(len(board)):
            for j in range(len(board[0])):
                if i == 0 or i == len(board) - 1 or j == 0 or j == len(board[0]) - 1:
                    dfs(i,j)

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "#":
                    board[i][j] = "O"

DEV Community: Einsteinder

Multi-Leader Replication

Problems with Replication Lag

1. Post not instantly show

2. Monotonic Reads

DFS and BFS