发表于

大家好，我是煎鱼。

这是一个很多其他语言工程师转 Go 语言的时间节点，这就难免不论一番比较。其中一个经典的运算上的就是 “三元运算符”：

图片

为什么 Go 语言不支持三元运算符，Go 不支持三元运算符就是设计的不好，是历史在开倒车吗？

今天就由煎鱼来和大家一起摸索为什么。

三元运算符是什么

三元运算符，在典型的数学意义上，或者从解析器的角度来看，是一个需要三个参数的运算符。而我们日常中，最常见的是二元运算符：

1
2
3
复制代码x + y
x / y
x * y

还有一元运算符：

1
2
3
css复制代码-a
~b
!c

以及今天的男主角 “三元运算符”。在 C/C++ 等多种语言中，我们可以根据条件声明和初始化变量的习惯来选择性使用三元条件运算符：

1
kotlin复制代码int index = val > 0 ? val : -val

Go 使用三元运算符

想在 Go 语言里也使用三元运算符时，发现居然没有…想要实现与上面相同的代码段的方式似乎只能：

1
2
3
4
5
6
7
kotlin复制代码var index int

if val > 0 {
    index = val
} else {
    index = -val
}

看上去十分的冗余，不够简洁。

为什么 Go 没有三元运算符

为什么 Go 没有 ?: 操作符，没有的话，官方推荐的方式是怎么样的。

通过 Go FAQ 我们可以得知：

图片

Go 官方就是推荐我们使用前面提到的方式来替代，并且明确了如下态度：

  • Go 中没有 ?: 的原因是语言的设计者看到这个操作经常被用来创建难以理解的复杂表达式。
  • 在替代方案上，if-else 形式虽然较长，但无疑是更清晰的。一门语言只需要一个条件控制流结构。

整体来讲，Go 语言的设计者是为了考虑可读性拒绝了实现三元运算符，”less is more.” 也是标榜台词了。

社区争议

Go 语言的一些点与众不同，基本是大家皆知的。无论是 if err != nil，又或是本次的三元运算符，要大家用 if-else 替代：

1
2
3
4
5
ini复制代码if expr {
    n = trueVal
} else {
    n = falseVal
}

反对和同意

反对

因此有社区小伙伴给出了反对，基本分为如下几类：

  1. 认为 if-else 也有以类似情况能被滥用，设计者的理由不够充分，认为是 “借口”。
  2. 认为三元运算符的 “丑陋” 问题，是开发者的编码问题，而不是语言问题。三元在各种语言中很常见，它们是正常的，Go 语言也应该要有。
  3. 认为用 if-else 替代三元运算符也很麻烦，让开发者多读了 3-4 行和额外的缩进级别。

同意

认可这个决策的也有不少，为此给出了大量的真实工程案例。

一般来讲，我们用三元运算符是希望这么用：

1
erlang复制代码cond ? true_value : false_value

你可能见过这么用：

1
erlang复制代码cond ? value_a + value_b : value_c * value_d

还见过这样：

1
2
3
less复制代码(((cond_a ? val_one) : cond_b) ? val_two) : val_three

cond_a ? (val_one : (cond_b ? (val_two : val_three)))

还能嵌套三元运算符：

1
2
3
ini复制代码int a = cond_a ? val_one :
    cond_b ? val_two :
    cond_c ? val_three : val_four;

也能出现可读性更差的：

1
2
3
4
5
6
7
8
arduino复制代码void rgb_to_lightness_(
  const double re, const double gr, const double bl, double &li)
{
  li=((re < gr) ? ((gr < bl) ? bl : gr) : ((re < bl) ? bl : re) +
                            (gr < re)
                          ? ((bl < gr) ? bl : gr)
                          : ((bl < re) ? bl : re)) / 2.0;
}

说白了就是真实的代码工程中，大家见到过大量三元运算符滥用的场景，纷纷给出了大量的难理解的例子，让大家困扰不堪。

总结

在这篇文章中，首先针对 “三元运算符” 做了基本的介绍。紧接着根据 Go 语言不支持三元的态度进行了说明，且面向社区的争议我们分为了正反方面的基本诠释。

实际上一个简单的 ?: 既整洁又实用，但是没有很好又高效的办法方法可以防止丑陋的嵌套，也就是排除可读性的问题。

在真实的业务工程中，常常能看到一个三元运算符，一开始只是很简单。后面嵌套越加越深，逻辑越写越复杂，从而带来了许多维护上的问题。

给大家抛出如下问题：

  • 你认为 Go 语言是否要有三元运算符呢？
  • 如果要有，复杂嵌套的三元运算符又如何考虑呢？

欢迎大家在评论区留言和交流 ：）

若有任何疑问欢迎评论区反馈和交流，最好的关系是互相成就，各位的点赞就是煎鱼创作的最大动力，感谢支持。

文章持续更新，可以微信搜【脑子进煎鱼了】阅读，本文 GitHub github.com/eddycjy/blo… 已收录，学习 Go 语言可以看 Go 学习地图和路线，欢迎 Star 催更。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于
  • 本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

非常感谢你阅读本文~
欢迎【👍点赞】【⭐收藏】【📝评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://juejin.cn/user/2771185768884824/posts 博客原创~

  1. 保持城市天际线：

在二维数组grid中，grid[i][j]代表位于某处的建筑物的高度。 我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。 高度 0 也被认为是建筑物。

最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。

建筑物高度可以增加的最大总和是多少？

样例 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
less复制代码输入：
	grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：
	35
解释：
	The grid is:
	[ [3, 0, 8, 4], 
	  [2, 4, 5, 7],
	  [9, 2, 6, 3],
	  [0, 3, 1, 0] ]
	
	从数组竖直方向（即顶部，底部）看“天际线”是：[9, 4, 8, 7]
	从水平水平方向（即左侧，右侧）看“天际线”是：[8, 7, 9, 3]
	
	在不影响天际线的情况下对建筑物进行增高后，新数组如下：
	
	gridNew = [ [8, 4, 8, 7],
	            [7, 4, 7, 7],
	            [9, 4, 8, 7],
	            [3, 3, 3, 3] ]

提示

  • 1 < grid.length = grid[0].length <= 50。
  • grid[i][j] 的高度范围是： [0, 100]。
  • 一座建筑物占据一个grid[i][j]：换言之，它们是 1 x 1 x grid[i][j] 的长方体。

分析

  • 首先要明白天际线是什么：城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。影响轮廓的就是你所看方向上，每一行或列上最高的建筑的高度。
  • 所以我们把所看方向上较低的建筑增高到恰好是最高建筑一样的高度，就是在不影响天际线的情况下，建筑物能增加的最大高度。
  • 但是四个方向的天际线都不能影响，思考一下就知道上和下，左和右的天际线是一致的。那么我们只需要在增加建筑物高度的时候，同时考虑2个天际线就可以了，并且我们只能增加到其中较低的高度才能都不影响。
  • 可以分两步，第一步先算出天际线，第二步统计结果。

题解

java

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
java复制代码class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int   n        = grid.length;

        // 算出天际线
        int[] rowMaxes = new int[n];
        int[] colMaxes = new int[n];
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                rowMaxes[r] = Math.max(rowMaxes[r], grid[r][c]);
                colMaxes[c] = Math.max(colMaxes[c], grid[r][c]);
            }
        }

        int ans = 0;

        // 计算结果
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                ans += Math.min(rowMaxes[r], colMaxes[c]) - grid[r][c];
            }
        }

        return ans;
    }
}

c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
c复制代码int maxIncreaseKeepingSkyline(int** grid, int gridSize, int* gridColSize){
    // 算出天际线
    int rowMaxes[gridSize];
    int colMaxes[*gridColSize];
    memset(rowMaxes, 0, sizeof(rowMaxes));
    memset(colMaxes, 0, sizeof(colMaxes));
    for (int r = 0; r < gridSize; ++r) {
        for (int c = 0; c < *gridColSize; ++c) {
            rowMaxes[r] = fmax(rowMaxes[r], grid[r][c]);
            colMaxes[c] = fmax(colMaxes[c], grid[r][c]);
        }
    }

    int ans = 0;

    // 计算结果
    for (int r = 0; r < gridSize; ++r) {
        for (int c = 0; c < *gridColSize; ++c) {
            ans += fmin(rowMaxes[r], colMaxes[c]) - grid[r][c];
        }
    }

    return ans;
}

c++

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
cpp复制代码class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int   n        = grid.size();

        // 算出天际线
        vector<int> rowMaxes(n, 0);
        vector<int> colMaxes(n, 0);
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                rowMaxes[r] = max(rowMaxes[r], grid[r][c]);
                colMaxes[c] = max(colMaxes[c], grid[r][c]);
            }
        }

        int ans = 0;

        // 计算结果
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c];
            }
        }

        return ans;
    }
};

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
python复制代码class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 算出天际线
        rowMaxes = [0] * n
        colMaxes = [0] * n
        for r in range(n):
            for c in range(n):
                rowMaxes[r] = max(rowMaxes[r], grid[r][c])
                colMaxes[c] = max(colMaxes[c], grid[r][c])
        ans = 0
        #计算结果
        for r in range(n):
            for c in range(n):
                ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
        return ans

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
27
28
29
30
31
32
33
34
35
36
37
38
go复制代码func maxIncreaseKeepingSkyline(grid [][]int) int {
    n := len(grid)

	// 算出天际线
	rowMaxes := make([]int, n)
	colMaxes := make([]int, n)
	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			rowMaxes[r] = max(rowMaxes[r], grid[r][c])
			colMaxes[c] = max(colMaxes[c], grid[r][c])
		}
	}

	ans := 0

	// 计算结果
	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
		}
	}

	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

