不知名程序员韭菜个人博客

不知名程序员韭菜个人博客

不知名程序员韭菜个人博客
0%

发表于 更新于 分类于 Valine：

来源&参考

本题来自leetcode: 1206. 设计跳表
文章参考: Redis内部数据结构详解(6)——skiplist

什么是跳表

skiplist本质上也是一种查找结构，用于解决算法中的查找问题（Searching），即根据给定的key，快速查到它所在的位置（或者对应的value）。

跳表这种数据结构是由 $\text{William Pugh}$ 发明的，关于跳表的详细介绍可以参考论文: <<Skip Lists: A Probabilistic Alternative to
Balanced Trees>>，论文中详细阐述了关于 $\texttt{skiplist}$ 查找元素、删除元素、插入元素的算法伪代码，以及时间复杂度的分析。

跳表是一种随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树、$\texttt{AVL}$ 树不相上下，但是跳表的原理非常简单，目前在 $\texttt{Redis}$ 和 $\texttt{LevelDB}$ 中都有用到。跳表的期望空间复杂度为 $O(n)$，跳表的查询，插入和删除操作的期望时间复杂度均为 $O(\log n)$。跳表实际为一种多层的有序链表，跳表的每一层都为一个有序链表，且满足每个位于第 ii 层的节点有 pp 的概率出现在第 $i+1$ 层，其中 $p$ 为常数。

跳表结构简介

skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。

我们先来看一个有序链表，如下图（最左侧的灰色节点表示一个空的头结点）：

在这样一个链表中，如果我们要查找某个数据，那么需要从头开始逐个进行比较，直到找到包含数据的那个节点，或者找到第一个比给定数据大的节点为止（没找到）。也就是说，时间复杂度为O(n)。同样，当我们要插入新数据的时候，也要经历同样的查找过程，从而确定插入位置。

假如我们每相邻两个节点增加一个指针，让指针指向下下个节点，如下图：

每两个节点增加一个跳跃指针的有序链表

这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半（上图中是7, 19, 26）。现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中进行查找。比如，我们想查找23，查找的路径是沿着下图中标红的指针所指向的方向进行的：

一个搜索路径的例子

  • 23首先和7比较，再和19比较，比它们都大，继续向后比较。
  • 但23和26比较的时候，比26要小，因此回到下面的链表（原链表），与22比较。
  • 23比22要大，沿下面的指针继续向后和26比较。23比26小，说明待查数据23在原链表中不存在，而且它的插入位置应该在22和26之间。

在这个查找过程中，由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。

利用同样的方式，我们可以在上层新产生的链表上，继续为每相邻的两个节点增加一个指针，从而产生第三层链表。如下图：

两层跳跃指针

在这个新的三层链表结构上，如果我们还是查找23，那么沿着最上层链表首先要比较的是19，发现23比19大，接下来我们就知道只需要到19的后面去继续查找，从而一下子跳过了19前面的所有节点。可以想象，当链表足够长的时候，这种多层链表的查找方式能让我们跳过很多下层节点，大大加快查找的速度。

skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。为了表达清楚，下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程：

skiplist插入形成过程

从上面skiplist的创建和插入过程可以看出，每一个节点的层数（level）是随机出来的，而且新插入一个节点不会影响其它节点的层数。因此，插入操作只需要修改插入节点前后的指针，而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。实际上，这是skiplist的一个很重要的特性，这让它在插入性能上明显优于平衡树的方案。这在后面我们还会提到。

根据上图中的skiplist结构，我们很容易理解这种数据结构的名字的由来。skiplist，翻译成中文，可以翻译成“跳表”或“跳跃表”，指的就是除了最下面第1层链表之外，它会产生若干层稀疏的链表，这些链表里面的指针故意跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候能够先在高层的链表中进行查找，然后逐层降低，最终降到第1层链表来精确地确定数据位置。在这个过程中，我们跳过了一些节点，从而也就加快了查找速度。

刚刚创建的这个skiplist总共包含4层链表，现在假设我们在它里面依然查找23，下图给出了查找路径：

skiplist上的查找路径展示

需要注意的是，前面演示的各个节点的插入过程，实际上在插入之前也要先经历一个类似的查找过程，在确定插入位置后，再完成插入操作。

