想必写过 C 的程序员对指针都会有一种复杂的情感，与内存相处的过程中可以说是成也指针，败也指针。一不小心又越界访问了，一不小心又读到了内存里的脏数据，一不小心多线程读写数据又不一致了……我知道讲到这肯定会有人觉得“出这种问题还不是因为你菜”云云，但是有一句话说得好：“自由的代价就是需要时刻保持警惕”。

Rust 几乎把“内存安全”作为了语言设计哲学之首，从多个层面（编译，运行时检查等）极力避免了许多内存安全问题。所以比起让程序员自己处理指针（在 Rust 中可以称之为 Raw Pointer），Rust 提供了几种关于指针的封装类型，称之为智能指针（Smart Pointer），且对于每种智能指针，Rust 都对其做了很多行为上的限制，以保证内存安全。

• Box<T>
• Rc<T> 与 Arc<T>
• Cell<T>
• RefCell<T>

我在刚开始学习智能指针这个概念的时候有非常多的困惑，Rust 官方教程本身对此的叙述并不详尽，加之 Rust 在中文互联网上内容匮乏，我花了很久才搞清楚这几个智能指针封装的异同，在这里总结一下，以供参考，如有错误，烦请大家指正。

以下内容假定本文的读者了解 Rust 的基础语法，所有权以及借用的基本概念，这里是相关链接。

Box<T>

Box<T> 与大多数情况下我们所熟知的指针概念基本一致，它是一段指向堆中数据的指针。我们可以通过这样的操作访问和修改其指向的数据：

let a = Box::new(1);  // Immutable
println!("{}", a);    // Output: 1

let mut b = Box::new(1);  // Mutable
*b += 1;
println!("{}", b);    // Output: 2

然而 Box<T> 的主要特性是单一所有权，即同时只能有一个人拥有对其指向数据的所有权，并且同时只能存在一个可变引用或多个不可变引用，这一点与 Rust 中其他属于堆上的数据行为一致。

let a = Box::new(1);  // Owned by a
let b = a;  // Now owned by b

println!("{}", a);  // Error: value borrowed here after move

let c = &mut a;
let d = &a;

println!("{}, {}", c, d);  // Error: cannot borrow `a` as immutable because it is also borrowed as mutable

Rc<T> 与 Arc<T>

Rc<T> 主要用于同一堆上所分配的数据区域需要有多个只读访问的情况，比起使用 Box<T> 然后创建多个不可变引用的方法更优雅也更直观一些，以及比起单一所有权，Rc<T> 支持多所有权。

Rc 为 Reference Counter 的缩写，即为引用计数，Rust 的 Runtime 会实时记录一个 Rc<T> 当前被引用的次数，并在引用计数归零时对数据进行释放（类似 Python 的 GC 机制）。因为需要维护一个记录 Rc<T> 类型被引用的次数，所以这个实现需要 Runtime Cost。

use std::rc::Rc;

fn main() {
    let a = Rc::new(1);
    println!("count after creating a = {}", Rc::strong_count(&a));
    let b = Rc::clone(&a);
    println!("count after creating b = {}", Rc::strong_count(&a));
    {
        let c = Rc::clone(&a);
        println!("count after creating c = {}", Rc::strong_count(&a));
    }
    println!("count after c goes out of scope = {}", Rc::strong_count(&a));
}

输出依次会是 1 2 3 2。

需要注意的主要有两点。首先， Rc<T> 是完全不可变的，可以将其理解为对同一内存上的数据同时存在的多个只读指针。其次，Rc<T> 是只适用于单线程内的，尽管从概念上讲不同线程间的只读指针是完全安全的，但由于 Rc<T> 没有实现在多个线程间保证计数一致性，所以如果你尝试在多个线程内使用它，会得到这样的错误：

use std::thread;
use std::rc::Rc;

fn main() {
    let a = Rc::new(1);
    thread::spawn(|| {
        let b = Rc::clone(&a);
        // Error: `std::rc::Rc<i32>` cannot be shared between threads safely
    }).join();
}

如果想在不同线程中使用 Rc<T> 的特性该怎么办呢？答案是 Arc<T>，即 Atomic reference counter。此时引用计数就可以在不同线程中安全的被使用了。

use std::thread;
use std::sync::Arc;

fn main() {
    let a = Arc::new(1);
    thread::spawn(move || {
        let b = Arc::clone(&a);
        println!("{}", b);  // Output: 1
    }).join();
}

Cell<T>

Cell<T> 其实和 Box<T> 很像，但后者同时不允许存在多个对其的可变引用，如果我们真的很想做这样的操作，在需要的时候随时改变其内部的数据，而不去考虑 Rust 中的不可变引用约束，就可以使用 Cell<T>。Cell<T> 允许多个共享引用对其内部值进行更改，实现了「内部可变性」。

fn main() {
    let x = Cell::new(1);
    let y = &x;
    let z = &x;
    x.set(2);
    y.set(3);
    z.set(4);
    println!("{}", x.get());  // Output: 4
}

这段看起来非常不 Rust 的 Rust 代码其实是可以通过编译并运行成功的，Cell<T> 的存在看起来似乎打破了 Rust 的设计哲学，但由于仅仅对实现了 Copy 的 T，Cell<T> 才能进行 .get() 和 .set() 操作。而实现了 Copy 的类型在 Rust 中几乎等同于会分配在栈上的数据（可以直接按比特进行连续 n 个长度的复制），所以对其随意进行改写是十分安全的，不会存在堆数据泄露的风险（比如我们不能直接复制一段栈上的指针，因为指针指向的内容可能早已物是人非）。也是得益于 Cell<T> 实现了外部不可变时的内部可变形，可以允许以下行为的发生：

use std::cell::Cell;

fn main() {
    let a = Cell::new(1);
    
    {
        let b = &a;
        b.set(2);
    }

    
    println!("{:?}", a);  // Output: 2
}

如果换做 Box<T>，则在中间出现的 Scope 就会使 a 的所有权被移交，且在执行完毕之后被 Drop。最后还有一点，Cell<T> 只能在单线程的情况下使用。

RefCell<T>

因为 Cell<T> 对 T 的限制：只能作用于实现了 Copy 的类型，所以应用场景依旧有限（安全的代价）。但是我如果就是想让任何一个 T 都可以塞进去该咋整呢？RefCell<T> 去掉了对 T 的限制，但是别忘了要牢记初心，不忘继续践行 Rust 的内存安全的使命，既然不能在读写数据时简单的 Copy 出来进去了，该咋保证内存安全呢？相对于标准情况的静态借用，RefCell<T> 实现了运行时借用，这个借用是临时的，而且 Rust 的 Runtime 也会随时紧盯 RefCell<T> 的借用行为：同时只能有一个可变借用存在，否则直接 Painc。也就是说 RefCell<T> 不会像常规时一样在编译阶段检查引用借用的安全性，而是在程序运行时动态的检查，从而提供在不安全的行为下出现一定的安全场景的可行性。

use std::cell::RefCell;
use std::thread;

fn main() {
    thread::spawn(move || {
       let c = RefCell::new(5);
       let m = c.borrow();
    
       let b = c.borrow_mut();
    }).join();
    // Error: thread '<unnamed>' panicked at 'already borrowed: BorrowMutError'
}

如上程序所示，如同一个读写锁应该存在的情景一样，直接进行读后写是不安全的，所以 borrow 过后 borrow_mut 会导致程序 Panic。同样，ReCell<T> 也只能在单线程中使用。

如果你要实现的代码很难满足 Rust 的编译检查，不妨考虑使用 Cell<T> 或 RefCell<T>，它们在最大程度上以安全的方式给了你些许自由，但别忘了时刻警醒自己自由的代价是什么，也许获得喘息的下一秒，一个可怕的 Panic 就来到了你身边！

组合使用

如果遇到要实现一个同时存在多个不同所有者，但每个所有者又可以随时修改其内容，且这个内容类型 T 没有实现 Copy 的情况该怎么办？使用 Rc<T> 可以满足第一个要求，但是由于其是不可变的，要修改内容并不可能；使用 Cell<T> 直接死在了 T 没有实现 Copy 上；使用 RefCell<T> 由于无法满足多个不同所有者的存在，也无法实施。可以看到各个智能指针可以解决其中一个问题，既然如此，为何我们不把 Rc<T> 与 RefCell<T> 组合起来使用呢？

