题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

裴波那契数列

1
2
3
4
5
6
7
8
9
10
11
12

public int JumpFloor(int target) {
    if (target < 3) {
        return target;
    }
    int[] fb = new int[target + 1];
    fb[1] = 1;
    fb[2] = 2;
    for (int i = 3; i < target + 1; i++) {
        fb[i] = fb[i - 2] + fb[i - 1];
    }
    return fb[target];
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/8c82a5b80378478f9484d87d1c5f12a4?answerType=1&f=discussion
来源：牛客网

迭代

本质上还是斐波那契数列，所以迭代也可以求

当成 dp 问题来想的话：首先分析问题，它最终解是由前面的解累积起来的解，如何缩小问题的规模？

首先可知，第一阶有只能一步，一种；，第二阶可以两次一步、一次两步两种

• 若楼梯阶级 n = 3
  • 跳 2 步到 3：剩下的是第一步没跳，起始跳到第一步只有一种
  • 跳 1 步到 3：剩下的是第二步没跳，起始跳到第二步有两种

通过分类讨论，问题规模就减少了:

• 若楼梯阶级 n = n
  • 跳 2 步到 n：剩下的是第 n - 2 步没跳，起始跳到第 n - 2 步设它为 pre2 种
  • 跳 1 步到 n：剩下的是第 n - 1 步没跳，起始跳到第 n - 1 步设它为 pre1 种

同时可以发现第 n 阶的解法，只要用到 n - 1 和 n - 2 阶是多少，其他的不用考虑，因此用两个变量临时存下来即可

dp(i) = dp(i-2) + dp(i-1)

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

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 2){
            return target;
        }
        int pre2 = 1, pre1 = 2;
        for (int i = 3; i <= target; i++){
            int cur = pre2 + pre1;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

n<=39;

使用数组存储中间状态(最简单的动态规划),避免递归造成的调用栈空间消耗

1
2
3
4
5
6
7
8

public int Fibonacci(int n) {
    int[] fb=new int[40];
    fb[0]=0;fb[1]=1;
    for (int i = 2; i < 40; i++) {
        fb[i]=fb[i-2]+fb[i-1];
    }
    return fb[n];
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3?answerType=1&f=discussion
来源：牛客网

1. 递归法

1. 分析

斐波那契数列的标准公式为：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
根据公式可以直接写出：

2. 代码

1
2
3
4
5
6
7
8

public class Solution {
    public int Fibonacci(int n) {
        if(n<=1){
            return n;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

3. 复杂度

时间复杂度：
空间复杂度：

2. 优化递归

1. 分析

递归会重复计算大量相同数据，我们用个数组把结果存起来8！

2. 代码

1
2
3
4
5
6
7
8
9
10
11

public class Solution {
    public int Fibonacci(int n) {
        int ans[] = new int[40];
        ans[0] = 0;
        ans[1] = 1;
        for(int i=2;i<=n;i++){
            ans[i] = ans[i-1] + ans[i-2];
        }
        return ans[n];
    }
}

3. 复杂度：

时间复杂度：
空间复杂度：

3. 优化存储

1. 分析

其实我们可以发现每次就用到了最近的两个数，所以我们可以只存储最近的两个数

• sum 存储第 n 项的值
• one 存储第 n-1 项的值
• two 存储第 n-2 项的值

2. 代码

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

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }
        int sum = 0;
        int two = 0;
        int one = 1;
        for(int i=2;i<=n;i++){
            sum = two + one;
            two = one;
            one = sum;
        }
        return sum;
    }
}

3. 复杂度：

时间复杂度：
空间复杂度：

4. 持续优化

1. 分析

观察上一版发现，sum 只在每次计算第 n 项的时候用一下，其实还可以利用 sum 存储第 n-1 项，例如当计算完 f(5) 时 sum 存储的是 f(5) 的值，当需要计算 f(6) 时，f(6) = f(5) + f(4)，sum 存储的 f(5)，f(4) 存储在 one 中，由 f(5)-f(3) 得到
如图：

2. 代码

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

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }
        int sum = 1;
        int one = 0;
        for(int i=2;i<=n;i++){
            sum = sum + one;
            one = sum - one;
        }
        return sum;
    }
}

3. 复杂度

时间复杂度：
空间复杂度：

本文内容为慕课网Python全栈案例入门课程笔记,点击跳转课程页面

后端

Python web框架

• flask 简单轻量,灵活性大,创建于2010
• django 简单,比flask重,灵活性不如flask,创建于2006
• web.py 简单轻量,不再维护,创建于2008

web应用开发流程

1. 产品分析: 用户需求,市场调研
2. 技术选型: 前端,后端,数据库,业务框架(大数据,直播)
3. 开发实现: 前后端开发,测试
4. 生产上线: 部署,升级,峰值处理,成本优化,警报处理

   Python基础

   常用数据类型

• 字符串:str,unicode
  python3.x只有str
• 列表:list 可变列表, tuple 不可变列表, set 唯一列表
  tuple内的元素是不变的
• 字典:dict
  key —> value映射,数据量大可用redis数据库

生成器

generator

1
2
3
4
5
6
7

# 一次性产生10个元素的数组,占内存
for i in range(10)
	print i
	
#xrange() 函数用法与 range 完全相同，所不同的是生成的不是一个数组，而是一个生成器,依次产生1,2,3...节省内存
for i in xrange(10) #
	print i

迭代器

迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束。迭代器只能往前不会后退。
迭代器有两个基本的方法：iter()和 next()。
字符串str，列表list或元组tuple对象都可用于创建迭代器：