至此，skiplist的查找和插入操作，我们已经很清楚了。而删除操作与插入操作类似，我们也很容易想象出来。这些操作我们也应该能很容易地用代码实现出来。

当然，实际应用中的skiplist每个节点应该包含key和value两部分。前面的描述中我们没有具体区分key和value，但实际上列表中是按照key进行排序的，查找过程也是根据key在比较。

但是，如果你是第一次接触skiplist，那么一定会产生一个疑问：节点插入时随机出一个层数，仅仅依靠这样一个简单的随机数操作而构建出来的多层链表结构，能保证它有一个良好的查找性能吗？为了回答这个疑问，我们需要分析skiplist的统计性能。

在分析之前，我们还需要着重指出的是，执行插入操作时计算随机数的过程，是一个很关键的过程，它对skiplist的统计特性有着很重要的影响。这并不是一个普通的服从均匀分布的随机数，它的计算过程如下：

  • 首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。
  • 如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。
  • 节点最大的层数不允许超过一个最大值，记为MaxLevel。
    这个计算随机层数的伪码如下所示：
1
2
3
4
5
6
randomLevel()
    level := 1
    // random()返回一个[0...1)的随机数
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

randomLevel()的伪码中包含两个参数，一个是p，一个是MaxLevel。在Redis的skiplist实现中，这两个参数的取值为：

1
2
p = 1/4
MaxLevel = 32

跳表的代码实现

此段参考 Java手写实现跳表

跳表实现的主要难度在于插入(add)算法。只要把add方法搞明白之后，一切都迎刃而解了。

关于跳表的插入，一张图即可描述出来，

通过这张图，可以先确定跳表中每个节点的数据结构：

1
2
3
4
5
6
7
8
9
class Node{
    Integer value; //节点值
    Node[] next; // 节点在不同层的下一个节点

    public Node(Integer value,int size) { // 用size表示当前节点在跳表中索引几层
        this.value = value;
        this.next = new Node[size];
    }
}

然后就需要考虑：我插入一个节点Node，它到底应该是索引到第几层呢？

一开始我还想着如何准确的维护上一层是下一层的1/2，发现越想越复杂；然后通过相关资料，发现人家早就给出一个解决方案：随机出来一个层数。

这里有一个疑惑：就凭随机出来的一个层数，能保证查询与插入性能吗？

在分析之前，我们还需要着重指出的是，执行插入操作时计算随机数的过程，是一个很关键的过程，它对skiplist的统计特性有着很重要的影响。这并不是一个普通的服从均匀分布的随机数，它的计算过程如下：
首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。
如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。
节点最大的层数不允许超过一个最大值，记为MaxLevel。
这个计算随机层数的伪码如下所示：

1
2
3
4
5
6
int randomLevel()
    int level = 1;
    while (Math.random()<p && level<MaxLevel){
        level ++ ;
    }
    return level;

randomLevel()的伪码中包含两个参数，一个是p，一个是MaxLevel。在Redis的skiplist实现中，这两个参数的取值为：

1
2
p = 1/4
MaxLevel = 32

知道了层数，这下就好办了。思路如下：

1、先随机出来一个层数，new要插入的节点，先叫做插入节点newNode；
2、根据跳表实际的总层数从上往下分析，要插入一个节点newNode时，先找到节点在该层的位置：因为是链表，所以需要一个节点node，满足插入插入节点newNode的值刚好不大于node的下一个节点值，当然，如果node的下个节点为空，那么也是满足的。

我们先把找节点在某一层位置的方法封装起来：

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 找到level层 value 刚好不小于node 的节点
* @param node 从哪个节点开始找
* @param levelIndex 所在层
* @param value 要插入的节点值
* @return
*/
private Node findClosest(Node node,int levelIndex,int value){
    while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
        node = node.next[levelIndex];
    }
    return node;
}

3、确定插入节点newNode在该层的位置后，先判断下newNode的随机层数是否小于当前跳表的总层数，如果是，则用链表的插入方法将newNode插入即可。

4、如此循环，直到最底层插入newNode完毕。

5、循环完毕后，还需要判断下newNode随机出来的层数是否比跳表的实际层数还要大，如果是，直接将超过实际层数的跳表的头节点指向newNode即可，该跳表的实际层数也就变为newNode的随机层数了。