use std::rc::Rc;
use std::cell::RefCell;

fn main() {
    let shared_vec: Rc<RefCell<_>> = Rc::new(RefCell::new(Vec::new()));
    // Output: []
    println!("{:?}", shared_vec.borrow());
    {
        let b = Rc::clone(&shared_vec);
        b.borrow_mut().push(1);
        b.borrow_mut().push(2);
    }
    shared_vec.borrow_mut().push(3);
    // Output: [1, 2, 3]
    println!("{:?}", shared_vec.borrow());
}

通过 Rc<T> 保证了多所有权，而通过 RefCell<T> 则保证了内部数据的可变性。

参考

1. Wrapper Types in Rust: Choosing Your Guarantees
2. 内部可变性模式
3. 如何理解Rust中的可变与不可变？
4. Rust 常见问题解答

今天面试的时候，面试官问我了一个问题：Python 如何实现单例模式？说起来「单例模式」这个词我倒并不陌生，但从来没有实际的上手实现过，当时只在面试官的提示下写出了伪代码和思路，现在来这复盘，认真看看所有可行的实现方式。

单例模式是一个在软件设计中很常见的概念，即单例模式的类只能至多拥有一个实例。具体的应用场景可以考虑一个服务器中的 logger，且是一个在很多地方我们都会用到的同一个 logger，如果每次调用时我们都实例化一个新的，无疑是对服务器资源的浪费。这时候就可以用到单例模式，将 looger 变成一个无论多少次实例化，都只会拥有一个实例的类。

在 Python 中主要有这三个实现方式：

• 改写 __new__
• 使用装饰器 decorator
• 使用元类 meteclass
• 换个思路：模块

改写 __new__

这是比较符合直觉的一个方法之一，在类生成实例的时候，__init__ 之前首先被调用的是 __new__，所以我们可以在类中引入一个变量来存储第一次实例化过后的实例对象，之后的每一个实例都指向它。

class Logger(object):
    __instance = None    # 用于存储实例对象的类变量
    def __new__(cls, *args, **kwargs):
        if cls.__instance is None:
        # 调用父类的 __new__ 方法
            cls.__instance = super(Logger, cls).__new__(cls, *args, **kwargs)
        return cls.__instance
    
logger_1 = Logger()
logger_2 = Logger()
    
print(logger_1 is logger_2)    # True

使用装饰器 decorator

同样，使用装饰器也是一个比较显而易见的办法（然而面试时却没有想到，呵呵），在装饰器中使用一个私有的字典来存储被装饰类已经实例化的第一个对象。

    from functools import wraps

def singleton(cls):
    __instances = {}
    @wraps(cls)
    def wrapper(*args, **kwargs):
        if cls not in __instances:
            __instances[cls] = cls(*args, **kwargs)
        return __instances[cls]
    return wrapper

@singleton
class Logger(object):
    pass

使用元类 meteclass

类的创建可以由更底层的元类来控制，所以使用元类也可以达到我们的目的，基本思路也跟之前相同。

class Singleton(type):
    __instances = {}
    def __call__(cls, *args, **kwargs):
        if cls not in cls._instances:
            cls._instances[cls] = super(Singleton, cls).__call__(*args, **kwargs)
        return cls._instances[cls]
    
class Logger(metaclass=Singleton):
    pass

换个角度：模块

除了这些比较符合直觉的做法，还有没有什么更巧妙的办法？实际上模块在 Python 的解释运行中就有单例模式的影子。在第一次运行过后，模块的 .py 文件会被解释器生成一份 .pyc 文件，包含了编译过后生成的字节码，以期提高再次运行时的效率，也是如此，我们若是在一个模块中定义了我们的 logger，就可以在一次编译后直接获得一个单例类。

# logger.py
class Logger(object):
    pass

my_logger = Logger()

# mian.py
from logger import my_logger

好久没有写东西了，一是因为自己的服务器到期了没有再续，博客也跑不起来了，二是因为自己现在面对屏幕上跳动的光标，没法像以前一样能讲出大段的话来，平时太多的感悟要么沉在了心底，要么都讲给了能和我一起倾听和讨论的人，至于剩下的，便很难拿到台面上来再写出来了。 今天凌晨看了 Apple 的 WWDC 开幕会，很晚才睡的觉，而且睡得并不好，燥热的空气让人处在半梦半醒的边缘，像被胶水黏住了时间，很迷离也很漫长。我向来是睡觉会做梦的人，很多人说睡觉做梦是睡眠不好，算是不正常，然而对我来说吧，如果一天晚上没有做梦，那才是不正常。

还有不到两个月的时间我就要迎来高三的生活了，对于每一个学生来说，除了即将铺面而来的繁重学习，还会迎接那么一个特殊群体的归来——每年的这个时候都会有许多在外学成归来的隶属于本地的学生，因为籍贯的原因回到这个他们曾经离开过的地方，开始他们在进入大学之前最后一个阶段的学习。这本来没有什么，但是有那么一个人，她同样属于这样一群人的行列，她也即将归来。于我而言，这本没什么关系，但细究，在这无关系之间，又埋藏着曾经奇怪的那么一撇。

昨晚上的梦很奇怪，一个这样一个已经和我近乎没有了交集的人突兀的出现，让我清醒后在思索时有点无所适从。

她是一个活在我记忆里的人，现实中唯一能让我意识到这个人存在的，是偶尔出现在 QQ 空间里那么三言两语的说说；她曾是一个很神奇的人，让我迷失过方向，在她的世界里走失；她也是一个我早已放下的人，我不会跟她再有更多的交集，现在没有，未来也不会有；然而，我也肯定能用我仅有的记忆肯定的描述到：她是一个善良的人。

我很谢谢她。谢谢她能在我即将过去17年的生命里扮演了一个让我的回忆不那么乏味的多彩的人，扮演了一个让我回忆起来能有一丝欣慰笑容的人。如此，我认为她是一个善良的人。

生命之路，我要走过17年了。这17年来，我写了很多字，其中一些在垃圾桶，其中一些在互联网之上，更有一些在心里；拍了不少的照片，其中有肉眼所见的记录，有精神所向往的视角，更有你所见的我眼中的这个世界；认识了很多人，其中一些已经消失在人海，其中一些正陪在我左右并肩而行，更有那么一个人正和我走在精神的共同道路上，我很幸运我能认识那些能陪我走过人生某一段路的人，更幸福有一个愿意和我一直走下去的我爱的也爱我的人。

谢谢那些生活在耿海直过去17年生命里的人，那些生活在我的现在的人和即将陪我一起到我的未来的人儿。

2013年9月21日，我在空间里创建了一个叫“随手拍”的相册，时至今日总共过去了超过两年多，照片数量已经从最开始的0张变成了607张，在一段长长的时间里，能一直坚持做下来的事情不多，这算是其中一件。

从刚开始拍了照片只是简单的加滤镜，到现在每一次拍摄都要从头到尾仔细的观察和思考，镜头中的景物在和我一起成长。在那很久很久以后我才明白一个道理，其实每个人都有一个顶级的照相机——真正在记录景物的其实不是人手中的光学镜片，而是每个人自己的眼睛。我在随手拍的相册简介里写到：

分享生活，留住感动。

上次讲到那天在学校实验楼看到的夕阳，遗憾于没有记录下来。然而那一天物理老师有心的发现我们沉醉于窗外的景色，在我们离去后，用手机把那副景记录了下来。

那一瞬间真的很感动，我所理解的一个摄影师在做的，正是应该是帮人留住景物，让更多的眼睛能够看到摄影师的眼睛看到的景物，这里面有这个世界，也有摄影师的世界。

忘了在哪看到过一句话：“一个人在不断的经历和成长后，真正可贵的，是自始至终都不要失去感受幸福的能力。”可爱的人可是会感受生活，分享生活！

我觉得这就是身为一个摄影者的信仰。

分裂可以说是 Region 生命周期中最为重要的一步，如同细胞一般，分裂是 Region 被创造并持续增多的唯一方式。