1
2
3
4
5
6
7
8
9

>>> list=[1,2,3,4]
>>> it = iter(list)    # 创建迭代器对象
>>> print (next(it))   # 输出迭代器的下一个元素
1
>>> print (next(it))
2
# 可以使用常规for语句进行遍历：
for x in it:
    print (x, end=" ")

切片

1
2
3
4
5
6
7

>>> list = range(10)
>>>> list
[0,1,2,3,4,5,6,7,8,9]
>>> list[5 : 7]    # 切片,第5-6个位置
[5, 6]
>>> list[-2 : ]    # 倒数第二个位置到最后
[8, 9]

函数

• def 自定义函数
• lambda 匿名函数

  1 2 3 4

  ```python >>> sum = lambda arg1, arg2: arg1 + arg2 >>> print ("相加后的值为 : ", sum( 10, 20 )) 相加后的值为 : 30

• functools.partial 函数封装
• functools.wraps 装饰器

python中函数像变量一样,可作为参数传入另一个函数:

列表 / 字典推导式

• 列表推导式可以方便地由a_list生成新的列表b_list
• 字典推导式可以方便地由列表a_list和string.letters生成新的字典b_dict
  

  列表 / 字典解析式

• 使用enumerate可以在遍历时方便地获取列表下标index
• 使用iteritems()迭代器可以方便地遍历字典(key,value),快速又省内存
  

  Flask

  最简单的web app

  1 2 3 4 5 6 7 8 9 10 11

  from flask import Flask app = Flask(__name__) ### 生成一个web app对象 @app.route('/') ### 注册一个url,当请求url+'/'这个网址时,执行hello_world函数 def hello_world(): return 'Hello, World!' if __name__ == '__main__': app.run() ### run(host=None, port=None, debug=None, **options) ### 默认host: 127.0.0.1 ### 默认port: 5000

  调试flask应用

• 设置app.run(debug=True)
• Python打印log,前端页面打印log(开发者模式)
• 本地开发可以使用断点调试

  图书馆管理系统

  
  

  项目文件

接口与逻辑分开设计

• views.py: url接口逻辑
  
• logic.py: 逻辑处理
  
• run.py: 应用发布
  

实践:DashBoard可视化

点击获取项目源码

应用设计

项目文件结构:

python应用发布工具

CI / CD 持续集成,持续部署

1. setup.py打包至pip公共仓库, 通过pip安装 / 卸载
2. github hooks, travis 轻量,适合中小型项目
3. jenkins 较重,适合中大型项目

前端

前端开发三把瑞士军刀:

• HTML 超文本标记语言 HyperText Markup Language
  一种标记语言,用标记标签描述网页(静态网页)
• CSS 层叠样式表 Cascading Style Sheets
  样式定义如何显示HTML元素,大小,形状等
  样式表可内置于HTML文件中,但专业的做法是独立存放
• JS JavaScript
  一种轻量级的高级编程语言
  服务于网页交互,生成动态网页
  同CSS一样,JS可嵌入在HTML文件中,但专业的做法是单独存放

补充

• jQuery
  jQuery是一个轻量级的”写的少，做的多”的JavaScript库。是目前最流行的 JS 框架，而且提供了大量的扩展。jQuery 极大地简化了 JavaScript 编程.
• bootstrap
  Bootstrap来自 Twitter,是基于HTML5和CSS3开发的CSS框架，它在jQuery的基础上进行了更为个性化的完善，形成一套自己独有的网站风格，并兼容大部分jQuery插件,可以方便地使用预定义的各种CSS元素和样式。

• JSP java服务器页面 Java Server Pages
  JSP是为了简化Servlet的工作出现的替代品，Servlet输出HTML非常困难(需要一行一行print)，JSP就是替代Servlet输出HTML的。jsp更注重前端显示，servlet更注重模型和业务逻辑.简单地说,jsp就是在html里面写java代码，servlet就是在java里面写html代码,其实jsp经过容器解释之后就是servlet.
  MVC模式在Web开发中的好处是非常明显，它规避了JSP与Servlet各自的短板，Servlet只负责业务逻辑而不会通过out.append()动态生成HTML代码；JSP中也不会充斥着大量的业务代码。这大大提高了代码的可读性和可维护性。

• Ajax Asynchronous JavaScript + XML
  异步JavaScript和XML,Ajax是一种技术方案，但并不是一种新技术。它依赖现有的CSS/HTML/JavaScript，而其中最核心的依赖是浏览器提供的XMLHttpRequest对象，是这个对象使得浏览器可以发出HTTP请求与接收HTTP响应。实现了在页面不刷新个情况下和服务器进行数据交互。

• Grunt
  是一个前端自动化工具,提高工作效率.Grunt可以帮助你处理需要重复执行的压缩，编译，单元测试，代码检查以及打包发布等任务.

• Node.js
  是一种通过JavaScript语言开发web服务端应用的框架,简单地说就是运行在服务端的 JavaScript。Node.js是一个事件驱动I/O服务端JavaScript环境，基于Google的V8引擎，V8引擎执行Javascript的速度非常快，性能非常好。
  如果你是一个前端程序员，你不懂得像PHP、Python或Ruby等动态编程语言，然后你想创建自己的服务，那么Node.js是一个非常好的选择。当然，如果你是后端程序员，想部署一些高性能的服务，那么学习Node.js也是一个非常好的选择。

简单的例子

显示当前时间,刷新页面更新时间

对应的.html文件

<head>定义了当前网页在浏览器标签栏的标题,编码格式,当前页面css,js资源下载链接
<body>定义了网页中显示的元素
<script>js脚本,定义动态内容,这里每刷新一次更新一次显示时间

调试

chrome –> F12 –> Console
输入

1
2
3

>>> a = document.getElementById("time")
>>> a.textContent = " hello world "
 " hello world "

网页内容会跟着改变

复杂一点的例子

点击开始显示当前实时时间,点击停止时间暂停更新
颜色,布局:居中显示,设置字体颜色

• .html文件
  <head>下新定义了.css和.js文件位置
  <button>新定义了点击事件
  
• .css文件
  id选择器:#id { 属性 }
  
• .js文件
  业务逻辑
  

前后端分离

职责分离,架构分离
前后端分开开发,各自持续集成,分离上线
前后端协作依靠配置文件
注意区别全栈工程师和前后端分离前的web工程师

在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：

1. 行数 m 应当等于给定二叉树的高度。

2. 列数 n 应当总是奇数。

3. 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。

4. 每个未使用的空间应包含一个空的字符串””。

5. 使用相同的规则输出子树。

示例 1:

输入:
1
/
2
输出:
[[“”, “1”, “”],
[“2”, “”, “”]]
示例 2:

输入:
1
/
2 3

4```
输出:
[[“”, “”, “”, “1”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“”, “”, “4”, “”, “”, “”, “”]]
示例 3:

