Kenway's Blog

发表于 更新于 分类于

必背重点题

字典序的第K小数字

给一个整数n和一个k，求在字典序排序的小于n的数组中的第k个数字

解法：

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
int findKthNumber(int n, int k) {
    int count = 1;
    int cur = 1;
    while(count < k){
        int tmpCount = getCount(cur, n);
    
        if(count + tmpCount > k){ 
            cur *= 10;
            count++;
        }else{
            cur++;
            count += tmpCount;
        }
    }
        
    return cur;
}

int getCount(int cur, int n){
    int res = 0;
    for(int a = cur, b = cur+1; a <= n; a*=10, b*=10){
        res += min(n+1, b) - a;
    }
    
    return res;
}

约瑟夫环问题

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3

1
2
3
4
5
vector<int> dp(n+1);
for (int i = 2; i <= n; i++) {
    dp[i] = (dp[i-1] + m) % i;
}
return dp[n];

二叉树的前序遍历(迭代)

  • 迭代法(统一格式)：栈 + nullptr标识已访问节点
    • 前序遍历
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      vector<int> ans;
      stack<TreeNode*> s;
      if(root) s.push(root);

      while(!s.empty()){
          TreeNode* now = s.top();
          s.pop();
          if(now){
              if(now->right) s.push(now->right);
              if(now->left) s.push(now->left);
              s.push(now);
              s.push(nullptr);
          }else{
              now = s.top();
              s.pop();
              ans.push_back(now->val);
          }
      }

      return ans;

寻找排序数组旋转后的最小值

给一个排序数组经过若干步旋转后得到的数组，求用logn的时间复杂度找到最小值(即原先排序数组的头部成员)

解法：二分法变形

1
2
3
4
5
6
7
8
9
10
11
12
13
int left = 0, right = nums.size()-1;

while(left < right){
    int mid = left +(right - left) / 2;
    
    if(nums[mid] < nums[right]){
        right = mid;
    }else{
        left = mid + 1;
    }
}

return nums[right];

进阶：这个数组里面可能有重复数字

解法：在基础上多加一个nums[mid] == nums[right]的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int left = 0, right = nums.size()-1;

while(left < right){
    int mid = left +(right - left) / 2;
    
    if(nums[mid] < nums[right]){
        right = mid;
    }else if(nums[mid] < nums[right]){
        left = mid + 1;
    }else{
        right--;
    }
}

return nums[right];

快速排序

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
//快速排序从小到大
void quickSort(int left, int right, vector<int>& arr)
{
	if(left >= right) return;
	
    srand((int)time(0));
    int tmp = (rand() % (right - left + 1)) + left; 
    int temple = nums[tmp];
    nums[tmp] = nums[left];
    nums[left] = temple;

	int i, j, base, temp;
	i = left, j = right;
	base = arr[left]; 
	while (i < j){
		while (arr[j] >= base && i < j) j--;
		while (arr[i] <= base && i < j) i++; 
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	
	arr[left] = arr[i];
	arr[i] = base;
	quickSort(left, i - 1, arr);
	quickSort(i + 1, right, arr);
}

归并排序

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
vector<int> sortArray(vector<int>& nums) {
    vector<int> temple(nums.size());
    mergeSort(nums,temple,0,nums.size()-1);
    
    return nums;
}


void mergeSort(vector<int>& nums, vector<int>& temple, int left, int right){
    if(left >= right) return;
        
    int mid = (right - left) / 2 + left;
    mergeSort(nums, temple, left, mid);
    mergeSort(nums, temple, mid+1, right);
    merge(nums, temple, left, right); 
        
    return;
}

void merge(vector<int>& nums, vector<int>& temple, int left, int right){
    int mid = (right - left) / 2 + left;
        
    int i = left, j = mid+1, k = 0;
    while(i <= mid && j <= right){
        if(nums[i] < nums[j]) temple[k++] = nums[i++];
        else temple[k++] = nums[j++];
    }
        
    while(j <= right) temple[k++] = nums[j++];
        
    while(i <= mid) temple[k++] = nums[i++];
        
    for(int i = left; i <=right; i++) nums[i] = temple[i-left]; 
        
    return;
}

堆排序

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
vector<int> main(vector<int> nums){
    heapSort(nums);
    
    return nums;
}

void heapSort(vector<int> &arr, int size){
    for(int i=size/2 - 1; i >= 0; i--){
        adjust(arr, size, i);
    }
 
    for(int i = size - 1; i >= 1; i--){
        swap(arr[0], arr[i]);
        adjust(arr, i, 0);
    }
}

void adjust(vector<int> &arr, int len, int index){
    int left = 2*index + 1;
    int right = 2*index + 2;
 
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;
 
    if(maxIdx != index){
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);
    }
}

至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
解法：对字符种类个数kind依次枚举+滑动窗口

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
int longestSubstring(string s, int k) {
    int res = 0;
    for(int i = 1; i <= 26; i++){
        res = max(res, box(s, k, i));
    }
    return res;
}

int box(string s, int k, int kind){
    int left = 0, right = 0;
    unordered_map<char, int> memo;
    
    int maxLen = INT_MIN;
    int isValid = 0;
    while(right < s.size()){
        memo[s[right]]++;
        if(memo[s[right]] == k){
            isValid++;
        }
        right++;
        
        while(memo.size() > kind){
            memo[s[left]]--;
            if(memo[s[left]] == k-1) isValid--;
            if(memo[s[left]] == 0) memo.erase(s[left]);
            left++;
        }
        
        if(isValid == kind) maxLen = max(maxLen, right-left);
    }
    
    return maxLen;
}

分割数组的最大值

给一个数组和分割次数m，求分割m次后，最小的最大子数组之和，例如1,2,3,4分割两次得到123和4，最大子数组之和为6，该值在这个分割情况是最小的

