SLA

在构建大型系统时，常常会遇到各种错误。在计划构建一个系统时，定义系统的“健康状态”十分重要。

“健康状态”必须是可度量的，一般做法是使用SLAs来度量系统的“健康状态”。最常见的SLA为

• 可达性

  从时间维度衡量（99.999%可达性，每年下线50分钟）

• 准确性

  对于数据的丢失或失真是否可以接受？可以达到多少百分比？对于支付系统来说，不接受任何数据的丢失和失真

• 容量

  系统支持并发

• 延迟

  响应延迟，一般衡量95%请求的响应时间和99%请求响应时间

确保新系统比被替代系统“更好”，可以使用上面四个SLA指标来衡量，可达性是最重要的需求。

水平和垂直伸缩

随着新业务的增长，负载也会增加。最常见的伸缩策略是垂直和水平伸缩。

水平伸缩就是增加更多的机器或节点，对于分布式系统来说水平伸缩是最常有的方式。

垂直伸缩基本上就是买更大/好的机器。

一致性

可达性对于任何系统都是很重要的，但是分布式系统一般都构建在低可达性的机器上（比如：服务的可达性要求99.999% 机器的可达性为99.9%）。简单的做法是维护一组机器组成集群，这样服务的可达性不依赖单独的机器。

一致性是在高可用系统中最需要关心的。一个一致性系统在所有的节点上看到和返回的数据在同一时间是相同的。如果使用一组机器来组成集群，它们还需要互相发送消息来保持同步，但是发送消息可能失败，这样一些节点就会因为不一致而不可达。

一致性有多个模型，在分布式系统最常用的是强一致性，弱一致性和最终一致性。一般来说，一致性要求越低，系统可以工作的更快，但是返回的数据不一定是最新的。

系统中的数据需要是一致的，但是到底是怎样的一致？对于一些系统，需要强一致性，比如一次支付必须是强一致的存储下来。对于没那么重要的部分，最终一致性是可以考虑的权衡。比如列出最近的交易。

数据持久性

持久性表示一旦数据成功添加到数据存储，它就永远可以访问到。不同的分布式数据库拥有不同级别的数据持久性。一般使用副本来增加数据持久性。

对于支付系统来说，数据不允许丢失。我们构建的分布式数据存储需要支持集群级别的数据持久型。目前Cassandra, MongoDB, HDFS和Dynamodb 都支持多种级别的数据持久性。

消息保持与持久性

分布式系统中的节点执行计算，存储数据，互相发送消息。发送消息的关键是消息的可靠到达。对于关键系统，经常需要消息零丢失。

对于分布式系统，发送消息一般石油分布式消息服务发送，如RabbitMQ，Kafka。这些消息服务支持不同级别的消息投递可靠性。

消息保持表示当节点处理消息失败时，在错误被解决前消息一直被保持着。消息的持久性一般在消息队列层被使用。如果在消息发送的时候队列或节点下线了，那在它们重新上线是还能接收到消息。

在支付系统中我们需要每一条消息投递一次，在构建系统中保证投递一次和投递至少一次在实现上是有区别的。最后我们使用了kafka来保证投递至少一次。

幂等性

在分布式系统中，很多东西都可能出错，连接会丢包或超时，客户端经常会重试这些请求。一个幂等的系统保证无论多少特定的请求被执行，一个请求实际的操作只会执行一次。比如支付请求，如果客户端请求支付并且请求已经成功，但是客户端超时了，客户端是能够重试相同的请求的。对于一个幂等的系统，一个个人的支付是不能被收取两次的。

对幂等的设计，分布式系统需要某种分布式锁机制。假设我们想要使用乐观锁来实现幂等性，这时系统需要强一致性的锁来执行操作，我们可以使用同一个版本的乐观锁来检查是否有启动了额外的操作。

根据系统的一致性和操作的类型，有很多方式来实现幂等性。在设计分布式系统时，幂等性时最容易忽略的。在支付系统中，幂等操作时最重要的，它避免了双花和双收问题。消息系统已经保证了消息至少消费一次，我们只需要保证所有重复的消息保证幂等性即可。我们选择使用乐观锁，并使用强一致性存储作为乐观锁的数据源。

分片和法定人数

分布式系统经常需要存储大量的数据，远超一台节点的容量。一般的解决方案时使用分片，数据使用某种hash算法被水平分区。尽管很多分布式数据库屏蔽了分片的实现，但是分片还是挺有意思的，特别是关于重新分片。

许多分布式系统在多个拥有数据和统计信息。为保证对数据操作的一致性，使用基于投票的方式是不行的，只有超过一定数量的节点操作成功，这个操作才是成功的，这个叫做法定人数。

Actor模型

描述分布式系统最普遍的做法是使用Actor模型，还有一种方法是CSP。

Actor模型基于actor互相发送消息并作出回应。每一个actor只能做少量的动作，创建其他actors, 发送消息或者决定如何处理下个消息。通过这些简单的规则，复杂的分布式系统可以被准确描述，可以在actor崩溃后自我修复。