输入:
1
/
2 5
/
3
/
4
输出:
[[“”, “”, “”, “”, “”, “”, “”, “1”, “”, “”, “”, “”, “”, “”, “”]
[“”, “”, “”, “2”, “”, “”, “”, “”, “”, “”, “”, “5”, “”, “”, “”]
[“”, “3”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]
[“4”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]]
注意: 二叉树的高度在范围 [1, 10] 中。

先递归求出树的高度,生成矩阵框架,再递归填充节点值.

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

class Solution {
    List<List<String>> ans = new ArrayList<>();

    public List<List<String>> printTree(TreeNode root) {
        if (root == null) {
            return ans;
        }
        int height = getHeight(root);
        int n = (int) Math.pow(2, height) - 1;
        /** 生成矩阵 */
        for (int i = 0; i < height; i++) {
            ans.add(new ArrayList<>());
            for (int j = 0; j < n; j++) {
                ans.get(i).add("");
            }
        }

        printNode(root, 0, 0, n - 1);

        return ans;
    }

    /**
     * 打印节点
     */
    private void printNode(TreeNode root, int level, int begin, int end) {
        if (root == null) {
            return;
        }
        int index = (begin + end) / 2;
        ans.get(level).set(index, root.val + "");
        printNode(root.left, level + 1, begin, index - 1);
        printNode(root.right, level + 1, index + 1, end);
    }

    /**
     * 树的高度
     */
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.max(leftH, rightH) + 1;
    }


}

原文链接 作者:Draven

虽然我们经常将 Redis 看做一个纯内存的键值存储系统，但是我们也会用到它的持久化功能，RDB 和 AOF 就是 Redis 为我们提供的两种持久化工具，其中 RDB 就是 Redis 的数据快照，我们在这篇文章想要分析 Redis 为什么在对数据进行快照持久化时会需要使用子进程，而不是将内存中的数据结构直接导出到磁盘上进行存储。

概述

在具体分析今天的问题之前，我们首先需要了解 Redis 的持久化存储机制 RDB 究竟是什么，RDB 会每隔一段时间中对 Redis 服务中当下的数据集进行快照，除了 Redis 的配置文件可以对快照的间隔进行设置之外，Redis 客户端还同时提供两个命令来生成 RDB 存储文件，也就是 SAVE 和 BGSAVE，通过命令的名字我们就能猜出这两个命令的区别。

其中 SAVE 命令在执行时会直接阻塞当前的线程，由于 Redis 是 单线程 的，所以 SAVE 命令会直接阻塞来自客户端的所有其他请求，这在很多时候对于需要提供较强可用性保证的 Redis 服务都是无法接受的。

我们往往需要 BGSAVE 命令在后台生成 Redis 全部数据对应的 RDB 文件，当我们使用 BGSAVE 命令时，Redis 会立刻 fork 出一个子进程，子进程会执行『将内存中的数据以 RDB 格式保存到磁盘中』这一过程，而 Redis 服务在 BGSAVE 工作期间仍然可以处理来自客户端的请求。

rdbSaveBackground 就是用来处理在后台将数据保存到磁盘上的函数：

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

int rdbSaveBackground(char *filename, rdbSaveInfo *rsi) {
    pid_t childpid;

    if (hasActiveChildProcess()) return C_ERR;
    ...

    if ((childpid = redisFork()) == 0) {
        int retval;

        /* Child */
        redisSetProcTitle("redis-rdb-bgsave");
        retval = rdbSave(filename,rsi);
        if (retval == C_OK) {
            sendChildCOWInfo(CHILD_INFO_TYPE_RDB, "RDB");
        }
        exitFromChild((retval == C_OK) ? 0 : 1);
    } else {
        /* Parent */
        ...
    }
    ...
}

Redis 服务器会在触发 BGSAVE 时调用 redisFork 函数来创建子进程并调用 rdbSave 在子进程中对数据进行持久化，我们在这里虽然省略了函数中的一些内容，但是整体的结构还是非常清晰的，感兴趣的读者可以在点击上面的链接了解整个函数的实现。

使用 fork 的目的最终一定是为了不阻塞主进程来提升 Redis 服务的可用性，但是到了这里我们其实能够发现两个问题：

1. 为什么 fork 之后的子进程能够获取父进程内存中的数据？
2. fork 函数是否会带来额外的性能开销，这些开销我们怎么样才可以避免？