解法：合法函数+二分查找

  • 最大子数组之和，最小值为最大数字，最大值为原数组之和
  • 亮点是：已知上下界，将其转换成二分查找的思想
    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
    int splitArray(vector<int>& nums, int m) {
        int left = 0, right = 0;
        for(int i = 0; i < nums.size(); i++){
            right += nums[i];
            left = max(left, nums[i]);
        }

        int res = 0;
        while(left <= right){
            int mid = left + (right - left) / 2;
            
            if(isValid(nums, m, mid)){
                res = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        
        return res;
    }

    bool isValid(vector<int>& nums, int m, int x){
        int sum = 0;
        int count = 0;
        for(int i = 0; i < nums.size(); i++){
            if(sum + nums[i] > x){
                sum = nums[i];
                count++;
            }else{
                sum += nums[i];
            }
        }
        
        if(sum != 0) count++;
        
        if(count > m) return false;
        return count;
    }

搜寻名人

有编号从0到n-1的人，其中有一个名人，所有人都认识名人，名人不认识任何人。只能用knows(i,j)来询问i是否认识j

解法：

  • 先找出不认识任何人的人famous，利用所有人都认识名人这一点来迭代更新
  • 检验这个人是否是名人
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int famous = 0;
    for(int i = 1; i < n; i++){
        if(knows(famous, i)){
            famous = i;
        }
    }

    for(int i = 0; i < n; i++){
        if(i == famous) continue;
        
        if(knows(famous, i) || !knows(i, famous)) return -1;
    }

    return famous;

最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。例如输入：s = “banana” 输出：”ana”

解法：二分查找+字符串哈希

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
string longestDupSubstring(string s) {
    int len = -1, index = -1;
    
    int left = 1, right = s.size();
    while(left <= right){
        int mid = (right-left) / 2 + left;
        
        int t = isValid(s, mid);
        if(t != -1){
            index = t;
            len = mid;
            left = mid + 1;
        }else right = mid - 1;
    }
    
    if(len == -1 || index == -1)  return "";
    return s.substr(index, len);
}
    
    int isValid(string& s, int m){
    int mode = pow(10, 9) + 7;
    int base1 = 131;
    unordered_map<int, bool> memo;
    
    vector<unsigned long long> hash1(s.size()+1);
    vector<unsigned long long> power1(s.size()+1);
        
    power1[0] = 1;
    for(int i = 1; i <= s.size(); i++){
        hash1[i] = hash1[i-1] * base1 + s[i-1]-'a';
        power1[i] = power1[i-1] * base1;
    }
    
    for(int i = 1; i + m -1 <= s.size(); i++){
        int j = i + m - 1;
        int code1 = hash1[j] - hash1[i-1]*power1[j-i+1];
        
        if(memo.count(code1) > 0){
            return i-1;
        }
        
        memo[code1] = true;
    }
    
    return -1;
}

发表于 更新于 分类于

1.修改nginx配置文件

  • 获得nginx路径
    1
    nginx -t
  • 进入到nginx文件夹中修改nginx.conf文件，加入以下内容
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    server{
        listen 8090;
        server_name 39.105.120.230;

        location /buffer/ {
            alias /home/gowork/gopath/dy/buffer/;
            autoindex on;
        }

    }
  • 此时就可以
    • 通过url:39.105.120.230:8090/buffer/xx.mp4
    • 来访问位于服务器/home/gowork/gopath/dy/buffer/xx.mp4文件
  • 如果使用的云服务器记得打开安全组端口8090，并且重启实例

发表于 更新于 分类于 
1
2
心得：
1.错误处理很关键，前期可以只打印日志，后面还需要写入数据库或者发邮件等等

Go重写Redis中间件

Runtime介绍

1.Go语言的优势

  • 不像Java还有一个JVM层，和C++一样直接编译成二进制让机器执行
  • 自带运行环境，无需处理GC问题
  • 一次编码，多套环境使用
  • 天生支持高性能并发

2.Runtime的概念

  • 是go的一个官方库，也是go程序的运行环境，用来支撑go代码的正常运行，相当于Java的JVM
  • 编译成二进制时，会自动把Runtime作为程序的一部分打包进去
  • Runtime实际上也就是一堆google开发者写的代码，和用户程序同时运行的，也可以直接通过函数来调用

3.Runtime的功能

  • 内存管理：自动为变量分配内存
  • 垃圾回收：回收堆上的空间
  • 超强的并发能力：协程的实现
  • 有一定屏蔽系统调用的能力
  • go、new、make、<-等其实都是去调用Runtime的函数

4.Go的编译

  • 编译指令是go build
    1
    go build
  • .a文件是compile编译过程中出现的机器码的中间文件，后续需要link成exe文件
  • 编译过程
    • 词法、句法、语义分析
    • 生成平台无关的中间码SSA(类似汇编语言)
      1
      2
      3
      4
      5
      # 查看SSA可以依次执行下列命令
      $env:GOSSAFUNC="main"
      export GOSSAFUNC=main
      go build
      # 加-n表示不实际编译，只打印出编译的过程
    • 生成二进制的机器码.a文件
    • 链接生成.exe文件

5.go程序运行

  • 1.运行rt0文件。go程序的入口底层上是runtime库的rt0_xx.s汇编文件，而不是main.go
    • rt意思是runtime，0表示入口，rt0有多个文件不同的操作系统、芯片用不同的rt0文件
  • 2.起g0协程。g0是调度协程的协程，即母协程，是第一个协程
    • 启动调度器
  • 3.启动主协程，并放入调度器等待调。用来来运行main.go
    • 执行runtime包的init()方法
    • 启动GC垃圾收集器
    • 执行用户包依赖的init()方法
    • 执行用户的main()方法

6.细节

  • argc存参数的数量，argv存参数的值，args泛指参数
  • ide中双击shift只会查找有意义的变量和方法，即它会忽略汇编文件里的成员，要找的话要再选file选项去找

7.在struct中只声明类型没指定名字的变量，称为匿名字段，go会自动到里面去调用函数(因为没有成员名，算一种语法糖)

8.Go的接口其实就是抽象出来的一组方法，哪个struct里实现了里面的所有方法，就说这个struct实现了该接口

9.一些包管理的方法

  • 在go.mod文件里用如下语句可以把对应的包换成本地存在的库
    1
    replace github.com/Jeffail/tunny => xx/xx
  • 执行以下命令可以把依赖的包都缓存到本地，以免go mod的时候去网上拉
    1
    2
    3
    go mod vendor

    //也可以 go build -mod vendor
  • 自动向远程仓库推送生成go.mod文件
    1
    go mod init github.com/xx/xx

Go的数据结构底层

10.go的数据结构

  • 指针大小和int保持一致，32位系统4字节，64位系统8字节
  • 独立的空结构体的大小是0，但是也是有一个地址的，所有的空结构体共有这个地址，该地址叫zerobase
    • 该设计用于节省内存，但是如果一个父结构体包含了空结构体，那么这个空结构体就不能算独立了，它的地址就要跟着它的兄弟结构体了，还有内存补齐等问题
    • set可以用map来声明，将val声明为空结构体
      1
      2
      3
      set1 := map[string]struct{}{}
      set1["aa"] = struct{}{}
      //正常写法应该是map[string]int{}，struct{}表示空结构体类型

11.string在底层是由一个unsafe.point指针(本质是byte数组)和一个int组成的结构体，分别指向字符串值地址和存字符串byte长度

  • 注意len(str)的结果是字符串底层字节的长度！！例如“慕a”的len()就是4
  • rune就是utf8字符的意思，底层是int32
  • utf-8的文件在runtime/utf8.go里面

12.切片的底层slice由一个unsafe.point指针和两个int类型的len、cap组成，参考C++的vector

  • 声明定义时[]写了具体数字的就是数组，没写的就是切片
  • 只增加len就只由编译器负责，如果需要扩容增加cap就要去调runtime.growslice()
  • 默认扩容是长度小于1024扩大到2倍，大于1024扩大到0.25倍，除非期望容量比要扩容的还大那就采用期望容量
  • 切片的扩容是并发不安全的，扩容要记得加锁，因为扩容会把老数组丢掉

13.map的底层其实是HashMap实现的

  • go的map是由链表法实现的，hmap底层又由bucket指针指向一个由bmap结构体组成的数组，每一个bmap放8个哈希值相同的数据
    • bmap
      • 有tophash存hash值的前8位
      • 有一个overflow指针指向可用的bmap，若超过8个的话就把多的数据根据这个指针传到另一个bmap去
      • 有key和value，最多只能存8个k-v对，注意这里存的不是值，也是key和value的地址
    • 将key值和hash0输入到hash函数里面会得到一个二进制的hash值，然后取后B位作为桶数，例如100010 B=3，则取010，即该key应该放在bucket2里
      • 然后再根据前8位的值作为tophash得到这个key具体在bucket2的哪个位置，tophash的设置就是为了快速定位的(因为是二进制表示节省开销，而用key去匹配可能是string等开销大的类型)
  • 在runtime包里面
  • 开放寻址法和链表法其实差不多，区别只在于开放寻址法的槽存值，而链表法的槽存指针(也叫桶法)
  • 字面量赋值，少于25个之间编译成一个个赋值，多余25个会自动建key数组和val数组然后改写成for赋值
  • 扩容是因为如果哈希值太多，溢出桶指向溢出桶指向溢出桶，这样性能就会大跌
    • 装载因子超过6.5会触发扩容，即每个桶里平均装了6.5个以上数据
    • 溢出桶数量大于普通桶数量也会触发扩容(这里的扩容有可能不增加桶数，只做整理，因为可能之前很多然后删了之后现在数据很少，会很稀疏地存在)
    • step1：建新的双倍普通桶，然后bucket指向新桶，oldbucktet指向旧桶，并且把该hmap标记为扩容
    • step2：渐进式转移数据，即每一次数据要写到旧桶时才把这个旧桶的数据转移到新桶里(因为根据B的增加只增加一个高位，所以根据高位是0还是1只分成两部分放入新桶)
    • step3：当所有旧桶里都迁移完了之后就释放旧桶占据的内存空间（所以会有并发问题）
  • 并发里用map要用sync.Map，里面自动会给读、写加锁
    • 里面有两个map，一个read map，一个dirty map，他们的key都是一样的并且都指向同一组val地址
      • 正常的读、修改都走read这个map；发生追加的时候走dirty这个map，mutex锁会去锁dirty，同一时间只允许一个协程去操作dirty
        • 每次去read读读不到并且read的mended为true则要去dirty里面找，每发生一次misses+1，当misses==len(dirty)时触发把dirty上升为read，然后之前那个read删掉，新建一个老dirty的副本作为新dirty——当时并不新建，发生追加时才顺便新建
      • 删除则是把执行val的指针置为空，这样过段时间go就会自动回收空间
        • 如果是提升之前dirty里追加的就被删了，那么提升后新dirty就不会再建立这个key

Go的并发

14.常用并发

  • 简单的并发
    1
    2
    3
    go func(){
        fmt.print("123")
    }
  • 简单的阻塞
    1
    select {}
  • 简单的利用管道缓冲(以下表示最多同时运行3000个协程)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    func main(){
        c := make(chan struct{}, 3000)
        for...{
            c <- struct{}{}
            go do(c)
        }
    }

    func do(ch chan struct{}){
        time.sleep(time.Hour)
        <-ch
    }
  • 简单的加锁：在结构体里新增一个mutex类型成员
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    type person struct{
        mu sync.mutex
        name string
    }

    func(p *person) promote{
        p.mu.Lock()
        ...
        p.mu.Unlock()
    }
  • 另一种加锁方式：用原子操作，这种方法不实用，在并发大的时候已卡住，因为触发不了协程切换
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    type person struct{
        mu int32 //0表示未锁，1表示已上锁
        name string
    }

    func(p *person) promote{
        atomic.CompareAndSwapInt32(&p.mu, 0, 1);
        ...
        atomic.CompareAndSwapInt32(&p.mu, 0, 1);
    }

15.interface{}的底层，一个实例化的接口有以下特性

  • 接口的数据用runtime.iface表示
  • iface记录了数据的地址
  • iface也记录了底层是由什么类型实现的和实现的方法
    • 所以当接口有类型信息时，空接口就不会是nil了

16.nil不一定是空指针，可能是别的类型的0值。在底层文件builtin里面nil的类型时可变的

  • 空接口不一定是nil，因为如果这个空接口有类型信息的话它就不会是nil
  • 空结构体的指针是zerobase，跟nil没关系

17.以下语句可以获得对齐系数

1
unsafe.Alignof()

18.可以调整结构体的成员声明顺序，来节省空间，因为会有字节对齐

  • 结构体的对齐系数是其最大成员对齐系数，和C++一样
  • 空结构体在末尾时要补齐字节，比如前面字节已经对齐了，然后多了一个空结构体，那么也要补齐字长

19.go用协程而不是线程的原因

  • 协程资源开销、切换开销更小，协程本质是一段包含了运行状态的程序
  • 协程并发其实就是用同一个线程先执行协程a的一步计算，把状态保存到协程a，再去切换到协程b计算再保存，又切回协程a继续计算。这样的好处就是cpu一直在一个线程上跑，减少了cpu在线程之间切换带来的开销
  • 协程底层是一个g结构体(g0是母协程)，g结构体里包含的gobuf成员的sp堆栈指针记录的是运行到哪个方法了，pc程序计数器记录的是运行到哪一行了
    • 描述线程的底层是m结构体，里面记录了母协程g0、当前协程curg和操作系统的信息mOS
  • go执行协程会把这个协程要运行的方法依次压入栈中，并且初始化这个栈的时候先压入一个goexit()用于执行完成退出协程

20.go协程在线程中执行的循环过程(一个线程是一个循环)

  • 首先，g0的stack上执行schedule()、execute()、gogo()等
  • 然后，去对应协程的g的stack上执行业务方法
  • 最后，在g的stack上运行到goexit()的时候又返回g0开始下一个执行协程的循环

21.GMP调度模型：用于协程的调度

  • go以前是用一个有全局锁的协程队列实现多线程并发
    • 每个线程循环运行完后，就去队列里拿一个协程进行下一个循环
  • G是协程，M是线程，P是送料体，每一个P服务一个M，P里面有：
    • 指向本地协程队列头尾的指针，当前协程的指针，下一个协程指针
    • 线程信息
  • 某个P的本地队列用完之后，就会去全局锁队列里面获取一批新的协程作为本地队列
    • 如果全局的队列也用完，会出现任务窃取：从其他本地队列里偷
  • 新建协程时，会随机寻找一个P放入本地队列，若本地队列满再放入全局队列，这是因为go认为新协程更需要先完成

21.协程的并发

  • 如果顺序执行的话，会产生饥饿问题：大协程卡住了线程，后面的协程永远得不到执行
  • 触发切换时，正在线程中循环的协程会被保存现场然后放回队列去
    • 四种触发方式：
      • gopark()，主动调用或者在方法内执行sleep等操作后go自动调用
      • 系统调用后去执行exitsyscall()，系统调用指的是，比如linux会去定期检查网络连接等
      • 抢占式调度，当被标记为抢占的协程触发了morestack()，就会触发切换
        • 当某个协程运行超过10ms时，系统会把它标记为抢占
      • 垃圾回收器定期让线程去调用doSigPreempt()，注册信号函数
  • 每执行61次协程循环，就去全局队列里去拿一个协程进入本地队列

22.协程的方法a里再去调方法b时，编译器会自动在b()前面去先调用runtime.morestack()

  • morestack()本质意为去检查协程方法栈里面是否有空间再放入一个b()

23.协程过多

  • 带来问题：
    • 文件打开数限制
    • 内存限制
    • 调度开销过大限制
  • 解决办法：
    • 优化业务逻辑
    • 利用channel缓存区：channel大小就是允许同时运行的协程数量
    • 协程池tunny：预创建一定数量协程，然后把任务送入协程池队列，协程池再不断取出可用协程来执行任务
      • 不太推荐，因为go的协程调度已经有池的思想了，再自己套一个池的逻辑会冗余、出问题难以查错
    • 增加系统资源

24.atomic包的原子锁是一种硬件层面的加锁，因为它是用底层汇编语言来实现的，会进行对某块内存加锁

  • 只能用于简单变量的加减操作，不能对结构体、map这种复杂类型使用

25.sema锁是信号量锁，是mutex这些互斥锁、读写锁的底层实现

  • 底层用平衡二叉树来存协程
  • sema锁为几就表示有几个协程可以同时获取这个sema锁
    • 为0的时候，就会把要获取这个sema锁的协程放进平衡二叉树树里面去休眠
    • 有一种用法是，把sema设为0然后当成一个休眠队列把要休眠的放进去，要用时再对sema赋>0的值

26.mutex的state的最后一位0表示未被锁，1表示被锁

  • 正常模式：默认模式
    • 当一个协程去获取mutex的锁时，若获取不到，则会自旋一段时间后再去获取，还获取不到就放到sema的休眠队列里去
    • 会有饥饿问题，即协程a等锁等了很久，终于锁释放了然后轮到唤醒它去拿锁，但是那一瞬间有新来的协程一起在竞争这个锁，那这样协程a可能永远也得不到执行
  • 饥饿模式(先来后到)：当某个协程等锁等了1ms就会进入
    • 新来的协程不自旋，直接进sema休眠
    • 休眠队列里的协程被唤醒时，直接获得这把锁，不用再去和刚来的新队列竞争
    • 当sema队列被清空时，退出饥饿模式，返回正常模式
  • mutex有3个sema，一个mutex的sema，一个readSema，一个writeSema

27.iota是以此类推的意思，下面一次多加1，是go的语法糖

  • 另一个常用语法糖，在方法后.var可以快速新建变量来接受方法返回值

28.只读锁mutex.RLock()：锁上的时候不能再去写，但是还可以去读，即第一个读协程锁上，最后一个读协程释放

  • 加读锁
    • 给readCount+1
      • 如果readCount > 0，表示加锁成功
      • 如果readCount < 0，表示有写锁，要被放入readerSema去等待
  • 解读锁
    • 给readCount-1
      • 如果readCount > 0，表示解锁成功
      • 如果readCount < 0，表示有写协程在writerSema里等待，如果此时自己是readerWait里的最后一个读协程，那么还要去唤醒这个写协程

29.读写锁mutex.Lock()

  • 加读写锁
    • 先加mutex的锁，如果已经有锁了就会阻塞等待
    • 将readCount前面加-号变为负值，阻塞读锁的获取
    • 如果有读协程还未释放，那么就进入writerSema
  • 解写锁
    • 解开mutex的锁
    • 将readCount变为正值，允许读锁的获取
    • 释放在rederSema中等待的读协程

29.加锁的底层

  • 加互斥锁就是去竞争mutex的state的最后一位，希望它由0变成1
  • 读锁是共享锁，写锁是互斥锁

30.开go协程的时候一定要记得：主程序退出会把所有协程都终止！

31.sync.WaitGroup对象：用于实现一组协程要等待另一组协程

  • Add(int)方法进行设置等待数
  • Done()方法会结束一个等待
  • Wait()方法只有在等待数为0时才不阻塞

32.让一段代码全局只执行一次的方法

  • 调用sync包的once，底层也是用mutex互斥锁来实现的
    1
    2
    3
    4
    5
    o := sync.Once{}
    go o.Do(xx.xx())
    go o.Do(xx.xx())
    ......
    //这样无论起多少个协程，xx.xx()全局只被执行一次

33.并发问题的检查工具

  • 锁千万不要去拷贝，因为会连锁状态、sema休眠队列等也一起拷贝的，会有死锁等很多问题
    • 拷贝结构体的时候要注意里面有没有锁mutex的情况
  • vet检查：用于检测xx.go文件里的锁拷贝等问题，例如拷贝了某个有锁的结构体
    1
    go vet xx.go
  • race检查：用于检查出文件里的数据竞争问题，例如并发地加某个变量值而不上锁
    1
    2
    go build -race xx.go
    //然后运行xx.go
  • go-deadlock库：用于检测死锁，实际是检测锁解开的时间来实现的
    • 用go-deadlock包的mutex来取代sync包

channel管道

34.管道的阻塞

  • 以下代码会在第二行阻塞，因为channel没有缓冲区，塞不进去
    • 能运行的情况是有另一个协程阻塞着等着从a里面拿数据
      1
      2
      3
      a := make(channel int)
      a <- 1
      <- a
  • 使用管道比共享内存好的原因
    • 避免协程竞争和数据冲突问题
    • 减少开销，可以省去循环一遍遍查询，管道是一种信号机制，一旦有值就会通过
    • 更高级的抽象，代码逻辑清晰，更容易模块解耦
  • 原则上：不要通过共享内存的方式来通信，而是要用通信的方式来共享内存

35.channel底层

  • channel的底层结构体是hchan
    • 指针实现ring buffer，缓存是用环状结构来实现的
      • 环状可以降低垃圾回收GC开销，固定环的长度新增的数据直接放在下一个数据块即可，如果不用环状的话，新增要开辟空间，删除要回收空间
    • 接受队列Receive Queue，用于存放准备读这个channel里数据的协程(休眠等待)————此时ring buffer一定是空的
      • 从这个队列被唤醒时，数据已经被拷贝放到了这个协程里面
    • 发送队列Send Queue，用于存放准备把数据放到这个channel里的协程(休眠等待)————此时ring buffer一定是满的或者没有缓存区
    • mutex成员，任何对该channel的修改都要去获取mutex
      • 一般人说的“channel无锁”，指的是ring buffer里有位置，数据只有放进去的一瞬间要加锁，很短暂，所以说无锁

36.channel实践

  • 实践中用select搭配channel更方便
    • 因为select可以用case来判断哪个channel里有数据或哪个channel可以塞数据，然后执行不同逻辑
  • time库的timer对象里的成员C是一个channel，在这个timer对象计时结束后会自动往里面塞一个数据
    • 利用这个特性可以实现计时的并发逻辑

用netpoll管理socket(go的网络编程是基于epoll的)

37.socket

  • TCP连接应该要有三次握手四次挥手的，socket是操作系统对这些操作的封装，我们只需操作socket即可实现TCP，不用去具体写什么时候握手什么时候挥手等
  • socket的id叫文件描述符FD

38.Go封装的epoll

  • 把linux/windows/mac的多路复用统一抽象成Network Poller
  • 底层核心方法netpoll()用来查询发生了什么事件
    • 里面实际是调用epoll_wait()来具体查询的
    • 会返回一个关心这些事件的协程列表pollDesc(链表结构)
      • pollcache是带锁的链表头，不含具体信息，它后面跟的pollDesc才有数据
      • pollDesc是链表成员-也是runtime包对socket的详细描述
  • 实际逻辑
    • 首先，runtime里的gcStart()会调用netpoll()，因为gc是周期性的所以可以理解为周期性地调用netpoll()查询，发现某Socket可读写的时候，给对应的rg或wg置为pdReady(1)，在g0协程上运行的
    • 然后，当协程运行的时候会去判断rg或wg是否就绪，如果就绪就往下走；如果不就绪就会把这个协程的地址写到rg或wg上，并把协程休眠，等rg或wg就绪的时候就会用这个地址去唤醒协程

39.net包是go原生的网络包，它实现了TCP、UDP、HTTP等网络操作，底层靠NetworkPoller实现

  • net.Listen()会得到一个TCPListener对象(listen状态的socket)，底层如下
    • 新建一个Socket，并执行bind和listen
    • 新建一个FD，FD是net包对socket的描述，相当于runtime包的pollDesc
  • TCPListener.Accept()得到TCPConn对象(establish状态的socket)
    • 直接调用accept，新生成一个socket来连接
    • 如果失败了就休眠等待
  • TCPConn.Read()和TCPConn.Write()就可以对socket进行读写了

40.把byte数组转成字符串的方法

1
2
# b是[]byte类型
string(b[:])

41.怎样实现一个协程负责一个socket

  • 死循环里每监听到一个新的连接，就新起一个协程去处理这个连接
  • 即主协程监听listen，然后起新协程去处理连接
  • 这种代码风格也叫goroutine-per-connection编程

Go的GC垃圾回收

42.Go的栈也是从堆上申请的，即不像C++等栈由程序释放，Go的栈依旧由GC释放

  • 堆内存在操作系统的虚拟内存上
  • 函数参数传递顺序和C++一样，从右往左传，因为栈是后进先出
  • Go天然有一个runtime.main栈帧(一个协程有一个自己的协程栈，多个栈帧组成了一个协程栈)
    • 运行主函数时有一个main.main栈帧紧跟着runtime的栈帧
    • Go的main()调用一个函数，会在新起一个栈帧跟着main.main的后面(C++的递归太多导致栈溢出就是这个原理)

43.Go解决协程栈溢出的方法

  • 逃逸分析：不是所有的变量都能放在协程栈上，用来减少栈空间不足
    • 指针逃逸：某方法返回了一个指向它局部变量的指针，按理来说这个局部变量应该要被回收，但是指针被传出去了，外面的其他方法可能会用到，所以就把这个局部变量放到堆上(C++的策略是直接回收)
      • 例如a()调用了b()，按理说b()的变量要全删，但是因为b()返回了一个指针给a()使用，那么这个指针指向的变量就不能删，会逃逸到堆上
    • 空接口逃逸(反射导致)：某方法用局部变量调用了另一个参数类型是空接口的方法，那么这个局部变量就会逃逸了，因为空接口的方法往往都会用到反射，而反射要求变量需要在堆上
    • 大变量逃逸：太大的变量会导致协程栈空间不足，一般64位的机器超过64kb的变量都直接放堆上
  • 栈扩容：Go之前采用分段栈，原理类似链表；现在采用连续栈，原理类似vector，找一个2倍的空间然后迁移过去

43.Go的堆内存结构，类似tcmalloc-也是C++17推荐用的内存结构

  • Go申请和释放虚拟内存的单位是64M(一个heapArena)，许多个64M组成了Go的用的所有内存(底层用mheap描述)
    • 在heapArena里面给对象分配内存策略
      • 分级分配，给heapArena里的空间分割成不同大小的箱子，每个箱子只能放一个对象，然后把每个对象放到能放下它的最小的箱子
        • 每一级箱子叫做一个mspan，即如果分成2级，就有两个mspan
        • go最多有68个mspan(0级-67级)，是根据对象的内存需求再去分割的，最小8bit，最大32kb
      • 不用线性和链表分配，是因为易出现内存碎片
  • 用mcentral来做mspan的索引，而每个mspan里面有两个mcentral，分别记录需要GC扫描的内存和不需要GC扫描的内存，里面有互斥锁
  • 每个线程P有一个本地的内存mcache做缓存用，里面每个级别的mspan分别有2个(scan和noscan)，每次线程要申请空间时不用去中央要，先从自己本地去要，这种结构类似协程调度的GMP模型
  • 即整体结构，heapArena里用mcentral来指向mspan，采用分级分配，线程本地的mspan缓存叫做mcache

44.堆内存的分配

  • 微对象tiny(0,16b)，不包含指针。把多个微对象合并成一个16 bite分配到2级mspan，优先使用本地的mcache
  • 小对象small[16b,32kb]。分配到对应等级的mspan，优先使用本地的mcache
  • 大对象large(32kb, 无穷大)。分配到量身定制的0级mspan，即0级mspan没有固定大小，它是根据大对象来改的，只能从中央要

45.GC垃圾回收

  • “标记-清除”：把需要的内存标记，然后清除，易内存碎片，go采用，因为go用了分级分配，不会有内存碎片问题
    • 标记的对象(GC Root)
      • 被栈上的指针引用
      • 被全局变量指针引用
      • 被寄存器中的指针引用(即os正在操作处理时用的指针)
    • 每次标记的时候会对每个Root Set对象进行bfs，因为如果某个对象是Root Set的话，那么它里面引用的对象也不能清除
    • GC的策略
      • 串行GC：停下其他协程，然后GC，开销大影响业务
  • “标记-整理”：把需要的内存标记，然后把还在用的内存往前移，开销大，老java用
  • “标记-复制”：把需要的内存标记，然后只把标记的部分复制到另一个空间，新java用

46.三色标记法-go采用的并发的垃圾回收，并发指的是程序一边运行业务一边进行GC(说是并发，但是其实关键操作的瞬间还是会暂停程序，只不过时间及其短)

  • 含义
    • 黑色：有用，并且已经分析扫描过了
    • 灰色：有用，还未分析扫描
    • 白色：无用或者还没分析到，最后需要清除的对象
  • GC过程
    • 首先，所有的节点都置为白色
    • 接着，把所有Root Set节点置为灰色
    • 然后，把Root Set引用的所有节点置为灰色
    • 如此循环往复，当灰色队列里面为空时表示扫描完成，开始清除
  • 解决GC对新引用节点标记错误的问题：解决思路都是，保险起见把有改变的节点都置灰
    • 删除屏障(也叫快照标记)：把释放的指针指向的对象置灰色
    • 插入屏障：把新增的指针指向的对象置灰色
    • go采用的是混合屏障，即删除屏障+插入屏障
  • 触发GC方式
    • sysmon定时检查超过2分钟没GC，自动触发
    • 分配的堆大小达到阈值，自动触发
    • 如果检测GC机制没有启动，启动GC并触发一次
    • 代码里用runtime.GC方法强制触发(不推荐)

47.写代码过程中优化GC的方式

  • 减少堆上垃圾
    • 减少逃逸：因为逃逸会使栈上的对象跑到堆上，不能靠栈来回收，而变成堆上的垃圾等GC来回收，例如fmt这种常会用到反射的包
    • 常用空结构体：因为所有空结构体指向同一个地址，不占用堆空间
  • GC分析工具
    1
    2
    $env:GODEBUG="gctrace=1"
    gun run main.go

Go的cgo、defer、recover、反射

48.在Go里面调用C写的代码

  • 在package下面，import上面用注释的形式写C的代码
    1
    2
    3
    /*
    int sum(int a){return a;}
    */
  • 使用，先导入包C，然后用C.sum()来使用
    1
    2
    import "C"
    fmt.Println(C.sum(1))
  • 注意执行c程序的时候，不一定快，因为有以下开销
    • 调度器就会暂停不再调度，直到执行完这个c程序
    • 从go的协程栈切换到系统栈上方便c执行

49.defer

  • 碰到defer的时候会把地址记录，然后函数返回的时候调deferreturn()去执行这个地址
    • 一般记录在栈上，如果defer里面有recover就放到堆上
  • 另一种是defer的语句在编译的时候就确定了，那么编译器会直接把defer的内容加在函数末尾，也叫开放编码

50.print和fmt.print区别

  • print和println输出到标准错误流中并打印，官方不建议写程序时候用它，后期不保证是否会继续保留
  • fmt.Print，fmt，Println属于官方包fmt中自带的打印方法，属于标准输出流，一般使用它来进行屏幕输出.

51.recover用于从panic中恢复

  • panic一旦触发会直接终止当前协程，并向调用堆栈的上层函数传播，直到被最外层的recover捕获或者程序结束
    • 如果在协程里panic的话，会触发当前协程的defer，但不会触发主协程main的defer
  • 在当前协程的defer里面写recover()，可以让当前协程因为panic退出时不带崩其他协程
    1
    2
    3
    4
    defer func(){
        recover()
    }()
    panic("")

52.反射reflect，底层还是把变量的值和类型转换成一个eface结构体表示

  • 获取变量的值和类型
    1
    2
    ty := reflect.TypeOf(s)
    val := reflect.ValueOf(s)
  • 把变量的值还原成变量
    1
    2
    str := val.Interface().(string)
    //意为先转成空结构体，再转成字符串
  • 处理函数，用于框架和用户方法解耦，由框架来调用，用户来实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    func CallAdd(f func(a int, b int) int){
        val := reflect.ValueOf(f)
        if val.Kind() != reflect.Func {
            return;
        }
        argv := make([]reflect.Value, 2)
        argv[0] = reflect.Value(1) //表示把第一个参数a存到argv[0]里
        argv[1] = reflect.Value(2)
        
        val.Call(argv) //这一步就会用argv作为参数去调用上面传进来的f()方法
    }

myRedis开发

1.RESP是Redis的数据序列化协议，即client和server之间如何交流的协议，其定义了5种数据格式

  • 正常回复：以”+”开头，以”\r\n”结尾，例如+OK\r\n
  • 错误回复：以”-“开头，以”\r\n”结尾，例如-Error message\r\n
  • 整数：以”:”开头，以”\r\n”结尾，例如:123456\r\n
  • 多行字符串：以”$”开头后跟字符数量，数据由”\r\n”隔断，例如:$6\r\n123456\r\n
  • 数组：以”*“开头后跟成员数量，每个成员由”\r\n”隔断，例如:*2\r\n$4\r\nstr1\r\n$4\r\nstr2\r\n

2.myRedis的解析异步化

  • 对外公布的Parser()方法会返回一个<-ch *PayLoad，因为方法里面用协程去调用了执行解析的实际方法，当解析完成时，会吐到这个channel里面
    1
    2
    3
    4
    5
    func ParseStream(reader io.Reader) <-chan *Payload{
    	ch := make(chan *Payload, 0)
    	go parse0(reader, ch)
    	return ch
    }

3.k-v和dict的实现

  • k-v的val用interface{}，是因为可以适应各种数据类型的值
  • dict里面的方法:get、put、len等等的实现，其实就是底层对sync.map的业务调用，而因为这样封装了一层，以后改用不是sync.map的数据结构实现也方便

4.数据命令解析过程

  • 主线程监听端口，用handle去处理
  • parse0里面根据传的命令第一个字符是’*’还是’$’分别调不用的函数进行处理，当前读取的状态用state结构体记录
  • 解析得到args数组后吐到channel里
  • handle接受了这个channel里面的数据args数组后，去调数据库内核的Exce方法
    • echo_database这个数据库内核的Exce()实现的是，传什么进来就返回什么回去，所以会把解析好的数据再重新包装

5.核心链路

  • tcp包里监听接口的数据，然后拿去给resp协议层handle()处理
  • handle()去调parseStream解析命令
  • parseStream将翻译后的命令转给内核database去处理
    • 这里是异步执行，通过go parse0异步往channel里写数据，然后主程序去获取这个channel的产出往下执行
  • 每个内核database里面有一个*DB列表
  • 每个db里面有一个它的序号和一个dict
  • 每个dict底层用sync.map实现了Get()、PUT()等一系列方法

6.aof落盘逻辑

  • database内核在初始化时，也会初始化aof，先根据aof文件恢复之前状态
    • 恢复依然是走的parseStram()方法
  • 初始化有buffer的管道，然后起一个协程去异步从管道里拿操作命令写aof文件(落盘)
    • 每次出现set、rename这种写命令时，就调一次addAof()把命令塞入管道

7.碰到的问题

  • aof落盘的时候，明明应该是db0，但是落盘成db15
    • 原因：
      • 初始化database内核时，用匿名函数赋予里面的成员db的addAof()方法出现闭包问题
      • 因为闭包去调addAof()的方法会使用到局部变量db.index，所以这个局部变量db会逃逸到堆上，然后每次for遍历的时候都会去更新这个堆上的db值
      • 最后实际堆上是遍历的最后一个db成员
    • 解决办法：
      • for循环里新定义一个临时变量来放db
    • 原理：
      • for循环头部的变量每次循环中在内存上的地址其实是一样的，只是每次的值不一样(所以有时候这个地址逃逸到堆上就会产生闭包问题)
      • 而for循环内部定义的变量每次循环都会是一个新的内存地址，单次循环结束后就销毁

8.集群化

  • 采用一致性哈希，好处是：增加一个新节点只用迁移部分数据
  • 每个节点运行有一个database内核和一个连接池
      - 连接池是自己作为客户端与其他节点的连接(客户端用的是github上的开源库)
  • 对于数据不存在自己本地上的命令，会把本机当做一个redis客户端去访问别的节点

Go秒杀系统

1.系统架构设计

  • 需求
    • 前端页面承载大流量
    • 在并发量大的情况下解决超卖问题
    • 后端接口要满足可横向扩展
  • 解决方案
    • CDN->阿里提供的流量负载器->流量拦截系统->Go服务器集群->消息队列->DB数据库

2.RabbitMQ

  • 定义：面向消息的中间件，用于组件之间的解耦，主要体现在消息的发送者和消费者之间无强依赖关系
  • 使用场景：流量削峰，异步处理，应用解耦等
  • RabbitMQ安装命令
    • 安装erlang，因为RabbitMQ是用erlang编写的
      1
      2
      3
      sudo apt install erlang

      wget http://www.rabbitmq.com/releases/erlang/erlang-19.0.4-1.el7.centos.x86_64.rpm
    • 检测erlang是否安装成功
      1
      erl
    • 安装RabbitMQ
      1
      sudo apt install rabbitmq-server
    • 检测RabbitMQ是否安装成功
      1
      rabbitmqctl status
    • 启动RabbitMQ
      1
      systemctl start rabbitmq-server
    • 启动RabbitMQ的插件，要用web控制台必须启动这个
      1
      rabbitmq-plugins enable rabbitmq_management
    • 访问web控制页面
      1
      2
      本地部署直接访问127.0.0.1:15672(默认用账户guest密码guest访问)
      远程部署先开放防火墙15672端口，然后再用公网ip:15672访问(需要新建一个用户)
    • 远程部署需要创建admin用户并赋权限
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      # 创建一个账户为admin，密码为admin的新用户
      rabbitmqctl add_user admin admin

      # 给这个admin用户赋管理员权限
      rabbitmqctl set_user_tags admin administrator

      # 给这个admin用户赋virtual host的所以配置、读、写权限
      # virtual host权限是管理虚拟机的权限
      rabbitmqctl set_permissions -p "/" admin ".*" ".*" ".*"

      # 查看当前存在的用户和他们对应的权限
      rabbitmqctl list_users
  • RabbitMQ使用命令
    • 启动RabbitMQ
      1
      systemctl start rabbitmq-server
    • 停止RabbitMQ
      1
      rabbitmqctl stop
    • 插件管理命令
      1
      2
      3
      4
      5
      6
      7
      8
      # 表示查看插件列表
      rabbitmq-plugins list

      # 表示启用rabbitmq_management
      rabbitmq-plugins enable rabbitmq_management

      # 表示卸载rabbitmq_management
      rabbitmq-plugins disable rabbitmq_management
  • RabbitMQ核心概念
    • virtual host虚拟机
      • 每个账户需要绑定一个virtual host才能使用
      • 每个virtual host起的是一个数据隔离的作用
    • connection连接
      • 连接的进程
    • exchange交换机
      • 消息要经过交换机
      • 把消息经过对应的规则处理绑定到特定的key上
    • channel通道
      • 一个connection里面有多个channel
    • queue队列
      • 临时存储信息
    • binding绑定
      • 把队列绑定到交换机上
  • RabbitMQ工作模式(重点)
    • Simple简单模式：生产者把消息放到队列里，消费者从队列里取出来消费
      • 一个生产者，一个队列，一个消费者
      • 只用queue来做区分，exchange和key都为空
    • Work工作模式：一个消息只能被一个消费者获取，即一个消息只能被消费一次
      • 一个生产者，一个队列，多个消费者
      • 适用于生产效率高于消费效率的情境，来提高系统运行速度
      • 用于起到负载均衡的作用
    • Publish/Subscribe订阅模式：一个消息可以被多个消费者获取
      • 一个生产者，一个交换机，多个队列，多个消费者
    • Routing路由模式：一个消息可以被多个消费者获取，并且可以通过key来指定哪个队列接受消息
      • 一个生产者，一个交换机，多个队列，多个消费者

go mod tidy -go=1.16 && go mod tidy -go=1.17

3.不同项目对比

  • 趣约课、校友平台
    • 架构：用户->Web服务器->Mysql
    • 缺点：
      • Web服务器既要验证安全性，又要处理请求，负载大
      • 用户每发起一次请求就要去查一次数据库，数据库有压力
      • 高并发的情况下无法保证数据一致性
  • 秒杀系统
    • 架构：用户->SLB负载均衡器->分布式安全验证->秒杀数量控制->Web服务器->RabbitMQ->Mysql

4.CDN流程

  • 用户产生访问url的请求
  • 请求打到DNS服务器
  • CDN网络的智能DNS解析系统会把这个请求解析得到离用户最近的CDN节点并返回用户
  • 用户再对这个CDN节点直接请求
  • CDN节点
    • 如果本身有静态文件缓存的话会直接返回给用户(这一步就大大减少了对Web的请求流量)
    • 如果没有的话会对我们的Web站点发起一次请求获得静态文件，本次及下次就可以直接用了
  • 前四步都由CDN的厂商做，我们做项目只关注Web站点这一步

5.cookie和token

  • cookie存放在客户端，所以是不安全的，人为可以清除。
  • cookie有过期时间设定。如果不设置过期时间，说明这个cookie就是当前浏览器的会话时间，浏览器关了，cookie就不存在了。如果有过期时间，cookie就会存储到硬盘上，浏览器关闭不影响cookie。下次打开浏览器，cookie还存在
  • cookie有大小的限制，4KB。
  • 最后，对于一个分布式的web系统，通用的解决方案就是cookie+token。由服务端生成token，将用户信息与token进行关联，token返回给浏览器，存储到cookie中。后续请求都携带cooke或者将token从cookie取出以参数传递(其实把token放在header里更好，还易于解决跨域问题)

6.一致性Hash算法

  • 作用：用于分布式结构中，快速定位资源位置
  • 实现过程：
    • 把存储空间看成一个Hash圆环，出发地址0，终点地址2^32-1，超过终点地址就又从0开始
    • 把服务器的ip地址或者服务器的名称作为关键字进行Hash，然后均匀地分布在Hash圆环上
      • 哈希算法是把string转换成byte[]数组，长度小于64的用0补满到64，然后用IEEE多项式返回crc-32校验和，也就是哈希值
    • 把数据也按hash算法放到圆环上，然后以这个数据的位置为起点，顺时针去找最近的一个服务器，这个服务器即是这个数据应该放的物理地址
    • 当请求的数据不存在本机时，以本机作为代理去向其它主机发起http请求
  • 解决分布不均匀的办法
    • 虚拟节点：把每个服务器的值略作修改，生成多个虚拟节点，如果数据最终要放到这个虚拟节点上，那么直接把数据放到对应的服务器上，这样即使服务器数量过少或者服务器和数据分布不均也可以尽量均匀分布
  • 不考虑hash冲突的原因
    • 数据hash冲突，无影响。因为数据只用去找最近的节点，就算算出来的哈希位置是一样的，说明这两个数据应该放到同一个服务器上，且本项目中的数据是userId，唯一标识基本不考虑冲突情况
    • 节点hash冲突，节点是ip+虚拟节点编号，这个重复的概率极低，发生重复那么说明的是网络出现了问题

7.为什么不用redis

  • 如果用Redis的话要用redis cluster来提高性能，商品信息分散在各个cluster上
  • 但是这样在对单件商品并发请求流量大的话，流量还是会集中到某一个redis cluster，这样的话其实性能还是会受限
  • 而采用go语言写的数量控制接口可以解决以上问题

8.引入消息队列的作用

  • 异步
  • 解耦
  • 削峰

9.为什么用这么多组件来控制流量

  • 保障系统稳定的情况下，不浪费系统资源，即最大化系统利用
  • 因为如果不控制的话，在某个点流量全堆到接口上，导致暴库、接口挂掉等线上故障，而如果设置一个休眠时间的话，又很难利用好系统资源，所以就有以上的流量控制，接口做完自己手上的事才发起请求要下一个事来

10.一共需要启动四个程序

  • 拦截器(分布式在此实现)
  • 数量控制接口
  • 后端api接口
  • 消费端接口

11.流量控制措施

  • 同一用户抢购设置间隔
  • 对异常频繁请求的用户建立黑名单
  • 限流方法：
    • 漏桶算法
    • 令牌算法
  • 秒杀前
    • 增加冗余机器来保证稳定
    • 预估访问量等级和峰值时间
  • 秒杀中
    • 分批次秒杀

12.总结

  • 开发系统流程
    • 需求分析
    • 原型设计
    • 系统设计
    • 编码
    • 后期迭代优化
  • 秒杀难点
    • 消息队列RabbitMQ
    • Gin框架
    • 高并发分布式验证
    • token权限验证
    • 超卖问题(Redis会有瓶颈，采用go接口实现)
    • 横向扩展设计
  • 一个请求按顺序走过的节点
    • 前端CDN
    • SLB
    • 分布式权限验证
    • SLB
    • 分布式数量控制接口
    • 后端web服务器
    • 消息队列RabbitMQ
    • 数据库Mysql

Go微服务和容器化

1.微服务是一种架构模式，里面的一个服务仅仅用于一个特定功能，可以单独拿出来用而不依赖其他架构模块

2.Docker搭建微服务

  • 拉取微服务镜像
    1
    sudo docker pull micro/micro
  • 设置工作目录
    1
    2
    # user是模块名称，后面会换成git地址
    sudo docker run --rm -v $(pwd):$(pwd) -w $(pwd) \ micro/micro new user

3.ProtoBuf，简称pb，后缀名是.proto

  • 概念：本质上是一种序列化数据的协议，常用于存储数据和需要远程数据通信的情景，可以提高数据传输效率和解决数据格式不规范问题
    • 服务端与服务端之间只需要关注接口方法名（service）和参数（message）即可通信，而不需关注繁琐的链路协议和字段解析
  • 数据类型：int32/64、float、double、string、bool、bytes
  • 一个pb实例
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    syntax = "proto3";

    package go.micro.service.product;

    service Product{
        rpc AddProduct(ProductInfo) returns (ResponseProduct){}
    }

    message ProductInfo{
        int64 id = 1;
        string product_name = 2;
    }

    message ResponseProduct{
        int64 product_id = 1;
    }

4.命令行工具micro

  • 安装
    1
    docker pull micro/micro

5.go-micro的主要组件

  • 注册Registry：提供服务发现机制
  • 选择器Selector：实现负载均衡
  • 传输Transport：服务之间通信

6.一个微服务架构

  • 服务注册
    • client端通过Slector去服务注册中心发现服务
    • server端通过Registry去服务注册中心注册服务
  • 客户端请求
    • client通过Broker发布消息到消息队列里面
    • server通过Broker从消息队列里面订阅消息
  • 客户端和服务端的信息传输直接用Tranport

7.根据pb文件生成go代码

  • 下载proto-compile，并且注册到环境变量里
  • 安装go的支持插件
    1
    2
    go install google.golang.org/protobuf/cmd/protoc-gen-go@v1.28
    go install google.golang.org/grpc/cmd/protoc-gen-go-grpc@v1.2
  • 运行，根据.proto文件生成.go文件
    1
    protoc --go_out=./test --go-grpc_out=./test test\test.proto

9.安装go-micro

1
go get go-micro.dev/v4

10.一个简单微服务

  • 结构
    1
    2
    3
    4
    5
    6
    7
    rpc_demo
        - test //该文件夹里go文件是根据.proto文件自动生成的
            - test.pb.go
            - test.proto
            - test_grpc.pb.go
        - server.go
        - client.go
  • 客户端
    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
    func main(){
    	address := "127.0.0.1:5004"

    	conn, err := grpc.Dial(address, grpc.WithInsecure(), grpc.WithBlock())
    	if err != nil {
    		fmt.Println(err)
    		return
    	}
    	defer conn.Close()

    	client := test.NewTestClient(conn)
    	message := "hello world"

    	ctx, cancel := context.WithTimeout(context.Background(), time.Second)
    	defer cancel()

    	res, err := client.SayHello(ctx, &test.SayRequest{Message: message})
    	if err != nil {
    		fmt.Println(err)
    		return
    	}

    	fmt.Println(res.Answer)

    	return
    }
  • 服务端
    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
    type Server struct{
    	test.UnimplementedTestServer
    }

    func (s *Server) SayHello(ctx context.Context, req *test.SayRequest) (*test.ResponseSay, error){
    	fmt.Println(req.GetMessage())
    	return &test.ResponseSay{Answer: "你好世界"}, nil
    }

    func main(){
    	listen, err := net.Listen("tcp", "127.0.0.1:5004")
    	if err != nil {
    		fmt.Println(err)
    		return
    	}

    	s := grpc.NewServer()

    	test.RegisterTestServer(s, &Server{})

    	err = s.Serve(listen)
    	if err != nil {
    		fmt.Println(err)
    		return
        }
        return
    }

11.用docker在git仓库上建模板

  • 拉micro
    1
    docker pull micro/micro
  • ~~~
    sudo docker run –rm -v $(pwd):$(pwd) -w $(pwd) micro/micro new user
    ~~收益

发表于 更新于 分类于

1.前置准备

  • 安装内置的kitex命令行工具
    1
    2

    go install code.byted.org/kite/kitex/tool/cmd/kitex@latest
  • 安装带idl管理功能的kitex工具
    1
    wget --header="X-Tos-Access: internal" "http://kitex.tos-cn-north.byted.org/kx/kx-macos" -O /usr/local/bin/kx && chmod a+x /usr/local/bin/kx

发表于 更新于 分类于

目录

Go

C++

Go

1.转移函数StructTo()

  • 用于结构体、map、json格式的字符串之间的数据转移
  • 依据是tag的json标签
  • 注意，使用时要StructTo(&xx1, &xx2)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    tp := reflect.TypeOf(old)
    	var bt []byte
    	var err error
    	if tp.Name() == "string" {
    		bt = []byte(old.(string))
    	} else {
    		bt, err = json.Marshal(old)
    		if err != nil {
    			return err
    		}
    	}
    	err = json.Unmarshal(bt, new)
    	if err != nil {
    		return err
    	}
    	return nil

2.反转数组

1
2
3
4
5
6
7
func ReverseSlice(s interface{}) {
	size := reflect.ValueOf(s).Len()
	swap := reflect.Swapper(s)
	for i, j := 0, size-1; i < j; i, j = i+1, j-1 {
		swap(i, j)
	}
}

3.正则判断字符串格式

  • 判断手机号
    1
    2
    3
    4
    5
    6
    func VerifyMobileFormat(mobileNum string) bool {
    	regular := "^((13[0-9])|(14[5,7])|(15[0-3,5-9])|(17[0,3,5-8])|(18[0-9])|166|198|199|(147))\\d{8}$"

    	reg := regexp.MustCompile(regular)
    	return reg.MatchString(mobileNum)
    }
  • 判断身份证号
    1
    2
    3
    4
    5
    6
    7
    8
    func VerifyIdFormat(id string) bool {
    	if len(id) < 18 {
    		return false
    	}
    	pattern := `^([1-6][1-9]|50)\d{4}(18|19|20)\d{2}((0[1-9])|10|11|12)(([0-2][1-9])|10|20|30|31)\d{3}[0-9Xx]$`
    	reg := regexp.MustCompile(pattern)
    	return reg.MatchString(id)
    }
  • 判断邮箱
    1
    2
    3
    4
    5
    6
    func VerifyEmailFormat(email string) bool {
    	pattern := `^[0-9a-z][_.0-9a-z-]{0,31}@([0-9a-z][0-9a-z-]{0,30}[0-9a-z]\.){1,4}[a-z]{2,4}$`

    	reg := regexp.MustCompile(pattern)
    	return reg.MatchString(email)
    }

4.md5加密明文

  • 一般使用这样的形式保存用户密码Md5Make(password + salt + ApiSecret)
    • salt是用户表里每个用户独有随机生成的字段
    • ApiSecret是config配置文件里配置的字符串
    • 好处是攻击者获得数据库或获得config文件之一都不能破解密码，只有二者都具备才能解密
      1
      2
      3
      4
      5
      func Md5Make(s string) string {
      	md5 := md52.New()
      	md5.Write([]byte(s))
      	return hex.EncodeToString(md5.Sum(nil))
      }

5.项目根据配置文件初始化

  • 初始化配置文件config.json，以有user和admin两个端的项目为例
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    {
      "userWeb" : {
        "api_port" : "8085",
        "api_secret": "RaFmEoUgGINWwHecXGEhfKogPfRyzgfL",
        "save_dir" : "/api/upload/user_web/"
      },
      "adminWeb" : {
        "api_port" : "8086",
        "api_secret" : "gLhUdClFoIfppzAUzYZigbaEEdaOwYQc",
        "save_dir" : "/api/upload/admin_web/"
      },
      "mysql" : {
        "driver": "mysql",
        "user": "root",
        "pass_word": "123456",
        "host": "121.5.184.118",
        "port": "3306",
        "db_name": "xy",
        "charset": "utf8mb4",
        "show_sql": true, //用于给engine.ShowSQL(mysql.ShowSql)调用，表示是否往控制台打印sql语句
        "parseTime": "true",
        "loc": "Asia/Shanghai"
      }
    }
  • 初始化方法ConfigInit()
    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
    type Config struct {
    	Mysql    Mysql
    	UserWeb  UserWeb
    	AdminWeb AdminWeb
    }
    type Mysql struct {
    	Driver    string `json:"driver"`
    	User      string `json:"user"`
    	PassWord  string `json:"pass_word"`
    	Host      string `json:"host"`
    	Port      string `json:"port"`
    	DbName    string `json:"db_name"`
    	Charset   string `json:"charset"`
    	ShowSql   bool   `json:"show_sql"`
    	ParseTime string `json:"parse_time"`
    	Loc       string `json:"loc"`
    }
    type UserWeb struct {
    	ApiPort   string `json:"api_port"`
    	ApiSecret string `json:"api_secret"`
    	SaveDir	  string `json:"save_dir"`
    }
    type AdminWeb struct {
    	ApiPort   string `json:"api_port"`
    	ApiSecret string `json:"api_secret"`
    	SaveDir	  string `json:"save_dir"`
    }

    var Conf *Config

    //path存的是config.json的路径，一般用os.GetWd()+"xx"获取
    func ConfigInit(path string) *Config {

    	config := new(Config)

    	file, err := os.Open(path)
    	if err != nil {
    		fmt.Println(err)
    		panic("打开配置文件错误" + path)
    	}

    	confByte, err := ioutil.ReadAll(file)
    	if err != nil {
    		panic("读取配置文件错误")
    	}

    	err = json.Unmarshal(confByte, config)
    	if err != nil {
    		fmt.Println(err)
    		fmt.Println("*************")
    		fmt.Println(path)
    		panic("解析配置文件错误")
    	}

    	Conf = config
    	return Conf
    }

6.项目的main()函数

1
2
3
4
5
6
7
8
9
10
11
func main() {
	dir, err := os.Getwd()
	if err != nil {
		panic(err)
	}
	config.ConfigInit(dir + "/internal/configs/config.json")  //根据配置文件初始化
	
	router := user_web_api.RouterInit() //采用user_web_api文件夹里面的router.go
	
	_ = router.Run(":" + config.Conf.UserWeb.ApiPort) //采用配置文件里的端口号
}

7.路由文件router.go的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func RouterInit() *gin.Engine {
    //gin常规写法，过两个默认中间件
	router := gin.Default()
	router.Use(gin.Logger())
	router.Use(gin.Recovery())
	
	router.Use(auth.CORS()) //自己写的解决跨域问题的
	mysqlStore, err := mysql.GetMysqlFactory() //使用工厂生成mysqlStore对象
	store.SetClient(mysqlStore)
	pkg.SetStore(mysqlStore)
	
	app := router.Group("/xy_web_user") //设置总路由
	userRouter := app.Group("/user") //设置子路由分组
	{
		userController := user.NewUserController(mysqlStore)
		userRouter.POST("/login", userController.UserLogin)
		userRouter.Use(auth.MiddleWare()) //在此之下的路由都会过中间件
		userRouter.POST("/update_password", userController.UpdatePassword)
	}
	return router
}

8.jwt生成和解密token

  • 使用传入的user_ id、branch_id，再加上配置文件里的secret字段生成token
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    func GetToken(userId, branchId int,secret string) (string,error) {
    	appSecret := secret
    	jwtKey = []byte(appSecret)
    	claim := &MyClaims{
    		UserId: userId,
    		BranchId: branchId,
    		StandardClaims:jwt.StandardClaims{
    			IssuedAt:  time.Now().Unix(),
    			Subject:   "userToken",
    		},
    	}
    	token := jwt.NewWithClaims(jwt.SigningMethodHS256, claim)
    	tokenString, err := token.SignedString(jwtKey)
    	if err != nil {
    		return "", err
    	}

    return tokenString, nil
    }
  • 解析token
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    func ParseToken(tokenString string)(*MyClaims, error)  {
    	claim := &MyClaims{}
    	jwtKey = []byte(config.Conf.AdminWeb.ApiSecret)
    	token,err := jwt.ParseWithClaims(tokenString,claim, func(token *jwt.Token) (interface{}, error) {
    		return jwtKey,nil
    	})
    	if err == nil && token != nil {
    		if token.Valid {
    			return claim,nil
    		} else {
    			return nil,errors.New("token解析失败")
    		}
    	}
    return nil,err
    }
  • 使用
    • 生成token
      1
      token, err := jwt.GetToken(admin.Id, admin.BranchId, config.Conf.AdminWeb.ApiSecret)
    • 中间件内解析token，并将其绑定到ctx上
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      //基础写法
      myClaims, err := jwt.ParseToken(token)
      ctx.Set("user_id", myClaims.UserId)
      ctx.Set("branch_id", myClaims.BranchId)

      //另一种保证安全性的写法，即保证token解析出来的token要在数据库里存在，如果上一步由于某种原因生成了错误的token，这里就会判断不存在并返回解析失败
      myClaims, err := jwt.ParseToken(token)
      user := &models.XyAdministrator{
      	Id: myClaims.UserId,
      	BranchId: myClaims.BranchId,
      }
      user, flag, err := store.Client().Admin().Get(ctx, user)
      if !flag {
      	code.BuildReturn(ctx, 0, "解析失败", "")
      	ctx.Abort()
      	return
      }
      ctx.Set("user_id", user.Id)
      ctx.Set("branch_id", user.BranchId)

9.上传文件接口的实现

  • 接受前端传的文件，得到一个*multipart.FileHeader类型变量
    1
    2
    3
    type param struct {
    		File	*multipart.FileHeader	`form:"file" json:"file" binding:"required"`
    	}
  • 用一个util包里的函数处理*multipart.FileHeader
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    func Upload(host, dir string, file *multipart.FileHeader) (string, error) {
        //获取当前运行路径
    	now, err := os.Getwd()

        //创建文件夹
    	dir = now + dir
    	err = os.MkdirAll(dir, os.ModePerm)
        
        //创建空白文件
    	fileName := dir + file.Filename
    	f, err := os.Create(fileName)
        
        //打开*multipart.FileHeader文件
    	defer f.Close()
    	open, err := file.Open()
    	
        //将打开的文件中的数据复制到刚刚创建的空白文件中
    	_, err = io.Copy(f, open)

    	url := host + fileName
    	return url, nil
    }
  • 调用方式
    1
    2
    3
    host := ctx.Request.Host //服务器地址
    dir := config.Conf.UserWeb.SaveDir //文件存储路径
    url, err := util.Upload(host, dir, request.File)

10.支付的实现

  • service层
    • 新建一个rpc对象，并用以下形式发起一个rpc请求
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      req := &protos.PayRequest{
      		Corp:   int32(corpId), //config.json文件里写好的值
      		Amount: amount,
      		Order:  order.OrderNo,
      		Open:   user.OpenId,
      		Notify: "https://sbd.sc-edu.com/qyk_app/qyk_app_api/order/callback", //支付完成后微信用Post访问的回调路由
      		//Notify: "www.baidu.com",
      		Body: "华澳教育课程购买",
      	}
      pay, err := rpcS.Pay.GetPay(ctx, req)
  • 回调路由的controller层
    • 处理回调内容，并回调rpc
      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
      func (c *ControllerOrder) OrderCallBack(ctx *gin.Context) {
      	// 回复微信的数据
      	rsp := new(wechat.NotifyResponse)
      	//获取参数
      	notifyReq, err := wechat.ParseNotifyToBodyMap(ctx.Request)
      	fmt.Println(notifyReq)
      	payTime := notifyReq["time_end"].(string)
      	if err != nil {
      		rsp.ReturnCode = gopay.FAIL
      		ctx.String(http.StatusOK, "%s", rsp.ToXmlString())
      		return
      	}
      	//校验签名
      	ok, err := wechat.VerifySign("fia6iaFI2iUhvzsHk4rfV9w4PRZLfZVk", wechat.SignType_MD5, notifyReq)
      	if !ok {
      		rsp.ReturnCode = gopay.FAIL
      		ctx.String(http.StatusOK, "%s", rsp.ToXmlString())
      		return
      	}
      	order, _ := c.store.Order().GetByOrderNo(ctx, notifyReq["out_trade_no"].(string))
      	if notifyReq["result_code"].(string) == "SUCCESS" && notifyReq["return_code"].(string) == "SUCCESS" {
      		//rpc回调
      		rpcS, _ := rpc.NewRpcService()
      		req := &protos.NotifyRequest{
      			Order:   order.OrderNo,
      			PayTime: times,
      		}
      		_, err = rpcS.Pay.PayNotify(ctx, req)
      		if err != nil {
      			fmt.Println(err.Error())
      		}
      		rsp.ReturnCode = gopay.SUCCESS

      		ctx.String(http.StatusOK, "%s", rsp.ToXmlString())
      		return
      	}
      	rsp.ReturnCode = gopay.FAIL
      	ctx.String(http.StatusOK, "%s", rsp.ToXmlString())
      	return
      }
    • 处理数据库相关字段的更新

11.处理过期15分钟的未支付订单脚本

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
package main

import (
	"430api/internal/qyk_back_api/store/mysql"
	"fmt"
	"time"
)

func main() {
	fmt.Println("SyncWxCourseOrder" + time.Now().Format("2006-01-02 15:04:05"))
	d, _ := time.ParseDuration("-15m")
	pastTime := time.Now().Add(d).Format("2006-01-02 15:04:05")

	mysqlStore, _ := mysql.GetMysqlFactory()
	orderList, err := mysqlStore.Order().GetListForPastTime(pastTime)
	if err != nil {
		fmt.Println(err)
		return
	}
	for _, qykOrder := range orderList {
		_ = mysqlStore.OrderDetail().UpdateForPastTime(qykOrder.Id)
	}
	fmt.Println("over")
}

C++

1.字符串分割

  • 以char分割版本
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    vector<string> split(string& str, char target){
       	vector<string> res;

       	string temple = "";
       	istringstream templeStream(str);
       	while (getline(templeStream, temple, target)){
         	res.push_back(temple);
       	}
       	
       	return res;
    }
  • 以string分割版本
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    vector<string> splitWithStl(const string &str,const string &pattern){
        vector<string> resVec;
        
        if ("" == str)
        {
            return resVec;
        }
        //方便截取最后一段数据
        string strs = str + pattern;
        
        size_t pos = strs.find(pattern);
        size_t size = strs.size();
        
        while (pos != string::npos)
        {
            string x = strs.substr(0,pos);
            resVec.push_back(x);
            strs = strs.substr(pos+1,size);
            pos = strs.find(pattern);
        }
        
        return resVec;
    }