soyo的跨机房部署、同城双活、异地多活、9个9高可用博客yuque笔记同步site

ε=(´ο｀*)))唉，学Java的这辈子有了

发表于 更新于 分类于

函数 malloc/calloc/realloc，free

封装得太好，内存对于程序员来说就是一黑箱操作

内存碎片问题很烦

随机的bug大概率跟 内存有关系

如何避免内存碎片的产生？

内存池。

第一个版本，分配的块用链表串起来

分配：找到一个flag=0的块就使用，没有就新建

释放：

第二个版本，解决第一个版本的缺点：内存利用率以及查找性能问题

比链表查找效率高的组件：rbtree,skiplist,btree,hash

根据大小查找 key为内存大小

以下做法buffer出不了while循环

以下做法会出现大量的1k 内存块

解决以上问题，需要引入大块拆成大块，小块拆成大块的做法

发表于 分类于

它是指当我们的Consumer数量发生变动时，kafka会重新分配topic partition给Consumer，以保证每个

Consumer的分区数量尽可能均衡

简单地说就是实现消费者负载均衡

重平衡的3个触发机制：

1、Consumer数量发送变化

2、订阅的partition发生变化

3、订阅的topic发生变化

当kafka集群要出发重平衡机制时，大致的步骤

  1. 暂停消费
  2. 计算分区分配方案
  3. 通知消费者
  4. 重新飞陪分区
  5. 恢复消费

重平衡会造成 Consumer的 STW，我们应该尽量避免触发它

发表于 分类于

ISR，In-Sync Replicas 同步副本拿到意思

在每个kafka中，每个topic partition可以有多个replica。ISR是与Leader replica保持同步的follower

replica集合

可以说ISR机制就是确保数据的可靠性和一致性的

当消息被sender线程发送后，它会先被写入Leader副本，然后再由follower主动轮询Leader同步消息

只有ISR中的所有副本成功接收到并确认了消息后，主副本才会认为消息已经成功提交

ISR列表维护

什么时候follower会被移除出ISR列表

replica.lag.max.messages

在0.9x之前是，表示follower落后Leader这个数就会被移除

这个就有大问题，如果高并发场景，Leader一下子收到几万条消息，那么所有follower都会被驱逐

在0.9x后，

新增了replica.lag.max.ms

表示follower的LEO一直落后Leader超过这个replica.lag.max.ms时间，才会被移除出境

发表于 分类于

HW

高水平位，用于控制哪些消息是对Consumer可读的。一个普通消费者只能“看到”Leader副本上介于Log

Start Offset和HW（不含）之间的所有消息。follower同步完消息后会更新HW

也就是说在HW之前的数据都是已经被所有的Follower所同步，比较安全

HW取自于所有follower副本的 LEO

LEO

Log End Offset。消息的末尾偏移，表示日志下一条待插入消息的位移值。比如当时log文件里有10条

日志，位移值从0开始，那么，第10条消息的位移值就是9。此时，LEO = 10。

follower故障：

follower长时间没和Leader同步，就会被提出ISR（follower同步集合）。待follower恢复后，会读取本地的H

W，然后截取Log上大于HW的部分，进行同步。当该follower的LEO大于HW，即代表follower追上Leader就

会重新加入ISR

Leader故障

Leader故障后，由Controller从 ISR中选取一个follower成为新的Leader。之后为了保证多个follower副本数

剧一致性，其余的follower会将log中高于新Leader的LEO的部分截掉，然后从新的Leader同步数据

比如一个Leader现在有 3个follower，F1：读到了3，F2：读到了5，F3：读到了4。此时HW=min()=3

然后这时候Leader宕机了，F1成为了新的Leader，F2就会丢弃3-5的消息，F4丢弃4-5的消息

那如果F2成为了Leader呢？F1和F2就不会丢？

发表于 更新于 分类于

双端队列区别于普通的队列，可以直接往队列头塞元素，这样可以满足分区内数据有序性，再尝试发送。

DQ由RecordAccumulator维护

一个topic里的partition都会对应一个DQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
    ：:方法内容
    -> ： 方法调用方法

**/

sendProducerRequest():
    //回调
    RequestCompletionHandler callback = response -> handleProduceResponse(response, recordsByPartition, time.milliseconds());
    ->
    handleProduceResponse() ->
        completeBatch() :
            if (canRetry(batch, response, now)) {
                //......
                
                //消息从新入队    
                reenqueueBatch(batch, now);
            }
            reenqueueBatch: this.accumulator.reenqueue(batch, currentTimeMs);