既然 Redis 选择使用了 fork 的方式来解决快照持久化的问题，那就说明这两个问题已经有了答案，首先 fork 之后的子进程是可以获取父进程内存中的数据的，而 fork 带来的额外性能开销相比阻塞主线程也一定是可以接受的，只有同时具备这两点，Redis 最终才会选择这样的方案。

设计

为了分析上一节提出的两个问题，我们在这里需要了解以下的这些内容，这些内容是 Redis 服务器使用 fork 函数的前提条件，也是最终促使它选择这种实现方式的关键：

1. 通过 fork 生成的父子进程会共享包括内存空间在内的资源；
2. fork 函数并不会带来明显的性能开销，尤其是对内存进行大量的拷贝，它能通过写时拷贝将拷贝内存这一工作推迟到真正需要的时候；

子进程

在计算机编程领域，尤其是 Unix 和类 Unix 系统中，fork 都是一个进程用于创建自己拷贝的操作，它往往都是被操作系统内核实现的系统调用，也是操作系统在 *nix 系统中创建新进程的主要方法。

当程序调用了 fork 方法之后，我们就可以通过 fork 的返回值确定父子进程，以此来执行不同的操作：

• fork 函数返回 0 时，意味着当前进程是子进程；
• fork 函数返回非 0 时，意味着当前进程是父进程，返回值是子进程的 pid；

1
2
3
4
5
6
7

int main() {
    if (fork() == 0) {
        // child process
    } else {
        // parent process
    }
}

在 fork 的 手册 中，我们会发现调用 fork 后的父子进程会运行在不同的内存空间中，当 fork 发生时两者的内存空间有着完全相同的内容，对内存的写入和修改、文件的映射都是独立的，两个进程不会相互影响。

The child process and the parent process run in separate memory spaces. At the time of fork() both memory spaces have the same content. Memory writes, file mappings (mmap(2)), and unmappings (munmap(2)) performed by one of the processes do not affect other.

除此之外，子进程几乎是父进程的完整副本（Exact duplicate），然而这两个进程在以下的一些方面会有较小的区别：

• 子进程用于独立且唯一的进程 ID；
• 子进程的父进程 ID 与父进程 ID 完全相同；
• 子进程不会继承父进程的内存锁；
• 子进程会重新设置进程资源利用率和 CPU 计时器；
• …

最关键的点在于父子进程的内存在 fork 时是完全相同的，在 fork 之后进行写入和修改也不会相互影响，这其实就完美的解决了快照这个场景的问题 —— 只需要某个时间点下内存中的数据，而父进程可以继续对自己的内存进行修改，这既不会被阻塞，也不会影响生成的快照。

写时拷贝

既然父进程和子进程拥有完全相同的内存空间并且两者对内存的写入都不会相互影响，那么是否意味着子进程在 fork 时需要对父进程的内存进行全量的拷贝呢？假设子进程需要对父进程的内存进行拷贝，这对于 Redis 服务来说基本都是灾难性的，尤其是在以下的两个场景中：

1. 内存中存储大量的数据，fork 时拷贝内存空间会消耗大量的时间和资源，会导致程序一段时间的不可用；
2. Redis 占用了 10G 的内存，而物理机或者虚拟机的资源上限只有 16G，在这时我们就无法对 Redis 中的数据进行持久化，也就是说 Redis 对机器上内存资源的最大利用率不能超过 50%；

如果无法解决上面的两个问题，使用 fork 来生成内存镜像的方式也无法真正落地，不是一个工程中真正可以使用的方法。

就算脱离了 Redis 的场景，fork 时全量拷贝内存也是难以接受的，假设我们需要在命令行中执行一个命令，我们需要先通过 fork 创建一个新的进程再通过 exec 来执行程序，fork 拷贝的大量内存空间对于子进程来说可能完全没有任何作用的，但是却引入了巨大的额外开销。

写时拷贝（Copy-on-Write）的出现就是为了解决这一问题，就像我们在这一节开头介绍的，写时拷贝的主要作用就是将拷贝推迟到写操作真正发生时，这也就避免了大量无意义的拷贝操作。在一些早期的 *nix 系统上，系统调用 fork 确实会立刻对父进程的内存空间进行复制，但是在今天的多数系统中，fork 并不会立刻触发这一过程：

在 fork 函数调用时，父进程和子进程会被 Kernel 分配到不同的虚拟内存空间中，所以在两个进程看来它们访问的是不同的内存：

• 在真正访问虚拟内存空间时，Kernel 会将虚拟内存映射到物理内存上，所以父子进程共享了物理上的内存空间；
• 当父进程或者子进程对共享的内存进行修改时，共享的内存才会以页为单位进行拷贝，父进程会保留原有的物理空间，而子进程会使用拷贝后的新物理空间；

在 Redis 服务中，子进程只会读取共享内存中的数据，它并不会执行任何写操作，只有父进程会在写入时才会触发这一机制，而对于大多数的 Redis 服务或者数据库，写请求往往都是远小于读请求的，所以使用 fork 加上写时拷贝这一机制能够带来非常好的性能，也让 BGSAVE 这一操作的实现变得非常简单。

总结

Redis 实现后台快照的方式非常巧妙，通过操作系统提供的 fork 和写时拷贝的特性轻而易举的就实现了这个功能，从这里我们就能看出作者对于操作系统知识的掌握还是非常扎实的，大多人在面对类似的场景时，想到的方法可能就是手动实现类似『写时拷贝』的特性，然而这不仅增加了工作量，还增加了程序出现问题的可能性。