本文将介绍以下内容：

• Region Split 是由谁触发的。
• Region Split 是如何计算 Split Key 的。
• Region Split 最终是如何执行的。

我们先来看一个 Region Split 过程的大致流程：

1. TiKV/PD/TiDB 触发 Region Split 事件。
2. Raftstore 处理 Region Split 事件，计算 Split Key。
3. Raftstore 执行 Split。

Region Split 的触发方式

我们可以将 Region 的分裂从动机上分为两类：

• 内部机制导致的 Region 被动分裂（例如 Region 的大小超过阈值，Load Base Split 被触发等）
• 人工手段对 Region 进行主动分裂（建表或手动 Split Region）

TiKV 触发分裂

因为 Region 是 TiKV 的逻辑存储单元，Region 最基本的分裂方式也是来源于 TiKV 的控制。

定期检查

TiKV 默认会 10s 进行一次 Region 的分裂检查，此举由 Raft 状态机驱动，定期 Tick 进行触发。函数名称为 PeerFsmDelegate::on_split_region_check_tick。

因为 Region Split 的行为后续会作为一条 Raft log 在副本间进行同步，所以该函数会首先检查当前 Region peer 是否为 leader，以避免进行无用的检查。

if !self.fsm.peer.is_leader() {
    return;
}

if self.fsm.peer.may_skip_split_check
    && self.fsm.peer.compaction_declined_bytes < self.ctx.cfg.region_split_check_diff().0
    && self.fsm.peer.size_diff_hint < self.ctx.cfg.region_split_check_diff().0
{
    return;
}

紧接着 Leader check 之后，就是对 Split 必要性的检查，为了避免过多的 Split check，我们设置了以下 3 个条件来进行过滤：

• Region peer 的 may_skip_split_check flag 是否为 True
• Region peer 的 compaction_declined_bytes 是否小于 region-split-check-diff 阈值
• Region peer 的 size_diff_hint 是否小于 region-split-check-diff 阈值

may_skip_split_check 的 flag 会在必要时被设置为 False 来确保 Split 检查会尽可能地被执行（例如 TiKV 刚刚启动时）。compaction_declined_bytes 和 size_diff_hint 均是对 Region 大小变化的增量统计（分别统计自 Compaction 数据和 Apply 数据的过程），它们在此隐含了这样一个条件：只有 Region 的大小变化超过 region-split-check-diff 后才需要进行分裂检查（这个配置的默认值是 region-split-size 的 1/16，即 96 / 16 = 6 MB）。

而后就是一些特殊逻辑的检查，在此不进一步展开，他们包括：

• 当前是否有堆积未完成的 Split 任务
• 当前是否处于 Lightning/BR 的导入过程中
• 当前是否正在生成 Snapshot

需要注意此阶段的检查仅仅是触发了 Region Split 的事件，具体能否分裂以及如何分裂还取决于后续的 Split 触发过程。

Load Base Split

TiKV 还有一个会触发 Region Split 的功能来自于 Load Base Split。其核心代码位于 AutoSplitController::flush。StatsMonitor 会收集读请求的统计信息，包括请求的数目，请求读取的流量以及读取的 Key Range 等。对于 QPS 或 Byte 满足 qps_threshold 和 byte_threshold 的 Region，则会在之前收集的 Key Range 基础上对 Key 进行采样，选择一个切分后左右 Region 上的请求数量最为均衡的 Key 作为切分点进行切分。

PD 触发分裂

PD 也可以进行分裂的触发。此举可以通过以下方式进行：

• 调用 /regions/split 的 HTTP API 触发
• 通过 pd-ctl 创建 Operator 触发
• 通过调用 gRPC 接口 SplitRegions/SplitAndScatterRegions 来触发

其中，pd-ctl 作为主要面向用户的操作，方式如下：

>> operator add split-region 1 --policy=approximate     // 将 Region 1 对半拆分成两个 Region，基于粗略估计值
>> operator add split-region 1 --policy=scan            // 将 Region 1 对半拆分成两个 Region，基于精确扫描值

上述操作的本质都是创建一个 Split 的 Operator 并下发给对应 Region。具体的 PD 侧代码可以通过 RegionSplitter::SplitRegions 函数进行自上而下的研究，在此不多做表述。

Operator 通过 Region 心跳下发给 TiKV 后，TiKV 会根据下发的 Split 任务类型去创建对应的事件，具体代码在此。

if resp.has_split_region() {
    let mut split_region = resp.take_split_region();
    info!("try to split"; "region_id" => region_id, "region_epoch" => ?epoch);
    let msg = if split_region.get_policy() == pdpb::CheckPolicy::Usekey {
        CasualMessage::SplitRegion {
            region_epoch: epoch,
            split_keys: split_region.take_keys().into(),
            callback: Callback::None,
            source: "pd".into(),
        }
    } else {
        CasualMessage::HalfSplitRegion {
            region_epoch: epoch,
            policy: split_region.get_policy(),
            source: "pd",
            cb: Callback::None,
        }
    };
    if let Err(e) = router.send(region_id, PeerMsg::CasualMessage(msg)) {
        error!("send halfsplit request failed"; "region_id" => region_id, "err" => ?e);
    }
}

可以看到根据不同的 Split 方式，所创建的事件也不同——若是给定了分裂点 Key 则会直接下发 CasualMessage::SplitRegion 事件，否则根据不同的分裂策略创建一个 CasualMessage::HalfSplitRegion 事件，期以对 Region 进行对半分。这里的策略主要分为 Scan 和 Approximate 两类，具体的区别会在后文中进行介绍。

TiDB 触发分裂

DDL

在建表或添加分区时，TiDB 会在 DDL 阶段对表的 Region 进行预切分，为每个表或分区创建单独的 Region，用于避免发生大量建表和写入造成的热点问题。此举也是通过调用 PD 的 Split 接口达成的（早期版本是 TiDB 直接下发给 TiKV，现已废弃）。具体的代码入口在 ddl::preSplitAndScatter 接口，你可以通过该方法的调用情况来看不同的 Split Table 发生在何时何处。

SQL

除了建表时自动为每个表切分出的一个 Region，如果在单表内部存在写入热点，我们也可以通过 SQL 来手动 Split Region。这个原理其实和上述的 DDL 过程相同，均是调用统一的 SplitRegions 接口来进行 Split 任务的下发。

具体的 SQL 语法可以参考官方文档：Split Region 使用文档。

其他

上面只阐述了 3 大组件的常见 Region Split 触发流程，事实上还有很多其他机制会触发 Region Split，例如 Lightning/BR 这样的工具导入数据前也会对 Region 进行预切分和打散，以求导入后数据的均衡。tikv-ctl 也可以触发 Region 的 Split。

Region Split Key 的计算方式

以上述方式触发 Region Split 事件后，具体的 Split 的 Key 可以以多种方式和维度被计算出来。例如通过精确的 Scan 扫描来确定 Region 大小上的中点进行分裂，或通过指定的 Key 直接进行分裂等，不同的方式往往用于不同的场景，具体原理如下。

Coprocessor

此 Coprocessor 非 TiKV 中用于下推 SQL 执行的 Coprocessor，而是 raftstore 代码中的一个概念。其主要作用相当于外挂在 TiKV 的 Raft 层上的一个协处理工具集合，用于观测和处理与 Raft 相关的周边事件。SplitChecker 就是其中之一，用于接受，处理和下发与 Region Split 有关的事件。

/// SplitChecker is invoked during a split check scan, and decides to use
/// which keys to split a region.
pub trait SplitChecker<E> {
    /// Hook to call for every kv scanned during split.
    ///
    /// Return true to abort scan early.
    fn on_kv(&mut self, _: &mut ObserverContext<'_>, _: &KeyEntry) -> bool {
        false
    }

    /// Get the desired split keys.
    fn split_keys(&mut self) -> Vec<Vec<u8>>;

    /// Get approximate split keys without scan.
    fn approximate_split_keys(&mut self, _: &Region, _: &E) -> Result<Vec<Vec<u8>>> {
        Ok(vec![])
    }

    /// Get split policy.
    fn policy(&self) -> CheckPolicy;
}

