在微服务中网关的作用

1. 统一反向代理
2. 流量控制，降级，熔断
3. 统一日志管理
4. 内外网管理，权限控制

其中1，2，3相对比较确定，通过hystrix，filter，redis ratelimit等机制可以完成。和架构本身关系不大。

内外网控制

对于第4点内外网控制，需要解决几个问题

1. 模块A可能是内网访问，也可能是外网访问，也可能是内外网都可以访问
2. 模块A是外网可以访问，但是模块A中个别接口是只能内网访问

对于第1点，有几种做法

• 使用多个eureka，内网系统注册到内网eureka，外网注册外网eureka，使用不同的网关访问对应eureka的系统。

  缺点：如果一个系统内网外网都要访问，必须注册两个eureka。

• 使用一个eureka，但是使用两个网关，内网网关和外网网关。微服务在注册时候通过eureka maps填写自定义字段NETWORK_TYPE, 如果是外网系统，该值设为OUTER。

  内网网关可以访问所有微服务，外网网关访问微服务的时候，获取eureka中对应的NETWORK_TYPE字段，如果为空，默认为内网系统，如果是OUTER则表示可以外网访问

对于第2点，有几种做法：

• 拆分系统，保证某个模块中所有接口只能外网访问
• 规定某个urlpath，比如/private，这个路径下的接口是不能外网访问的，只能通过内网网关进行访问

网关Token校验

• 外网网关

  对于对外暴露的接口，不能以userid形式暴露，必须通过token，避免userid可以遍历。如果让底层微服务校验token会造成耦合问题。所以统一在外网网关中进行token校验，并转化为userid。

1. 擦除header中USER_ID字段，避免客户端直接透传
2. 如果header里面没有token，不做任何操作
3. 如果header中有token，将token通过sso转为userid，并访问header的USER_ID字段
4. 下游服务根据接口需求通过header中获取userid，如果获取不到，则根据业务返回特定数据
5. token统一在sso生成，使用jwt，网关通过http请求sso，如果觉得性能有问题，可以增加缓存
6. 原则，永远不能对外暴露userid的接口

• 内部网关

  内部调用或者调试等原因，可能直接调用userid比较方便，可以开设一个内部网关，不进行token校验。

• 后端系统

  后端不处理token，获取header中的userid

1. token bucket

   基于计数的方式进行限制，类似于信号量semaphore，每次请求都需要先获取一个token，如果取完了，就不能请求。token会定时增加。

2. 固定窗口

   基于时间窗口，如秒，分钟，小时等，通过计数的方式来控制，优点是简单，缺点是对于边界无法精确控制次数，可能超出原有阈值的两倍

3. 滑动窗口

   每次请求记录请求时间，统计某个时间窗口内请求次数，并删除这个时间范围之前的所有请求记录数据。

   一般可以用redis的sorted set来记录。方式如下

   1 2 3 4

   zremrangebyscore key 0 now - TTL zcount key now-TTL now zadd key now now expire key ttl

4. 分布式

   如果高并发情况下，上述方式可能不够精确，如果需要完全准确计数，需要使用redislock来保证一致性。但是会牺牲性能。

Reference

https://blog.figma.com/an-alternative-approach-to-rate-limiting-f8a06cf7c94c

https://blog.figma.com/an-alternative-approach-to-rate-limiting-f8a06cf7c94c

点赞

说明：每个视频，用户可以点赞，每天有10亿条记录，预计100w视频，1亿用户量。放在kafka中。每天凌晨统计每天点赞数最高100条视频，同时给这100个视频作者推送200个最近点赞用户

统计点赞数最高的100条视频，并且这100个视频每个视频只要存储最后的200个点赞用户，所以并不需要保存每个用户的每次点赞记录。每个视频需要记录总的点赞数，同时要记录每个视频最近的200个点赞用户.

由于每天有10亿数据，那么每秒有10^10/86400条记录~=12000条/s，所以使用mysql性能会有问题，可以使用redis或者其他的nosql数据库

• redis存储：

1. 记录每天每个url记录的点赞数，使用HINCRBY key=URL_DATE， field：URL，value：点赞数count
2. 每个url记录当天最近200个点赞用户，使用zset保存，key: URL_DATE_USER, value：用户id，score：ts，按ts倒序保存。这边使用zset保存用户数据，主要目的是方便查询去重，避免一个用户点赞两次造成重复
3. 每个zset只保存最近的最近的200条，所以超过200条的需要删除，可以通过ZREMRANGEBYRANK URL_DATE_USER 0 -201的方式去除最新200条以外的数据