到这里，我们简单总结一下 Redis 为什么在使用 RDB 进行快照时会通过子进程的方式进行实现：

1. 通过 fork 创建的子进程能够获得和父进程完全相同的内存空间，父进程对内存的修改对于子进程是不可见的，两者不会相互影响；
2. 通过 fork 创建子进程时不会立刻触发大量内存的拷贝，内存在被修改时会以页为单位进行拷贝，这也就避免了大量拷贝内存而带来的性能问题；

上述两个原因中，一个为子进程访问父进程提供了支撑，另一个为减少额外开销做了支持，这两者缺一不可，共同成为了 Redis 使用子进程实现快照持久化的原因。到最后，我们还是来看一些比较开放的相关问题，有兴趣的读者可以仔细思考一下下面的问题：

• Nginx 的主进程会在运行时 fork 一组子进程，这些子进程可以分别处理请求，还有哪些服务会使用这一特性？
• 写时拷贝其实是一个比较常见的机制，在 Redis 之外还有哪里会用到它？

如果对文章中的内容有疑问或者想要了解更多软件工程上一些设计决策背后的原因，可以在博客下面留言，作者会及时回复本文相关的疑问并选择其中合适的主题作为后续的内容。

Reference

• Redis Persistence
• Understanding Redis Background Memory Usage
• FAQ · Redis
• Copy-on-write
• rdbSaveBackground · Redis
• Fork (system call)
• Which file in kernel specifies fork(), vfork()… to use sys_clone() system call
• Trying to understand fork() and Copy-on-Write (COW)

原文链接 作者:Java3y

前言

在读《Redis设计与实现》关于哈希表扩容的时候，发现这么一段话：

执行BGSAVE命令或者BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）来优化子进程的使用效率，所以在子进程存在期间，服务器会提高负载因子的阈值，从而避免在子进程存在期间进行哈希表扩展操作，避免不必要的内存写入操作，最大限度地节约内存。

触及到知识的盲区了，于是就去搜了一下copy-on-write写时复制这个技术究竟是怎么样的。发现涉及的东西蛮多的，也挺难读懂的。于是就写下这篇笔记来记录一下我学习copy-on-write的过程。

本文力求简单讲清copy-on-write这个知识点，希望大家看完能有所收获。

一、Linux下的copy-on-write

在说明Linux下的copy-on-write机制前，我们首先要知道两个函数：fork()和exec()。需要注意的是exec()并不是一个特定的函数, 它是一组函数的统称, 它包括了execl()、execlp()、execv()、execle()、execve()、execvp()。

1.1简单来用用fork

首先我们来看一下fork()函数是什么鬼：

fork is an operation whereby a process creates a copy of itself.

fork是类Unix操作系统上创建进程的主要方法。fork用于创建子进程(等同于当前进程的副本)。

• 新的进程要通过老的进程复制自身得到，这就是fork！

如果接触过Linux，我们会知道Linux下init进程是所有进程的爹(相当于Java中的Object对象)

• Linux的进程都通过init进程或init的子进程fork(vfork)出来的。

下面以例子说明一下fork吧：

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

#include <unistd.h>  
#include <stdio.h>  
 
int main ()   
{   
    pid_t fpid; //fpid表示fork函数返回的值  
    int count=0;
	
	// 调用fork，创建出子进程  
    fpid=fork();

	// 所以下面的代码有两个进程执行！
    if (fpid < 0)   
        printf("创建进程失败!/n");   
    else if (fpid == 0) {  
        printf("我是子进程，由父进程fork出来/n");   
        count++;  
    }  
    else {  
        printf("我是父进程/n");   
        count++;  
    }  
    printf("统计结果是: %d/n",count);  
    return 0;  
}

得到的结果输出为：

1
2
3
4
5
6
7

我是子进程，由父进程fork出来

统计结果是: 1

我是父进程

统计结果是: 1

解释一下：

• fork作为一个函数被调用。这个函数会有两次返回，将子进程的PID返回给父进程，0返回给子进程。(如果小于0，则说明创建子进程失败)。
• 再次说明：当前进程调用fork()，会创建一个跟当前进程完全相同的子进程(除了pid)，所以子进程同样是会执行fork()之后的代码。

所以说：

• 父进程在执行if代码块的时候，fpid变量的值是子进程的pid
• 子进程在执行if代码块的时候，fpid变量的值是0

1.2再来看看exec()函数

从上面我们已经知道了fork会创建一个子进程。子进程的是父进程的副本。

exec函数的作用就是：装载一个新的程序（可执行映像）覆盖当前进程内存空间中的映像，从而执行不同的任务。

• exec系列函数在执行时会直接替换掉当前进程的地址空间。

我去画张图来理解一下：

参考资料：

• 程序员必备知识——fork和exec函数详解blog.csdn.net/bad_good_ma…
• linux中fork（）函数详解（原创！！实例讲解）：blog.csdn.net/jason314/ar…
• linux c语言 fork() 和 exec 函数的简介和用法：blog.csdn.net/nvd11/artic…
• Linux下Fork与Exec使用：www.cnblogs.com/hicjiajia/a…
• Linux 系统调用 —— fork()内核源码剖析：blog.csdn.net/chen8927040…

1.3回头来看Linux下的COW是怎么一回事

fork()会产生一个和父进程完全相同的子进程(除了pid)

如果按传统的做法，会直接将父进程的数据拷贝到子进程中，拷贝完之后，父进程和子进程之间的数据段和堆栈是相互独立的。

但是，以我们的使用经验来说：往往子进程都会执行exec()来做自己想要实现的功能。

