wudaijun's blog

本文主要谈谈CPU Cache的设计，内存屏障的原理和用法，最后简单聊聊内存一致性。

我们都知道存储器是分层级的，从CPU寄存器到硬盘，越靠近CPU的存储器越小越快，离CPU越远的存储器越大但越慢，即所谓存储器层级(Memory Hierarchy)。以下是计算机内各种存储器的容量和访问速度的典型值。

从广义的概念上来说，所有的存储器都是其下一级存储器的Cache，CPU Cache缓存的是内存数据，内存缓存的是硬盘数据，而硬盘缓存的则是网络中的数据。本文只谈CPU Cache，一个简单的CPU Cache示意图如下:

图中忽略了一些细节，现代的CPU Cache通常分为三层，分别叫L1,L2,L3 Cache, 其中L1,L2 Cache为每个CPU核特有，L3为所有CPU核共有，L1还分为缓存指令的i-cache(只读)和缓存程序数据的d-cache，L2 L3 Cache则不区分指令和程序数据，称为统一缓存(unified cache)。本文主要讨论缓存命中和缓存一致性的问题，因此我们只关注L1 Cache，不区分指令缓存和程序数据缓存。

Perf(Performance Event)是Linux 2.6.31后内置的性能分析工具，它相较其它Prof工具最大的优势在于与Linux Kernel紧密结合，可以进行内核甚至硬件级的性能分析。我之前只零散地用一些ptrace,strace之类的小工具，与Perf比起来，确实小巫见大巫。也赶紧花了点时间简单了解和试用一下，添加到工具箱，以备不时之需。

聊聊游戏服务器的一些难点，以及它和Web服务器的差异。

一. 状态性

游戏服务器是后端，做后端的，每天耳濡目染横向扩展，自动伸缩等炫酷的特性，要说放在以前，这些特性还是巨头的”专利”，我们想要自己实现这些东西挑战性是比较大的，但近几年有了容器生态如k8s的加持，只要你实现了一个无状态应用，你几乎马上就可以得到一个可伸缩的集群，享受无状态本身带来的各种好处，机器挂了自动重启，性能不够了就自动扩展等等。而作为一名游戏服务器开发者，自然也想充分享受容器时代的红利，所以我们来捋捋无状态游戏服务器的可行性。

本文谈谈在函数式编程中的延迟计算，惰性求值等技术及其应用。

Racket

本文将以 Racket 为例，以下是 Racket 的概要:

1. 更广泛的函数概念: 什么 if define + myfunc 等，统统都是函数
2. 前缀表达式: 同 Lisp, Scheme 等语言一样，Racket 使用前缀表达式，如(myfunc 1 2)，(+ 1 2 3)等
3. 支持可变性: 可修改变量值(不建议)，如 (set! x 2)，并且支持修改 Pair，Map 的指定元素

其它关于 Racket 的具体语法和 API 细节请参考Raccket 中文文档。

Delay Evaluation

Delay Evaluation 意为延迟计算，即表达式只在必要时才求值，而非被赋给某个变量时立即求值。

本文简单讨论如何在服务端实现基于三角形网格的寻路算法。

地图表示

1. 基于路点

基于路点是最原始的寻路方案，比如要让你实现一个迷宫，你会很自然地想到用0代表通路，1代码障碍物，整个迷宫地图由0和1构成的点阵来表示。这就是基于路点，本质上是将地图上可以通过的位置(坐标状态)都记录下来。

前段时间又和同事讨论到 GS 中的 数据一致性，在这里简单聊聊。这里的数据一致性即系统内部的数据一致性(ACID中的C)，而非分布式系统对外体现的一致性(CAP中的C)。

假设我们有一个业务逻辑叫做行军，玩家需要先消耗一定的钻石，才能发起行军。在单线程下，其逻辑如下:

1
2
3
4
5
6
7
8
9
10

if !checkDiamond(cost) {
    return error_Diamond_not_enough
}

if !checkMarch(troopId) {
    return error_troop_can_not_march
}

deductDiamond(cost)
startMarch(troopId)

这个逻辑在单线程下是没什么问题的，如果现在我们由于性能原因，将 Play(玩家数据逻辑) 和 Map(大地图玩法) 分为了两个 Actor (如goroutine,节点)，玩家钻石由 Play Actor 管理，部队数据由 Map Actor 管理，那么我们现在的逻辑变成了分布式中最常见的 Check-Do 模型:

调度的概念这里就不赘述了，调度本质上就是一个资源分配算法，本文谈谈调度的基础策略，常见模型，以及 Go 和 Erlang 的一些调度特性。

调度策略

抢占 vs 协作

从调度机制上来讲，调度可以分为抢占式和协作式。

非抢占方式是指一旦将调度资源(如 CPU)分配给某任务 后，便让该任务一直执行，直到该任务完成或阻塞或主动让出CPU控制权，非抢占调度又称为协作式调度，它实现简单，并且对共享资源的访问也更安全(如允许使用不可重入函数)。非抢占算法常见的如 FIFO，STCF(Short time to complete first)等。