一个 SplitChecker 包含 4 个方法，分别是：

• on_kv，在使用 Scan 方式时，用于在 Iterator 扫描 Key 的过程中接受 Key，并在内部维护对应的状态来实现不同的分裂方式。
• split_keys，在完成扫描后通过此方法来拿到最终的 Split Key 结果。
• approximate_split_keys，在使用 Approximate 方式时，不进行 Scan 而直接拿到 Split Key 结果
• policy，返回当前的 Split 检查策略，有 Scan/Approximate 两种方式。

对这 4 个方法不同的实现也就决定了不同的分裂方式，下面我们分别介绍 TiKV 内部支持的所有不同的分裂方式。

Half

HalfCheckObserver 实现了对 Region 的 Sizie 对半切策略，在 Scan 模式下，为了找到一个 Region 内 Size 维度上的中点，把所有的 Key 都记录下来显然是不合理的，这样可能会占用大量的内存。取而代之的方式是根据配置计算出一个最小的 Size 单位 n MB，计算函数名为 half_split_bucket_size 通过将 region_max_size 除以 BUCKET_NUMBER_LIMIT（常量，值为 1024），计算出一个 Bucket 大小，最小为 1 MB，最大为 512 MB。

fn half_split_bucket_size(region_max_size: u64) -> u64 {
    let mut half_split_bucket_size = region_max_size / BUCKET_NUMBER_LIMIT as u64;
    let bucket_size_limit = ReadableSize::mb(BUCKET_SIZE_LIMIT_MB).0;
    if half_split_bucket_size == 0 {
        half_split_bucket_size = 1;
    } else if half_split_bucket_size > bucket_size_limit {
        half_split_bucket_size = bucket_size_limit;
    }
    half_split_bucket_size
}

在后续的扫描过程中，仅在每扫描过 n MB 大小后才记录下当前的 Key，这样可以通过牺牲一定的精度换来了较少的内存占用。

fn on_kv(&mut self, _: &mut ObserverContext<'_>, entry: &KeyEntry) -> bool {
    if self.buckets.is_empty() || self.cur_bucket_size >= self.each_bucket_size {
        self.buckets.push(entry.key().to_vec());
        self.cur_bucket_size = 0;
    }
    self.cur_bucket_size += entry.entry_size() as u64;
    false
}

fn split_keys(&mut self) -> Vec<Vec<u8>> {
    let mid = self.buckets.len() / 2;
    if mid == 0 {
        vec![]
    } else {
        let data_key = self.buckets.swap_remove(mid);
        let key = keys::origin_key(&data_key).to_vec();
        vec![key]
    }
}

在后续计算中点 Key 的过程中，也只需要取我们收集到的 Key 的中间元素，即可获得近似的 Region Size 中点，用于后续的切分。

对于具体 approximate_split_keys 的实现取决于不同的 KV Engine，以默认的 RocksDB 为例，为了避免对整个区间上全 Key-Value 的扫描，我们使用了 RocksDB 的 TableProperties 特性，来在 RocksDB 构建每个 SST 文件的时候就提前收集一些 Key 相关的信息，从而可以在此时避免进行 I/O 操作即可获得近似的 Key Range 上的 Key 信息，再辅之以采样等手段，相较于 Scan 策略会更不精准，但省去了不少资源。对应的代码在 RocksEngine::get_range_approximate_split_keys_cf 方法中。

Size

SizeCheckObserver 实现了根据 Region Size 切分 Region 的策略。其逻辑相对简单，在默认配置下，会对 Region 的 KV 进行 Scan 遍历，每扫描过 96 MB 的数据便会记录下当前的 Key，一次最多记录 10 个。

fn on_kv(&mut self, _: &mut ObserverContext<'_>, entry: &KeyEntry) -> bool {
    let size = entry.entry_size() as u64;
    self.current_size += size;

    let mut over_limit = self.split_keys.len() as u64 >= self.batch_split_limit;
    if self.current_size > self.split_size && !over_limit {
        self.split_keys.push(keys::origin_key(entry.key()).to_vec());
        // if for previous on_kv() self.current_size == self.split_size,
        // the split key would be pushed this time, but the entry size for this time should not be ignored.
        self.current_size = if self.current_size - size == self.split_size {
            size
        } else {
            0
        };
        over_limit = self.split_keys.len() as u64 >= self.batch_split_limit;
    }

    // For a large region, scan over the range maybe cost too much time,
    // so limit the number of produced split_key for one batch.
    // Also need to scan over self.max_size for last part.
    over_limit && self.current_size + self.split_size >= self.max_size
}

fn split_keys(&mut self) -> Vec<Vec<u8>> {
    // make sure not to split when less than max_size for last part
    if self.current_size + self.split_size < self.max_size {
        self.split_keys.pop();
    }
    if !self.split_keys.is_empty() {
        std::mem::take(&mut self.split_keys)
    } else {
        vec![]
    }
}

approximate_split_keys 的实现和 Half 类似，在此不表，依然是基于 RocksDB 的 TableProperties 功能。

Keys

KeysCheckObserver 实现了根据 Region Key 数量切分 Region 的策略，其原理和 SizeCheckObserver 相同，只不过把计算方式改成了 Key 数量的统计，在此不过多展开，

Tabel

TableCheckObserver 实现了根据 Region 范围内 Key 所属的 Table 进行切分的策略。这个 Checker 的实现比较特殊，它在 TiKV 内部引入了 SQL 层的概念。原理也比较简单，在 Scan 时去 Decode 每个 Key，检查其所属的表 ID 和之前 Key 是否相同，若不同则加入 Split Key 进行分裂。

/// Feed keys in order to find the split key.
/// If `current_data_key` does not belong to `status.first_encoded_table_prefix`.
/// it returns the encoded table prefix of `current_data_key`.
fn on_kv(&mut self, _: &mut ObserverContext<'_>, entry: &KeyEntry) -> bool {
    if self.split_key.is_some() {
        return true;
    }

    let current_encoded_key = keys::origin_key(entry.key());

    let split_key = if self.first_encoded_table_prefix.is_some() {
        if !is_same_table(
            self.first_encoded_table_prefix.as_ref().unwrap(),
            current_encoded_key,
        ) {
            // Different tables.
            Some(current_encoded_key)
        } else {
            None
        }
    } else if is_table_key(current_encoded_key) {
        // Now we meet the very first table key of this region.
        Some(current_encoded_key)
    } else {
        None
    };
    self.split_key = split_key.and_then(to_encoded_table_prefix);
    self.split_key.is_some()
}

由于工作原理决定了它只能基于 Scan 策略进行工作，所以没有提供 approximate_split_keys 方法的实现。

优先级

上面一共介绍了 TiKV 支持的 4 种 Split 方式，那么具体工作过程中，实际到底哪一个方式会被触发呢？答案是都有可能。

每个 SplitChecker 都会被加入到一个 SplitCheckerHost 中，并被赋予不同的优先级，每次 Split 都会依次“询问”每个 SplitChecker 的“意见”，如果高优先级的 Checker 不能给出 Split Key 那么就依次向更低优先级的 Checker 轮训，直到得到一个 Split Key 或确认无法 Split。优先级在将 SplitChecker 注册到 Coprocessor 时就被定义好了，代码位于 CoprocessorHost::new。

pub fn new<C: CasualRouter<E> + Clone + Send + 'static>(
    ch: C,
    cfg: Config,
) -> CoprocessorHost<E> {
    let mut registry = Registry::default();
    registry.register_split_check_observer(
        200,
        BoxSplitCheckObserver::new(SizeCheckObserver::new(ch.clone())),
    );
    registry.register_split_check_observer(
        200,
        BoxSplitCheckObserver::new(KeysCheckObserver::new(ch)),
    );
    registry.register_split_check_observer(100, BoxSplitCheckObserver::new(HalfCheckObserver));
    registry.register_split_check_observer(
        400,
        BoxSplitCheckObserver::new(TableCheckObserver::default()),
    );
    CoprocessorHost { registry, cfg }
}