这样每天凌晨，通过 HSCAN URL_DATE的方式，遍历每天被点赞的url和数量，记录下top100的url，并通过遍历ZRANGE URL_DATE_USER 0 -1这个zset获取这个视频最后100个点赞的用户，并进行推送

• 资源消耗：

1. qps~=12000/s，一台redis足够
2. 内存：100W视频，一个hset用来记录每个视频的点赞数，一个zset用来保存每个视频最后点赞的200个用户。每个视频url长度按1k计算，1000000 1000 ~= 1g，每个视频用户id按64位int计算，1000000 8 * 200 ~= 1.6g，所以内存一台机器物理机足够

任务模式

每个用户有一个任务列表taskList:[task1,task2,…]，每个任务有次数限制，分为每日次数，每周次数，每月次数。一次请求，需要操作年月日的活动。用户量1亿。

每一次请求，通过userid+taskid获取获取用户任务数据, 判断当前时间和上一次任务时间是否在一天或者一周或者一个月。

1
2
3
4
5
6
7
8
9
10
11

key: user_id+task_id, value: {

	"day":1,

	"week":3,

	"month":6,

	"time": ts

}

伪代码：

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

if sameday(ts,now()){
    day+1
    week+1
    month+1
}
if(isnotsameday(ts,now())&&issameweek(ts,now()) && issamemonth(ts,now())){
    day=0;
    week+1
    month+1
}
if(isnotsameday(ts,now())&&isnotsameweek(ts,now()) && issamemonth(ts,now())){
    day=0;
    week=0;
    month+1
}
if(isnotsameday(ts,now())&&issameweek(ts,now()) && isnotsamemonth(ts,now())){
    day=0;
    week+1
    month=0
}
if(isnotsameday(ts,now())&&isnotsameweek(ts,now()) && isnotsamemonth(ts,now())){
    day=0;
    week=0
    month=0
}

1. 字符串处理

   • 原地reverse字符串单测

2. 数组

   • Find All Numbers Disappeared in an Array

     比较讨巧，因为题目限定了Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array)，所以可以通过原数组来记录某个数字是否出现，如果出现，将nums[i]设为nums[i]*-1，然后找到nums[i] 大于0的即可。

   • Find All Duplicates in an Array

     接上题Find All Numbers Disappeared in an Array，遍历两次，第一次找出没有出现过得，则出现过得数字对应下标变为负数，第二遍将出现过一次的数字对应的下标变为正数，剩下的负数表示出现两次的

   • First Missing Positive

     • 将nums[i] -1数字放入对应下标位置。如果nums[i]-1>=0&&nums[i]-1<nums.length&&nums[nums[i]-1]=nums[i]
     • 也可以通过将原数组改为负数的方式，同上两题。但是要注意有原数组有负数和0存在

   • Majority Element

     找到数组中出现次数大于一半的元素，可以通过计数的方式，相同的计数加1，不相同减一，记录count为零时的元素，最后一个即为出现次数超过一半的元素

3. 树遍历

   • 树对称

4. 链表

   • 链表反转

     遍历或者递归计算

5. 二分搜索

   • Divide Two Integers

     不能用乘法、除法、取模操作进行除法操作。只能通过加分来操作。由于一个个加太慢，所以可以通过两倍两倍加来模拟乘法，类似二分

   • three sum问题

     在一个数组中找到三个数，和为0。类似一个数组中找到两个数相加为target，可以通过对数组排序后使用二分查找来查询。对于三个元素，可以先排序数组后，遍历数组过程中先指定一个元素i，然后通过二分查询在[i+1,n]中找到合为0-nums[i]的两个元素

   • four sum问题

     在three sum问题基础上，先确定一个元素，然后调用three sum找到特定和的三个元素即可

   • Trapping Rain Water

     蓄水池算法，左右两边找到柱子，中间的水是可以保留下来。有点像二分查询

6. 贪心

   • Maximum Length of Pair Chain

     dp和贪心都可以，但是本题可以用贪心来解决