以上就是插入的算法。

理解了插入算法后，查找跟删除就简单多了。

不管是插入、查找还是删除，均是从跳表上层往下层分析，复用上面的findClosest方法，找到要查询的值 在该层closest的节点。比如查询，只需要判断findClosest出来的节点值是否等于该查询值即可，是就返回，不是则继续往下层判断。删除方法思想也是一致的。

代码

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
class Skiplist {
        /**
         * 最大层数
         */
        private static int DEFAULT_MAX_LEVEL = 32;
        /**
         * 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
         */
        private static double DEFAULT_P_FACTOR = 0.25;

        Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点

        int currentLevel = 1; //表示当前nodes的实际层数，它从1开始


        public Skiplist() {
        }

        public boolean search(int target) {
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, target);
                if (searchNode.next[i]!=null && searchNode.next[i].value == target){
                    return true;
                }
            }
            return false;
        }

        /**
         *
         * @param num
         */
        public void add(int num) {
            int level = randomLevel();
            Node updateNode = head;
            Node newNode = new Node(num,level);
            // 计算出当前num 索引的实际层数，从该层开始添加索引
            for (int i = currentLevel-1; i>=0; i--) {
                //找到本层最近离num最近的list
                updateNode = findClosest(updateNode,i,num);
                if (i<level){
                    if (updateNode.next[i]==null){
                        updateNode.next[i] = newNode;
                    }else{
                        Node temp = updateNode.next[i];
                        updateNode.next[i] = newNode;
                        newNode.next[i] = temp;
                    }
                }
            }
            if (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
                for (int i = currentLevel; i < level; i++) {
                    head.next[i] = newNode;
                }
                currentLevel = level;
            }

        }

        public boolean erase(int num) {
            boolean flag = false;
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, num);
                if (searchNode.next[i]!=null && searchNode.next[i].value == num){
                    //找到该层中该节点
                    searchNode.next[i] = searchNode.next[i].next[i];
                    flag = true;
                    continue;
                }
            }
            return flag;
        }

        /**
         * 找到level层 value 大于node 的节点
         * @param node
         * @param levelIndex
         * @param value
         * @return
         */
        private Node findClosest(Node node,int levelIndex,int value){
            while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
                node = node.next[levelIndex];
            }
            return node;
        }


        /**
         * 随机一个层数
         */
        private static int randomLevel(){
            int level = 1;
            while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
                level ++ ;
            }
            return level;
        }


        class Node{
            Integer value;
            Node[] next;

            public Node(Integer value,int size) {
                this.value = value;
                this.next = new Node[size];
            }

            @Override
            public String toString() {
                return String.valueOf(value);
            }
        }

    }

skiplist的算法性能分析

在这一部分，我们来简单分析一下skiplist的时间复杂度和空间复杂度，以便对于skiplist的性能有一个直观的了解

我们先来计算一下每个节点所包含的平均指针数目（概率期望）。节点包含的指针数目，相当于这个算法在空间上的额外开销(overhead)，可以用来度量空间复杂度。

根据前面randomLevel()的伪码，我们很容易看出，产生越高的节点层数，概率越低。定量的分析如下：

  • 节点层数至少为1。而大于1的节点层数，满足一个概率分布。
  • 节点层数恰好等于1的概率为1-p。
  • 节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。
  • 节点层数大于等于3的概率为p2，而节点层数恰好等于3的概率为p2(1-p)。
  • 节点层数大于等于4的概率为p3，而节点层数恰好等于4的概率为p3(1-p)。
    ……
    因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：

skiplist平均层数计算

现在很容易计算出：

  • 当p=1/2时，每个节点所包含的平均指针数目为2；
  • 当p=1/4时，每个节点所包含的平均指针数目为1.33。这也是Redis里的skiplist实现在空间上的开销。

接下来，为了分析时间复杂度，我们计算一下skiplist的平均查找长度。查找长度指的是查找路径上跨越的跳数，而查找过程中的比较次数就等于查找长度加1。以前面图中标出的查找23的查找路径为例，从左上角的头结点开始，一直到结点22，查找长度为6。