使用akka提供了标准的分布式模型，避免我们重复造轮子。

反应式架构

当构建大型分布式系统时，目标常常是它们的弹性，伸缩性，和扩展性。反应式架构是在这个领域最流行和最通用的方案。

序言

这次遇到贝壳花名的需求，需要使用最长公共子串对花名做校验。这种算法在面试题中算是必会题，各种四层循环，三层循环，两层循环的代码在我脑中闪过，但是今天就是要带你实现不一样的最长公共子串！

教科书式实现

使用动态规划，两层循环，使用二维数组存储状态，时间复杂度O(n^2^)，空间复杂度O(n^2^)或O(2n)

一张图解释原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

                  先 横 向 处 理
         +--------------------------->

           e   a   b   c   b   c   f
  +      +---+---+---+---+---+---+---+
  |    a | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
纵 |      +---------------------------+
向 |    b | 0 | 0 | 2 | 0 | 1 | 0 | 0 |
累 |      +---------------------------+
加 |    c | 0 | 0 | 0 | 3 | 0 | 2 | 0 |
  |      +---------------------------+
  |    d | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  |      +---------------------------+
  |    e | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
  v      +---+---+---+---+---+---+---+
           e   a   b   c   b   c   f

优化空间复杂度至O(1)

从上图可以发现，在纵向累加时实际只需要左上方的计数器即可, O(n^2^)的空间白白被浪费了,最优的空间复杂度应该是O(1)。那么该如何处理呢？

一张图解释原理：

                                   e   a   b   c   b   c   f
    +---+                        +---+---+---+---+---+---+---+
  a | 0 |                            | 1 | 0 | 0 | 0 | 0 | 0 | a
    +-------+                        +-----------------------+
  b | 0 | 0 |                            | 2 | 0 | 1 | 0 | 0 | b
    +-----------+                        --------------------+
  c | 0 | 0 | 0 |                            | 3 | 0 | 2 | 0 | c
    +---------------+                        ----------------+
  d | 0 | 0 | 0 | 0 |                            | 0 | 0 | 0 | d
    +-------------------+                        +-----------+
  e | 1 | 0 | 0 | 0 | 0 |                            | 0 | 0 | e
    +---+---+---+---+---+-------+                    +---+---+
      e   a   b   c   b   c   f

答案就是沿着等长对着线处理。

有意思的代码抽象

大家可以根据上面思路写一下，一般会把算法分成两部分：处理长方形的左下部分和处理长方形的右上部分，两部分都是双层循环，时间复杂度和空间负载度已经变为了O(n^2^) ，O(1)。

肯定有人已经发现自己的代码处理左下角的代码和处理右上角的代码不能复用，一个是从中间向左下角处理，一个是从中间向右上角处理，明明很类似，但是就是没发合并。

那么有没有方法把这两部分处理抽象成公共代码呢？不卖关子了，直接上图：

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

                                                         +
                                                       e |
                                                         +--+
  e   a   b   c   b   c   f                            a | 1|
+---+---+---+---+---+---+---+                            +-----+
    | 1 | 0 | 0 | 0 | 0 | 0 | a                        b | 0| 2|
    +-----------------------+                            +--------+
        | 2 | 0 | 1 | 0 | 0 | b                        c | 0| 0| 3|
        --------------------+         翻      折           +-----------+
            | 3 | 0 | 2 | 0 | c     +------------>     b | 0| 1| 0| 0|
            ----------------+                            +--------------+
                | 0 | 0 | 0 | d                        c | 0| 0| 2| 0| 0|
                +-----------+                            +--------------+
                    | 0 | 0 | e                        f | 0| 0| 0| 0| 0|
                    +---+---+                            +--------------+
                                                           a  b  c  d  e

如果你想使用公共代码同时实现处理左下角和右上角是不可能的了。所以你需要把右上角的三角翻折，然后你就得到了两个三角：

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

                                      +
                                    e |
                                      +--+
                                    a | 1|
  +---+                               +-----+
a | 0 |                             b | 0| 2|
  +-------+                           +--------+
b | 0 | 0 |                         c | 0| 0| 3|
  +-----------+                       +-----------+
c | 0 | 0 | 0 |                     b | 0| 1| 0| 0|
  +---------------+                   +--------------+
d | 0 | 0 | 0 | 0 |                 c | 0| 0| 2| 0| 0|
  +-------------------+               +--------------+
e | 1 | 0 | 0 | 0 | 0 |             f | 0| 0| 0| 0| 0|
  +---+---+---+---+---+------         +--------------+
    e   a   b   c   b   c   f           a  b  c  d  e

这样就变成了处理两遍左下角了，代码也可以完美复用！！！

最终实现

我的完整思考过程已经分析完毕，这样沿对着线处理还有一个小小的优点：提前结束搜索。这一点大家可以自行思考，这里不做过多解释。

直接干货上场：

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

