ARST打卡第186周[186/521]

发表于 分类于 阅读次数：
lc1752_检查数组是否经排序和轮转得到 Students' Guide to Raft 为什么netstat对某些服务只显示了tcp6监听端口 raft加速日志回退算法以及理解的基础_一些举例 hexo的node12出问题

Algorithm

lc1752_检查数组是否经排序和轮转得到

直接遍历解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func check(nums []int) bool {
    // 这个题不是剑指offer的二分题，而是更简单，因为它这里面要所以数值相同，所以遍历就行
    len := len(nums)
    if len <= 1 {
        return true 
    }
    for i := 0; i < len; i++ {
        j := 1
        ok := true
        for ; j < len; j++ {
            if nums[(i+j-1)%len] > nums[(i+j)%len] {
                ok = false
                break
            }
        }
        if j == len && ok {
            return true
        }
    }
    return false
}

发现答案优化了一下，可以先找出一个可能的最小值，然后再去遍历，这样可以节省一些时间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func check(nums []int) bool {
    n := len(nums)
    x := 0
    for i := 1; i < n; i++ {
        if nums[i] < nums[i-1] {
            x = i
            break
        }
    }
    if x == 0 {
        return true
    }
    for i := x + 1; i < n; i++ {
        if nums[i] < nums[i-1] {
            return false
        }
    }
    return nums[0] >= nums[n-1]
}

// 链接：https://leetcode.cn/problems/check-if-array-is-sorted-and-rotated/solutions/1990942/jian-cha-shu-zu-shi-fou-jing-pai-xu-he-l-cbqk/

Review

Students’ Guide to Raft

mit6.824的2016年的助教老师写的Raft实验课程指导，主要是读懂了大概raft过程，然后应用了raft日志快速退避算法

Tips

为什么netstat对某些服务只显示了tcp6监听端口

Share

raft加速日志回退算法以及理解的基础_一些举例

算法思想

加速日志回溯优化:

  • 如果一个追随者在其日志中没有prevLogIndex，它应该返回conflictIndex = len(log)和conflictTerm = None。
  • 如果一个追随者prevLogIndex在它的日志中确实有，但是term不匹配，它应该返回conflictTerm = log[prevLogIndex].Term，然后在它的日志中搜索第一个条目具有term等于 conflictTerm 的索引。
  • 收到冲突响应后，领导者应首先在其日志中搜索conflictTerm。如果它在其日志中找到具有该term的条目，则应将其nextIndex设置为超出其日志中该term中最后一个条目的索引的条目。
  • 如果它没有找到包含该term的条目，它应该设置nextIndex = conflictIndex.

一个折衷的解决方案是只使用conflictIndex（并忽略 conflictTerm），这简化了实现，但领导者有时最终会向跟随者发送比更新它们所必需的更多的日志条目。

理解的基础

理解上面的核心是要知道: raft机制保证了同位置同任期的内容一定是一样的.

例子

S1:3455
S2:3567
先发7过去，然后经过上面过程，发67过去，发现4,5还是不匹配，再发567过去，然后发现3匹配了，然后就可以直接覆盖了，因为之前3在同样的位置，都是raft机制保证了同位置同任期的内容一定是一样的，单独的leader保证了单独的任期里面发送给单独的位置一定是相同的内容。(这一点很重要)

S1: 4444
S2: 4455
所以确实返回5的下标，然后去覆盖

S1:33
S2:34555
先跳转到3的位置，把555发过去，然后发现冲突任期是3，S2就把4555发过去

hexo的node12出问题

1
2
3
4
5
~ hexo new "ARST打卡186周[186/521]"
dyld: Library not loaded: /usr/local/opt/icu4c/lib/libicui18n.68.dylib
  Referenced from: /usr/local/opt/node@12/bin/node
  Reason: image not found
[1]    6378 abort      hexo new "ARST打卡186周[186/521]"

然后发现node@12已经不支持了，所以需要手动修改一些东西才能继续使用

  1. brew edit node@12
  2. Comment out the line disable! date: "2022-04-30", because: :unsupported . Save the file.
  3. brew install node@12