/**
* Re-enqueue the given record batch in the accumulator. In Sender.completeBatch method, we check
* whether the batch has reached deliveryTimeoutMs or not. Hence we do not do the delivery timeout check here.
*/
public void reenqueue(ProducerBatch batch, long now) {
    batch.reenqueued(now);
    Deque<ProducerBatch> deque = getOrCreateDeque(batch.topicPartition);
    synchronized (deque) {
        if (transactionManager != null)
            insertInSequenceOrder(deque, batch);
        else
            deque.addFirst(batch);
    }
}

发表于 更新于 分类于

必看

回溯模版的解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//向数组中的每个整数前添加 '+' 或 '-'

//对于每个节点两种选择： + or -。不能硬套模版
/**
fun dfs():
    for(int i = 0; i < nums.length; i++){
        add
        dfs
        delete
    }
以上是因为每个节点都有多选择 比如 排列，组合


 */

岛屿数量[289]

思路：

1. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    int [][]direct={{1,0},{0,1},{-1,0},{0,-1}};
    public int numIslands(char[][] grid) {
        int res=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                  res++;
                  dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    public void dfs(char [][]grid,int x,int y){
        if(x<0||y<0||x>=grid.length||y>=grid[0].length){
           return;
        }
        if(grid[x][y]=='0'){
           return;
        }
        else {
            //用海水把陆地淹掉，相当于valid数组的作用
            grid[x][y]='0';
        }
        for(int i=0;i<4;i++){
           //四个方向
           int nextX=x+direct[i][0];
           int nextY=y+direct[i][1];
           dfs(grid,nextX,nextY);
        }
    }
}

@週刊少年 时间复杂度BFS会低一点，空间复杂度感觉DFS会好一点（但是要考虑递归调用的堆栈的空间就不好说了）

被问到深度优先和广度优先的差别、计算时间空间复杂度
面试用BFS写出来了，然后让我用并查集再写一个，字节

全排列[277]

思路：

  1. used[i] 用于控制 防止走回头路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    List<List<Integer>> res=new ArrayList<>();
    //存放路径
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean []used=new boolean[nums.length];
        dfs(nums,used);
        return res;
    }
    public void dfs(int []nums,boolean []used){
        if(path.size()==nums.length){
          res.add(new ArrayList<>(path));
        }
        for(int i=0;i<nums.length;i++){
           if(used[i]){
              continue;
           }
           //递归
           path.add(nums[i]);
           used[i]=true;
           dfs(nums,used);
           //回溯
           path.removeLast();
           used[i]=false;
        }
    }
}

时间复杂度：

问题类型 是否需要 startIndex 控制逻辑 示例
排列 Permutation ❌ 不需要 用 used[i] 防止重复选 [1,2] vs [2,1] 都算不同
组合 Combination ✅ 必须 用 startIndex 防止重复，为了防止来回选，必须 保证后面的选择只能从当前元素后面开始。 [1,2] 和 [2,1] 视为相同

全排列 II[57]

去重版的全排列 I，用HashSet存结果集即可

课程表[56]

思路：

  1. spring
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    //k：
    Map<Integer, List<Integer>> graph = new HashMap<>();
    Set<Integer> wait = new HashSet<>();      // 当前正在修的课程（类似 wait 集合）
    Set<Integer> completed = new HashSet<>(); // 已确认可修完的课程（类似缓存）

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建依赖图
        for(int i=0;i<numCourses;i++) graph.put(i, new ArrayList<>());
        for(int[] pre : prerequisites) graph.get(pre[1]).add(pre[0]);

        // 遍历所有课程
        for(int i=0;i<numCourses;i++)
            if(!completed.contains(i) && !dfs(i)) return false;

        return true;
    }

    private boolean dfs(int course) {
        if(wait.contains(course)) return false; // 当前路径已出现 → 有环
        if(completed.contains(course)) return true; // 已确认可完成

        wait.add(course); // 加入 wait 集合（正在修）
        for(int next : graph.get(course)) {
            if(!dfs(next)) return false; // 依赖课程不可修完 → 当前也不可修
        }
        wait.remove(course);       // 移出 wait 集合
        completed.add(course);     // 加入已完成缓存
        return true;
    }
}

交错字符串[27]

单词拆分[64]

思路：

DFS + 记忆化搜索

还是得把回溯树给画出来，才清晰易懂！！！（明天来搞）

https://leetcode.cn/problems/word-break/solutions/302779/shou-hui-tu-jie-san-chong-fang-fa-dfs-bfs-dong-tai/

竟然可以记忆化，说明可以转成DP