rust

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
rust复制代码impl Solution {
    pub fn max_increase_keeping_skyline(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();

        // 算出天际线
        let mut rowMaxes = vec![0; n];
        let mut colMaxes = vec![0; n];
        for r in 0..n {
            for c in 0..n {
                rowMaxes[r] = rowMaxes[r].max(grid[r][c]);
                colMaxes[c] = colMaxes[c].max(grid[r][c]);
            }
        }

        let mut ans = 0;

        // 计算结果
        for r in 0..n {
            for c in 0..n {
                ans += rowMaxes[r].min(colMaxes[c]) - grid[r][c];
            }
        }

        return ans;
    }
}

在这里插入图片描述

原题传送门：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/

欢迎在评论区讨论，掘金官方将在掘力星计划活动结束后，在评论区抽送100份掘金周边，抽奖详情见活动文章

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

本文已参与 「掘力星计划」 ，赢取创作大礼包，挑战创作激励金。

最近在工作中，有这么一个场景用到了JWT签发和验证token，只是单纯的使用JWT，也没有使用SpringSecurity和Shiro什么的进行整合，没想到一个简单的功能前前后后一周改了四五遍，可以说经历了不断的优化，来一起看看修改的历程吧。

1.0版本

最初的版本是这样处理的，在Controller层的接口里传入HttpServletRequest参数：

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码@RestController
@RequestMapping("api")
public class TestController {
    @Autowired
    MyService myService;

    @GetMapping("test")
    public String test(HttpServletRequest request){
        String result = myService.test(request);
        return result;
    }
}

为了简单明了，这里省略了Service的接口层，直接调用Service层的方法：

1
2
3
4
5
6
7
8
9
java复制代码@Service
public class MyService {
    public String test(HttpServletRequest request){
        String token = request.getHeader("token");
        System.out.println(token);
        //验证token，处理业务逻辑
        return "success";
    }
}

在方法中通过HttpServletRequest获取头信息中的token，然后进行验证，之后再做业务逻辑处理。乍一看没什么问题，但是写多了就觉得这么写很麻烦，每个接口都要多这么一个不必要的参数，能不能处理一下呢？

2.0版本

这时候想起来了，以前学Spring的时候不就说过吗，处理这种和业务无关的大量重复劳动，放在切面里不就好了吗。但回头一想，Service里的方法也不是每个都需要验证token，干脆写个注解，用切面来处理加了注解的方法。

定义一个注解，名字叫NeedToken，也不需要什么属性，简单易懂：

1
2
3
4
5
java复制代码@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface NeedToken {
}

切面要做的很简单，通过SpringMvc提供的RequestContextHolder获取当前的HttpServletRequest请求，然后再取出header中的token。

这时候第一个问题来了，我在切面获取到了token以后，怎么传递给Service中调用的方法呢？

回想到在切面中可以获取方法的参数，然后动态修改参数的值就可以了。修改Service方法的参数，去掉烦人的HttpServletRequest，添加一个Strings类型的参数，用于接收token。

1
2
3
4
5
6
7
8
9
java复制代码@Service
public class MyService {
    @NeedToken
    public String test(String token){
        System.out.println(token);
        //验证token，处理业务逻辑
        return "success";
    }
}

切面实现如下：

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
java复制代码@Aspect
@Component
public class TokenAspect {
    @Pointcut("@annotation(com.cn.hydra.aspectdemo.annotation.NeedToken)")
    public void tokenPointCut() {
    }

    @Around("tokenPointCut()")
    public Object doAround(ProceedingJoinPoint point) throws Throwable {
        ServletRequestAttributes attributes = (ServletRequestAttributes) RequestContextHolder.getRequestAttributes();
        HttpServletRequest request = attributes.getRequest();
        String token = request.getHeader("token");

        Object[] args = point.getArgs();
        Signature signature = point.getSignature();
        MethodSignature methodSignature = (MethodSignature) signature;
        String[] paramName = methodSignature.getParameterNames();
        List<String> paramNameList = Arrays.asList(paramName);
        if (paramNameList.contains("token")){
            int pos = paramNameList.indexOf("token");
            args[pos]=token;
        }

        Object object = point.proceed(args);
        return object;
    }
}

切面中做了下面几件事：

  • 定义切点，在加了@NeedToken注解的方法织入逻辑
  • 通过RequestContextHolder获取HttpServletRequest ，获取header中的token
  • 通过MethodSignature 获取方法的参数列表，修改参数列表中的token的值
  • 使用新的参数列表调用原方法，这时候就把token传递给了方法

顺带修改一下Controller的方法，这时候就已经不需要传入HttpServletRequest 了，但是因为要调用Service的方法，并且方法中有一个参数token，这里可以随意传一个值，暂且传了个null：

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码@RestController
@RequestMapping("api")
public class TestController {
    @Autowired
    MyService myService;
    
    @GetMapping("test")
    public String test(){
        String result = myService.test(null);
        return result;
    }
}

写到这里，虽然说能解决问题，但是要多写一个null的参数，就让人就很难受了，作为强迫症必须想办法把它干掉。

3.0版本

那么如果不通过传递参数的方式，有什么办法能把token传递给方法呢？这里灵机一动，可以通过切面获取方法属于的对象啊，有了对象就好办了，直接通过反射给某个属性注入值。再次修改Service，声明一个全局变量，用于反射注入token使用。

1
2
3
4
5
6
7
8
9
10
11
java复制代码@Service
public class MyService{
    private String TOKEN;
    
    @NeedToken
    public String test() {
        System.out.println(TOKEN);
        //验证token，处理业务逻辑
        return  TOKEN;
    }
}

修改切面实现方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
java复制代码@Around("tokenPointCut()")
public Object doAround(ProceedingJoinPoint point) throws Throwable {
    try {
        ServletRequestAttributes attributes=(ServletRequestAttributes) RequestContextHolder.getRequestAttributes();
        HttpServletRequest request = attributes.getRequest();
        String token = request.getHeader("token");

        Field tokenField = point.getTarget().getClass().getDeclaredField("TOKEN");
        tokenField.setAccessible(true);
        tokenField.set(point.getTarget(),token);

        Object object = point.proceed();
        return object;
    } catch (Throwable e) {
        e.printStackTrace();
        throw e;
    }
}

注意这里不再去修改方法传入的参数，而是通过获取类的Field ，然后向当前对象的token对应的Field注入实际值来实现的。

写到这自我感觉良好了一会，但是写了几个类发现了我每个Service类都得多声明一个String类型的token全局变量啊，不光是麻烦，万一哪个类忘了写不就直接gg了，有没有什么更简便、安全的方法呢？

4.0版本

所以说偷懒和摸鱼的愿景真的是推动社会进步的一大原动力，左思右想后干脆写一个父类，把token声明在父类里，然后每个Service作为子类来继承他，这样就不会忘记了，并且代码也干净了很多。

先定义一个父类，至于为什么使用父类而不是接口，原因就是接口中声明的变量是默认被final修饰的，所以是不能被改变的。

1
2
3
java复制代码public class BaseService {
    public String TOKEN = null;
}

修改Service代码，继承BaseService类，删掉自己的TOKEN变量：

1
2
3
4
5
6
7
8
9
java复制代码@Service
public class MyService extends BaseService {
    @NeedToken
    public String test() {
        System.out.println(TOKEN);
        //验证token，处理业务逻辑
        return  TOKEN;
    }
}

调用一下接口测试，结果抛出异常：

1
2
3
4
vbscript复制代码java.lang.NoSuchFieldException: TOKEN
  at java.lang.Class.getDeclaredField(Class.java:2070)
  at com.cn.hydra.aspectdemo.aspect.TokenAspect.doAround(TokenAspect.java:35)
  ...

分析了一下，看样子是反射的时候不能通过当前对象拿到父类中定义的变量，那我们就简单修改一下切面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
java复制代码@Around("tokenPointCut()")
public Object doAround(ProceedingJoinPoint point) throws Throwable {
    try {
        ServletRequestAttributes attributes=(ServletRequestAttributes) RequestContextHolder.getRequestAttributes();
        HttpServletRequest request = attributes.getRequest();
        String token = request.getHeader("token");

        //Field tokenField = point.getTarget().getClass().getDeclaredField("TOKEN");
        Class<?> baseClazz = point.getTarget().getClass().getSuperclass();
        Field tokenField = baseClazz.getDeclaredField("TOKEN");
        tokenField.setAccessible(true);
        tokenField.set(point.getTarget(),token);

        Object object = point.proceed();
        return object;
    } catch (Throwable e) {
        e.printStackTrace();
        throw e;
    }
}

修改为通过当前对象获取父类，然后获取父类中的变量，再通过反射注入token值。

测试了几遍token获取都没啥问题，简直美滋滋。但是隔了一天突然发现不对啊，众所周知Spring的默认情况下Bean都是单例模式，并且全局变量的值任何一个线程都可能去改变。那么就存在情况，可能一个线程会拿到另一个线程修改后的token。修改的方法倒也不是没有，但是为了个token我再把Bean的作用域改为prototype或者request，岂不是得不偿失。

想到这里，立马着手验证一下拿到的token是否是自己的，在Service中添加一个方法，方法有一个参数name表明用户身份，一会要拿来和token进行比对：

1
2
3
4
5
6
7
8
java复制代码@Service
public class MyService extends BaseService {
    @NeedToken
    public boolean checkToken(String name) {
        System.out.println(name+"  "+TOKEN  +" "+ name.equals(TOKEN));
        return  name.equals(TOKEN);
    }
}