为了计算查找长度，这里我们需要利用一点小技巧。我们注意到，每个节点插入的时候，它的层数是由随机函数randomLevel()计算出来的，而且随机的计算不依赖于其它节点，每次插入过程都是完全独立的。所以，从统计上来说，一个skiplist结构的形成与节点的插入顺序无关。

这样的话，为了计算查找长度，我们可以将查找过程倒过来看，从右下方第1层上最后到达的那个节点开始，沿着查找路径向左向上回溯，类似于爬楼梯的过程。我们假设当回溯到某个节点的时候，它才被插入，这虽然相当于改变了节点的插入顺序，但从统计上不影响整个skiplist的形成结构。

现在假设我们从一个层数为i的节点x出发，需要向左向上攀爬k层。这时我们有两种可能：

  • 如果节点x有第(i+1)层指针，那么我们需要向上走。这种情况概率为p。
  • 如果节点x没有第(i+1)层指针，那么我们需要向左走。这种情况概率为(1-p)。

这两种情形如下图所示：

skiplist沿查找路径回溯

用C(k)表示向上攀爬k个层级所需要走过的平均查找路径长度（概率期望），那么：

1
2
C(0)=0
C(k)=(1-p)×(上图中情况b的查找长度) + p×(上图中情况c的查找长度)

代入，得到一个差分方程并化简：

1
2
3
C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)
C(k)=1/p+C(k-1)
C(k)=k/p

这个结果的意思是，我们每爬升1个层级，需要在查找路径上走1/p步。而我们总共需要攀爬的层级数等于整个skiplist的总层数-1。

那么接下来我们需要分析一下当skiplist中有n个节点的时候，它的总层数的概率均值是多少。这个问题直观上比较好理解。根据节点的层数随机算法，容易得出：

  • 第1层链表固定有n个节点；
  • 第2层链表平均有n*p个节点；
  • 第3层链表平均有n*p2个节点；
  • …

所以，从第1层到最高层，各层链表的平均节点数是一个指数递减的等比数列。容易推算出，总层数的均值为log1/pn，而最高层的平均节点数为1/p。

综上，粗略来计算的话，平均查找长度约等于：

  • C(log1/pn-1)=(log1/pn-1)/p

即，平均时间复杂度为O(log n)。

当然，这里的时间复杂度分析还是比较粗略的。比如，沿着查找路径向左向上回溯的时候，可能先到达左侧头结点，然后沿头结点一路向上；还可能先到达最高层的节点，然后沿着最高层链表一路向左。但这些细节不影响平均时间复杂度的最后结果。另外，这里给出的时间复杂度只是一个概率平均值，但实际上计算一个精细的概率分布也是有可能的。详情还请参见William Pugh的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。

skiplist与平衡树、哈希表的比较

  • skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
  • 在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
  • 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
  • 从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
  • 查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
  • 从算法实现难度上来比较，skiplist比平衡树要简单得多。

发表于 更新于 分类于 Valine：

前言

最近使用hexo+next 搭建博客完毕，大体框架已经上线。
忽然间想了解自己博客的一个访问情况。
这就需要用到网站统计了。

网站统计的原理

如上图所示，现在市面上的网站统计基本都是通过嵌入js脚本实现的。

网页被打开时，页面中的埋点javascript片段会被执行，该js会请求一个后端的数据收集脚本（图1中的backend），就此完成数据收集。

现在市面上常见的网站统计有

由于next已经集成了百度统计，就直接选择了百度统计。

hexo+next集成百度统计具体操作

1、注册百度统计账号
2、点击【使用设置】-【新增网站】添加需要统计的网站地址

3、点击获取代码，获取嵌入的js代码

1
2
3
4
5
6
7
8
9
10
<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?xxxxxxx";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>

4、由于next已经帮我们嵌入了上面这段代码，我们只需在/hexo/them/next/_config.yml里找到baidu_analytics 填入上面hm.js?后面的一串密钥即可。

1
2
3
4
# Baidu Analytics
# See: https://tongji.baidu.com
baidu_analytics: a805ddefgf9181cd83 # <app_id>

5、大概等待20分钟，回到百度统计，在主页下即可查看网站统计情况。

发表于 更新于 分类于 Valine：

创建新库命令

1
create database hive;

创建新用户命令

1
create user 'hive'@'%' identified by 'xxpasswordxx';

