记录：2022-9-29 腐烂的橘子 大厂实现分布式Id的方法

学习时间：2022-9-29

学习内容

1、leetcode

994. 腐烂的橘子

思路

我的思路是每一次拿到所有的同一批次的坏橘子，然后每一次都去增加遍历值 这个值就是要的ans
但是有几点需要注意：

if(queue.size() == 0){
    continue;
}
当不能继续往下后，ans不能继续加了

代码

class Solution {
    public int orangesRotting(int[][] grid) {
        //拿到所有坏橘子一起做BFS
        LinkedList<int[]> queue = new LinkedList<int[]>();
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        boolean isNoFresh = true;
        //初始化
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(grid[i][j] == 2){
                    queue.add(new int[]{i,j});
                }
                if(grid[i][j] == 1){
                    isNoFresh = false;
                }
            }
        }
        int ans = -1;
        //若初始就没有新鲜橘子，则返回0
        if(isNoFresh){
            return 0;
        }
        while(!queue.isEmpty()){
            LinkedList<int[]> list = new LinkedList<int[]>();
            while(!queue.isEmpty()){
                list.add(queue.poll());
            }
            //将同一批次的橘子全部poll
            while(!list.isEmpty()){
                int[] node = list.poll();
                int row = node[0];
                int col = node[1];
                if(row<0||col<0||row>=m||col>=n||grid[row][col]==0||visited[row][col]){
                    continue;
                }
                visited[row][col] = true;
                grid[row][col] = 2;
                queue.add(new int[]{row+1,col});
                queue.add(new int[]{row-1,col});
                queue.add(new int[]{row,col+1});
                queue.add(new int[]{row,col-1});
            }
            if(queue.size() == 0){
                continue;
            }
            ans++;
        }
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(!visited[i][j]&&grid[i][j] == 1){
                    return -1;
                }
            }
        }
        return ans;
    }
}

更优解

首先把每个腐烂的橘子入队，队中的每个元素都是一个长度为 3 的一维数组，分别装烂橘子的行数、列数和腐烂的时间，时间初始为0。
在遍历的同时用 fresh 变量记录新鲜的橘子数。
然后从每个 2 开始 一圈一圈的向周围的 1 扩散，已经扩散过的烂橘子从队列中拿掉，刚被扩散的新鲜橘子放入队列中，同时记录扩散的时间（在上一个烂橘子腐烂的时间基础上加 1 ）。
最后，如果队列中的烂橘子都已经全部拿出，新鲜橘子的数量仍然不为 0 ，则返回 -1 （有新鲜橘子不能不能扩散到），否则，返回最后一个腐烂橘子的腐烂时间（即所有橘子腐烂完需要的时间）。

可以说是非常优雅了
我这个代码很冗余，但其实这个长度为3的数组我是想到了的，但没有写出来

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int m = grid.length, n = grid[0].length;
        int fresh = 0, min = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 2) {
                    queue.offer(new int[]{i, j, 0});
                } else if(grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        int[] dx = {1, 0, 0, -1};
        int[] dy = {0, 1, -1, 0};
        while(!queue.isEmpty()) {
            int[] rot = queue.poll();
            int x = rot[0], y = rot[1];
            min = rot[2];
            for(int i = 0; i < 4; i++) {
                int x1 = x + dx[i];
                int y1 = y + dy[i];
                if(x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && grid[x1][y1] == 1) {
                    grid[x1][y1] = 2;
                    fresh--;
                    queue.offer(new int[]{x1, y1, min + 1});
                }
            }
        }
        if(fresh != 0) {
            return -1;
        }
        return min;
    }
}

作者：yi-ge-s
链接：https://leetcode.cn/problems/rotting-oranges/solution/by-yi-ge-s-ulbt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

比较一下，量级是一个量级，我应该做了不少多余操作

2、大厂实现分布式Id的方法

看雪花算法有感，读了一篇博文
一线大厂的分布式唯一 ID 生成方案是什么样的

改造数据库主键自增

利用缓存，把数据放入到JVM缓存中避免多次查询，不过还是有规律的自增

整体流程：
1、【用户服务】在注册一个用户时，需要一个用户ID；会请求【生成ID服务(是独立的应用)】的接口
2、【生成ID服务】会去查询数据库，找到user_tag的id，现在的max_id为0，step=1000
3、【生成ID服务】把max_id和step返回给【用户服务】；并且把max_id更新为max_id = max_id + step，即更新为1000
4、【用户服务】获得max_id=0，step=1000；
5、 这个用户服务可以用ID=【max_id + 1，max_id+step】区间的ID，即为【1，1000】
6、【用户服务】会把这个区间保存到jvm中
7、【用户服务】需要用到ID的时候，在区间【1，1000】中依次获取id，可采用AtomicLong中的getAndIncrement方法。
8、如果把区间的值用完了，再去请求【生产ID服务】接口，获取到max_id为1000，即可以用【max_id + 1，max_id+step】区间的ID，即为【1001，2000】

感觉是一个消费者生产者模式，先在ID生成服务生成，用户服务用到的时候再去取

这个问题的解决需要用到锁，每次max_id变了，都要回写数据库
这个写法还会产生阻塞问题，比如有三个服务里存了300个Id，每个服务中有100个Id
若突然来了很大的ID请求量，就会导致三个服务全被消费完，此时三个服务都去请求数据库，有两个线程会被阻塞，表现为在一段时间内慢，然后恢复正常

双buffer

为解决并发阻塞问题，使用双buffer

1、当前获取ID在buffer1中，每次获取ID在buffer1中获取
2、当buffer1中的Id已经使用到了100，也就是达到区间的10%
3、达到了10%，先判断buffer2中有没有去获取过，如果没有就立即发起请求获取ID线程，此线程把获取到的ID，设置到buffer2中。
4、如果buffer1用完了，会自动切换到buffer2
5、buffer2用到10%了，也会启动线程再次获取，设置到buffer1中
6、依次往返
每次到10%就去获取，避免阻塞，因为一次只有一个线程做这个操作

bizTag+版本号

mysql+趋势递增有另一套方法：每个实例以bizTag申请号，获取步长个的号，号范围从基线值到基线值+步长，通过version控制并发，更新基线值。实例拿到后通过内部线程安全方法消费号，消耗完再取。