7. 数组动态规划

   1. Climbing Stairs

      fibonacci数列 f(n) =f(n-1)+f(n-2)

   2. Min Cost Climbing Stairs

      在Climbing Stairs基础上增加了cost，问题分解为

      sum[i] 到达i节阶梯的花费，sum[i] = min(sum[i-1]+cost[i-1],sum[i-2]+cost[i-2])

   3. Continuous Subarray Sum

      求任意子数组的和是不是等于k的倍数

      一个比较巧妙的思路是每个和模k，如果出现一个数之前出现过，即中间的数和为k的倍数

   4. House Robber

      动态规划入门，sum[i]表示盗取i获得的最大钱数，sum[i] = max(sum[i-2]+c[i],sum[i-1])

   5. Partition to K Equal Sum Subsets

      从数组中找到和为特定值的子数组，貌似没什么特别好的方法，暴力枚举

   6. Counting Bits

      统计每个元素的二进制1个数，可以依赖之前的计算结果

      f(n) = k if n == 2^k

      f(n) = 1 + f(n-2^k) if 2^k<n<2^k+1

   7. Split Array Largest Sum

      分解为两道题目：

      • 给定一个数组int[]nums，份数m，最大值max，需要将数组nums切分为连续的最多m份，每一份的和<=max
      • Given a lower bound (left), an upper bound (right), an unknown bool array (B), and an API uses i as input and tells you whether B[i] is true. If we know there exists an index k, that B[i] is false when i < k, and B[i] is true when i >= k. What is the fastest way to find this k (the lower bound)?

      第一问通过贪心算法，不断累加数组，如果超过>max，之前的数组作为一段，并重新开始累加，最多形成m份数组

      第二问可以用二分查找方法找到k。

      组合这两个问题，原问题是找到一个数k，满足将原数组切分为m份，并且每一份的和<=k,使得k最小。由于k>=每一份数组的和，即max(nums)<=k<=sum(nums)。

   8. 最长有效子数组Longest Valid Parentheses

      动态规划：longest[i] 表示i为结尾的最长有效括号对

      如果s[i]==’(‘ 则忽略，如果s[i] == ‘)’ 并且s[i - longest[i-1] - 1] == ‘(‘ 则配对成功，长度加二，并且如果i - longest[i-1] - 2也是一个最长子串，则可以拼接成为新的最大子串

      if s[i] == ‘(‘ longest[i] = 0;

      if s[i] == ‘)’ && s[i - longest[i-1] - 1] == ‘(‘ then: longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]

   9. 丢鸡蛋问题

      100层楼，有两个鸡蛋。如果鸡蛋从第k层丢下去不碎，则[0, k-1]都不会碎。问最少丢多少次，才知道从k层下丢不碎，k+1层会碎

      保守策略：第一次从k层下丢，如果碎了，则从[0,k-1]一层层尝试，一共k次。如果不碎，第二次尝试k+k-1,如果碎了，则尝试[k+1,k+k-1]，一共k次。所以可以得到k+k-1+k-2+…. = 100，即(1+k)*2/k = 100，可以得到k=14次

      dp：这个是个dp问题，f(n,m)表示n层楼，m个鸡蛋，需要的次数。

      f(0,m) = 0

      f(n,1) = n

      f(n,m) 表示从i楼下降，如果碎了即f(i-1,m-1)，如果不碎，则结果为f(n-i,m) ，即

      f(n,m) = min(max(f(i-1,m-1),f(n-i,m)))+1 for i = 1 ~ n，+1表示从i楼的那一次尝试

   10. Longest Increasing Subsequence

       动态规划：dp[i]表示[i]的最长LIS

       dp[i] = max(1+dp[j]); for nums[j] > nums[i], j =[i+1,n]

   11. Largest Sum of Averages

       问题分解：dp[0][k] 表示[0-n]中选择k段可以获得的LSA，则

       dp[0][k] = max(dp[i][k-1]+avg(0,i)) for i = [1,n]

   12. Longest Palindromic Substring

       最大回文串：将数组变为奇数个元素。遍历数组，对于每一元素像两边扩展找回文，记录最长回文

   13. Split Array with Equal Sum

       求和问题一般都会用一个数组sum[i]记录[0,i]之间的元素和，那如果要求任意两段数据和为sum[i,j] = sum[i] - sum[j]。该题目的方法是找到i, j 使得 sum[0,i-1] = sum[i+1,j-1]，然后再在j右边找到k，是得sum[j+1,k-1] = sum[k+1,n-1]

8. 图论

   邻接矩阵edge方法存储

   搜索算法：Dfs,bfs,Dijkstra算法

9. ​

整数处理往往涉及溢出，一般的处理方案就是将整数转为long以后进行处理。

判断整数溢出的方式为，如果两个正数相加返回负数，则溢出。如果两个负数相加返回正数则溢出

题目描述：

https://leetcode.com/problems/divide-two-integers/description/

解题思路：

除法无法使用，可以通过加法来模拟，题目中注意的问题是如果每次只是增加divisor，速度过慢，会超时，所以通过加分模拟乘法的方式来加快速度。

代码

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

public long findMultiply(long dividend, long divisor, boolean isNegative) {

    if (dividend < divisor) {
        return 0;
    }

    long sum = divisor;
    long result = isNegative ? -1 : 1;
    while ((sum + sum) <= dividend) {
        result += result;
        sum += sum;
    }
    return result + findMultiply(dividend - sum, divisor, isNegative);
}

public int divide(int dividend, int divisor) {
    long result = 0;
    long ldividend = dividend;
    long ldivisor = divisor;

    if (ldividend > 0 && ldivisor > 0) {
        result = findMultiply(ldividend, ldivisor, false);
    } else if (ldividend < 0 && ldivisor < 0) {
        result = findMultiply(Math.abs(ldividend), Math.abs(ldivisor), false);
    } else if (ldividend > 0 && ldivisor < 0) {
        result = findMultiply(Math.abs(ldividend), Math.abs(ldivisor), true);
    } else if (ldividend < 0 && ldivisor > 0) {
        result = findMultiply(Math.abs(ldividend), Math.abs(ldivisor), true);
    }

    if (result > Integer.MAX_VALUE) {
        result = Integer.MAX_VALUE;
    }

    return (int) result;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public void stringtoint() {

        assert divide(10, 5) == 2;
        assert divide(42, 5) == 8;
        assert divide(11, 5) == 2;

        assert divide(-10, -5) == 2;
        assert divide(-11, -5) == 2;
        assert divide(-9, -5) == 1;

        assert divide(9, -5) == -1;
        assert divide(10, -5) == -2;

        assert divide(10, -5) == -2;
        assert divide(1000000000, -5) == 1000000000 / -5;

        assert divide(Integer.MAX_VALUE, 1) == Integer.MAX_VALUE;
        assert divide(Integer.MIN_VALUE, 1) == Integer.MIN_VALUE;
        assert divide(Integer.MAX_VALUE, -1) == Integer.MIN_VALUE + 1;
        assert divide(Integer.MIN_VALUE, -1) == Integer.MAX_VALUE;
    }

• Leetcode url

  https://leetcode.com/problems/bulls-and-cows/description/

• Test Code

  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

  import ( "testing" "github.com/stretchr/testify/assert" ) func TestGuessAllCorrect(t *testing.T) { t.Run("guess4BullsAndNoCows", func(t *testing.T) { ret := getHint("1111", "1111") assert.Equal(t, "4A0B", ret, "guess4BullsAndNoCows failed") }) t.Run("guessNoBullsAndCows", func(t *testing.T) { ret := getHint("1111", "2222") assert.Equal(t, "0A0B", ret, "guessNoBullsAndCows failed") }) t.Run("guessOneBullAndNoCow", func(t *testing.T) { ret := getHint("1111", "1222") assert.Equal(t, "1A0B", ret, "guessOneBullAndNoCow failed") }) t.Run("guessOneBullAndOneCow", func(t *testing.T) { ret := getHint("1112", "1323") assert.Equal(t, "1A1B", ret, "guessOneBullAndOneCow failed") }) t.Run("guessOneBullAndOneCowWithDuplicateGuessNumber", func(t *testing.T) { ret := getHint("1112", "1223") assert.Equal(t, "1A1B", ret, "guessOneBullAndOneCowWithDuplicateGuessNumber failed") }) t.Run("guessNoBullAndOneCowWithDuplicateGuessNumber", func(t *testing.T) { ret := getHint("1234", "0111") assert.Equal(t, "0A1B", ret, "guessNoBullAndOneCowWithDuplicateGuessNumber failed") }) t.Run("guessNoBullAndFourCowWithDuplicateDigital", func(t *testing.T) { ret := getHint("1122", "2211") assert.Equal(t, "0A4B", ret, "guessNoBullAndFourCowWithDuplicateDigital failed") }) t.Run("guessNoBullAndOneCowWithDuplicatePosition", func(t *testing.T) { ret := getHint("1122", "0001") assert.Equal(t, "0A1B", ret, "guessNoBullAndOneCowWithDuplicatePosition failed") }) }

• 实现代码

  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

  import "fmt" func getHint(secret, guess string) string { A := 0 B := 0 guessBytes := []byte(guess) secretBytes := []byte(secret) guessedByteMap := make(map[int]int) secretByteMap := make(map[int]int) for guestIndex, guestValue := range guessBytes { if guestValue == secretBytes[guestIndex] { setGuessAndSecretIndexPair(guessedByteMap, secretByteMap, guestIndex, guestIndex) A = increaseBullNumber(A) } } for guestIndex, guestValue := range guessBytes { for secretIndex, secretValue := range secretBytes { if guestIndex != secretIndex && guestValue == secretValue && checkSecretAndGuessIndexUsed(guessedByteMap, secretByteMap, guestIndex, secretIndex) { B = increaseCowNumber(B) setGuessAndSecretIndexPair(guessedByteMap, secretByteMap, guestIndex, secretIndex) } } } return fmt.Sprintf("%dA%dB", A, B) } func increaseBullNumber(a int) int { return a + 1 } func increaseCowNumber(b int) int { return b + 1 } func setGuessAndSecretIndexPair(guessedByteMap map[int]int, secretByteMap map[int]int, guestIndex, secretIndex int) { guessedByteMap[guestIndex] = 1 secretByteMap[secretIndex] = 1 } func checkSecretAndGuessIndexUsed(guessedByteMap, secretByteMap map[int]int, guestIndex, secretIndex int) bool { return secretByteMap[secretIndex] == 0 && guessedByteMap[guestIndex] == 0 }

  思路：遍历guess字符串两边，第一遍遍历产生bull个数，第二遍产生cows个数。需要两个map记录guess和secret被使用过的字符下标，避免重复计算

1. 认证（authorization）和授权(authentication)的区别

   • 认证（authorization）：验证A是A，即A用户输入用户名密码，验证是不是正确
   • 授权（authentication）：认证A是A后，判断A是不是有访问某个url或者某个数据的权限

2. 认证有几种方式

   • 微信认证
   • 用户名密码
   • 手机号+密码
   • 手机号+验证码

3. 认证流程

   • 微信认证登录

     微信登录的方式通过微信认证用户，本地不进行认证。微信认证完成后获取微信用户信息并保存到用户信息模块，信息包括union_id,open_id,昵称等。随后生成jwt token返回给客户端

     

     SSO和用户存储管理系统分开两个模块，目的是保证SSO相对稳定独立，不和用户管理业务逻辑耦合。用户管理逻辑可能包括：用户查询，用户信息更新等

   • 手机号登录

     手机号+密码登录的方式认证用户合法性

     

4. SSO认证

   SSO是个登录门户，他通过调用微信服务或者用户系统认证用户信息合法性。如果合法，生成jwt token保存userid，有效期时间等信息给前端

5. 网关统一认证

   微服务体系下，对外接口有个约定：

   • 对外暴露服务不能以user_id作为接口参数，必须以token进行传输。

   如果微服务众多，每个服务都去验证token合法性会过于冗余。所以统一在网关层进行验证，流程如下：

   • 对于每一个接口请求，网关会从http_header中获取token，并去sso验证token合法性。如果合法返回token对应的user_id。
   • 网关将user_id放入http_header中传递到resource-service服务。
   • resource-service通过http_header获取user_id并调用授权服务验证用户是否有权限访问该接口

   

   如果对于网关不用每个接口都验证token，可以增加白名单，比如/public，/static路径可以不校验

6. 授权管理

   授权是认证后需要做的事情。一般授权管理的模型是基于role的模型，一般是用户属于某个role，role和权限关联。我们在这个基础上面做了扩充。

   • 引入了组unit，部门deparment，用户可以属于某个unit，department，role，这些对象和权限permission关联。
   • 权限permission关联一个或者多个资源，资源包括菜单，操作，视图等
   • 权限permission关联一个或者多个动态管理函数funtion（使用js或者groovy写）
   • 权限permission关联模块分类，分类关联平台

   

   ​

   ​

存储模型

1. 关系数据库：mysql，postgresql。主从结构，以文件存储为主，索引使用b+树。适合结构化数据
2. 文档数据库：mongodb
   • 适合非结构化业务，非常灵活
   • 不支持事务，4.0开始支持
3. 内存数据库：redis（缓存，KV）
   1. hash：hset key f v
   2. zset：hashtable+skiplist
4. 分布式一致性工具：etcd，zookeeper。KV存储，配置管理，服务发现，分布式锁，通知监听，分布式自增序列等功能
   1. eted: 使用raft协议。底层KV存储使用bbolt。
   2. zookeeper：zab协议，类似paxos
5. 本地KV：
   • LSM模型：leveldb，rocksdb
   • B树：bolt，bbolt
6. elasticsearch
   • TODO

队列选型：

1. kafka
   • 包含：broker，topic，partition，producer，consumer，consumer group
   • 性能较高，顺序读写日志。10万级别/s
   • 单播广播都支持，一个topic可以由一个或多个consumer group消费，每个consumer属于一个consumer group
   • 高可用：主从模式。通过zookeeper选举leader
2. rabbitmq
   • producer，exchanger（topic，direct，fanout），queue，consumer
   • 性能较高，内存+文件。万级别/s
   • 广播单播都支持
   • 高可用：镜像模式，外面加haproxy

服务发现

• 嵌入式

1. eureka
   • 服务端：java
   • 客户端：java，golang，nodejs
2. consul：
   • 服务端：golang
   • 客户端：golang，java，nodejs，etc.
3. etcd，zookeeper:
   • 分布式一致性工具，可以实现服务发现，需要做一定工作
   • 相比eureka，consul，这类工具比较强大，除了服务发现，还有locking，kv存储等

• 非入侵

  通过容器进行服务发现，一般都是通过Linux网络VIP+IPVS方式

1. docker-swarm
2. k8s

网关

• zuul
• kong
• traeffic

监控

• prometheus

区块链简介

1. 区块链是什么？一句话，它是一种特殊的分布式数据库

2. 区块链特点：去中心化，解决相互信任问题

3. 区块：区块链由一个个区块（block）组成。区块很像数据库的记录，每次写入数据，就是创建一个区块

   

4. 区块内容包括：

   版本号：4 字节；
   上一个区块头的 SHA256 hash 值：链接到一个合法的块上，32 字节；
   包含的所有验证过的交易的 Merkle 树根的哈希值，32 字节；
   时间戳timestamp：4 字节；
   难度指标difficulty：4 字节；
   Nonce：4 字节，PoW 问题的答案；

   10分钟内的所有交易内容

5. 共识机制

   解决分布式一致性问题

   PoW：Proof of Work。计算一个hash值，小于一个特定的数值。当掌握超过51%的计算，即可控制区块链网络。缺点是慢

   PoS：Proof of Stake。权益证明，解决Pow浪费资源问题。获得的权益越多，获得记账的概率越大

   PBFT：实用拜占庭容错算法。至少4个节点，n为节点个数，F为可以出错的节点个数，当满足n>3F+1则PBFT算法可以保证节点达到共识。速度比较快

   Paxos: 三类角色：proposer，acceptors，learners，也是通过二阶段提交的方式，prepare和accept两个阶段，如果一个proposal被大多数acceptors接受了，该proposal就表示被接受

   Raft：简易版paxos，leader，follower，candidate。通过投票选举leader，超过一半的节点认同即可成为leader。follower通过log同步leader数据

6. 区块链合并

   如果同一个时刻有多个人在修改一个区块链，取长度最长的那个区块链

7. 安全：通过加密SHA265算法保证

8. 公有链，联盟链，私有链

9. 智能合约：区块链触发器，一堆代码实现的业务逻辑

10. 矿工收益：

    • 手续费
    • 奖励的比特币

比特币：

1. 基于区块链的技术，通过PoW算法达成分布式一致性。通过挖矿产生新的区块记录交易信息

2. 挖矿

   目的：产生区块

   方法：每个计算节点计算hash值，当hash值小于某个难度系数才有效。区块链保证平均每10分钟能够产生一个有效hash值。难度系数每两周（2016个区块）调整一次，使得能够保持平均每10分钟能够产生一个有效区块

区块链、以太坊

比特币使用了区块链技术，而以太坊是区块链技术的一个实现平台

从交易延伸到了智能合约

开放问题

为什么比特币要挖矿

比特币为什么使用PoW共识算法

简易版区块链

• 需求1：简单区块链

  1. 设计实现api增加区块（代替挖矿），查看区块链

  2. 区块定义：节点编号，生成时间，当前节点hash值，前一个节点hash值，自定义数据(int)

  3. 符合区块链的基本原理

     • 当前节点hash=hash(previous_hash + index+timestamp+data)
     • 检查区块引用的上一个区块是否存在且有效，即当前节点previoushash=前一个节点hash
     • 当前节点的编号=前一个节点编号+1

  4. 方便起见，初始化第一个节点为

     index=0

     Timestamp=0

     data=0

     hash=”f78b037f6d1ecfc5a00bc7d96858bdc7af9ac8dbf95fdd5736d0f950ab279b9e”

     previoushash=””

• 需求2：设计P2P区块链

  1. 在第一个需求基础上，增加P2P通讯接口（增加node，查看nodes）。
  2. 可以通过websocket远程通信多个节点，并同步区块链信息。同步规则为：
     • 当节点A产生一个新的区块，A节点广播新增区块信息到所有节点。如果B节点收到新增区块并且验证可以增加到本地区块链中，则增加。如果不能，需要广播获取网络中最长的区块链并覆盖本地区块链
  3. 其他同上

• 需求3：Pow

  1. 在前两个基础上，增加Pow

开放问题答案

为什么比特币要挖矿

货币的本质是购买力，如果货币被不断增发，其所代表的购买力将不断下降，就会出现通货。比特币原本的目的是为了解决通货的问题。为了保证比特币的稀缺性，比特币作者使用算力来体现稀缺性，所以需要挖矿才能产生比特币

比特币为什么使用PoW共识算法

因为是公网环境，网络情况不稳定，安全性较差，所以PoW是一种相对公平可以达到一致性的算法，虽然效率较低。相比PoS，PBFT，Raft等算法性能会高很多。

参考资料：

http://www.ruanyifeng.com/blog/2017/12/blockchain-tutorial.html

https://medium.com/@lhartikk/a-blockchain-in-200-lines-of-code-963cc1cc0e54

https://medium.com/@mycoralhealth/code-your-own-blockchain-in-less-than-200-lines-of-go-e296282bcffc

http://www.infoq.com/cn/articles/bitcoin-and-block-chain-part02 Pow

https://blockchain.info/

http://www.ey.com/Publication/vwLUAssets/ey-blockchain-platform-research-and-analysis-cn/$FILE/ey-blockchain-platform-research-and-analysis-cn.pdf

Bash 多行注释

• 传统的C语言多行注释

1
2
3
4
5

/*
this is a comment
this is a comment again
this is another comment 
*/

• bash多行注释

那么在bash环境中要怎么做呢？可以这样做：

1
2
3
4
5
6

#!/bin/bash
:<<\true
  ls
  read
  `read`
true

这里涉及到两个unix知识点

• Here Document

  Here Document 是在Linux Shell 中的一种特殊的重定向方式，它的基本的形式如下
  cmd << delimiter
  Here Document Content
  delimiter

  其作用是将两个 delimiter 之间的内容(Here Document Content 部分) 传递给cmd 作为输入参数

• 空指令：

  :是一个unix命令，含义是do nothing

那么上面这段bash的含义是：以true作为here document的分隔符，其中所有的内容作为输出到空命令：，那么达到的效果是什么都不做，即为注释。那为什么true之前要加一个\,原因是如果不加\，那么here document内容中如果出现\或者`，那么here document转义会失败，所以需要增加\，避免转义失败。

• 关闭注释

  上面这段bash只修改一行就可以开关注释，要怎么做？

  我们知道bash中单行注释通过#，那么如果把here document 注释了需要注释here document头尾两行。如下代码

  1 2 3 4 5 6

  #!/bin/bash #:<<\true ls read `read` #true

  但是我们代码末尾的分隔符是true，所以其实不注释也没问题，执行不会有任何报错。所以只要注释here document的行首即可，代码如下

  1 2 3 4 5 6

  #!/bin/bash #:<<\true ls read `read` true

  ​