其中hive为用户名
‘%’表示允许所有ip登录
xxpasswordxx 表示密码

授权命令

1
grant all privileges on hive.* to 'hive'@'%' with grant option;

hive.* 表示授权hive库下的所有表
‘hive‘@’%’ 表示hive用于，允许所有ip登录

发表于 更新于 分类于 Valine：

设计模式随笔

最近复习下设计模式，顺便写下随笔

设计模式的六大原则

  1. 单一职责原则 英文：single responsibility principle,缩写：SRP
    单一职责就是一个借口或类，只完成一个职责
    好处： 类的复杂性降低、可读性提高、可维护性提高、降低变更引起的风险

  2. 里式替换原则
    官方定义：所有引用基类的地方必须能透明的使用其子类对象
    简单的说，就是父类使用的地方，都能用子类替换

  3. 依赖倒置原则
    定义：

    1. 高层模块不应该依赖底层模块，两者都应该依赖期抽象
    2. 抽象不应该依赖细节
    3. 细节应该依赖抽象

    不可分割的原子逻辑就是底层模块，原子逻辑再组装就是高层模块，java中，抽象就是借口或抽象类，细节就是实现类，也就是new 出来的对象

    最精简的定义：面向接口编程

    采用依赖倒置原则可以减少类间的耦合性，提高系统的稳定性，降低并行开发引起的风险，提高代码的可读性和可维护性

  4. 接口隔离原则

    定义： 客户端不应该依赖它不需要的接口，类间的依赖关系应建立在最小接口上

    简单来说就是建立单一接口，功能细化，不要臃肿，不要去实现不必要的接口

  5. 迪米特法则，law of demeter lod，也成最少知识原则(least knowlege priciple lkp)

    一个对象应该对其他对象有对少的了解

    通俗说，一个类不关心耦合类的内部接口，只关心耦合类暴露的方法

    核心：高内聚，低耦合

  6. 开闭原则
    定义： 一个软件实体，如类、模块和函数，应该对扩展开放，对修改关闭

    简单来说，通过新增类扩修改业务代码进行扩展，而非修改功能性代码。

23种设计模式

  1. 单例模式
    定义：确保某一个类只有一个实例，且自行实例化冰箱整个系统提供这个实例

  2. 工厂方法模式

    定义： 定义一个用于创建对象的接口，让子类决定实例化哪一类，工厂方法使用一个类的实例化延迟到其子类

  3. 抽象工厂模式
    定义： 为创建一组相关或相互依赖的对象提供一个接口，而且无需指定他们的具体类

  4. 模板方法模式

    定义：定义一个操作中的算法的框架，将一些步骤延迟到子类中。使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤

  5. 建造者模式

    定义：将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示

  6. 代理模式

定义： 为其他对象提供一种代理以控制对这个对象的访问
7. 原型模式

定义： 用原型示例指定创建对象的种类，并且通过拷贝这些原型创建新的对象

java中jdk自带的clone就是

优点： 对象的创建时内存二进制流的拷贝，性能比new对象好

  1. 中介者模式

定义： 用一个中介对象封装一系列的对象交互，中介者使各对象不需要显示的相互作用，从而使其耦合松散，，而且可以独立的改变他们之间的交互

  1. 命令模式

定义：将一个请求封装成一个对象，从而让你使用不同的请求把客户端参数化，对请求排队或者记录请求日志，可以提供命令的撤销和恢复功能

  1. 责任链模式

定义：使多个对象都有机会处理请求，从而避免了请求的发送者和接受者之间的耦合关系。将这些对象连城一条链，并沿着这条链传递该请求，知道有对象处理它为止。

  1. 装饰模式 decorator pattern

定义：动态的给一个对象添加一些额外的职责。就增加功能来说，装饰模式相比生成子类更为灵活

优点：

1. 装饰类和被装饰类可以独立发展，而不会互相耦合
2. 装饰模式是集成关系的一个替代方案
3. 装饰模式可以动态的扩展一个实现类的功能

缺点：剁成的装饰是复杂的

使用场景：