可以看到 HalfCheckObserver 有最高优先级，其次是 SizeCheckObserver 和 KeysCheckObserver，TableCheckObserver 最低。但是我们所见到的大多数 Region 分裂都是基于 Size 的，Half 分裂尽管有最高优先级，为什么不会被频繁触发呢？答案是我们每次基于注册在 Coprocessor 的 Split Checker 创建 SplitCheckerHost 时（代码入口在 CoprocessorHost::new_split_checker_host），并不会将所有的 Checker 都导入，而是根据不同的配置以及场景进行有选择的添加。例如只有 auto_split 选项设置为关闭时，HalfCheckObserver 才会被添加到 Host 中，这个选项在 TiKV 定时检查触发 Split 时会开启，所以在对应场景下 HalfCheckObserver 不会起作用。

#[derive(Clone)]
pub struct HalfCheckObserver;

impl Coprocessor for HalfCheckObserver {}

impl<E> SplitCheckObserver<E> for HalfCheckObserver
where
    E: KvEngine,
{
    fn add_checker(
        &self,
        _: &mut ObserverContext<'_>,
        host: &mut Host<'_, E>,
        _: &E,
        policy: CheckPolicy,
    ) {
        if host.auto_split() {
            return;
        }
        host.add_checker(Box::new(Checker::new(
            half_split_bucket_size(host.cfg.region_max_size().0),
            policy,
        )))
    }
}

再例如只有当 split_region_on_table 配置开启时，TableCheckObserver 才会被添加到 Host 中，该配置默认关闭。

#[derive(Default, Clone)]
pub struct TableCheckObserver;

impl Coprocessor for TableCheckObserver {}