• 所以，如果按照上面的做法的话，创建子进程时复制过去的数据是没用的(因为子进程执行exec()，原有的数据会被清空)

既然很多时候复制给子进程的数据是无效的，于是就有了Copy On Write这项技术了，原理也很简单：

• fork创建出的子进程，与父进程共享内存空间。也就是说，如果子进程不对内存空间进行写入操作的话，内存空间中的数据并不会复制给子进程，这样创建子进程的速度就很快了！(不用复制，直接引用父进程的物理空间)。
• 并且如果在fork函数返回之后，子进程第一时间exec一个新的可执行映像，那么也不会浪费时间和内存空间了。

另外的表达方式：

在fork之后exec之前两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。

当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间。

如果不是因为exec，内核会给子进程的数据段、堆栈段分配相应的物理空间（至此两者有各自的进程空间，互不影响），而代码段继续共享父进程的物理空间（两者的代码完全相同）。

而如果是因为exec，由于两者执行的代码不同，子进程的代码段也会分配单独的物理空间。

Copy On Write技术实现原理：

fork()之后，kernel把父进程中所有的内存页的权限都设为read-only，然后子进程的地址空间指向父进程。当父子进程都只读内存时，相安无事。当其中某个进程写内存时，CPU硬件检测到内存页是read-only的，于是触发页异常中断（page-fault），陷入kernel的一个中断例程。中断例程中，kernel就会把触发的异常的页复制一份，于是父子进程各自持有独立的一份。

Copy On Write技术好处是什么？

• COW技术可减少分配和复制大量资源时带来的瞬间延时。
• COW技术可减少不必要的资源分配。比如fork进程时，并不是所有的页面都需要复制，父进程的代码段和只读数据段都不被允许修改，所以无需复制。

Copy On Write技术缺点是什么？

• 如果在fork()之后，父子进程都还需要继续进行写操作，那么会产生大量的分页错误(页异常中断page-fault)，这样就得不偿失。

几句话总结Linux的Copy On Write技术：

• fork出的子进程共享父进程的物理空间，当父子进程有内存写入操作时，read-only内存页发生中断，将触发的异常的内存页复制一份(其余的页还是共享父进程的)。
• fork出的子进程功能实现和父进程是一样的。如果有需要，我们会用exec()把当前进程映像替换成新的进程文件，完成自己想要实现的功能。

参考资料：

• Linux进程基础：www.cnblogs.com/vamei/archi…
• Linux写时拷贝技术(copy-on-write)www.cnblogs.com/biyeymyhjob…
• 当你在 Linux 上启动一个进程时会发生什么？zhuanlan.zhihu.com/p/33159508
• Linux fork()所谓的写时复制(COW)到最后还是要先复制再写吗？www.zhihu.com/question/26…
• 写时拷贝（copy－on－write） COW技术blog.csdn.net/u012333003/…
• Copy-On-Write 写时复制原理blog.csdn.net/ppppppppp20…

二、解释一下Redis的COW

基于上面的基础，我们应该已经了解COW这么一项技术了。

下面我来说一下我对《Redis设计与实现》那段话的理解：

• Redis在持久化时，如果是采用BGSAVE命令或者BGREWRITEAOF的方式，那Redis会fork出一个子进程来读取数据，从而写到磁盘中。
• 总体来看，Redis还是读操作比较多。如果子进程存在期间，发生了大量的写操作，那可能就会出现很多的分页错误(页异常中断page-fault)，这样就得耗费不少性能在复制上。
• 而在rehash阶段上，写操作是无法避免的。所以Redis在fork出子进程之后，将负载因子阈值提高，尽量减少写操作，避免不必要的内存写入操作，最大限度地节约内存。

参考资料：

• fork()后copy on write的一些特性：zhoujianshi.github.io/articles/20…后copy on write的一些特性/index.html)
• 写时复制：miao1007.github.io/gitbook/jav…

三、文件系统的COW

下面来看看文件系统中的COW是啥意思：

Copy-on-write在对数据进行修改的时候，不会直接在原来的数据位置上进行操作，而是重新找个位置修改，这样的好处是一旦系统突然断电，重启之后不需要做Fsck。好处就是能保证数据的完整性，掉电的话容易恢复。

• 比如说：要修改数据块A的内容，先把A读出来，写到B块里面去。如果这时候断电了，原来A的内容还在！

参考资料：

• 文件系统中的 copy-on-write 模式有什么具体的好处？www.zhihu.com/question/19…
• 新一代 Linux 文件系统 btrfs 简介:www.ibm.com/developerwo…

最后

最后我们再来看一下写时复制的思想(摘录自维基百科)：

写入时复制（英语：Copy-on-write，简称COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被建立，因此多个调用者只是读取操作时可以共享同一份资源。

至少从本文我们可以总结出：

• Linux通过Copy On Write技术极大地减少了Fork的开销。
• 文件系统通过Copy On Write技术一定程度上保证数据的完整性。

其实在Java里边，也有Copy On Write技术，称为延迟拷贝。

Java中有三种类型的对象拷贝：浅拷贝(Shallow Copy)、深拷贝(Deep Copy)、延迟拷贝(Lazy Copy)。

这部分留到下一篇来说，敬请期待~

参考资料：

• 写时复制，写时拷贝，写时分裂，Copy on write：my.oschina.net/dubenju/blo…
• 不会产奶的COW(Copy-On-Write)www.jianshu.com/p/b2fb2ee5e…

原文链接 作者:Draven