1. 需要扩展一个类的功能，或者给一个类增加附加功能
2. 需要动态的给一个对象增加功能，这些功能可以动态的撤销
3. 需要为一批的兄弟类进行改装或加装功能
  1. 策略模式 strategy pattern

  • 定义：定义一组算法，将每个算法都封装起来，并且使它们之间可以互换

  • 优点：

    1. 算法可以自由切换
    2. 避免使用多重条件判断
    3. 扩展性良好

  • 缺点：

    1. 策略类数量增多
    2. 所有的策略类都需要对外暴露

  • 使用场景：

    1. 多个类只有在算法或行为上稍有不同的场景
    2. 算法需要自由切换的场景
    3. 需要屏蔽算法规则的场景
  1. 适配器模式 adapter pattern
  • 定义：将一个类的接口变换成客户端所期待的另一种接口，从而使原本因接口不匹配而无法在一起工作的两个类能够在一起工作
  • 优点：
    1. 适配器模式可以让两个没有任何关系的类在一起运行，只要适配器这个角色能够搞定他们就成
    2. 增加了类的透明性
    3. 提高了类的复用度
    4. 灵活性非常好
  • 缺点：
  • 使用场景：后期修改一个接口或类
  1. 迭代器模式 iterator pattern
  • 定义：它提供一种方法访问一个容器对象中各个元素，而又不需暴露该对象的内部细节
  • 优点：
  • 缺点：
  • 使用场景：
  1. 组合模式
  • 定义：
  • 优点：
    1. 高层模块调用简单
    2. 节点自由增加
  • 缺点：
  • 使用场景：维护和展示部分-整体关系的场景
  1. 观察者模式 observer pattern
  • 定义：定义对象间一种一对多的依赖关系，使得每当一个对象改变状态，则所有依赖于它的对象都会得到通知并被自动更新
  • 优点：
    1. 观察者和被观察之间是抽象耦合
    2. 建立一套触发机制
  • 缺点：
  • 使用场景：
  1. 门面模式 facade pattern

  • 定义：要求一个子系统的外部与其内部的通信必须通过一个统一的对象进行。门面模式提供一个高层次的接口，使得子系统更易于使用。

  • 优点：

    1. 减少系统的相互依赖
    2. 提高灵活性
    3. 提高安全性

  • 缺点：

  • 使用场景：

    1. 为一个复杂的模块或子系统提供一个供外界访问的接口
    2. 子系统相对独立——外界对子系统的访问只要黑箱操作即可
  1. 备忘录模式
  • 定义：
  • 优点：
  • 缺点：
  • 使用场景：
  1. 访问者模式 visitor pattern
  • 定义：封装一些作用于某种数据结构中的各元素的操作，它可以在不改变数据结构的前提下定义作用于这些元素的新的操作。
  • 优点：
    1. 符合单一职责远侧
    2. 优秀的扩展性
    3. 灵活性高
  • 缺点：
    1. 具体元素对访问者公布细节
    2. 具体元素变更比较困难
    3. 违背了依赖倒置原则
  • 使用场景：
  1. 状态模式 state pattern

  • 定义：当一个对象内在状态改变时允许其改变行为，这个对象看起来像改变了其类

  • 优点：

    1. 结构清晰
    2. 遵循设计原则
    3. 封装性非常好

  • 缺点：子类太多

  • 使用场景：

    1. 行为随状态改变而改变的场景
    2. 条件、分支判断语句的替代者
  1. 解释器模式 intrpreter pattern
  • 定义：给定一门语言，定义它的文法的一种表示，并定义一个解释器，该解释器使用该表示来解释语言中的句子
  • 优点：
  • 缺点：
    1. 解释器模式会引起类膨胀
    2. 采用递归调用方法
    3. 效率问题
  • 使用场景：
  1. 享元模式 flyweight pattern
  • 定义：使用共享对象可有效地支持大量的细粒度的对象
  • 优点：
  • 缺点：
  • 使用场景：
    1. 系统中存在大象的相似对象
    2. 细粒度的对象都具备较接近的外部状态，而且内部状态与环境无关
    3. 需要缓冲池场景
  1. 桥梁模式 bridge pattern
  • 定义：将抽象和实现解耦，使得两者可以独立地变化
  • 优点：
    1. 抽象和实现分离
    2. 优秀的扩充能力
    3. 实现细节对客户透明
  • 缺点：
  • 使用场景：
    1. 不系统或不适用继承的场景
    2. 接口或抽象类不稳定的场景
    3. 重要性要求较高的场景