impl<E> SplitCheckObserver<E> for TableCheckObserver
where
    E: KvEngine,
{
    fn add_checker(
        &self,
        ctx: &mut ObserverContext<'_>,
        host: &mut Host<'_, E>,
        engine: &E,
        policy: CheckPolicy,
    ) {
        if !host.cfg.split_region_on_table {
            return;
        }
        ...
}

所以说在大多数情况下，只有 KeysCheckObserver 和 SizeCheckObserver 主导 Region 的分裂方式。

Region Split 的执行过程

通过 Raftstore 的 Coprocessor 确定好 Region 的 Split Key 后，最后就来到了 Split 的执行阶段。Region 的 Split 任务会被下发到具体的 Region，继而触发 PeerFsmDelegate::on_prepare_split_region 函数，正式开启 Region 的 Split 执行。

Pre-check

首先 TiKV 会再次确认当前 Region 为 leader，并检查 Epoch 等属性是否发生了变化，Epoch 内的 Version 属性只有在完成 Split 或 Merge 的情况下才会增加，因为 Version 一定是严格单调递增的，所以 PD 使用了这个规则去判断范围重叠的不同 Region 的新旧。在检查通过后，便向 PD 发送 AskBatchSplit 请求为即将分裂出来的新 Region 获取 Region ID，并触发 Raft 开始进行 Split log 的 Proposal。

info!(
    "try to batch split region";
    "region_id" => region.get_id(),
    "new_region_ids" => ?resp.get_ids(),
    "region" => ?region,
    "task" => task,
);

let req = new_batch_split_region_request(
    split_keys,
    resp.take_ids().into(),
    right_derive,
);
let region_id = region.get_id();
let epoch = region.take_region_epoch();
send_admin_request(
    &router,
    region_id,
    epoch,
    peer,
    req,
    callback,
    Default::default(),
);

Raft Proposal & Apply

通过 Raft log 将 Split 同步到各个 Peer 之上完成 Commit 之后，ApplyDelegate::exec_batch_split 便开始执行 Region 的分裂。创建新 Region，更改 Region 边界，并将 Region 的新信息写入落盘。

 for new_region in &regions {
    if new_region.get_id() == derived.get_id() {
        continue;
    }
    let new_split_peer = new_split_regions.get(&new_region.get_id()).unwrap();
    if let Some(ref r) = new_split_peer.result {
        warn!(
            "new region from splitting already exists";
            "new_region_id" => new_region.get_id(),
            "new_peer_id" => new_split_peer.peer_id,
            "reason" => r,
            "region_id" => self.region_id(),
            "peer_id" => self.id(),
        );
        continue;
    }
    write_peer_state(kv_wb_mut, new_region, PeerState::Normal, None)
        .and_then(|_| write_initial_apply_state(kv_wb_mut, new_region.get_id()))
        .unwrap_or_else(|e| {
            panic!(
                "{} fails to save split region {:?}: {:?}",
                self.tag, new_region, e
            )
        });
}
write_peer_state(kv_wb_mut, &derived, PeerState::Normal, None).unwrap_or_else(|e| {
    panic!("{} fails to update region {:?}: {:?}", self.tag, derived, e)
});

在默认的分裂方式下，原 Region 要分裂到右侧，举例而言，假设分裂前的 Region 数量一共有 2 个，ID 分别为 1 和 2。2 是即将要分裂的 Region，且 Split Key 为 "b"。

Region 1 ["", "a"), Region 2 ["a", "")

分裂后的新 Region 被分配了 ID 3，那么分裂后的 Region 会形如：

Region 1 ["", "a"), Region 3 ["a", "b"), Region 2 ["b", "")

在 TiKV 完成 Split log 的 Apply 后，会通过 ApplyResult::Res 事件触发 PeerFsmDelegate::on_ready_split_region 来完成 Split 的预后工作。如果当前 Region 是 leader，则会给 PD 发送一个 Report(Batch)Split 的 RPC 请求，仅供 PD 打个日志记录，方便我们在查问题时通过 PD 的日志看到各个 Region 的 Split 记录。由于 Region 的 ID 分配也是严格保证单调递增，所以我们可以说 Region ID 越大的 Region 则越新。

if is_leader {
    self.fsm.peer.approximate_size = estimated_size;
    self.fsm.peer.approximate_keys = estimated_keys;
    self.fsm.peer.heartbeat_pd(self.ctx);
    // Notify pd immediately to let it update the region meta.
    info!(
        "notify pd with split";
        "region_id" => self.fsm.region_id(),
        "peer_id" => self.fsm.peer_id(),
        "split_count" => regions.len(),
    );
    // Now pd only uses ReportBatchSplit for history operation show,
    // so we send it independently here.
    let task = PdTask::ReportBatchSplit {
        regions: regions.to_vec(),
    };
    if let Err(e) = self.ctx.pd_scheduler.schedule(task) {
        error!(
            "failed to notify pd";
            "region_id" => self.fsm.region_id(),
            "peer_id" => self.fsm.peer_id(),
            "err" => %e,
        );
    }
}

其余则是一些向 PD 上报心跳，统计信息的初始化工作，更新分裂后的 Region epoch 并在 Raft group 中注册 Region 的路由。这些工作完成后，当前 TiKV 上的 Region 可以说是已经完成分裂了。

Raft Election

对于分裂前的原 Region 是 Leader 的 Peer 来说，分裂后的 Region 是可以立马发起选举的，而对于原 Region 非 Leader 的 Peer 来说，它分裂创建出的新 Region 是不能立马发起选举的，而是需要等待一个 Raft 的选举超时时间。这样实现的原因是存在下列的 Case：

1. 假设有一个 3 副本的 Region
2. Split 的 Log 已经复制到了所有的 Follower 上
3. 所有的 Follower 完成了 Region Split Log 的 Apply，完成了分裂
4. Region 的 Leader 还没有开始或完成分裂

如果允许原 Peer 非 Leader 的新 Region 分裂出来后立马开始选举，则会出现同一个数据范围内存在两个 Region leader 对外提供服务，一个是分裂后的新的更小的 Region leader，一个是尚未分裂的原 Region leader（Lease 尚未过期），这样一来就存在破坏线性一致性的可能。由于一次 Raft 的选举超时时间要大于 Leader 的 Lease 时间，所以只要我们保证以下两点：

1. 完成分裂的 Region 等待一个 Raft 的选举超时时间再开始选举
2. 需要 Split 的 Region 不再续约 Lease

所以当新分裂的 Region 开始选举时，旧的 Region leader 早些时候一定会因为发现自身的 Epoch 与其余两个 Follower 不同而选举失败完成退选。

踩坑经验

Split Key 的格式为 Encoded Key without TS

在 TiDB 和 TiKV 的语境下，当我们说到 Key 编码时，它可能指的是以下几种情况：

• Raw Key
• Encoded Key without TS
• Encoded Key with TS

TiDB 在发送请求时使用的是 Raw Key，也即不带任何与 MVCC 相关的信息，也没有 Padding，只包括诸如 TableID，RowID 等基本信息。

TiKV 的 Raftstore 以及 PD 在处理诸如 Region 边界，Split 等 Key 时使用的是 Encoded Key without TS，它在 Raw Key 的基础上进行了 Encode，添加了用于保持字典序的 Padding，但由于此层尚未涉及到具体的事务，所以并没有 TS 参与其中。

TiKV 在实际读写底层 RocksDB 数据时，会将请求的 TS 一并 Encode 到 Key 里来区分 MVCC 信息，所以这一层使用的是 Encoded Key with TS。

Region Split 发生在 Raftstore 这一层，所以其格式均为 Encoded Key without TS，在开发相关功能时，要注意对 Key 进行 Encode，并且剔除 TS 信息，以免出现一些预期外的行为。

参考

• TiKV 源码解析系列文章（二十）Region Split 源码解析
• TiKV 源码解析系列文章(十九) read index 和 local read 情景分析 | PingCAP
• TiKV 源码解析系列文章(十八) Raft Propose 的 Commit 和 Apply 情景分析 | PingCAP
• Deep Dive TiKV
• Region 的一生
• Tipedia • Memory Comparable Encoding

在开始之前，我想先念叨几句。

《开端》这部剧其实我很早就关注了，起因是我女朋友是白敬亭的粉丝，所以对他的动向一直有所关注，去年底看到豆瓣条目，彼时的《开端》还是 20 集的长度。后来随着杀青和一系列制作的完成，最终成片为 15 集，单集片长 40 分钟。最初看到这个剧集长度我其实是满意的，毕竟从剧情概要上看也是所谓的“源代码”式国产“无限流”，难免会有场景时空重复，缩短剧集长度其实是一个明智之举，但这也对剧本，对导演来说是一个考验。

对于拍摄剧集，甚至说拍摄电影和拍摄短片来说，叙事节奏其实是比剧情本身更重要，更为考验导演功底的存在，小学语文老师针对写作文常说的一句话就是“详略得当”，如何把控好故事的节奏，在视听语言上做到“详略得当”是影视作品最后的成品能否做到有质感的第一要义。

其次便是人物，事件需要人物的参与和推动。舞台成型，作者退居幕后，角色来到台前。此时故事成品能否做到有质感的第二要义是故事能否仅由角色在舞台框架下的所思所想和所言所行来向前发展，而无需作者从幕后“现形”进行干预。后者在现实中的例子可以是各种剧作上巧合的引入，或是突然抛出的未知剧情，亦或是“机械降神”等强烈出格的手段。

在做好了这两点基础，也即节奏和人物之后，能进一步提升作品质感的，便是冲突的设置。冲突是影视作品中非常核心的一个概念，当一群角色因为不同的理念利益聚集到一起时，冲突的产生，爆发以及解决便是剧情与情感的多个释放点，能否牵动观众，打动观众甚至冒犯观众都会基于此而来。录像带之于《隐秘的角落》，江阳的死之于《沉默的真相》，爆炸案之于《开端》都是剧情的核心冲突点，其他冲突的发展与变化往往都来自于它们。能否处理好，引爆好或是解决这些冲突，也是剧作的功力所在。

那么《开端》在剧作上有些什么瑕疵呢？首先是叙事节奏，前十集把大量的篇幅花费在了男女主通过循环反复尝试和试探凶手上——剧情上这是合理的，但对于上帝视角的观众来说，其中许多情节其实是显而易见的，例如二次元小哥和瓜农大叔，可以很轻易地通过剧作套路和画面信息被观众排除，导演没有选择利用这一点进行一些反套路的设定（例如让前期一些被观众忽略的角色在中后部发挥至关重要的剧情扭转作用，达到出乎意料的效果），而是选择了“顺水推舟”让大量的剧情正中观众下怀，毫不意外的展开很容易让观众失去耐心。其中我比较印象深刻的几集都不是公交车上的动作戏或是警局里的对峙戏，反而是对二次元小哥，西瓜大叔以及见义勇为大叔在戏外人物形象的描写，很能牵动我，更容易让观众完成从一车素不相识的乘客到最后每一位都是鲜活人生写照的认知转变。

说到这就来到了第二部分，人物。如前所言，对公交车上其他乘客进行车外故事描写的部分我很喜欢，但同样的一个问题是，导演没有利用好这些人物的背景故事、动机和观众对他们的感情基础。这里面较为出彩人物设置其实是见义勇为大叔，通过他的背景故事埋下了“消防安全检查提前”的伏笔，以及通过爆炸后警方对其的调查引出了凶手所在地（港务新村），最后在阻止爆炸的过程中也是他发挥了比二次元小哥更直接的作用，而且他朴实的“见义勇为可以拿钱补贴家用”的动机也更纯粹，相比较二次元小哥能被叫出中二名就愿意帮忙来说，更能让观众理解与共情。事实上整部剧结束后我们能看到的，车上乘客在终局中扮演的作用无非只有一个——协助男女主阻止爆炸的工具人。说到这就引出了另外一个问题，如何更好地利用这些人物生平与形象？这里的答案我相信是仁者见仁，智者见智。我的一个想法是也许可以从“爆炸后的人生”这一点入手，首先不能把车上乘客的经历在大结局之前简单的设置成要么被炸死，要么就没有后续。刚出狱的爸爸因身陷爆炸案嫌疑而被影响父子关系，无家可归的父亲身无分文继续在城市中流浪，卢笛因险些“被”献出心脏而被母亲发现秘密基地最终导致猫猫全部被扔……这些更立体的人物困境其实要比死亡更能牵动观众的心，男女主若是能因为目睹到这些而进一步坚定走向 HE 的信念和决心，似乎要比救人一命更有戏剧上的说服力。无奈在当前的循环设定上来看，因为只有从爆炸到睡着的半天时间这些似乎也很难展开。

“循环”这个设定，其实也是《开端》做的好也不好的地方。好在哪里呢？它更像是一种剧情道具，或者说一种情景实验：假设男女主身处于这样一种循环下，面对循环和爆炸他们会怎样反应，怎样行动。这也是这部剧直接的看点来源；不好在哪里？它本应该和爆炸一起是本作中核心的冲突来源，循环因何而起？怎样才能脱离循环？循环的原理是什么？这些问题统统没有解释，也没有看到一丝深入的打算。不过我更愿意相信这是有更深层次的难言之隐，毕竟如果不想突兀地引入科幻元素，考虑神秘主义在审查上会遇到的问题，似乎很难找到一种合适的框架去解释这一切，所以我认为回避这一点其实是制作中的有意为之。对于之前网络上各种双循环的剧情猜测，我觉得也是不错的一个思路，但最终结局选择了更为保守和平稳的女性保护社会议题，中间穿插了一些对网络暴力的反思，这也是一种立意的升华和加分项。

不吐不快，一口气写了这么多，本来还有很多点要吐槽，诸如凶手夫妇的实际作案动机变化过渡，最后一次循环的处理等等……但现在回看 15 集 40 分钟的片长似乎给谁拍都不够用啊，最开始的 20 集好像也挺合适，那就这样吧，毕竟可能被喷“你行你上啊”所以暂且写到这，就目前的成片来看 8.2 分还是过高了，不过作为国产中该类型剧的第一次，以资鼓励还是应该的。只希望以后限制越来越少，创作越来越多，让观众多一些不一样的题材和故事去选择。

众所周知，国内互联网大厂的面试流程一般都比较公开透明，网上也会有不少所谓的面试经验分享，其形式内容基本大同小异，会谈及诸如有几面，每一面都问了哪些问题，做了什么笔试题云云。刨去一些跟每个面试者个人相关的项目问题，剩下的大多都是都是一些通用知识考察，比如操作系统，计算机网络，数据库等。面试者与被面试者往往都是科班出身，要说这些问题的难度也不过尔尔，只要有过系统性的学习，也基本都能从容应对。不过计算机领域之广袤，知识的广度和深度都非常可观，想要面面俱到，也并非易事，但作为企业，面试官总归是想要招到能力更强更好的全才，所以面试前的准备功课不可或缺。但常常出于功利的目的以及追求效率的考虑，很多面试者会选择这样一条道路——背题。上到算法题，下到基础性的概念，无所不背，如此急功近利的做法，往往还会颇有成效。想必在你的漫长面试生涯中，一定听过面试官问过这几个问题（甚至可以做到一字不差）：

1. 进程和线程有什么区别？
2. 什么是 TCP 的三次握手和四次挥手？
3. HTTP 中的 GET 和 POST 方法有什么区别？
4. B 树和 B+ 树有什么区别？
5. 什么是数据库的 ACID？
6. ......

如果你身经百战，这些问题的答案应该信手拈来，很多时候甚至这些知识在你脑中已经不再是一种储备，而是近乎肌肉记忆的条件反射，一听到关键词，答案在嘴边如同施法一般就脱口而出......毕竟面试官问的次数实在是太多了！然而，大多数时候面试官的问题便在此戛然而止，少数面试官会继续问一句「为什么」，但也不过是浅尝辄止，看你说个差不多就「满意」地点了点头，进入下一个问题。几乎没有面试官会继续追问问题更为本质的一面，即「为什么背后的为什么」，也是在此，理解者和背题家的差距便会被暴露。上面这几个问题刚好涵盖了操作系统，计算机网络和数据库，我们挑选其中一些来一一分析讲解，来看看这些问题到底简单在哪里，又难在哪里，以至于大多数人都知其然却不知所以然，通过不停的追问即可到达我们今天的目的：筛选背题家。

并发 vs 并行

比起进程和线程的区别，我想先来讲讲「并发」和「并行」这两个词。中文语境下这两个词的区别似乎并不大，意思也难有较大区分，所以我们先来看看它们的英文：Concurrency 和 Parallelism。这两者是有区别的：「并发 Concurrency」意指在同一时间我们同时处理多个事情，而「并行 Parallelism」意指在同一时间我们同时做多个事情。让我们来用一个比喻解释这两者行为的区别：

• 你吃饭吃到一半，电话来了，你一直到吃完了以后才去接，这是串行。
• 你吃饭吃到一半，电话来了，你停了下来接了电话，接完后继续吃饭，这是并发。
• 你吃饭吃到一半，电话来了，你一边打电话一边吃饭，这是并行。

可以看到，完成「吃饭」和「接电话」两件事情所需要的时间，串行 == 并发 > 并行。计算机中，并发和并行无论是在底层设计还是上层编程中都是我们用于提高计算机处理效率以及性能的主要思想。看到这你可能会有这样一个疑惑：这并发也没让我们处理事情的效率变高啊，不还是和串行要用一样的时间吗？我们知道，计算机进行计算是需要资源的，这些资源包括但不限于 CPU 算力，内存以及网络 I/O 等，在有限的资源上完成更多的事情显然是我们的一个目标，而并发和并行分别从两个角度来达成这一目的：

• 并发通过提高执行任务时的资源利用率来提高效率
• 并行通过减少执行任务的耗时来提高效率。

可以看到，前者省下的是资源，而后者省下的是时间（要做的这一点也许还会消耗更多资源）。回到刚才打电话吃饭的例子，串行和并发的两个场景，虽然用时相同，但有一个显著的区别，即在串行的场景下，你的电话在你吃饭的过程中一直在响（暂时忽略你太久不接它会自动或主动挂断这个设定），在整个过程中，你的电话一直处于这一个电话的「等待响应」状态中，此时如果有另一个人也想给你打电话，他显然只能听到忙音而无法联系上你，这时候我们就可以说「电话」这个资源在整个过程中因持续占用却不被处理而浪费了。反观并发的场景，你立马停止了吃饭接听电话，尽管并没有节约时间，但是你的电话资源很快便被处理并释放了出来，此时如果有第二个电话到来，比起第一个场景，你在相同的时间里更多地利用了「电话」，假设第二个电话直接帮助你谈成了一笔 1 个亿的大合同，比起串行场景下接不上可能导致的错亿，可以不可以说并发帮助我们提高了任务处理的效率呢？答案是显然的。

在了解了以上概念后，「进程和线程有什么区别」这个问题又可以引申出多个问题：

• 在多核 CPU 场景下，线程的执行是并行的吗？
• 在单核 CPU 场景下，使用多线程可以帮助我们提高程序的运行效率吗？
• GIL 的存在是否意味着 Python 无法做到并发？它会影响所有的多线程场景吗？
• 不同语言实现并发主要通过哪几种方法？

在此我不提供解答，希望大家能够自己发掘这些问题的答案，帮助自己更好地理解进程，线程，并发以及并行这些玩意儿。

GET vs POST

想成为一个 CRUD Boy，HTTP 协议想必你一定了解，面对面试官「HTTP 中的 GET 和 POST 方法有什么区别？」的提问，你心里也许已经想好了一大票答案来回答：

• GET 作为书签可收藏，POST 作为书签不可收藏。
• GET 使用 URL 传递参数，POST 使用表单传递参数。
• GET 对传输数据长度有限制，POST 没有限制。
• GET 用于获取数据，POST 用于发送数据。
• ......

很遗憾，以上所有都是片面的表象，甚至有些错误，而且也都不是 GET 和 POST 方法的本质区别。事实上，GET 和 POST 从理论上的技术使用来说，没有任何实质区别。GET 能做的事情 POST 也能做到，反之亦然。你完全可以只用 GET 方法来完成你 Web 应用里的所有请求，从读到写一应俱全，POST 也可以在 URL 里带参数，GET 也可以用 Body 来发送数据，实际产生的报文也仅有一些格式上的区别。那么既然「没区别」，那为什么还要区分不同的 HTTP 请求方法呢？要回答这个问题，我们需要从一个词入手：语义。

想必你一定会发现，实际场景中 GET 往往用于获取数据，而 POST 往往作为某些需要发起写数据的请求方式来使用。这几点其实并不是大家逐渐形成的使用习惯，而是早就在 HTTP 的 RFC 中有过明确的定义：

The GET method requests transfer of a current selected representation for the target resource. GET is the primary mechanism of information retrieval and the focus of almost all performance optimizations. Hence, when people speak of retrieving some identifiable information via HTTP, they are generally referring to making a GET request. A payload within a GET request message has no defined semantics; sending a payload body on a GET request might cause some existing implementations to reject the request.

The POST method requests that the target resource process the representation enclosed in the request according to the resource’s own specific semantics.

现在你可以发现，GET 和 POST 其实仅有语义上的区别。

• GET 意味向请求选择获取一系列资源，也就对应着「读资源」的场景，其需要满足安全，幂等和可缓存，即请求无害，多次请求结果一致，不会改变服务端的状态，并且读结果可以被缓存。对 GET 请求的携带消息并没有任何定义，如前文所述可以通过 URL 也可以通过 Body，但考虑到不同应用（诸如浏览器）的实现不同，选用后者也许会有一些问题。
• POST 根据请求负荷对制定资源作出处理，也就对应着「写资源」的场景，其不一定安全，不保证幂等，大部分实现不可缓存。

看到这里，再次面对「HTTP 中的 GET 和 POST 方法有什么区别？」的提问，你又会怎么回答呢？

B Tree vs B+ Tree

B 树和 B+ 树的区别想必也是老生常谈的话题了，说起来区别，什么一个根结点的儿子数为 [2, M]，一个数据只存在于叶节点等等，大多数人也是朗朗上口，倒背如流。MySQL 默认的存储引擎 InnoDB 会使用 B+ 树来存储数据，无论是表中数据的主索引还是辅助索引都会使用 B+ 树来存储数据，所以......为什么要用 B+ 树而不是 B 树呢？刚才说的那些区别，到底是为什么呢？

B 树和 B+ 树可以说都是平衡二叉树的变种。说区别前，我们先来看看平衡二叉树是为了解决什么问题而存在的。平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树数据结构，学过算法和数据结构的你一定知道，树的高度越矮，两边的节点越平均（平衡），越有利于我们将查找数据的速度优化到近于二分法查找，即 O(log n) 中的树高 n 越小，我们做一次数据访问和修改的代价越低。B 树和 B+ 树均为平衡多路查找树，对比二叉树最明显的区别就是一个父节点的查找路径不再是只有两个，可以是多个，这样一来便很直观地达到了一个目的——让我们的树更矮了。至于其他的区别，我们一一来辨明。

• B 树的非叶子节点同时保存关键字和对应数据，而 B + 树的非叶子节点只保存关键字，具体数据只存在于叶子结点

B 树和 B+ 树均以页为单位，每一页的大小默认即为操作系统的页大小（大多数情况下为 4KB），设想 B+ 树在页大小不变的情况下，只在非叶子结点存储关键字而不是全部数据，此优化让 B+ 树比起 B 树可以在同样的页大小下增加更多的关键字数量，相应的树层数也会减少，增加读取效率。

• B + 树叶子节点保存了父节点所存储关键字的所有具体数据

如上所说，两者均以页为单位划分数据，而操作系统在发现需要的数据不在内存中时，会以页为单位从硬盘上进行加载，这每一次加载便会触发一次 I/O 操作。假设我们要做一次范围查找，而范围的左右边界均在不同的页上，那么意味着想要找所有范围内的关键字数据，B 树需要我们多次从根节点页出发，依照查找路径访问不同的页，而 B+ 树中就不存在这个问，因为所有的数据都存储在叶节点中，并且这些叶节点之间往往又会通过类似链表的方式按顺序进行连接，在范围查找的场景下，我们只需要一次从跟节点页出发，到达范围的左边界后直接在多个子节点之间进行跳转，这样势必能比 B 树的多次换页查找节省大量的磁盘 I/O。

以上两个可以说是 B 树和 B+ 树最大的区别和其背后的设计原理，总结而言，B + 树的优点是：

• 更矮，因为每个非叶子结点只需要存储关键字。
• 更稳定，因为具体数据只存在于叶子结点上，所以每次查找的次数一定相同——为树的高度。
• 更快，因为叶子节点间互相链接且保证有序，所以进行扫描遍历更快。

B 树也不是一无是处，如果经常访问的数据离根节点很近，也就是说数据的访问频率和树的高度相关联场景下，B 树因为在非叶子结点中本身存了数据，会比 B+ 树更快。

下次再被问同样的问题，除了说出这些区别，主动再讲讲区别背后的考量和出发点，一定会让面试官眼前一亮。比起只能说出区别，而讲不出为什么，高下立判。

结语

由于篇幅有限，我不能针对更多的问题进行分析，所以只挑选了几个我认为具有代表性的问题来进行阐述。本文旨在抛砖引玉，作为面试者，我希望你能在日后的面试过程中能够注重对问题本质认识的发掘，这样可以更快的发现候选人身上的闪光点，筛选掉水平良莠不齐的面试「背题家」；作为被面试者，我希望你能在日后的学习过程中更深入的了解自己所学知识，比起知道 How 和 Why，知道 Why why 才是真正对许多事物有透彻理解的终点。在这里送大家一句话：

Stay foolish, stay hungry.

求知若渴，虚心若愚。

参考文献

• What's the difference between concurrency and parallelism?
• 并发与并行的区别是什么？
• GET 和 POST 到底有什么区别？
• Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content
• 为什么 MySQL 使用 B+ 树

本文为《Rust 内置 Traits 详解》系列第一篇，该系列的目的是对 Rust 标准库 std::prelude 中提供的大部分内建 Traits 以适当的篇幅进行解释分析，并辅之以例子（多来自官方文档），旨在帮助读者理解不同 Traits 的使用场景，使用方式及其背后的原因。

本篇作为试水，将包括几个简单的 Traits，均来自于 std::cmp

• Eq & PartialEq
• Ord & PartialOrd

Eq & PartialEq

Eq and PartialEq are traits that allow you to define total and partial equality between values, respectively. Implementing them overloads the == and != operators.

这两个 Traits 的名称实际上来自于抽象代数中的等价关系和局部等价关系，实际上两者的区别仅有一点，即是否在相等比较中是否满足反身性（Reflexivity）。

两者均需要满足的条件有：

• 对称性（Symmetry）：a == b 可推出 b == a
• 传递性（Transitivity）：a == b 且 b == c 可推出 a == c

Eq 相比 PartialEq 需要额外满足反身性，即 a == a，对于浮点类型，Rust 只实现了 PartialEq 而不是 Eq，原因就是 NaN != NaN。

PartialEq 可使用 #[derive] 来交由编译器实现，这样一个 struct 在进行相等比较时，会对其中每一个字段进行比较，如果遇到枚举，还会对枚举所拥有的数据进行比较。你也可以自己实现自己的 PartialEq 方法，例子如下：

enum BookFormat {
    Paperback,
    Hardback,
    Ebook
}

struct Book {
    isbn: i32,
    format: BookFormat,
}

impl PartialEq for Book {
    fn eq(&self, other: &Self) -> bool {
        self.isbn == other.isbn
    }
}

实现时只需要实现 fn eq(&self, other: &Self) -> bool 判断是否相等的函数，Rust 会自动提供 fn ne(&self, other: &Self) -> bool。

实现 Eq 的前提是已经实现了 PartialEq，因为实现 Eq 不需要额外的代码，只需要在实现了 PartialEq 的基础上告诉编译器它的比较满足反身性就可以了。对于上面的例子只需要：#[derive(Eq)] 或 impl Eq for Book {}。

Ord & PartialOrd

Ord and PartialOrd are traits that allow you to define total and partial orderings between values, respectively. Implementing them overloads the <, <=, >, and >= operators.

类似于 Eq，Ord 指的是 Total Order，需要满足以下三个性质：

• 反对称性（Antisymmetry）：a <= b 且 a >= b 可推出 a == b
• 传递性（Transitivity）：a <= b 且 b <= c 可推出 a <= c
• 连通性（Connexity）：a <= b 或 a >= b

而 PartialOrd 无需满足连通性，只满足反对称性和传递性即可。

• 反对称性：a < b 则有 !(a > b)，反之亦然
• 传递性：a < b 且 b < c 可推出 a < c，== 和 > 同理

Ord & PartialOrd 均可通过 #[derive] 交由编译器自动实现，当使用 #[derive] 实现后，将会基于 struct 的字段声明以字典序进行比较，遇到枚举中的数据也会以此类推。可以注意到 Ord & PartialOrd 的性质要求会进行等于的比较，所以有以下对 Eq & PartialEq 的依赖要求：

• PartialOrd 要求你的类型实现 PartialEq
• Ord 要求你的类型实现 PartialOrd 和 Eq（因此 PartialEq 也需要被实现）

实现 PartialEq，PartialOrd 以及 Ord 时要特别注意彼此之间不能有冲突。

use std::cmp::Ordering;

#[derive(Eq)]
struct Person {
    id: u32,
    name: String,
    height: u32,
}

impl Ord for Person {
    fn cmp(&self, other: &Self) -> Ordering {
        self.height.cmp(&other.height)
    }
}

impl PartialOrd for Person {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for Person {
    fn eq(&self, other: &Self) -> bool {
        self.height == other.height
    }
}

实现 PartialOrd 需要实现 fn partial_cmp(&self, other: &Self) -> Option<Ordering>，可以注意到这里的返回值是个 Option 枚举，之所以如此是要考虑到与 NaN 作比较的情况：

let result = std::f64::NAN.partial_cmp(&1.0);
assert_eq!(result, None);

完成后会为为你的类型提供 lt()，le()，gt() 和 ge() 的比较操作。

而实现 Ord 需要实现 fn cmp(&self, other: &Self) -> Ordering，完成后会为你的类型提供 max() 和 min()。在目前的 Nightly 版本中，实现 Ord 还会提供一个 clamp() 函数，用来比较类型是否在某个区间中。

#![feature(clamp)]

assert!((-3).clamp(-2, 1) == -2);
assert!(0.clamp(-2, 1) == 0);
assert!(2.clamp(-2, 1) == 1);