Redis 作为广为人知的内存数据库，在玩具项目和复杂的工业级别项目中都看到它的身影，然而 Redis 却是使用单线程模型进行设计的，这与很多人固有的观念有所冲突，为什么单线程的程序能够抗住每秒几百万的请求量呢？这也是我们今天要讨论的问题之一。

除此之外，Redis 4.0 之后的版本却抛弃了单线程模型这一设计，原本使用单线程运行的 Redis 也开始选择性使用多线程模型，这一看似有些矛盾的设计决策是今天需要讨论的另一个问题。

However with Redis 4.0 we started to make Redis more threaded. For now this is limited to deleting objects in the background, and to blocking commands implemented via Redis modules. For the next releases, the plan is to make Redis more and more threaded.

概述

就像在介绍中说的，这一篇文章想要讨论的两个与 Redis 有关的问题就是：

• 为什么 Redis 在最初的版本中选择单线程模型？
• 为什么 Redis 在 4.0 之后的版本中加入了多线程的支持？

这两个看起来有些矛盾的问题实际上并不冲突，我们会分别阐述对这个看起来完全相反的设计决策作出分析和解释，不过在具体分析它们的设计之前，我们先来看一下不同版本 Redis 顶层的设计：

Redis 作为一个内存服务器，它需要处理很多来自外部的网络请求，它使用 I/O 多路复用机制同时监听多个文件描述符的可读和可写状态，一旦收到网络请求就会在内存中快速处理，由于绝大多数的操作都是纯内存的，所以处理的速度会非常地快。

在 Redis 4.0 之后的版本，情况就有了一些变动，新版的 Redis 服务在执行一些命令时就会使用『主处理线程』之外的其他线程，例如 UNLINK、FLUSHALL ASYNC、FLUSHDB ASYNC 等非阻塞的删除操作。

设计

无论是使用单线程模型还是多线程模型，这两个设计上的决定都是为了更好地提升 Redis 的开发效率、运行性能，想要理解两个看起来矛盾的设计决策，我们首先需要重新梳理做出决定的上下文和大前提，从下面的角度来看，使用单线程模型和多线程模型其实也并不矛盾。

虽然 Redis 在较新的版本中引入了多线程，不过是在部分命令上引入的，其中包括非阻塞的删除操作，在整体的架构设计上，主处理程序还是单线程模型的；由此看来，我们今天想要分析的两个问题可以简化成：

• 为什么 Redis 服务使用单线程模型处理绝大多数的网络请求？
• 为什么 Redis 服务增加了多个非阻塞的删除操作，例如：UNLINK、FLUSHALL ASYNC 和 FLUSHDB ASYNC？

接下来的两个小节将从多个角度分析这两个问题。

单线程模型

Redis 从一开始就选择使用单线程模型处理来自客户端的绝大多数网络请求，这种考虑其实是多方面的，作者分析了相关的资料，发现其中最重要的几个原因如下：

1. 使用单线程模型能带来更好的可维护性，方便开发和调试；
2. 使用单线程模型也能并发的处理客户端的请求；
3. Redis 服务中运行的绝大多数操作的性能瓶颈都不是 CPU；

上述三个原因中的最后一个是最终使用单线程模型的决定性因素，其他的两个原因都是使用单线程模型额外带来的好处，在这里我们会按顺序介绍上述的几个原因。

可维护性

可维护性对于一个项目来说非常重要，如果代码难以调试和测试，问题也经常难以复现，这对于任何一个项目来说都会严重地影响项目的可维护性。多线程模型虽然在某些方面表现优异，但是它却引入了程序执行顺序的不确定性，代码的执行过程不再是串行的，多个线程同时访问的变量如果没有谨慎处理就会带来诡异的问题。

在网络上有一个调侃多线程模型的段子，就很好地展示了多线程模型带来的潜在问题：竞争条件 (race condition) —— 如果计算机中的两个进程（线程同理）同时尝试修改一个共享内存的内容，在没有并发控制的情况下，最终的结果依赖于两个进程的执行顺序和时机，如果发生了并发访问冲突，最后的结果就会是不正确的。

Some people, when confronted with a problem, think, “I know, I’ll use threads,” and then two they hav erpoblesms.

引入了多线程，我们就必须要同时引入并发控制来保证在多个线程同时访问数据时程序行为的正确性，这就需要工程师额外维护并发控制的相关代码，例如，我们会需要在可能被并发读写的变量上增加互斥锁：

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

var (
    mu Mutex // cost
    data int
)

// thread 1
func() {
    mu.Lock()
    data += 1
    mu.Unlock()
}

// thread 2
func() {
    mu.Lock()
    data -= 1
    mu.Unlock()
}

在访问这些变量或者内存之前也需要先对获取互斥锁，一旦忘记获取锁或者忘记释放锁就可能会导致各种诡异的问题，管理相关的并发控制机制也需要付出额外的研发成本和负担。

并发处理

使用单线程模型也并不意味着程序不能并发的处理任务，Redis 虽然使用单线程模型处理用户的请求，但是它却使用 I/O 多路复用机制并发处理来自客户端的多个连接，同时等待多个连接发送的请求。

在 I/O 多路复用模型中，最重要的函数调用就是 select 以及类似函数，该方法的能够同时监控多个文件描述符（也就是客户端的连接）的可读可写情况，当其中的某些文件描述符可读或者可写时，select 方法就会返回可读以及可写的文件描述符个数。

使用 I/O 多路复用技术能够极大地减少系统的开销，系统不再需要额外创建和维护进程和线程来监听来自客户端的大量连接，减少了服务器的开发成本和维护成本。

性能瓶颈