发表于 更新于 分类于 Valine：

今天在调整个人博客时，发现字体偏大

看着挺不舒服的，就想把字体调小一点。

搜索了一圈，发下next下有现成的配置。

在/them/next/_config.yml下，顺利的找到了调整的地方

1、将font下enable改为true，表示开启字体下载
2、将host设置为 https://fonts.googlefonts.cn 表示从哪个网站下载
2、将host设置为 https://fonts.loli.net 表示从哪个网站下载

系统默认的是 https://fonts.google.com ，然而由于国内的原因，你懂得，无法连接，万幸的是，有谷歌字体国内版：https://www.googlefonts.cn/ ，我们只要把host改成国内版即可

我们需要一些国内站替换或cdn，经过本人搜索，css.loli.net提供了国内对应谷歌的一些服务

1
2
3
4
ajax.googleapis。com  -> ajax.loli.net
fonts.googleapis。com -> fonts.loli.net
fonts.gstatic.com  -> gstatic.loli.net
themes.googleusercontent.com -> themes.loli.net

3、将global的size调整为0.8

调整完后，这字体就非常的舒适了。

发表于 更新于 分类于 Valine：

前言

数仓中的脚本作业，经常会存在补数或重刷历史数据的场景，一个高质量的脚本作业，往往具有极高的幂等性、鲁棒性。

这样，在重刷或补数时，才能以极简的操作保证数据的准确性，稳定性。

  • 缺少幂等性，可能存在传入相同的业务日期，但是结果不一致。
  • 缺少鲁棒性，可能导致脚本产出奔溃。

而要想写出具有幂等性、鲁棒性的脚本作业，必须考虑到动态传参及数据过滤，这就需要我们对数仓中的各日期含义一清二楚。

业务日期

数据日期

调度时间

调度运行时间

发表于 更新于 分类于 Valine：

背景

阅读spark源码时，从spark的单元测试入手是一个非常好的选择，spark的单元测试覆盖了非常多的场景，从单元测试入手非常有助于我们理解spark原理。
如：BroadcastSuite中的 

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
encryptionTest("Cache broadcast to disk") { conf =>
  conf.setMaster("local")
    .setAppName("test")
    .set(config.MEMORY_STORAGE_FRACTION, 0.0)
  sc = new SparkContext(conf)
  val list = List[Int](1, 2, 3, 4)
  val broadcast = sc.broadcast(list)
  assert(broadcast.value.sum === 10)
}

test("One broadcast value instance per executor") {
  val conf = new SparkConf()
    .setMaster("local[4]")
    .setAppName("test")

  sc = new SparkContext(conf)
  val list = List[Int](1, 2, 3, 4)
  val broadcast = sc.broadcast(list)
  val instances = sc.parallelize(1 to 10)
    .map(x => System.identityHashCode(broadcast.value))
    .collect()
    .toSet

  assert(instances.size === 1)
}

非常简单易懂，从字面意思我们就能理解这个单元测试是做什么的，那么如何debug呢？这就开启我们的debug之旅。

基本原理

采用java jdwp(Java Debug Wire Protocol) 实现，也就是远程debug，它定义了调试器（debugger）和被调试的 Java 虚拟机（target vm）之间的通信协议。

想要具体了解，可以参考此篇 使用jdwp远程debug java代码

我们采用idea作为服务器listner，spark sbt单元测试作为客户端的方式进行debug。

具体操作

idea remote debug listner开启

1、点击run下的edit configuration

2、配置remote debug，具体如下图所示
端口这些一般使用默认的就好

3、点击debug按钮，启动remote debug listner

SBT 操作

基于sbt，我们可以运行spark的单元测试，在运行我们设置好jvm参数即可链接上idea的remote debug listner，下面以运行spark core项目下的BroadcastSuite下的 test("Using TorrentBroadcast locally") 为例

1、进入spark目录
2、运行./build/sbt ，启动spark自带的sbt server


此时，sbt server启动完毕，可以看到我们在spark-parent总的项目下

3、输入 project core ，切换到spark core 子module下

4、输入