go module 是 go1.11 引入的新概念，为 go 当前饱受诟病的 GOPATH 和依赖管理提供了更好的解决方案。在理解 go module 之前，先回顾下当前 Go 的项目结构和依赖管理都有什么问题:

1.GOPATH

GOPATH一定程度上简化了项目构建，但是给了开发者过多的限制，你的项目必须位于 GOPATH 下，否则编译器找到它，想要使用你自己的项目组织结构，要么你需要为每个项目设置一个 GOPATH，要么使用软链接来实现。大多数 go 新手都会纠结于应该使用一个 GOPATH 还是为每个项目创建一个 GOPATH，还是为所有依赖创建一个 GOPATH，受到一堆限制，却并没有得到便利。

CGroup V1

1. CGroup 概念

• Task: 任务，也就是进程，但这里的进程和我们通常意义上的 OS 进程有些区别，在后面会提到。
• CGroup: 控制组，一个 CGroup 就是一组按照某种标准划分的Tasks。这里的标准就是 Subsystem 配置。换句话说，同一个CGroup 的 Tasks 在一个或多个 Subsystem 上使用同样的配置。
• Hierarchy: 树形结构的 CGroup 层级，每个子 CGroup 节点会继承父 CGroup 节点的子系统配置，每个 Hierarchy 在初始化时会有默认的 CGroup(Root CGroup)。
• Subsystem: 子系统，具体的物理资源配置，比如 CPU 使用率，内存占用，磁盘 IO 速率等。一个 Subsystem 只能附加在一个 Hierarchy 上，一个 Hierarchy 可以附加多个 Subsystem。

在计算机领域，谈到一致性这个词时，你会想到CAP理论的 consistency，或者数据 ACID 中的 consistency，或者 cache 一致性协议的 coherence，还是 Raft/Paxos 中的 consensus？

一致性大概是开发者最容易造成困惑的概念之一，在很多中文文献中，都将consistency，coherence，consensus 三个单词统一翻译为”一致性”，但是它们的意义是有所不同的。本文尝试以”一致性”为线头，梳理下相关概念，以及它们之间的区别和联系。

Consensus

更准确的翻译是共识，共识是容错分布式系统中的一个基本问题，共识的本质是多个节点就某个提议达成一致。在分布式系统下，由于节点故障，网络时延，网络分区等问题的存在，2PC/3PC这类强一致事务手段通常是不可取的: 任何节点故障或网络问题都会阻塞整个事务，降低系统的可用性，并且系统节点越多，可用性受影响越大。为了解决这个矛盾，分布式系统通常采用状态机复制+多数投票的机制来构建高可用容错系统:

• 状态机复制(State Machine Replication): 它的理论基础是任何初始状态一样的状态机(如KV Store)，如果执行的命令日志(包括新增、修改、删除等任何操作本质都将转化为新的命令日志追加)一样，则它们的状态机最终状态也将一样(KV数据一致)。如此不需要强制这些命令在各个节点是同时开始、同步完成的，只需要将连续的命令日志同步给其他节点(这个步骤也叫日志复制Log Replication)，允许在此期间节点存在内部状态的不一致(只要这些不一致不被外观察到)，所有的分布式节点的最终状态会达成一致。
• 投票机制(Quorum)): 少数服从多数原则，如果能在多数节点达成一致时就作出不可推翻的最终决策，那么就可以容忍少数节点的不可用，这也就打破了前面说的节点数越多，可用性越低的悖论

在状态机复制的场景下，Paxos/Raft 等共识算法被用来确保各个复制状态机(节点)的日志是一致的，但Paxos/Raft 本身对外不直接体现出一致性(Consistency)，一致性是应用层的决策，比如Raft算法中，写操作成功，仅仅意味着超过半数节点对该写日志进行Commit(命令日志一致)，但不保证它们对该命令进行了Apply(状态机一致)，这一层就是交由应用层去灵活实现的，类似的应用层取舍点还包括Follower是否提供读服务，网络分区后Follower/Candidate是否对外提供读服务等等，因此不同的应用可以基于Raft算法实现不同的一致性，比如ETCD基于Raft支持线性一致性(后面会聊到这个概念)的读写操作。从另一个角度来说，共识算法可以理解为达成一致的一种算法手段。

Paxos/Raft属于宕机容错(CFT，Crash Fault Tolerance)算法，因为它们只容忍了节点/网络故障，没有考虑节点不可信任，可能”作恶”的问题，如经典的拜占庭将军问题。能够(一定程度)容忍拜占庭问题的共识算法被称为拜占庭容错(Byzantine Fault Tolerance)算法，典型如POW(Proof of Work)、POS(Proof of Stake)、PBFT(Practical Byzantine Fault Tolerance)算法等，BFT算法通常比CFT算法实现成本更高，它通常适合用在公网，去中心化的情形下，如区块链场景。