最后要介绍的其实就是 Redis 选择单线程模型的决定性原因 —— 多线程技术能够帮助我们充分利用 CPU 的计算资源来并发的执行不同的任务，但是 CPU 资源往往都不是 Redis 服务器的性能瓶颈。哪怕我们在一个普通的 Linux 服务器上启动 Redis 服务，它也能在 1s 的时间内处理 1,000,000 个用户请求。

It’s not very frequent that CPU becomes your bottleneck with Redis, as usually Redis is either memory or network bound. For instance, using pipelining Redis running on an average Linux system can deliver even 1 million requests per second, so if your application mainly uses O(N) or O(log(N)) commands, it is hardly going to use too much CPU.

如果这种吞吐量不能满足我们的需求，更推荐的做法是使用分片的方式将不同的请求交给不同的 Redis 服务器来处理，而不是在同一个 Redis 服务中引入大量的多线程操作。

简单总结一下，Redis 并不是 CPU 密集型的服务，如果不开启 AOF 备份，所有 Redis 的操作都会在内存中完成不会涉及任何的 I/O 操作，这些数据的读写由于只发生在内存中，所以处理速度是非常快的；整个服务的瓶颈在于网络传输带来的延迟和等待客户端的数据传输，也就是网络 I/O，所以使用多线程模型处理全部的外部请求可能不是一个好的方案。

AOF 是 Redis 的一种持久化机制，它会在每次收到来自客户端的写请求时，将其记录到日志中，每次 Redis 服务器启动时都会重放 AOF 日志构建原始的数据集，保证数据的持久性。

多线程虽然会帮助我们更充分地利用 CPU 资源，但是操作系统上线程的切换也不是免费的，线程切换其实会带来额外的开销，其中包括：

1. 保存线程 1 的执行上下文；
2. 加载线程 2 的执行上下文；

频繁的对线程的上下文进行切换可能还会导致性能地急剧下降，这可能会导致我们不仅没有提升请求处理的平均速度，反而进行了负优化，所以这也是为什么 Redis 对于使用多线程技术非常谨慎。

引入多线程

Redis 在最新的几个版本中加入了一些可以被其他线程异步处理的删除操作，也就是我们在上面提到的 UNLINK、FLUSHALL ASYNC 和 FLUSHDB ASYNC，我们为什么会需要这些删除操作，而它们为什么需要通过多线程的方式异步处理？

删除操作

我们可以在 Redis 在中使用 DEL 命令来删除一个键对应的值，如果待删除的键值对占用了较小的内存空间，那么哪怕是同步地删除这些键值对也不会消耗太多的时间。

但是对于 Redis 中的一些超大键值对，几十 MB 或者几百 MB 的数据并不能在几毫秒的时间内处理完，Redis 可能会需要在释放内存空间上消耗较多的时间，这些操作就会阻塞待处理的任务，影响 Redis 服务处理请求的 PCT99 和可用性。

然而释放内存空间的工作其实可以由后台线程异步进行处理，这也就是 UNLINK 命令的实现原理，它只会将键从元数据中删除，真正的删除操作会在后台异步执行。

总结

Redis 选择使用单线程模型处理客户端的请求主要还是因为 CPU 不是 Redis 服务器的瓶颈，所以使用多线程模型带来的性能提升并不能抵消它带来的开发成本和维护成本，系统的性能瓶颈也主要在网络 I/O 操作上；而 Redis 引入多线程操作也是出于性能上的考虑，对于一些大键值对的删除操作，通过多线程非阻塞地释放内存空间也能减少对 Redis 主线程阻塞的时间，提高执行的效率。

如果对文章中的内容有疑问或者想要了解更多软件工程上一些设计决策背后的原因，可以在博客下面留言，作者会及时回复本文相关的疑问并选择其中合适的主题作为后续的内容。

Reference

• Redis is single threaded. How can I exploit multiple CPU / cores?
• Redis is single-threaded, then how does it do concurrent I/O?
• Why isn’t Redis designed to benefit from multi-threading?
• Concurrency is not parallelism
• The little-known feature of Redis 4.0 that will speed up your applications
• Redis 和 I/O 多路复用
• CPU Scheduling

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ：

输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：

   6
 /   \   
3     5
 \    / 
  2  0   
    \
      1

提示：

给定的数组的大小在 [1, 1000] 之间。

递归建树.

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

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int maxId = getMaxId(nums);
        int max = nums[maxId];
        TreeNode node = new TreeNode(max);
        if (maxId - 1 >= 0) {
            node.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxId));
        } else {
            node.left = null;
        }
        if (maxId + 1 < nums.length) {
            node.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxId + 1, nums.length));
        } else {
            node.right = null;
        }
        return node;
    }

    private int getMaxId(int[] nums) {
        int maxId = 0, max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                maxId = i;
                max = nums[i];
            }
        }
        return maxId;
    }
}

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。

递归遍历:

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

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Solution {
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
            if (t1==null&&t2==null){
                return null;
            }
            if (t1!=null&&t2!=null){
                TreeNode node=new TreeNode(t1.val+t2.val);
                node.left=mergeTrees(t1.left,t2.left);
                node.right=mergeTrees(t1.right,t2.right);
                return node;
            }
            if (t1!=null){
                TreeNode node=new TreeNode(t1.val);
                node.left=mergeTrees(t1.left,null);
                node.right=mergeTrees(t1.right,null);
                return node;
            }else {
//                if (t2!=null)
                TreeNode node=new TreeNode(t2.val);
                node.left=mergeTrees(null,t2.left);
                node.right=mergeTrees(null,t2.right);
                return node;
            }
        }
    }