1
set javaOptions in Test += "-agentlib:jdwp=transport=dt_socket,server=n,suspend=y,address=localhost:5005"

表示运行单元测试时，启动jvm代理，连接到本地5005端口，也就是上文idea启动的监听端口

5、运行单元测试

1
2
testOnly *BroadcastSuite -- -z "Using TorrentBroadcast locally"

其中，-z 后面的参数为scala test后面跟的字段

运行结果如下图所示：

可以看到，单元测试运行到broadcastSuit时被阻塞，这是因为我们在idea断debug了。


可以看到，idea的spark源码已经顺利进入断点模式，可以愉快的debug spark源码了，祝大家阅读源码愉快。

参考资料

基于spark源码做单元测试

发表于 更新于 分类于 Valine：

本文转自 ieda-远程调试(java -agentlib:jdwp)

背景

当项目投产后，可能会遇到之前测试环境上没有遇到的问题，而又无法快速定位问题原因，令人十分捉急。
如果开发人员电脑可以接入生产环境，则可以采用java -agentlib:jdwp命令、idea或eclipse进行远程调试。
本文中使用IDEA进行远程调试。

#概念介绍

-agentlib 是什么

agentlib表示加载本机的代理库，输入java命令后，可以看到agentlib的介绍

1
2
3
4
5
6
7
8
-agentlib:<libname>[=<选项>]
              加载本机代理库 <libname>, 例如 -agentlib:hprof
              另请参阅 -agentlib:jdwp=help 和 -agentlib:hprof=help
-agentpath:<pathname>[=<选项>]
              按完整路径名加载本机代理库
-javaagent:<jarpath>[=<选项>]
              加载 Java 编程语言代理, 请参阅 java.lang.instrument

JDWP 是什么？

JDWP 是 Java Debug Wire Protocol 的缩写，它定义了调试器（debugger）和被调试的 Java 虚拟机（target vm）之间的通信协议。

当使用java -agentlib:jdwp启动jar时，表示也在会address对应的端口上启动一个tcp监听，等待客户端（调试端，比如idea、eclipse）连接。

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

               Java Debugger JDWP Agent Library
               --------------------------------

  (see http://java.sun.com/products/jpda for more information)

jdwp usage: java -agentlib:jdwp=[help]|[<option>=<value>, ...]

Option Name and Value            Description                       Default
---------------------            -----------                       -------
suspend=y|n                      wait on startup?                  y
transport=<name>                 transport spec                    none
address=<listen/attach address>  transport spec                    ""
server=y|n                       listen for debugger?              n
launch=<command line>            run debugger on event             none
onthrow=<exception name>         debug on throw                    none
onuncaught=y|n                   debug on any uncaught?            n
timeout=<timeout value>          for listen/attach in milliseconds n
mutf8=y|n                        output modified utf-8             n
quiet=y|n                        control over terminal messages    n

Obsolete Options
----------------
strict=y|n
stdalloc=y|n

Examples
--------
  - Using sockets connect to a debugger at a specific address:
    java -agentlib:jdwp=transport=dt_socket,address=localhost:8000 ...
  - Using sockets listen for a debugger to attach:
    java -agentlib:jdwp=transport=dt_socket,server=y,suspend=y ...

Notes
-----
  - A timeout value of 0 (the default) is no timeout.

Warnings
--------
  - The older -Xrunjdwp interface can still be used, but will be removed in
    a future release, for example:
        java -Xdebug -Xrunjdwp:[help]|[<option>=<value>, ...]

远程debug操作

操作可以分为2类
1、idea作为服务，等待客户端连接
2、其他java进程作为服务，等待idea客户端连接
本文采用方式2

服务端配置

服务端启动jar命令，增加java -agentlib:jdwp，如下：

1
2
3
4
# 需要保证-agentlib:jdwp命令在 -jar命令之前
# server=y 表示是服务端
# syspend=n 表示启动时是否阻塞等待
java -agentlib:jdwp=transport=dt_socket,server=y,suspend=n,address=5005   -jar xxx.jar

客户端idea配置

使用的是idea remote jvm debug功能，如下图所示

启动调试

1、启动jar
2、在idea中启动配置好的Remote
3、在源码中打断点，就可以调试

另Arthas很强大，也可以使用Arthas进行线上调试。