判断可能性大概率是 DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    Boolean []memory ;
    public boolean wordBreak(String s, List<String> wordDict) {
        memory = new Boolean[s.length()];
        return dfs(s, 0, wordDict);
    }
    //leetcode7
    //leet code 
    public boolean dfs(String s,int startIndex,List<String> wordDict){
        if(startIndex == s.length()) return true;
        if(memory[startIndex] != null){
            return memory[startIndex];
        }
        for(String word: wordDict){
            int nextStartIndex = startIndex + word.length();
            if(nextStartIndex > s.length()){
                continue;
            }
            //startsWith：s中startIndex开头的子串是否以word开头
            if(s.startsWith(word, startIndex) && dfs(s,nextStartIndex,wordDict)){
                memory[startIndex] = true;
                return true;
            }
        }
        memory[startIndex] = false;
        return false;
    }
}

电话号码的字母组合[19]

思路：

  1. 回溯，最基础的题了。可以细想一下这个递归，最容易的一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[abc]

[iop]
交叉相乘，笛卡尔集

排列何尝不是一种算 笛卡尔集合
[a b c]
[a b c]
[a b c]
abb 只不过递归的集合不断为自己本身

for (int i = 0; i < t.get(tIndex).length(); i++) {
    path.append(t.get(tIndex).charAt(i));
    dfs(tIndex + 1);
    path.deleteCharAt(path.length() - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    Map<Integer, String> map = new HashMap();
    List<String> t = new ArrayList();
    List<String> res = new ArrayList();
    StringBuilder path = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        map.put(1, "");
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");

        for (char c : digits.toCharArray()) {
            t.add(map.get(c - '0'));
        }
        dfs(0);
        return res;
    }

    public void dfs(int tIndex) {
        if (path.length() == t.size()) {
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < t.get(tIndex).length(); i++) {
            path.append(t.get(tIndex).charAt(i));
            dfs(tIndex + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

删除无效的括号[18]

思路

  1. 将左右括号 -+化
  2. 对于path，则在参数中update

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    Set<String> res = new HashSet();
    int max = 0;
    String s;
    int n;
    //最大路径长度
    int maxPathLen = 0;
    public List<String> removeInvalidParentheses(String _s) {
        //左右括号
        int l = 0;
        int r = 0;
        s = _s;
        n = s.length();
        for(char c: s.toCharArray()){
            if(c == '(') l++;
            else if(c == ')') r++;
        }
        //max：最大括号数（单括号）
        max = Math.max(l, r);
        dfs(0, "", 0);
        return new ArrayList(res);
    }
    /**
     * 遍历 _s 字符串，记录有效路径
     * @param curCharIndex 当前遍历的字符下标
     * @param path 遍历时的路径（括号组合字符串）
     * @param score 分数，用于标记左右括号的得分，左则+1，右则-1
     */
    public void dfs(int curCharIndex, String path, int score){
        //不合法情况，0 <= score <= max 
        if(score < 0 || score > max) return;
        
        //当下标等于字符串长度，即遍历完时，则说明搜索完成，保存合法结果到 set
        if(curCharIndex == n){
            //只有score == 0结果才合法，并且当前路径长度要大于最大路径子串的长度才记录或者更新
            //小于最长路径子串就不用更新了
            if(score == 0 && path.length() >= maxPathLen){
                //为什么要有这一步，因为题目要求 删除最小数量的无效括号，换句话说，就是你结果集里的合法字符串要为最长的
                //如果有更长的了，就把前面的clear掉
                if(path.length() > maxPathLen) res.clear();
                
                //更新最大路径子串
                maxPathLen = path.length();
                res.add(path);
            }
            return;
        }
        //当前字符
        char c = s.charAt(curCharIndex);
        
        //对于( ) 都有选和不选两种选择
        if(c == '('){ // 选左括号，score + 1；不选score不变
            dfs(curCharIndex + 1, path + c, score + 1);
            dfs(curCharIndex + 1, path, score);
        }
        else if(c == ')'){// 选左括号，score - 1；不选score不变
            dfs(curCharIndex + 1, path + c, score - 1);
            dfs(curCharIndex + 1, path, score);
        }//选正确字符不变
        else dfs(curCharIndex + 1, path + c, score);
    }
}

戳气球

思路

  1. dfs + 回溯，有一个n层的数组，然后我往下走，戳当前i节点，并在下次递归之前把当前节点置为 -1，防止重复选，curLevel == n时更新结果。但超时，得进行记忆化

回溯树：

画板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    int n;
    int res = 0;
    public int maxCoins(int[] nums) {
        n = nums.length;
        dfs(nums, 0, 0);
        return res;
    }
    public void dfs(int[] nums, int curLevel, int curCoin){
        //回溯：一个n层的数组，我们从第一层走到底n层
        //nums[i] = -1来防止 重复选
        //为什么不是startIndex，这个主要是决定 选元素只能从startINdex后开始选，而不能往回选，对于组合这种 1 2和 2 1是一样的
        if(curLevel == n){
            res = Math.max(res, curCoin);
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == -1){
                continue;
            }
            int midQ = nums[i];
            //左测的气球编号
            int lQ = 1;
            //右侧的气球编号
            int rQ = 1;
            int l = i - 1;
            int r = i + 1;
            while(l >= 0 && nums[l] == -1){
                l--;
            }
            if(l < 0) lQ = 1;
            else lQ = nums[l];
            while(r < nums.length && nums[r] == -1){
                r++;
            }
            if(r >= nums.length) rQ = 1;
            else rQ = nums[r];
            int add = lQ * midQ * rQ;
            nums[i] = -1;

            //右侧的气球
            dfs(nums, curLevel + 1, curCoin + add);
            nums[i] = midQ;
        }
    }
}

时间复杂度 = O(n! × n)

  1. dp，dp[i][j] 表示 i 到 j能获得的最大金币
  2. dp[i][j] = 区间内的最大。那么dp[i][i + len] = res;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        // 创建一个辅助数组，并在首尾各添加1，方便处理边界情况
        int[] temp = new int[n+2];
        temp[0] = 1;
        temp[n+1] = 1;
        for(int i=0; i<n; i++){
            temp[i+1] = nums[i];
        }
        int[][] dp = new int[n+2][n+2];
        // len表示开区间长度
        for(int len=3; len<=n+2; len++){
            // i表示开区间左端点
            for(int i=0; i<=n+2-len; i++){
                int res = 0; 
                // k为开区间内的索引
                for(int k = i+1; k<i+len-1; k++){
                    int left = dp[i][k];
                    int right = dp[k][i+len-1];
                    //dp[i][j] 表示 i 到 j能获得的最大金币
                    //(i....k) k (k.... i + len -1)
                    res = Math.max(res, left + temp[i]*temp[k]*temp[i+len-1] + right);
                }
                dp[i][i+len-1] = res;
            }
        }
        return dp[0][n+1];
    }
}