public class Solution {
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        char[] achars = A.toCharArray(), bchars = B.toCharArray();
        return getMaxLength(bchars, achars, getMaxLength(achars, bchars, 0, 0), 1);
    }
    
    private static int getMaxLength(char[] s1, char[] s2, int maxLength, int startIndex) {
        
        for (int start = startIndex; start < s1.length; start++) {
            int upper = Math.min(s2.length, s1.length - start);
            // if (upper <= maxLength) break; //提前结束搜索
            for (int currentLineLength = 0, x = 0, y = start; x < upper; x++, y++) {
                if (s1[y] == s2[x])
                    maxLength = Math.max(maxLength, ++currentLineLength);
                else {
                    // if (upper - x - 1 <= maxLength) break; //提前结束搜索
                    currentLineLength = 0;
                };
            }
        }
        return maxLength;
    }
}

结尾

怎么样，经历这次优化过程是否感觉自己对最长公共子串的认识又更深了一步呢？虽然不能保证是首创（也可能是首创？），但是这次一步一步真切思考优化直到获得成果让我无比兴奋。

说了这么多，我就是要给我们贝壳招聘开发组打个广告>_>，期待更多爱思考优秀的同学加入！


1. 问题背景

权限系统现状

UC权限系统基于角色访问控制技术RBAC（Role Based Access Control） 。具体来说，就是赋予用户某个角色，角色给与角色对应的权限能访问及操作不同范围的资源。

什么是数据权限

代表一个角色对应某个权限所能操作的数据范围，比如gitlab组管理员能看到组下的所有项目代码，我们可以这样配置：

1. 创建组管理员
2. 分配给组管理员查看项目代码的权限
3. 查看项目代码权限设置约束条件，约束为自己组下的项目

实际产生遇到的问题

对绝大多数简单的系统来说一个用户对应一个系统只会有一个角色，一个角色只有一个数据权限范围（即使有多个，也可以合并成一个）。但是随着产品的功能迭代，用户的变更和系统设计的原因，总有一些特殊且重要的用户在同一个系统中拥有多个角色。在多角色和数据权限的组合下，一个用户可以拥有复数的数据权限范围。

考虑到实现复杂性，大多数系统选择使用角色切换的手段简化系统实现，同时对用户暴露出了他们不熟悉的角色这一概念，造成这些用户在系统使用中的各种不便。

本文重点讨论在避免角色切换的前提下，进行多角色数据范围查询的一种思路。

具体需要解决的需求

我们的数据报表后台，不同的角色拥有不同的数据查看范围（不同角色所能看到的员工数据字段也各不相同），例如：

• 薪酬管理员：查看非高职级员工数据
• 高级薪酬管理员： 查看高职级员工数据
• 长期激励管理员：查看有长期激励员工数据
• 等等

简单来说，拥有长期激励管理员和高级薪酬管理员的用户能否直接看到高职级员工数据和长期激励员工数据？至少在直觉上是可行的。

2.多角色数据范围查询

直觉的做法

单角色单数据范围可以使用一句sql查询出结果，那多角色多数据范围是不是使用多句sql查询出结果合并就可以了？

深入思考 多角色数据范围对行的影响

1. 查询条件合并还是结果合并？ —-结果合并
2. 如何排序？ —–外部排序，或先内部排序,limit,再外部排序
3. 有重复数据怎么办？ —-使用groupby去重
4. 查询性能有影响吗？—-有

具体体现：

1
2
3
4
5
6
7

select * from (
(select id, sortvalue from table_1 where t_name = 'a' order by sortvalue desc limit 20)  -- 先内部排序,limit
union all -- 结果合并
(select id, sortvalue from table_1 where t_name = 'b' order by sortvalue desc limit 20)  -- 先内部排序,limit
order by sortvalue desc  -- 外部排序
) a group by id -- 使用groupby去重
limit 10, 10

深入思考 多角色数据范围对列的影响

• 薪酬管理员： 查看员工薪酬字段
• 长期激励管理员：查看员工长期激励字段

如何解决？方法有很多！

综合思考，给出一种解决方案

1
2
3

graph LR
   A(查询行及角色信息) --> B(根据角色查询对应列字段)
   B --> C(结果) 

步骤：

1. 查询多角色数据范围下的数据，附带角色信息

1
2
3
4
5
6
7

select id, GROUP_CONCAT(a.role) as roles from (
(select id, 'role_a' as role from table_1 where sortvalue > 10 order by `sortvalue` desc limit 2)
union all
(select id, 'role_b' as role from table_1 where sortvalue > 20 order by `sortvalue` desc limit 2) 
order by `sortvalue` desc 
) a group by id
limit 0, 2

结果：

2. 根据每一行不同的角色，查询出可见的字段，例如id=1的行只能查看ROLE_B对应字段，而id=5的行可以看到ROLE_A,ROLE_B对应的两个角色的字段

3.总结和延伸

多角色数据范围写操作？

遍历角色直到找到满足条件的权限即可。

收获

自己不行动，等于等着被别人安排哈哈

还有疑问？

自己想。还可以点这里