使用CyclicBarrier测试200个并发请求，注意这里不要使用postman进行测试，因为说到底postman的runner执行请求的时候还是串行的。所以说如果对JMeter什么的工具不太熟悉的话，还是用CyclicBarrier比较简单实用。（对CyclicBarrier不熟悉的同学，可以看看以前写过的这篇CyclicBarrier）

测试类实现如下：

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
63
64
65
66
67
68
java复制代码public class HttpSendTest {
    public static void main(String[] args) {
        CyclicBarrier barrier=new CyclicBarrier(200);
        Thread[] threads=new Thread[100];
        for (int i = 0; i <100 ; i++) {
            threads[i]=new Thread(()->{
                try {
                    barrier.awit();sendGet("http://127.0.0.1:8088/api/test2","name=hydra","hydra");
                    //barrier.await();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            });
            threads[i].start();
        }

        Thread[] threads2=new Thread[100];
        for (int i = 0; i <100 ; i++) {
            threads2[i]=new Thread(()->{
                try {
                    sendGet("http://127.0.0.1:8088/api/test2","name=trunks","trunks");
                    /移上barrier.await();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            });
            threads2[i].start();
        }
    }

    public static String sendGet(String url, String param, String token) {
        StringBuilder result = new StringBuilder();
        BufferedReader in = null;
        try {
            String urlNameString = url + "?" + param;
            URL realUrl = new URL(urlNameString);
            URLConnection connection = realUrl.openConnection();
            connection.setRequestProperty("accept", "*/*");
            connection.setRequestProperty("connection", "Keep-Alive");
            connection.setRequestProperty("token", token);
            connection.setRequestProperty("user-agent", "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1;SV1)");
            connection.connect();
            in = new BufferedReader(new InputStreamReader(connection.getInputStream(), "UTF-8"));
            String line;
            while ((line = in.readLine()) != null) {
                result.append(line);
            }
            System.out.println(result);
        } catch (ConnectException e) {
            e.printStackTrace();
        } catch (SocketTimeoutException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                if (in != null) {
                    in.close();
                }
            } catch (Exception ex) {
                ex.printStackTrace();
            }
        }
        return result.toString();
    }
}

测试中传给参数的name属性和请求中携带的token相同，跑一下测试用例，发现在高并发情况下，确实出现了一些不匹配的情况，说明取到的token不是自己的：

图片

5.0版本

辛辛苦苦改了几版的代码居然有这么大的问题，这可咋整啊？再回头一想，不就是要保证每个线程有自己的唯一的一份token的副本吗，这不是正好可以使用ThreadLocal嘛。

重新定义父类，使用ThreadLocal保存token：

1
2
3
4
java复制代码spublic class BaseService2 {
    public static ThreadLocal<String> TOKEN= 
            ThreadLocal.withInitial(() -> null);
}

修改Service：

1
2
3
4
5
6
7
8
9
10
java复制代码@Service
public class MyService2 extends BaseService2 {
    @NeedToken
    public boolean testToken(String name) {
        String token=TOKEN.get();
        boolean check = name.equals(token);
        System.out.println(name+"  "+token +"  "+check);
        return  check;
    }
}

修改切面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码@Around("tokenPointCut()")
public Object doAround(ProceedingJoinPoint point) throws Throwable {
    try {

        ServletRequestAttributes attributes=(ServletRequestAttributes) RequestContextHolder.getRequestAttributes();
        HttpServletRequest request = attributes.getRequest();
        String token = request.getHeader("token");

        Class<?> baseClazz = point.getTarget().getClass().getSuperclass();
        Field tokenField = baseClazz.getDeclaredField("TOKEN");
        ThreadLocal<String> local = (ThreadLocal<String>) tokenField.get(point.getTarget());
        local.set(token);

        tokenField.setAccessible(true);
        tokenField.set(point.getTarget(),local);

        Object object = point.proceed();
        return object;
    } catch (Throwable e) {
        e.printStackTrace();
        throw e;
    }
}

通过反射拿到ThreadLocal对象，通过set方法给ThreadLocal赋值后，再通过反射把它写回对象 。再次并发测试，即使在600个并发请求情况下，也没有出现异常情况。优化过程到这里就暂且结束了，当然可能还有什么没想到的地方，欢迎大家给我留言讨论。

最后

如果觉得对您有所帮助，小伙伴们可以点赞、转发一下，非常感谢

公众号码农参上，加个好友，做个点赞之交啊

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

这是写给一些新人大学生的知识点，大神可以直接划走。

相信在大学时候打过算法竞赛的同学都已经在一开始接触过大数加法。有人会说，加法不是直接用+直接相加就行了吗？

的确例如 int a ; int b 直接相加可以得出 int c

如果数和小的话，的确是可以的但是如果数字是：100000000000000000000000000….省略几百位。

这样子的数字是int存不下的，就算你的int64最多也就存2的32次方-1这个数字已经是最大了，注意这里还有负数的存在，所以是2的32次方-1，而不是64次方。所以我们应该需要怎么办呢？

答案是数组，例如int a[300]这样的数字就可以存到300位数字。

1
2
3
4
5
6
7
8
scss复制代码
        char s1[M], s2[M];
	int num1[M] = {0};           // 数字数组num1 
	int num2[M] = {0};           // 数字数组num2 
	scanf("%s %s", s1, s2);    
	
	len_s1 = strlen(s1);         //	求第一个加数的位数 
	len_s2 = strlen(s2);	     // 求第二个加数的位数

直接开干，上面的M就是你自己定义的位数，这里你随意。一般定义100左右就行了，100位数，已经大得相当吓人。

1
2
3
4
5
6
7
8
9
10
ini复制代码        for(i=len_s1-1, j=0; i>=0; i--)   //将字符数组转化为数字数组，并倒数存放，作为第一个加数 
	{
		num1[j] = s1[i] - '0';
		j++;
	}
	for(i=len_s2-1, j=0; i>=0; i--)   //将字符数组转化为数字数组，并倒数存放，作为第二个加数 
	{
		num2[j] = s2[i] - '0';
		j++;
	}

将字符串转换为数字，需要-‘0’，然后最重要的一步就是为什么需要倒序呢？因为我们的加法就是从右到左的，1000+1000是0和0先加，而不是1和1先加，所以需要做一个倒序。如果整不明白的话，可以直接列出一条加法竖式就一目了然了。

1
2
3
4
5
6
7
8
9
ini复制代码        for(i=0; i<=M; i++)               //实现大数的加法 
	{
		num1[i] = num1[i]+num2[i];
		if(num1[i]>9)
		{
			num1[i] = num1[i]-10;
			num1[i+1]++; 	
		}	
	}

最后进行加法的模拟运算就行了，这里需要记得num1[i+1]++;进位操作，如果这个位置上面是大于等于10的数字，那么我们就需要进行进位。这也是在模拟我们的加法竖式而已。

image.png

上面是效果图。

上面的图，我只是随便写了两个数字，更复杂的数字也是可以计算出来的。

然后拓展思考一下，除了大数加法，我们还可以做大数减法，大数乘法，大数除法这些练习。原理不变，就是用数组来模拟平台的算数运算而已。

更加高阶一点的话，我们可以做带有小数点的运算。

欢迎和我讨论有关程序的问题，也可以答疑。关注公众号：诗一样的代码，交一个朋友。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

一、前言

  1024程序节，祝大家节日快乐呀！

  最近有小伙伴和我谈心，觉得刷算法题太难了，完全没有思路，很有挫败感，想要放弃了。想想自己也深有感触，有这些想法真都挺正常的，其实我们刷算法就是为了培养一个思考问题、解决问题的思维，这个思维养成并不是一蹴而就的，而是循序渐进的。

  所以，这个是成长的必经之路，取经还要经历九九百十一难呢，但只要坚持下来，每天都是一个全新的自己，小白变成大神的路注定不会简单，但你愿意一直碌碌无为，还安慰自己平凡可贵？

  坚持下来，就能剥茧成蝶！请继续跟小诚一起学习，小诚会尽自己最大的努力，将每道算法题从题目剖析到解决方案都讲得更加通俗理解，与大家共同成长。如果大家刷题时，感觉到挫败了，想要放弃了，欢迎找小诚吐槽，小诚会给你充满能量再出发！

二、无重复字符的最长子串

  心里话讲完了，来看看今天遇到的Boss: 《无重复字符的最长子串》。

  Boss介绍： 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

  示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ini复制代码
示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2：

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例三：

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例4：

输入: s = ""
输出: 0

  通过提示：

  • 0 <= s.length <= 5 * 10410^4104
  • s 由英文字母、数字、符号和空格组成

三、题目分析

  这个题目看起来其实相对来说比较简单，但是如果不能很好的理解它其中包含的细节，也很容易被误导方向。

  细节一：子串和子序列的区别

  子串： 子串是必须能够从原字符串中找到的，在原字符串必须连续的一段。如：字符串abc中ab、bc都为子串。

  子序列： 原序列中可以不连续的一段字符，如;字符串abc中ac即为字符序列

  细节二：字符串由英文字母、数字、符号和空格组成

  字符串不包含中文，这样方便我们使用第四种解决方案(猜猜是啥)

四、通关方式一：暴力破解

  方案介绍： 暴力破解，通过多个循环以穷举的方式 找出答案。简单且易想到的方案，包括之前我们刷的两道算法题也可以使用暴力破解来解决，缺点就是虽然简单，但是效率非常低，并非是最优方案。

  具体思路： 将字符串中每个字符作为一个循环，和子串的组合进行比较，从而获取最长字串长度。如字符串abc，则第一轮比较为: 字符 a和子串a、ab、abc比较，第二轮则为字符b和子串b、bc比较，以此类推，最后获取不重复的子串长度。

解题代码：

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
java复制代码 /**
     * 方案一：暴力破解
          *
          * @param s
               * @return
               */
            public static Integer lengthOfLongestSubstring(String s) {
            int maxLength = 0;
            //  每轮是用一个字符和子串进行比较，如果不存在重复字符则获取最大长度，知道最后一个字符位置
            for (int i = 0; i < s.length(); i++) {
                for (int j = i + 1; j <= s.length(); j++) {
                if (!judgeCharacterExist(i, j, s)) {
                    maxLength = Math.max(maxLength, j - i);
                }
                }
            }
            return maxLength;
            }


/**
 * 判断子串中是否存在重复字符
 *
 * @param start
 * @param end
 * @param param
 * @return
 */
private static Boolean judgeCharacterExist(int start, int end, String param) {
    HashSet<Character> hashSet = new HashSet<>();
    for (int i = start; i < end; i++) {
        if (hashSet.contains(param.charAt(i))) {
            return true;
        }
        hashSet.add(param.charAt(i));
    }
    return false;
}

  算法时间复杂度推导：

  通过上面实现的代码可知，随着输入问题规模增大(既字符串长度编程)，需要进行判断的逻辑之间的函数为f(n) = n3^33，根据大O记法可推导出，暴力破解算法的时间复杂度为O(n3^33)，三次方的函数，可想而知当输入规模变大时它的效率有多低了。

  解题结果： 放到leetcode上执行代码是没有问题的，但是提交的时候会提示超时，因为提交时需要验证987个案例，有些案例字符串包含字符非常多，最后导致执行超时，因此这个方案是绝对不推荐的！

image-20211024193021675

五、通关方式二：滑动窗口法

  滑动窗口： 是数组和字符串中一个抽象的概念，可以分为滑动和窗口两个概念理解。

  窗口：即表示一个范围，通常是字符串和数组从开始到结束两个索引范围中间包含的一系列元素集合。 如字符串abcd，如果开始索引和结束索引分别为0、2的话，这个窗口包含的字符则为：abc。

  滑动：它表示窗口的开始和结束索引是可以往某个方向移动的。 如上面的例子开始索引和结束索引分别为0、2的话，当开始索引和结束索引都往右移动一位时，它们的索引值则分别为1、3，这个窗口包含的字符为：bcd。

  下面使用具体的图片来更加形象地认识“滑动窗口”：

image-20211024195335027

  介绍完“滑动窗口”的概念后，下面我们来看看如何通过这个方式来解决无重复字符的最长子串问题，思路如下：

  使用一个HashSet来实现滑动窗口，用来检查重复字符。 维护开始和结束两个索引，默认都是从0开始，然后随着循环【向右移动结束索引】，遇到不是重复字符则放入窗里，遇到重复字符则【向右侧移动开始索引】，最终得到结果，下面来看具体图解：

  代码如下：

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
java复制代码    /**
     * 方案二：滑动窗口
          *
          * @param s
               * @return
               */
         public static Integer lengthOfLongestSubstring2(String s) {
            int maxLength = 0;
            // 左指针
            int leftPoint = 0;
            // 右指针
            int rightPoint = 0;
            // 用于判断重复的Set集合(窗口)
            Set<Character> set = new HashSet<>();
            while (leftPoint < s.length() && rightPoint < s.length()) {
                if (!set.contains(s.charAt(rightPoint))) {
                // 不存在重复字符时将字符存储入set，并将右边指针向后移动一位
                set.add(s.charAt(rightPoint++));
                maxLength = Math.max(maxLength, rightPoint - leftPoint);
                } else {
                // 存在重复元素，则将左边指针向右移动一位(删除与当前相同的字符)
                set.remove(s.charAt(leftPoint++));
                }
            }
            return maxLength;
            }

image-20211024202212197

  算法时间复杂度推导：

  通过上面实现的代码可知，随着输入问题规模增大(既字符串长度编程)，需要进行判断的逻辑之间的函数为f(n) = n，根据大O记法可推导出，滑动窗口算法的时间复杂度为O(n)，相比于暴力破解，它的效率大大提高了。

  执行结果：

image-20211024203629134

五、通关方式三：滑动窗口法优化(一)

  虽然方式使用了滑动窗口时间复杂度只有O(n)，但是如果存在重复字符还需要移动开始索引，因此我们可以考虑借助之前其他算法谈到的“空间换时间”的想法，通过借助HashMap建立字符和索引映射，避免手动移动索引。

  代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码 /**
     * 滑动窗口优化一
     *
     * @param s
     * @return
     */
    public static Integer lengthOfLongestSubstring(String s) {
        char[] charArray = s.toCharArray();
        // 使用HashMap来建立字符和索引的映射
        HashMap<Character, Integer> keyMapping = new HashMap<>();
        Integer maxLength = 0;
        // 开始索引
        Integer leftIndex = 0;
        for (int i = 0; i < charArray.length; i++) {
            if (keyMapping.containsKey(charArray[i])) {
            	//  存在重复数据则获取索引值最大的
                leftIndex = Math.max(leftIndex, keyMapping.get(charArray[i]));
            }
            // 值重复则进行覆盖
            keyMapping.put(charArray[i], i + 1);
            maxLength = Math.max(maxLength, i - leftIndex + 1);
        }
        return maxLength;
    }

  算法时间复杂度推导：

  通过上面实现的代码可知，随着输入问题规模增大(既字符串长度编程)，需要进行判断的逻辑之间的函数为f(n) = n，根据大O记法可推导出，滑动窗口法优化算法的时间复杂度为O(n)，虽然和上一种方案的时间复杂度是一样的，但是效率还是有一定的提高(思考问题时要思考是否还有其他有优质的方案，培养发散思维)。

  执行结果：

image-20211024204035861

七、通关方式四：字符与ASCII映射

  上面题目分析的时候就提到了要注意题目中提到的：【字符串英文字母、数字、符号和空格组成】，这些字符是可以使用ASCII表示(如字符a的ASCII值为97，想具体了解的可以百度下)，那么我们就可以建议字符与ASCII的映射关系，从而实现重复字符的排除。

  代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
ini复制代码public static Integer lengthOfLongestSubstring(String s) {
        int[] index = new int[128];
        int len = 0;
        int length = s.length();
        for (int i = 0, j = 0; j < length; j++) {
            // 如果存在重复字符，则获取最大的下标
            i = Math.max(index[s.charAt(j)], i);
            // 每轮都拿之前与【当前字符一样】最大的下标跟当前下标的差做为最大的字串长度
            len = Math.max(len, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return len;
    }

  算法时间复杂度推导：

  通过上面实现的代码可知，随着输入问题规模增大(既字符串长度编程)，需要进行判断的逻辑之间的函数为f(n) = n，根据大O记法可推导出，字符与ASCII映射算法的时间复杂度为O(n)。

  执行结果：

image-20211024213726230

八：算法思想在实际业务中的使用

  1、滑动窗口算法常用于解决字符串、数组中涉及子元素的一些问题。如本题中的查找无重复字符串最长子串长度。

  2、滑动窗口算法也可以用于优化for循环，将多重循环转换成单层循环，用于降低时间复杂度，提高执行性能。

九：写在最后

  一个问题，有些时间不要只纠结于一种解法，可以通过发散思维去多方面考虑，寻找解决方案。发散思维也不是一开始就有，需要不断的联系，积累。因此，每刷一道题，都需要学会自我总结，转换成自己的东西。

  时光不负有心人！如果文章如您有帮助，欢迎给我点赞、关注、收藏(一键三连)。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于
声明：本文只作学习研究，禁止用于非法用途，否则后果自负，如有侵权，请告知删除，谢谢！

项目场景：

我上一篇文章写了网易云参数的解密，这次我们来爬取画画的baby的全部评论。

解决方案：

1.先来看看评论的接口，可以看出是https://music.163.com/weapi/comment/resource/comments/get?csrf_token=ff57cff46ebe79b9a51dd10f8c9181bb这个接口，并且还携带了两个加密参数params和encSecKey，上一篇讲到的是获取歌曲接口的这两参数的解密，其实评论的这两个参数解密方法是一样的，就不细说了。

在这里插入图片描述

2.这里直接贴出评论接口的加密参数params和encSecKey生成方式，这里有这几个参数需要注意，一个是cursor，一个是pageSize，经过我的多次测试发现，每一页的评论都是基于该业最后的一条评论时间生成的cursor，然后每一页pagesize是20
1
javascript复制代码{"rid":"R_SO_4_1474342935","threadId":"R_SO_4_1474342935","pageNo":"3","pageSize":"20","cursor":"1600190813154","offset":"0","orderType":"1","csrf_token":"ff57cff46ebe79b9a51dd10f8c9181bb"}

在这里插入图片描述

3.那么问题就来了，我不知道每一页最后一条的评论时间是多少，无法生成相应的cursor怎么办，我的解决办法是：从发的第一条评论的当天日期（比如是2020-08-27），那么我就将cursor定义成最后一天时间的最后一秒，即‘2020-08-27 23:59:59‘的时间戳1598543999000（13位补3个0），一直到当天（比如是2020-09-16）最后一秒的时间戳即‘1600271999000’，然后设置pagesize=1000（1000条是最大值，orderType=1（按时间排序）），并且用相应的方法来避免每日会获取重复的评论，其实这样获取的评论数是不完整的，可以根据page和offset来细分当天的评论来获取完整评论信息（这里楼主懒，就没用这方法），如果大家有其他好的想法可以评论下哦！
1
2
python复制代码param = {"rid": "R_SO_4_" + song_id, "threadId": "R_SO_4_" + song_id, "pageNo": "1", "pageSize": "1000",
		"cursor": cursor, "offset": "0", "orderType": "1", "csrf_token": "ff57cff46ebe79b9a51dd10f8c9181bb"}
4.经过分析后，我们可以获取到该歌曲大部分的评论，代码如下：
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
python复制代码    now_day = datetime.date.today() #当天日期
    flag_info = None #重复评论标志
    num = 0
    for i in range(20, -1, -1):  # 获取 2020-08-27---2020-09-16 的日期
        pre_day = str(now_day - datetime.timedelta(days=i)) + ' 23:59:59'  # 获取T+1日期
        # 先转换为时间数组
        timeArray = time.strptime(pre_day, "%Y-%m-%d %H:%M:%S")
        # 转换为时间戳
        cursor = str(int(time.mktime(timeArray))) + '000'  # 拼接成13位时间戳
        print(pre_day, cursor)
        # 评论接口参数
        param = {"rid": "R_SO_4_" + song_id, "threadId": "R_SO_4_" + song_id, "pageNo": "1", "pageSize": "1000",
                 "cursor": cursor, "offset": "0", "orderType": "1", "csrf_token": "ff57cff46ebe79b9a51dd10f8c9181bb"}
        pdata = js_tool.call('d', str(param))
        response = requests.post('https://music.163.com/weapi/comment/resource/comments/get', headers=headers,data=pdata)
        # 获取评论信息
        data = json.loads(response.text)['data']
        comments = data.get('comments')
        # 存储评论信息
        with open('comments.txt', 'a', encoding='utf8') as f:
            for comment in comments:
                info = comment.get('content')
                if flag_info == info:  # 取到重复的评论则跳出循环，防止重复获取
                    break
                print(info)
                f.write(info + '\n')
                # folow_comments = comment.get('beReplied') # 附加的评论，暂不获取
                # if folow_comments:
                #     for folow_comment in folow_comments:
                #         print(folow_comment.get('content'))
                num += 1  # 获取评论数+1
        flag_info = comments[0]['content']  # 取每次请求的第一条
        print('每次请求的第一条', flag_info, '\n')
    print('获取评论数：', num)
5.然后我们就拿到了评论的数据，在用jieba对数据进行分词统计，输出词云图：
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
python复制代码# 分词
def fc_CN(text):
    # 接收分词的字符串
    word_list = jieba.cut(text)
    # 分词后在单独个体之间加上空格
    result = " ".join(word_list)
    return result

# 输出云词
def word_cloud():
    with open("./comments.txt", encoding='utf8') as fp:
        text = fp.read()
        # 将读取的中文文档进行分词
        text = fc_CN(text).replace('\n', '').split(' ')
        # 过滤部分分词
        filter_str = ['的', '，', '了', '我', '[', '你', '是', '就', ']', '！', '。', '？', '这', '不', '也', '都', '吧', '啊', '在',
                      '吗', '和', '吗', '听', '有', '说', '去', '好', '人', '给', '他', '…', '小', '来', '还', '没', '一', '']
        new_text = []
        for data in text:
            if data not in filter_str:
                new_text.append(data)
        print(new_text)
        # 词频统计
        word_counts = collections.Counter(new_text)  # 对分词做词频统计
        word_counts_top10 = word_counts.most_common(10)  # 获取前10最高频的词
        print(word_counts_top10)  # 输出检查

        # 词频展示
        mask = np.array(image.open('./love.jpg'))  # 定义词频背景--需要自行导入
        wc = wordcloud.WordCloud(
            # background_color='white',  # 设置背景颜色
            font_path='C:\Windows\Fonts\simhei.TTF',  # 设置字体格式
            mask=mask,  # 设置背景图
            max_words=200,  # 最多显示词数
            max_font_size=300,  # 字体最大值
            # scale=32  # 调整图片清晰度，值越大越清楚
        )

        wc.generate_from_frequencies(word_counts)  # 从字典生成词云
        image_colors = wordcloud.ImageColorGenerator(mask)  # 从背景图建立颜色方案
        wc.recolor(color_func=image_colors)  # 将词云颜色设置为背景图方案
        wc.to_file("./tmp.jpg")  # 将图片输出为文件
        plt.imshow(wc)  # 显示词云
        plt.axis('off')  # 关闭坐标轴
        plt.show()  # 显示图像
6.最后，Run!，总共评论数是8544条，爬到了8230条，还是有几百条没爬到的。

在这里插入图片描述

在这里插入图片描述

7.然后看看我们输出的词云图，哈哈哈，大写的giao字映入眼帘，不愧是我giao哥！，完整代码可访问我的git来获取：github.com/934050259/w…

在这里插入图片描述

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

原文链接 ：被 CSAPP 虐了

最近两个周末去图书馆刷 CSAPP 完全停不下来啊，这种看不懂却还是强忍着痛苦硬逼着自己去看的感觉，真让我着迷。

image-20211025202910686
这本书从真正意义上让我体会到了什么叫做看书五分钟，休息俩小时。

不过大家可千万别学我，我相信在坐的各位绝对比我牛批，为什么？因为后面我给你推荐了一款神器，那么首先我们先来介绍一下这本书。

image-20211025203724031
这本书总共分成十二个章节，我给你绘制了一个思维导图，比较简单明了。

image-20211025225218317

第一章是提纲挈领性质的一章，从一个 hello world 程序来引出 C、引出 UNIX、Linux ，引出 C 语言程序的编译过程，引出高速缓存、系统的硬件组成、存储结构、虚拟内存、网络编程、并发编程，非常 cool。第一章的内容虽然不难理解，却是能让人涨自信心的一章，这一章能让你产生一种激动的心情，因为内容不难，但是却能够开拓你的思路，把你的知识体系串联起来。

第一部分

第二章的内容比较枯燥，我个人认为需要一定的 C 语言基础，虽然这本书的简介中说如果你有 Java 基础的话。。。。。。

image-20211025230317641

还是有点难顶的，所以建议学一波 C 。

别挡我，C 语言我来了，这里推荐两本 C 语言的书吧，第一本书 《C Primer Plus》 这本书是把 C 语言揉碎了手把手教你，另外《C 程序设计语言》也不错。

第二章主要讲的是计算机中数据的存储方式，基本的数据类型和各种补码、反码的表示方式。总之看这一章如果不了解 C 的话，有点昏昏欲睡（原因是可能不太懂），但实际上第二章写的很不错，当你阅读了本书的第二章之后，也许会发现，你所谓的（懂）只是你的一厢情愿而已，数值系统远没有你想象的那么简单。

第三章是程序的机器级表示，如果你把 C 学的差不多了之后（其实如果单看第二章的话，把 C 语言数据类型恶、运算恶补一下即可），那么恭喜你，接下来你要学习一下汇编了，否则你根本看不懂第三章在说什么（别问我为什么知道的，因为我也看不懂）。你可能想知道诸如 pushq、movq、call、popq、ret*、%rbx、%rdx* 等等都是干嘛的，还有汇编是如何编写的。而且你还要懂 C 语言。

这么看来这本书根本就不是一本为初学者准备的书，也可以说是初学者的劝退书。

第四章又是一个打开新世界大门的一章，这章会直接从各种电路开始搞起，这 TM 马上就直接奔硬件了！主要讲了 Y86-64 体系、各种门电路、引出计算机流水线的设计。毕竟现代微处理器可以称得上是人类创造出的最复杂的系统之一。也会给你讲解各种指令集的区别。

与这一章节相关的书籍，可以看看《计算机组成与设计：软件/硬件接口》还有《编码》这两本书，都非常好，非常透彻。

这一章也会和你聊聊指令集架构，这些架构和宏观意义上的应用层架构不一样，非常复杂，比如下面这个 ARM 架构

image-20211026083152130

这本书是一个值得熟读 N 遍的一本书。

第五章：优化程序性能，现在普遍意义上提到的各种优化，不论是架构层优化、指令集优化等核心都离不开这一章所介绍的内容。优化的难点在于你需要对系统有充分理解，当然了在你做优化之前首先要保证原始程序功能正确（并且有回归测试），否则一切都是徒劳。比如你需要了解现在系统存在的性能瓶颈，才能系统性的进行优化，你才能够编写高效的程序。

编写高效程序需要做到下面这几点：

  • 选择适当的数据结构和算法。
  • 编写出编译器能够有效优化以转换成可执行代码的源代码。
  • 任务拆分，采用并行计算的方式。

第六章：存储器层次结构，这一章会向你介绍存储技术的发展，磁盘、主存、高速缓存的性能差距到底有多大，然后介绍局部性原理，一项非常强大的缓存技术。高速缓存读写是如何映射的，高速缓存不同参数的性能影响，如何编写高速缓存又好的代码，存储器山是个什么概念，以及你会见到封面的插图。

看这一章的时候强烈建议把 Ulrich Drepper 撰写的长达 114 页的经典论文 What Every Programmer Should Know About Memory 看了。

以上就是 CSAPP 的第一部分，第一部分主要介绍了程序和硬件之间的交互关系。

而第二部分则专注于程序和操作系统之间的交互关系，你会学到如何使用操作系统提供的服务来构建系统级程序。

第二部分

第七章：链接，我们使用 Linux 的时候，很多情况下会出现很多难以理解的错误，其中很多都是链接错误。链接分为静态链接和动态链接，我们写的 C 程序在执行的过程中都会经过链接阶段。

image-20211026162805480

除了这一章内容之外，大家也可以看一下一本把链接讲的非常透彻的一本书：《程序员的自我修养 – 链接, 装载与库》，主要讲授代码指令是如何保存的，库文件如何与应用程序代码静态链接，应用程序如何被装载到内存中并开始运行，动态链接如何实现，C/C++运行库的工作原理，以及操作系统提供的系统服务是如何被调用的。非常好的一本国产书。

第八章：异常控制流，世界上不会存在完美运行的程序，任何程序都会出错，这些错误可能是线程执行过程中出错、可能是系统调用异常、页面映射错误等等。这一章会向你介绍各种异常出现之后，操作系统是如何处理的。

第九章：虚拟内存，虚拟内存其实是存储器层次结构的衍生，至于为什么单独拿一章来说，因为虚拟内存太重要了。这一章会向你介绍为什么我们的计算机内存只有 8G（或其他）却能够运行自身数倍以上的程序。虚拟内存有的时候也是面试官比较爱问的一个点：虚拟内存是如何映射的，什么是页框、页表诸如此类。

第三部分

第三部分主要介绍程序间的相互通信，主要包括 IO、网络编程和并发编程。

IO 这部分介绍类 Unix 系统下的 I/O 读写，主要介绍系统层面的 I/O 接口。

今天互联网中的大千世界都立足于 TCP/IP 协议之上，Socket 甚至已经成为了网络编程的同义词。这部分主要向你介绍了网络的变迁，什么客户端-服务器编程模型、Web 服务器，最后再带你写一个 Web 服务器。

网络这部分内容远比这一章节介绍的复杂，网络这部分内容给大家推荐几本书：《计算机网络：自顶向下方法》、《TCP/IP 详解》，《UNIX 网络编程》。

你一定要知道的是 W. Richard Stevens，他的个人网站 www.kohala.com/start/

并发这一章节主要介绍了 C 中如何编写并发程序，如何榨干 CPU ，让其发挥峰值性能。

推荐一个网站

读 csapp 这本书还是需要一定基础的，而且读起来不是那么容易（起码对于我来说是这样的）。

不过，业界还是有一些好资源，能让你更快的深入这本书。

给大家推荐一个网站，fengmuzi2003.gitbook.io/csapp3e/

这个网站可以理解为是 CSAPP 的导读网站，对每一章都进行了介绍，而且推荐了一些不错的资源。

比如他分享的深入理解计算机系统的 B 站课程。

image-20211026170441694

看到这里有没有心潮澎湃的要马上学起来呢？

还有一些电子书的下载渠道：

image-20211026170730582

CSAPP 不管是中英版本都有一些勘误，有一些已经改正了，有一些还没改，大家可以在 www.yiligong.org/csapp3e/ 反馈你见到的勘误，有一些是影响阅读的，但是有一些是影响理解的。

这里给大家一个小提示，我粗略过了一遍，就拿中文版的《深入理解计算机系统》来说，大家可以看一下最开头处的印刷时间，然后针对这些勘误的提出时间进行比较，在印刷之前的很多勘误已经得到修正了。

也就是说，对于这个网站的使用方法，大家可以从后往前看。

image-20211026171149888

总结

上面只是我对这本书一个粗俗的理解，书我还没看完，不过我已经有相关 C 语言、汇编语言的学习计划了，另外，知乎上有一个对 《如何阅读深入浅出计算机系统》 的一个总结性回答，www.zhihu.com/question/20… 我认为还是非常好的。

这个回答里面有练习题的答案，还有学习这本书需要的前置知识，这个回答给我的感觉是答主已经刷过几遍了，作为过来人的经验还是值得学习的。

最最最重要的就是做实验，你可以在 csapp.cs.cmu.edu/3e/labs.htm… 上找到 csapp 的所有实验。

最后给大家推荐一下我自己的 Github github.com/crisxuan/be… ，里面有非常多的硬核文章，绝对会对你有帮助。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

前言

  • 不知道你还记不记得我们当初在学习servlet的时候有句口号叫：【一杯茶一根烟，一个参数我传一天】
  • 是的，servlet的传参是真的复杂，在业务开始之前我们得将参数进行校验、格式化赋值等操作才能做业务开发。但是自从用了spring我们再也不愁了。更确切的说自从用了springboot我们被解放了。

HttpMessageConverter

image-20210907160810583.png

  • 在web开发中浏览器就是客户端、我们java程序放在tomcat等容器中就是服务端。客户端和服务端之间的交互时通过IO流的方式进行交互的。
  • 客户端需要保存数据，提交给服务端，服务端持久化到数据库然后再告诉客户端保存成功！这个过程就涉及服务端和客户端的两次交涉
  • 第一次客户端将保存的数据通过字节流的方式提交给服务端。保存成功后服务端将保存成功的信息再次已字节流的方式返回完成交互！！！

疑问

  • 既然交互时通过字节流，那么我们在springboot项目中可重来没写过转字节流的动作。都是直接返回Java基本类型对象或者包装对象

image-20210907161154175.png

  • 既然我们没有做，那么springboot肯定帮我们做了。这就迁出今天的主角了。SpringMvc 中的HttpMessageConverter帮我们解决数据格式转换的问题了。
1
2
3
4
5
java复制代码/**
 * Strategy interface that specifies a converter that can convert from and to HTTP requests and responses.
 * 用于实现request到response之间数据互转的接口
 */
public interface HttpMessageConverter<T> {}

请求入口

  • RequestMappingHandlerAdapter是针对我们controller层中@RequestMapping注解的方法。关于springmvc的执行流程我们之前也有梳理过。RequestMappingHandlerAdapter是mvc中HandlerAdapter最经典的一类。他所承载的如何通过请求定位方法且进行方法入参和出参的格式转换。
  • HandlerAdapter中有个handle方法，源码中翻译过来就是request请求入口函数。

image-20210907171834188.png

  • 其中重点就在RequestMappingHandlerAdapter的invokeHandlerMethod上。

image-20210907172029313.png

  • 我们通过idea断点调试也能够看到controller的调用是从RequestMappingHandlerAdapter的invokeHandlerMethod上开始调用的。

image-20210907172817796.png

  • 最终会在RequestResponseBodyMethodProcessor进行数据返回的拦截。这个类对入参和出参都进行拦截。我这里值断点了他的返回函数。对入参数据的绑定在readWithMessageConverters方法中。而在数据写回过程中是他的父类AbstractMessageConverterMethodProcessor#writeWithMessageConverters起到关键作用。该方法内部会通过注册好的converter进行匹配请求头中的contentType来找到合适的转换器。而关于这个转换器spring在requestMappingHandlerAdapter中默认
1
2
3
4
5
6
7
8
9
10
11
12
java复制代码public RequestMappingHandlerAdapter() {
   this.messageConverters = new ArrayList<>(4);
   this.messageConverters.add(new ByteArrayHttpMessageConverter());
   this.messageConverters.add(new StringHttpMessageConverter());
   try {
      this.messageConverters.add(new SourceHttpMessageConverter<>());
   }
   catch (Error err) {
      // Ignore when no TransformerFactory implementation is available
   }
   this.messageConverters.add(new AllEncompassingFormHttpMessageConverter());
}
  • 这也对应上了我们mvc章节中提供的扩展
1
2
3
4
5
6
7
8
9
java复制代码/**
 * 定制消息转换器, 控制对象序列化格式
 */
@Override
public void extendMessageConverters(List<HttpMessageConverter<?>> converters) {
    //converters.clear();
    converters.add(getFormHttpMessageConverter());
    converters.add(getJsonHttpMessageConverter());
}
  • 这样我们就在spring默认的转换器基础上新增了我们的转换器。这里的messageConverters就是我们今天的重点HttpMessageConverter。

作用

1
java复制代码public abstract class AbstractHttpMessageConverter<T> implements HttpMessageConverter<T>
  • springboot中对他进行了抽象。我们自定义的消息转换器大多继承这个抽象类就可以了。
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
java复制代码public interface HttpMessageConverter<T> {

   /**
    * 标识指定class是否可以使用该转换器
    */
   boolean canRead(Class<?> clazz, @Nullable MediaType mediaType);

   /**
    * 该转换器是否支持将该class写出
    */
   boolean canWrite(Class<?> clazz, @Nullable MediaType mediaType);

   /**
    * 该转换器支持的请求头设置的mediaType
    */
   List<MediaType> getSupportedMediaTypes();

   /**
    * 从输入字节流中读取出指定class的数据
    */
   T read(Class<? extends T> clazz, HttpInputMessage inputMessage)
         throws IOException, HttpMessageNotReadableException;

   /**
    * 将指定class的数据输出到字节流中
    */
   void write(T t, @Nullable MediaType contentType, HttpOutputMessage outputMessage)
         throws IOException, HttpMessageNotWritableException;

}

InvocableHandlerMethod

  • 上面提到请求最终会落在RequestMappingHandlerAdapter的invokeHandlerMethod上。这个方法就是根据parameter和类对象决定使用具体哪一个HandlerMethodArgumentResolver来执行数据的解析工作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码@Nullable
private HandlerMethodArgumentResolver getArgumentResolver(MethodParameter parameter) {
   HandlerMethodArgumentResolver result = this.argumentResolverCache.get(parameter);
   if (result == null) {
      for (HandlerMethodArgumentResolver resolver : this.argumentResolvers) {
         if (resolver.supportsParameter(parameter)) {
            result = resolver;
            this.argumentResolverCache.put(parameter, result);
            break;
         }
      }
   }
   return result;
}
  • 根据MethodParameter获取对应的处理器也是通过每个处理器内置的支持方法来验证的。比如说RequestResponseBodyMethodProcessor他的支持很简单，凡是方法上带有RequestBody注解的都支持

image-20210908103645830.png

扩展

  • 我们可以自定义一个HttpMessageconverter，然后直接注册成bean就会被springmvc解析到然后添加到消息转换器的执行链上。也可以通过实现WebMvcConfigurer在extendMessageConverters方法中添加我们自定义的转换器。这里笔者不在实现
  • 同样在WebMvcConfigurer中还有一个addArgumentResolvers方法。通过这个方法名我们也可以知道他是支持我们上面提到的HandlerMethodArgumentResolver。他是负责解析我们参数的全过程。比如RequestParamMethodArgumentResolver负责解析RequestParam标注的请求类方法；RequestResponseBodyMethodProcessor负责解析RequestBody标注的请求类方法。前者通过addFormats中进行参数格式解析，后者通过HttpMessageconverter进行解析，正常是jackson进行解析当然他的内部也完成了数据格式的转换操作。
  • 我们平时开发中经常需要上传，下载文件。我们是否可以基于他自定义一个HandlerMethodArgumentResolver来实现下载数据时只需要准备流加上自定义注解就完成下载功能呢？

欢迎在评论区讨论，掘金官方将在掘力星计划活动结束后，在评论区抽送100份掘金周边，抽奖详情见活动文章

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

本文已参与 「掘力星计划」 ，赢取创作大礼包，挑战创作激励金。

  • 备战2022春招或暑期实习，祝大家每天进步亿点点！Day4
  • 本篇总结的是 《如何正确重写JDK的equals方法》，后续会每日更新~
  • 关于《Redis入门到精通》、《并发编程》等知识点可以参考我的往期博客
  • 相信自己，越活越坚强，活着就该逢山开路，遇水架桥！生活，你给我压力，我还你奇迹！

751a8ffe445fbc514b868f41fb1efccd.jpeg

1、简介

不知道大家有没有在开发中重写过hashcode方法，或者在面试中遇到相关的问题。比如一些比较基础的Java工作岗位可能会问：你有使用过对象作为HashMap的key吗？

这个问题其实考察的就是程序员对应hashcode方法重写的相关知识点，如下HashMap的put方法截图可以看出，往容器中添加元素计算hash值时，调用了key对象的hashcode方法。

如何正确的重写hashcode方法？

这其实是一个非常常见而又看似非常简单的问题，但是真正能写的很完善的程序员小捌见得确实不多。（往往越迷人的越危险，越简单的越复杂！！！）

大家往下瞅，看看自己属不属于那个写的很完善的程序员！

2、正文

2.1 什么时候重写

在深入研究如何重写hashcode方法之前，必须要先明白什么时候需要重写hashcode？

关于这个问题，总结起来就一句话：需要重写equals方法的类，都需要重写hashcode方法！

那这个时候你肯定会问，什么时候需要重写equals方法呢？

关于这个问题小捌已经在上一篇文章中讲过啦，需要的兄弟们可以去我的专栏《Java小知识100例》系列看看，顺便点波订阅，关注小捌学习Java不迷路哦！

2.2 如何重写

hashcode方法是Java的java.lang.Object提供的本地方法，这个方法在jvm中实现，它能返回当前对象在内存中地址。

1
2
csharp复制代码// 返回对象在内存中的地址
public native int hashCode();

所以当我们的类未重写hashcode方法，且类的其余超类也未重写；那么我们在调用hashcode方法时，它将永远返回的是对象的内存地址。这可能不是你想要的结果，那我们如何来重写它呢？

思路

首先我们需要知道，我们是通过对象的域来计算hash的， 在对象中域无非数组、引用类型、基本数据类型，有这么多类型的域，我们肯定不能选择某一个域的hash值来作为对象的hashcode方法的返回值；因此我们考虑将域的hash值累加起来返回！

  • 基本数据类型，大家可以参考其对应的包装类型的hashcode方法
  • 引用类型则直接调用hashcode()
  • 数组类型则需要遍历数组，依次调用hashcode()

通用实现

这是java.util.Objects提供的hash方法，用于计算hashcode。虽然这个不是一个计算hashcode的银弹，但是我们可以借鉴这种实现，而且Java JDK源码中大部分类的hashcode都是类似这种实现方式！

1
2
3
typescript复制代码public static int hash(Object... values) {
    return Arrays.hashCode(values);
}
1
2
3
4
5
6
7
8
9
10
11
ini复制代码public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

这个方法大致可以分为两步：

  1. 如果a==null，则返回hashcode为0
  2. 如果a != null，则遍历每一个域，域不为null，则调用域的hashcode方法并累加

这其中有一个非常显眼的数字 31， 每次循环时会将当前result*31，这是为什么呢？

其实每次计算result*31的作用是为了，防止hash冲突！因为如果不设置一个乘积因子，result计算的结果比较小，非常容易在累加的过程后出现相同的hash值，这种情况不是我们想见到的！

那为什么是31呢？ 31为什么能成为JDK计算团队选中的真命天子 ，就不能是2？不能是1001？

其实使用31作为乘积因子是有原因的，其原因小捌觉得有三点：

  1. 31是一个不大不小的数，它不会过小导致hashcode计算的结果容易发生冲突；因为返回值是一个int整数类型也不至于过大，导致hashcode返回值溢出。
  2. 31是一个奇数，一个数与奇数相乘，不容易丢失低位；因为乘以2相当于无符号左移一位，这样会在低位补0，这样的话hashcode计算的值，就非常容易冲突了。
  1. 31对虚拟机的识别非常友好，对于虚拟机来说31 = 2^5 - 1，他能针对这种数字做优化并转换为位运算，因此相乘的时候性能较好

小捌在这里分别用乘积因子2和乘积因子31做个测试：

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
java复制代码package com.liziba.part2;

import org.apache.commons.lang3.RandomStringUtils;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;

/**
 * <p>
 * HashCode方法测试
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/10/24 11:54
 */
public class HashCodeMethodDemo {

    /**
     * 计算hashcode
     *
     * @param value         需计算hashcode字符串
     * @param capacity      乘数因子
     * @return
     */
    public static int hashCode(String value, int capacity) {

        int hash = 0;
        if (Objects.nonNull(value) && value.length() > 0) {
            char[] chars = value.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                hash = capacity * hash + chars[i];
            }
        }

        return hash;
    }


    /**
     * hash值冲突比较
     *
     * @param capacity
     * @param hashValues
     */
    public static void conflictCompare(int capacity, List<Integer> hashValues) {

        Comparator<Integer> comparator = (x, y) -> (x > y) ? 1 : ((x < y) ? -1 : 0);
        Integer max = hashValues.stream().max(comparator).get();
        Integer min = hashValues.stream().min(comparator).get();
        long conflictNum = hashValues.size() - hashValues.stream().distinct().count();
        double conflictRate = conflictNum * 1.0 / hashValues.size() ;

        System.out.println(String.format("乘数因子capacity=%d 冲突数=%d 冲突率：%.4f%% 最大值：%d 最小hashCode：%d",
                capacity, conflictNum, conflictRate * 100, max, min));
    }

    
   
    public static void main(String[] args) {

        int num = 100000;
        int capacity2 = 2;
        int capacity31 = 31;
        List<Integer> hashValues2 = new ArrayList<>(num);
        List<Integer> hashValues31 = new ArrayList<>(num);
        for (int i = 0; i < num; i++) {
            // 生成随机数 org.apache.commons.lang3.RandomStringUtils
            String value = RandomStringUtils.randomAlphabetic(15);
            hashValues2.add(hashCode(value, capacity2));
            hashValues31.add(hashCode(value, capacity31));
        }

        conflictCompare(capacity2, hashValues2);
        conflictCompare(capacity31, hashValues31);

    }

}

一共测试10万个15位长的随机字符串

  • 当乘数因子为2时，冲突率接近4%
  • 当乘数因子为31时，冲突率只有0.0010%

那是不是重写hashcode方法的时候，都需要乘上31呢？

这肯定不是这样的啦！ 乘积因子31只是为了减小hash冲突的一种解决方案，当你用不上的时候肯定不需要使用乘积因子啦！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

分布式之Raft算法

仔细思索分布式的CAP理论，就能发现P数据分区是分布式的特性，是必须满足的特点。如果一个系统没有数据分区的存在，那这样的系统就是单体，而不是分布式。CAP三个特性无法同时满足，那么所有的分布式系统实现都是在A(可用性)和C（一致性）之间权衡选择。

Raft是一个分布式的一致性协议算法，放弃了CAP的可用性，保证严格的一致性。

Raft的应用非常广泛，etcd、consul等都使用了Raft协议。

Raft是一个分布式的一致性协议算法，通过选主机制和日志状态机模型来保证分布式系统的数据强一致性，如下图的基本模型:

ra1.png

关于选主机制和日志状态机模型，下面会详细的论述。

Raft的选主机制

为啥要有leader

在Raft协议里，系统中的所有节点中必须选出一个Leader。

因为分布式的数据分区特性，如果没有Leader来协调数据处理，就很难保证数据是一致的了。
如果没有Leader，则系统的每次操作都要进行一次投票，开销非常大。Paxos算法也是一个分布式一致性协议，使用P2P算法来保证，但是实际理解和实现都过于复杂。如果有一个leader会让决策变得简单快速。

Raft角色和演变

节点状态变迁如下：

raft6.png

Raft普通节点和Leader之间都有心跳，一有异常就等着重新选举。

  • 一个新的节点加入有leader的集群，先变成follower
  • term（任期）：表示当前节点被选为leader节点的一段时间,如下图

raft9.png

  • S1在term=1这段时间内是leader，S2和S3是follower
  • 后面S3和leader没有心跳，则S3发起term=2的选举，但未得到大多数投票(term=2的时间很短，实际不存在这段时间)
  • 后面S2发起term=3的选举，得到大多数投票当选；
  • …
  • term=4的这段时间，S3当选

系统参数和RPC通信

Raft系统有Leader、Follower、Candidate等角色，
每个角色都维护一些状态，遵守一些规则。

Raft系统采用RPC心跳来通信,主要有两种类型的RPC：

  • AppendEntries:
    • 用于Leader向其他Follower同步日志数据
    • 维护和Followers的心跳

ra2.png

  • RequestVote：Candidate调用的请求用于获取投票

ra3.png

选主过程

每次选主都有一个新的term,下图显示了选主的过程：

raft2.png

  • S2的时钟先发现心跳超时，发起选举（使用RequestVote的心跳包），作为Candidate投自己一票。
  • S3（使用RequestVote的心跳包）也投S2一票，则S2当选为新的Leader。
  • 当S1和S2重新有心跳时，发现系统有Leader，则也成为S2的Follower。

日志状态机

分布式要保证可用性，往往意味着多副本存储，且各副本节点的数据一致；Raft维持多副本数据一致的方式是使用日志状态机。

从上图对应的初始状态开始，这个时候如果有客户端发起操作数据的请求，这个数据会被leader接收，并且leader使用AppendEntries的RPC请求到其他各个Followers。

那么，什么是日志状态机呢？

日志状态机通过二元组(index,term)来作为日志状态向量。

  • index是连续递增的数字，是日志的逻辑序号，各个副本上相同的index，有相同的数据日志。
  • term任期也是连续递增的数字，如上面解释的那样，一个term则表示某个节点当选的一段时间。

日志状态向量在Raft系统里面的数据复制和选主过程里发挥着重要的作用。

我们知道Raft分布式系统正常工作时就处理请求，内部复制日志，异常的时候发生新的内部选举，对外可能就出现短暂的可用。下面分这两种情况具体分析。

日志状态向量在正常复制流程是怎样工作的？

下图也整体表现了日志状态向量在正常复制流程是怎样工作的。
raft13.png

S1是Leader，从图上可以看出，此时的S2复制了S1的全部日志，而S3还有所落后。

放大复制的日志条目来看：
raft-rep1.png

  • Leader知道大部分节点都成功之后，将这个index的日志状态设置为committed。Follower通过心跳包得知这个log（日志状态向量标记的）已经被成功复制，然后所有节点会将该日志状态设置为committed。
  • commit的日志可以应用到系统上（板上钉钉，不会回滚）。
  • S3比较慢，同步到（index=2,term=1）,和其他节点的（2，1）对应的数据都相同。
  • （index=4,term=1）的数据已经有大多数统一，则状态为committed。
  • 此时客户端都知道y=1，z=9，x=1。

异常时，日志状态向量在选举流程是怎样工作的？

选举的时候也会利用到这个日志状态向量(index,term)。

客户端找Leader

如下图，
Raft算法规定客户端将所有请求发送给Leader。

r1.png

如果Leader突然宕机，则客户端的请求不通。

r2.png

客户端启动的时候，如何知道哪一个节点是Leader呢？

具体办法是客户端随机挑选一个服务器进行通信，如果客户端选的服务器不是Leader，
那么被挑选的服务器会拒绝客户端的请求，
并且提供它最近接收到的Leader的信息，即通过收到Leader发送的心跳的RPC得到Leader的网络地址。
如果LEADER已经崩溃了，那么客户端的请求就会超时，客户端之后会再次重试随机挑选服务器的过程。

对于下图这种情况，客户端发送的请求则是无效的。

r3.png

在Raft系统里，特殊情况下，一部分请求可能存在短暂的不可用， 但保证了系统的严格一致性。

日志状态机帮助正确的选主

那么异常发生的时候，也就是说选举等过程是怎么利用这个日志状态向量的呢？
如下图的演变过程：

raft11.png

  1. 初始是S1是Leader，复制数据给S2和S3.
  2. 假设S3先发起选举Candidate(term=2)， 因为S3节点最近commit的数据(index=2,term=1), 而S2最近commit的数据(index=4,term=1),已经commit的数据包含S3所没有的(index=3,term=1)、(index=4,term=1)，也就是说数据比S3新，则S2不会投票给S3。
  3. 此后，S2会也发起选举Candidate（term=3）,因为S2的最新commit的日志状态向量是(index=4,term=1)， S3此时的日志状态向量(index=2,term=1)，S3知道S2的数据比自己新，则同意S2的选举。
  4. 随后继续接收请求，复制数据。

通过上面的分析，可以看出，日志状态机使得不至于选出拥有很老数据的节点来当Leader。

Raft为何一定要设计term这个概念?

上面章节的假设稍微有一点改变，假设S3 term=2的选举也是成功的，因为客户端的请求完全相同，这两个情况下的系统最后都有完全一样的数据（1，2，3，4，5，6，7）。

raft12.png
两个假设的场景，系统有完全一样的数据（1，2，3，4，5，6，7），但是通过term的表示可知道系统演化的状态是有区别的。（index=2，term=1）和（index=2，term=2）是不同的日志状态向量。

从上面的分析我们知道，有了term，我们才知道这个事情发生时的状态。

Raft设计任期这个概念，主要是基于这样的一些考虑：

  • 首先很形象，就像总统选举一样，每次都有一个任期号
  • 每个Term都有自己的leader，而且这个Term会带到log的每个entry（AppendEntries）中去，来代表这个entry是哪个leader 的term时期写入的。
  • 任期连续递增。如果在规定的时间内leader没有发送心跳,Follower就会认为leader已经挂掉，会把自己收到过的最高的Term加上1做为新的term去发起一轮选举。

如果参选人的term还没自己的高的话，follower会投反对票，保证选出来的新leader的term是最高的。

raft14.png
如果在time out周期内没人获得足够的选票（这是有可能的），则follower会在term上再加上1去做新的投票请求，直到选出leader为止。

最初的Raft是用C语言实现的，这个timeout时间可以设置的非常短，通常在几十ms，因此在raft协议中，leader挂掉之后基本在几十ms就能够被检测发现，故障恢复时间可以做到非常短。

新加入的日志是怎样应用压缩日志的？

  • 当日志被leader做了快照并删除了的时候，leader需要把快照发送给follower
  • 或者集群有新的节点加入，leader也可以直接发送快照，大量节点日志传输和回放时间。

快照只包括已提交的数据。
将已提交的数据和未提交的数据一起给follower就可以，大大节省了日志传输和回放时间。

raft5.png

未提交的日志在选主之后何去何从？

日志都提交的场景

这个场景，发起选举时，假设黑色节点比红色节点的index大1，且是提交的。此时黑色节点和红色节点commit的日志是（index=6，term=4），
黑色节点都有提交的数据（index=7，term=4）。

r6.png

选举后：

  • Follower的日志落后，从落后的地方开始复制Leader的数据。

有一个日志index未提交

下图这个场景，发起选举时，假设黑色节点比红色节点的index大1，但是这个数据的状态因为没有大多数的认同，目前还处于uncommit的状态：
此时黑色节点和红色节点commit的日志是（index=6，term=4），
黑色节点都有未提交的数据（index=7，term=4）。

r8.png
两种情况：

  • 黑色节点其中一个发起选举，被选为leader
    • 将未提交的数据也复制给其他Follower，等这个日志提交
  • 红色节点其中一个发起选举，被选为leader
    • leader上没有未提交的index日志，黑色节点的数据要保持和leader的一致，则会删除
      未提交的数据（index=7，term=4）

新Leader当选之后的数据复制

这个图是Raft论文里面的一个图，这是一个Raft系统某一时间的日志状态场景：


此时这个Leader节点处于任期8，准备向其他节点复制数据。

当选发生的时机是d宕机，当前节点发起TERM=8的选举，看看其他节点对选举的反应：

  • f节点:Candidate的当前日志（index=10，term=6）比f节点当前日志（index=11，term=3）的term大，所以f同意
  • a同意
  • b,e同意
  • 可是c不同意，d也不同意，不过已经有5票了，当前节点当选
    • c当前日志(index=11,term=6),Candidate的当前日志（index=10，term=6），先比较term相等，但index 11>10,所以c不同意
    • d当前日志(index=12,term=7),Candidate的当前日志（index=10，term=6），先比较term 7<6,所以d不同意

r9.png

变为Leader后，当前节点要把数据同步给其他节点，那么对于每个节点是怎么同步的呢？

r10.png

  1. a节点接收一个（10，6）
  2. b节点还有很多数据要同步，从（5，4）开始
  3. c节点多了一个，删除（11，6）
  4. d节点多了两个（12，7），（11，7），需要删除
  5. e节点要同步的数据也比较多，（7，5）和leader的（7，4）不一样，（6，5）和Leader的（6，4）也不一样，这两个日志先删掉，然后重新从leader同步数据过来
  6. f节点也是，需要删除的日志很多，然后再同步。
    • 产生f节点的原因是因为它当选了term 2和 term 3的leader，但是数据都不曾同步给其他节点，如下面这张图所示

r3.png

扩展问题

Raft复制和MySQL的复制有什么异同？

  • MySQL的binlog也是日志，被复制到其他的备机。
  • Raft在有异常的时候，是自动的选主、切换主备。
  • MySQL没有通过投票选主机制+复制日志的状态模式来选主，一般都是手动切换的。这是因为Raft看重分布式的一致性；而实际应用的时候，MySQL更看重可用性。
  • MySQL不支持这么复杂的分布式情况，侧重点在业务关系复杂性，保证高可用性。

什么是脑裂现象

在一个分布式系统系统，如果出现多个leader，则是脑裂。

r5.png

怎么解决？
需要设置大于半数的节点同意才是主。

如上图，如果要满足必须大于半数的节点同意才是主，则选不出Leader，系统瘫痪。

但是如果使用奇数个节点，必须大于半数的节点同意才是主，这样很容易满足，如下图：

r4.png

参考文献

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%