目标和[22]

思路

  1. DFS
  2. 每个节点两种选择 + or -

比较简单的回溯，和普通的回溯的区别，就是在循环过程中，如果是像组合排列这些题，就需要往后遍历找，即树的宽度不定，而这题则树宽为 1，每次直接一个数递归下去即可，不用循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    int res = 0;
    public int findTargetSumWays(int[] nums, int target) {

        dfs(nums, target, 0, 0);
        return res;
    }
    public void dfs(int[] nums, int target, int numIndex, int sum){
        if(numIndex == nums.length){
            if(target == sum) res++;
            return ;
        }
        //向数组中的每个整数前添加 '+' 或 '-'

        //对于每个节点两种选择： + or -。不能硬套模版
        /**
        fun dfs():
            for(int i = 0; i < nums.length; i++){
                add
                dfs
                delete
            }
        以上是因为每个节点都有多选择 比如 排列，组合
        
        
         */
        dfs(nums, target, numIndex + 1, sum + nums[numIndex]);
        dfs(nums, target, numIndex + 1, sum - nums[numIndex]);
    }
}

路径总和 II[75]

题目：

求叶子节点到根节点 路径和 为target的路径

思路：

  1. dfs 回溯。
  2. 注意！！！ 叶子结点定义，root.left == null && root.right == null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root == null) return new ArrayList(res);
        dfs(root, targetSum, 0, new ArrayList());
        return res;
    }

    public void dfs(TreeNode root, int targetSum, int sum, List<Integer> path) {
        if (root == null) {
            // if (sum == targetSum)
            //     // res.add(path.chars()
            //     //         .map(e -> e - '0')
            //     //         .boxed()
            //     //         .collect(Collectors.toList()));
            //     res.add(new ArrayList(path));
            // return;
            return ;
        }

        sum += root.val;
        //System.out.println(sum);
        path.add(root.val);
        //System.out.println(path);

        //到达叶子节点
        if(root.left == null && root.right == null){
            if (sum == targetSum)
                res.add(new ArrayList(path));
            //return; 肯定不能return啊，因为它是叶子结点到根节点
        }
        dfs(root.left, targetSum, sum, path);
        dfs(root.right, targetSum, sum, path);
        //回溯
        path.remove(path.size() - 1);
    }
}

发表于 分类于

跨域就是指跨 同一个协议，域名，端口进行数据请求，常见在现在前后端分离部署的场景。这主要是浏览器的一个安全策略，就是防止钓鱼网站携带像你的cookie像你的bank网站请求。然后我们正常开发要解决这种跨域问题，一般就得在服务端的响应头里CORS相关字段

1
2
3
4
5
6
7
HTTP/1.1 204 No Content
// 相信的前端页面网址，也就只有这个网址，服务端能放行
Access-Control-Allow-Origin: https://app.bank-partner.com 
Access-Control-Allow-Methods: GET, POST, PUT, DELETE
Access-Control-Allow-Headers: Content-Type, Authorization
Access-Control-Allow-Credentials: true