
> 导读：「分布式锁」技术科普系列，由 NebulaGraph 存储负责人 @critical27 整理自己的“学习笔记”而成。在单体应用中我们通过锁实现共享资源访问，而在分布式系统中，则通过分布式锁解决。NebulaGraph 作为一款分布式图数据库，邀请大家一起学习分布式系统架构中的分布式锁～


![](https://pic1.zhimg.com/80/v2-d555f7b4514545baf26266e355165dad_1440w.jpg?source=d16d100b)




🔍在开始本期的学习之间，推荐阅读⬇️

[技术科普｜深入理解分布式锁的原理与实现 part 1](https://mp.weixin.qq.com/s?__biz=Mzg4OTg0MzY0Mw==&mid=2247516628&idx=1&sn=ae7ed7051c882f9208946f872116245e&scene=21#wechat_redirect)

上期文末卖了个关子：当 Redlock 提出之后，DDIA 的作者 Martin Kleppman 质疑了这个算法，后来 Redis 的作者 Antirez 也下场进行了反驳。

两个人都是大牛，到底谁说的更有道理呢？本期来看看大牛们如何理解分布式锁。

# 一、Argues about Redlock

在 Redlock 提出之后，Designing Data-Intensive Applications 的作者 Martin Kleppmann 就在博客《How to do distributed locking》提出了质疑，Redlock 也作为一个反例被写进了这本书里（只不过没有点名是 Redlock）。

Martin Kleppmann 举了一个反例，客户端 1 在获取到分布式锁之后操作共享资源之前，发生了 GC，而 GC 期间锁又过期了。此时客户端 2 也可以获取到分布式，进而出现了两个客户端同时操作共享资源的问题。
![](https://nebula-cdn.nebula-graph.com.cn/nebula-website-5.0/share/lock1.webp)



**这里面 stop-the-world GC 只是一种客户端被阻塞的情况，比如文章中提到好几种可能：**

* GC: 任何 Garbage Collector 实现都可能需要 stop-the-world

* 操作共享资源时，发生了 network delay

* 发生 page fault，需要将硬盘上的数据加载进内存

* 进程收到了 SIGSTOP 或者 SIGPAUSE 信号

* 时钟漂移，甚至闰秒问题

除了上面的问题，Martin Kleppmann 还指出 Redlock 有以下缺陷，其核心在于 Redlock 是依赖于本地时间的比较来保证分布式锁互斥的。

**Redlock 主要有两个地方使用了本地时间，可以参照前文理解：**

* Redis 需要根据本地时间，决定记录的过期时间

* 客户端在获取锁成功之后，需要用两次本地之间的差值来计算锁的有效时间

Redis 使用  `gettimeofday` 来获取本地时间，这个时钟不是原子递增的，会出现时钟回退和漂移。因此，而 Redlock 却重度依赖于本地时间，又或者对网络延迟和超时时间做了时间上的假设，因此不是一个安全的分布式锁实现。

原文如下：

> "For algorithms in the asynchronous model this is not a big problem: these algorithms generally ensure that their safety properties always hold, without making any timing assumptions. Only liveness properties depend on timeouts or some other failure detector. In plain English, this means that even if the timings in the system are all over the place (processes pausing, networks delaying, clocks jumping forwards and backwards), the performance of an algorithm might go to hell, but the algorithm will never make an incorrect decision."
> 
> "However, Redlock is not like this. Its safety depends on a lot of timing assumptions: it assumes that all Redis nodes hold keys for approximately the right length of time before expiring; that the network delay is small compared to the expiry duration; and that process pauses are much shorter than the expiry duration."

博客里面举的一个反例如下，假设 ABCDE 组成一个 5 节点的 Redis 分布式锁集群：

* 客户端 1 获取到节点 A、B、C 上的锁

* 节点 C 上的时钟发生跳变（比如系统管理员突然把系统时间调大了），导致锁到期

* 客户端 2 此时就能获取节点 C、D、E 上的锁

* 客户端 1 和 2 都认为自己持有分布式锁

这个例子其实和 Redis 文档里面关于持久化一部分的例子几乎如出一辙，问题都出在其中一个节点在不超过 TTL 的时间内两次上锁成功。只不过文档中是节点发生了重启，而此处则是发生了时钟跳变。

**如果我们假设真的不会发生时钟跳变，那么套用前面的 GC，一样可以复现问题：**

* 客户端 1 向 A、B、C、D、E 发出上锁请求

* 客户端 1 在收到上锁的响应之前发生 GC，并一直卡住

* 所有节点锁都过期

* 客户端 2 获取锁成功

* 客户端 1 此时 GC 结束，收到之前上锁请求的响应，认为上锁成功

* 客户端 1 和 2 都认为自己持有分布式锁

**小结**

Martin Kleppmann 认为 Redlock 依赖于以下的假设：

* 有上限的网络延迟

* 有上限的进程暂停时间

* 有上限的时钟漂移

只要上面的任何一个假设在真实环境中不满足，Redlock 就不能保证 safety.

# 二、Fencing token

除此之外，Martin Kleppmann 提出了一个解决方案：每次分布式锁返回成功时，需要携带一个自增的 token. 客户端在操作共享资源时，需要携带这个 token. 而共享资源可以比较当前已经使用的最大 token，拒绝掉携带过期 token 的请求。通过每次生成的自增 token，去除了对本地时钟的依赖。

![](https://nebula-cdn.nebula-graph.com.cn/nebula-website-5.0/share/lock2.webp)


比如还是前面的例子，客户端 1 获取了分布式锁，token 为 33，然后被 GC 阻塞住。客户端在锁过期之后获取了分布式锁，token 为34，并操作了共享资源。当客户端 1 恢复时，再用 token 为 33 发送请求时，会被共享资源拒绝。

然而 Redlock 本身的限制导致不能使用 fencing token 来解决这些问题，一个核心点就在于 Redlock 的多个 Redis 节点都是主库，并且互相不通信，因此各个节点之间很难生成一个一致的自增 token 返回给客户端。

# 三、Is Redlock safe?

Redis 的作者 Antirez 之后也进行了反驳：

> "In this analysis I’ll analyze Martin’s analysis so that other experts in the field can check the two documents (the analysis and the counter-analysis), and eventually we can understand if Redlock can be considered safe or not."

**Antirez 的文章总结下来有几个论点：**

**论点 1 ：Martin 提出的 fencing token 不是必须的**

这里需要从两个方面进行解释：

* 是不是自增 id 关系不大，比如 Redlock 使用`/dev/urandom`中的 20 个字节作为 uuid，也能够通过 read-modify-write 进行比较（冲突概率认为极低）。比如往 MySQL 中更新记录可以这么做：

UPDATE table T SET val = $new_val WHERE id = $id

* 如果共享资源已经能通过某种机制拒绝掉过期请求（比如上面写入 MySQL），这种情况下就不需要使用分布式锁，直接通过 MySQL 中的记录不就好了吗？通常使用分布式锁的时候，都是因为共享资源不能提供类似分布式锁的互斥能力，比如写一个文件。

Antirez 的原话如下，这个论点我是比较 buy-in 的。

> "I want to mention again that, what is strange about all this, is that it is assumed that you always must have a way to handle the fact that mutual exclusion is violated. Actually if you have such a system to avoid problems during race conditions, you probably don’t need a distributed lock at all, or at least you don’t need a lock with strong guarantees, but just a weak lock to avoid, most of the times, concurrent accesses for performances reasons."

**论点 2 ：其余问题不只是存在于 Redlock**

针对 Martin 博文中对 Redlock 不能应对 NPC 问题（Network delay, Process pause, Clock drift），Antirez 也进行了反驳。

首先是时钟漂移，Redlock 的确假设了各个时钟之间的速度是相近的，也就是时钟偏移量是有上限的，但 Antirez 认为这个时钟模型是符合现实情况的，事实上的确也如此。至于 Martin 文章中提到的时钟跳变，主要出现在两种情形：

* 系统管理源手动修改系统时间

* NTP 同步

> "The above two problems can be avoided by “1” not doing this (otherwise even corrupting a Raft log with “echo foo > /my/raft/log.bin” is a problem), and “2” using an ntpd that does not change the time by jumping directly, but by distributing the change over the course of a larger time span."

这的确也是一种解决的技术手段，不过这就对对 Redis 分布式锁进行运维的人员就有要求了，不是所有人都看到过这番争论的。

**论点 3 ：网络延迟和进程暂停相关问题**

首先 Antirez 回顾了下 Redlock 的基本流程：

1. Get the current time.

2. All the steps needed to acquire the lock.

3. Get the current time, again.

4. Check if we are already out of time, or if we acquired the lock fast enough.

5. Do some work with your lock.

在第一步和第三步分别获取了一次本地时间，如果 Network delay 和 Process pause 发生在了第一步和第三步之间，那通过两次本地时间的比较是能够发现的。而第一步和第三步的时间间隔也很短，因此时钟漂移的影响可以忽略不计，但时钟跳变只能按前面所说的方法进行规避了。

**这里举了一个例子：**

当客户端发送请求尝试获取锁时，服务端已经成功授权锁，并发送了响应。然而此时发生网络丢包或者重传，导致当客户端收到响应时候，服务端已经认为过期了。所以客户端在收到响应时，网络延迟早就发生了，客户端也无能为力。客户端能做的就是必须检查我还有多少时间可以用来操作共享资源，这个检查是所有带自动过期的分布式锁算法都需要的。

那么只有 Network delay 和 Process pause 发生在第三步以后，才可能出现问题。而 Antirez 再次强调这是所有分布式锁服务都会遇到的问题，即客户端认为获取锁成功，而服务端已经认为锁过期的情况。即便使用 ZooKeeper 来作为分布式锁也一样会遇到问题。

**这里简单介绍 ZooKeeper 是如何实现的分布式锁的。**

1. 客户端 1 和 2 都尝试创建临时节点 ZNode，例如 `/lock`

2. 假设客户端 1 请求先到达，则加锁成功，客户端 2 加锁失败

3. 客户端 1 操作共享资源

4. 客户端 1 删除`/lock`节点，释放锁

ZooKeeper 不像 Redis 那样，需要考虑锁的过期时间问题，它是采用了临时节点，保证客户端 1 拿到锁后，只要连接不断，就可以一直持有锁。ZooKeeper 的客户端在创建临时节点后，会在和服务端的 Session 中不断发送心跳来续约，保证服务端。如果客户端的心跳由于 crash 或者 GC 终端，那么这个临时节点会自动删除，保证了锁一定会被释放。

**我们把之前的异常套用在 ZooKeeper 上：**

1. 客户端 1 创建临时节点 `/lock`成功，拿到了锁

2. 客户端 1 发生 GC，并一直卡住

3. 客户端 1 无法给 Zookeeper 发送心跳，Zookeeper 认为过期把临时节点 `/lock` 删除

4. 客户端 2 创建临时节点 `/lock`成功，拿到了锁

5. 客户端 1 进程此时 GC 结束

6. 客户端 1 和 2 都认为自己持有分布式锁

因此，即便是使用 Martin 推荐的 ZooKeeper 来做分布式锁服务，也无法完全避免 NPC 的问题。

# 四、结论

双方其实说的都有道理，这更从侧面验证了实现一个分布式锁服务本质上就是要实现一致性共识。而一个通常意义下的分布式锁服务，是无法在极端情况下保证 safety 和 liveness 的。


---

**Reference**

[1]万字长文说透分布式锁：https://zhuanlan.zhihu.com/p/403282013

[2]Distributed Locks with Redis：https://redis.io/docs/latest/develop/use/patterns/distributed-locks

[3]Redis 实现分布式锁：https://juejin.cn/post/6975069367574888478

[4]How to do distributed locking：https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

[5]Is Redlock safe?：https://antirez.com/news/101

[6]Redis Redlock 的争论：https://juejin.cn/post/6976538149904678925

[7]Because Coordinating Distributed Systems is a Zoo:https://zookeeper.apache.org/doc/current/zookeeperProgrammers.html

---

NebulaGraph 邀你参加开源之夏🌟⬇️

[开源之夏｜从 NebulaGraph 开启你的图数据库开源之旅！](https://mp.weixin.qq.com/s?__biz=Mzg4OTg0MzY0Mw==&mid=2247516493&idx=1&sn=cf0fac7165210fee057a889c77b6888b&scene=21#wechat_redirect)

 Redlock 提出之后，DDIA 的作者 Martin Kleppman 质疑了这个算法，后来 Redis 的作者 Antirez 也下场进行了反驳。到底谁说的更有道理呢？本期来看看大牛们如何理解分布式锁。

Redis 作者与 DDIA 作者激辩：Redlock 真的安全吗？

> 导读：「分布式锁」技术科普系列，由 NebulaGraph 存储负责人 @critical27 整理自己的“学习笔记”而成。在单体应用中我们通过锁实现共享资源访问，而在分布式系统中，则通过分布式锁解决。NebulaGraph 作为一款分布式图数据库，邀请大家一起学习分布式系统架构中的分布式锁～

重点速览：

* 为什么需要分布式锁？

* 分布式锁能够保证什么？

* 常见的分布式锁实现方式有哪些？

![](https://pic1.zhimg.com/80/v2-2625aa7ec640d0b58ff7c62b1203180c_1440w.jpg?source=d16d100b)



# 一、Distributed Lock

在单机多线程环境下，我们可以通过以下方式进行同步：

* 互斥锁 mutex

* 信号量 semaphore

* 用户态互斥锁 futex

那如果在分布式环境下，需要处理资源抢占问题时，我们经常想到的就是分布式锁和一致性共识协议。事实上，分布式锁就是一个简化版的共识协议，我们可以从一个分布式锁需要保证的几个性质来理解这一点：

1. Mutual exclusion: 同一个时刻只有一个客户端持有锁

2. Deadlock free: 不会因为出现死锁，进而导致有客户端始终无法获取到锁的情况

3. Fault tolerance: 一个分布式锁不能因为单点故障进而导致客户端始终无法获取到锁的情况

熟悉分布式系统的同学很快就能联想到，其实上面的三点本质上就是在描述两个重要性质：safety 和 liveness. 其中 safety 对应第一点，liveness 对应后两点。

**简单来说，safety 是系统的 invariant，无论何时系统都需要保证 invariant 成立。而 liveness 则是强调系统无论什么环境下，都要能最终保证其工作最终能够完成。**

举个例子，著名的哲学家进餐的解决方法和分布式锁需要保证的 safety 和 liveness 性质如出一辙：

* safety: 因为叉子不能共享，一个正在吃饭的哲学家两侧的哲学家不能在同时吃饭。

* liveness: 没有哲学家会挨饿，也就是有限时间内饿了的哲学家都能吃上饭。

> 其实用 TLA+ 来验证很多分布式算法时，验证的条件就是 safety 和 liveness. 我们后面会试着用 TLA+ 来描述一个分布式锁的实现。

如果一个分布式锁能够保证 safety 和 liveness，本质上就是一致性共识协议，也就是所有客户端通过分布式锁服务要能对当前谁持有锁达成共识。

**那为什么不直接用一致性共识协议呢？原因有以下几点：**

1. 一个完整的共识协议，比如 Paxos 和 Raft，其工程实现难度会比一个分布式锁服务复杂很多。又或者说，我们可以基于共识协议来实现分布式锁，比如著名的 ZooKeeper 和 etcd. 他们暴露了相对容易使用的分布式锁接口，但其内部仍然是是使用 Paxos 或者 Raft 来达成共识。

2. 上一点也提到，分布式锁的接口只关注于获取锁和释放锁，比一致性共识更加容易理解和使用。

3. 一个分布式锁服务可以独立部署，并供多个业务使用。

**分布式锁有几种常见的实现方式：**

* 基于数据库的实现：不管是不是内存型数据库，都是往数据库中写入一条携带 uuid 或者自增 id 的记录。通过检查这条记录中的 id 信息是否和客户端匹配，进而获知自己是否上锁成功。

* 借助分布式应用程序协调服务：比如前面提到的 ZooKeeper 或者 etcd，它们的客户端都提供了能够实现分布式锁的接口。

不同分布式协调服务的实现原理不尽相同，不在本文描述范围之内。本文重点还是关注基于数据库的实现，主要以 Redis 为例，整体思想大同小异。

> 选择 Redis 为例的一个重要原因是，关于 Redis 分布式锁在几年前有两个大牛也下场进行了一波争论。

# 二、基于单机数据库的实现方式

一种最简单的方式就是所有客户端，通过往数据库中写入一条记录表示获取锁，而删除掉这条记录就代表释放锁。当然获取锁的时候需要检查记录是否存在，比如通过 `IF NOT EXISTS` 这样的关键词。比如在 Redis 中就可以通过这样一条命令来完成，其中 `SETNX` 代表 `SET if Not eXists`.

```
SETNX lock 1 // 1是客户端id
```

1. 如果 Redis 中一开始没有 lock 这条记录，那么执行这条命令的客户端 1 就会成功写入 lock，代表获取锁成功。此时就可以去对分布式锁保护的共享资源进行相应操作。

2. 如果此时客户端 2 执行上锁逻辑就会返回失败，即获取锁失败。

3. 当客户端 1 进行完相应操作后，通过 `DEL lock` 删掉这条记录，代表释放锁。之后其他客户端就可以继续尝试写入 lock 获取锁。

## （一）如何避免锁不释放

**上面的方案非常直观，但有一个明显的问题，如果客户端上锁成功之后没有释放，此后其他客户端都无法获取锁，违背了 liveness 性质。**

没有释放的情况很多：

1. 应用程序忘了释放

2. 客户端进程出现了 stop-the-world 的 GC

3. 客户端进程挂掉了，节点宕机，机房断电等等

想要解决这个问题，一个通常的做法就是对这个数据增加一个过期时间 TTL(Time to Live)。当这个数据存活时间达到 TTL 之后，数据库就会自动将其删除，也就是锁自动释放。这个过期时间设置长短，需要考虑操作共享资源需要多长时间。比如在 Redis 中，我们可以对 lock 这条数据设置 10 秒的过期时间。

```
SETNX lock 1
EXPIRE lock 10
```

**那么 Redis 能否保证这两个命令能原子完成呢**？**答案是否定的**，也就会出现第一个命令成功，而第二个命令失败的情况，仍然会出现无法上锁成功的情况。 Redis 后来提供了原子的命令，保证两个操作能够原子执行。
```
// 下面的两个命令都等价于SETNX lock 1和EXPIRE lock 10
// 但能保证原子执行
SET lock 1 NX EX 10        // EX代表秒
SET lock 1 NX PX 10000     // PX代表毫秒
```


## （二）如何避免释放掉其他客户端上的锁

**增加了 TTL，就可能出现另一种问题**：客户端 1 操作共享资源期间，由于各种原因，时间超过了 TTL，此时 Redis 就会把客户端 1 上的锁释放。进而客户端 2 就会获取到锁，如果此时客户端 1 刚好操作完共享资源，开始释放锁，不就把客户端 2 的锁给释放了吗？

![](https://pica.zhimg.com/80/v2-8376e08737ed5caa570c24def32d3fd8_1440w.jpg?source=d16d100b)


**解决这个问题的关键就在于判断当前持有锁的客户端是不是自己**。回顾以下我们获取锁的命令是 `SET lock 1 NX EX 10`，其中 `1` 是客户端的 id. 之所以要把自身 id 写入到锁之中，就是为了在释放锁时检查持有锁的 id. 这是一个典型的 read-modify-write 操作，实际上就是要原子的执行如下伪代码：

```
If get(lock) == $id
    del(lock)
```

然而 Redis 没有提供这样原子执行的命令，而是通过调用 Lua 脚本的形式可以保证原子性。

```
if redis.call("GET", KEYS[1]) == ARGV[1]
then
    return redis.call("DEL", KEYS[1])
else
    return 0
end
```

如果 `get` 和 `del` 不是原子执行的，也会出现违反 safety 的现象。到这里，一个基于单机数据库的分布式锁服务基本就完成了。

然而，如果这个单机数据库发生了单点故障呢？这时候我们就只能将分布式锁服务替换成一个分布式服务了。

## （三）基于主从数据库的实现方式

如果我们基于主从数据库来实现一个分布式锁服务，最大的困难就在于主从复制是异步完成的。

**一种违背 safety 性质的情况如下：**

1. 客户端从主库获取锁成功

2. 主库在复制分布式锁这条记录之前 crash，此时从库中并没有相关记录

3. 从库被升为主库，此时其他客户端就可以获取锁。此时就会有两个客户端都以为已经成果获取锁，因此可能同时操作共享资源。

## （四）基于数据库 Quorum 的实现方式

主从数据库作为分布式锁服务的最大问题在于，客户端每次只和其中一个数据库节点进行通信，而主从数据库之间是异步复制，导致主库和从库之间有可能没有对哪个客户端获取成功锁达成共识，进而导致违背互斥。

想要解决这个问题，首先我们仍然需要多个数据库节点，但客户端在上锁时要么直接和多个数据库同时通信，并获取其中大多数的授权。要么多个数据库之间有一个一致性共识协议，客户端每次只和 leader 节点通信，由 leader 节点负责确保大多数节点达成了共识，并告知客户端上锁成功。后一种方法，其实已经和 ZooKeeper 和 Etcd 非常接近了。

# 三、Redlock

Redis 的作者后来基于 Qruorum 提出了 Redlock 这种分布式锁解决方案，这个方案有 2 个前提：

1. 多个 Redis 都是主库，不使用从库和哨兵实例

2. 主库要部署多个，官方推荐至少 5 个实例

**Redlock 的主要流程如下：**

1. 获取当前时间 `T1`，然后客户端依次对多个 Redis 实例进行加锁（方式和单个 Redis 上锁命令相同）。

2. 为了避免在某个节点长时间获取不到锁而阻塞，每次获取锁操作也有一个 timeout，并且远小于锁的过期时间 TTL. 如果对单个节点获取锁的时间超过 timeout 则认为失败，立即向下一个节点获取锁。

3. 当往所有节点都发送加锁命令后并取得结果(无论结果是成功、失败还是超时)，此时获取当前时间 `T2`，获取多把锁的总消耗时间就是 `T2 - T1`。只有在超过半数节点都上锁成功，并且 `T2 - T1 < TTL`，则认为成功获取锁。

4. 如果在第 3 步获取锁成功，需要重新计算当前锁的有效时间，避免在锁过期之后仍然操作共享资源。即分布式锁最早失效时间 `MIN_VALIDITY = 过期时间TTL - (T2 - T1)`。如果考虑时钟漂移，那么 `MIN_VALIDITY = 过期时间TTL - (T2 - T1) - 时钟漂移`。即在 `T2 - MIN_VALIDITY` 这段时间，客户端能够确保唯一持有分布式锁。当使用完共享资源后，也会向所有 Redis 实例发送释放锁的命令。

5. 如果在第 3 步获取锁失败，要向所有 Redis 实例发送释放锁的命令。

我们可以结合 Redlock 是如何保证 safety 和 liveness 性质来理解这个方案。

## （一）Safety Arguments

分几种情况来看：

* 如果客户端用大于等于 TTL 的时间来对所有 Redis 节点进行上锁，此时第 3 步会检查失败，并开始向所有节点释放锁。此时客户端并没有获取锁成功，可能有其他客户端获取锁成功，不违背 safety.

* 如果客户端用小于 TTL 的时间对所有 Redis 节点进行上锁，此时第 3 步会检查成功，认为该客户端获取分布式锁成功。**此时是如何保证 safety 成立呢？**

由于客户端至少向大多数的 Redis 节点成功写入了记录，因此成功写入的这些 Redis 节点保存的这条记录 TTL 相同（客户端上锁时指定的过期时间相同），而这些节点中这条记录的过期时间不尽相同（客户端往不同节点写入这条记录的时间不同）。

这里需要注意，客户端是从大多数 Redis 节点获取锁成功，有小部分 Redis 节点是可能超时或者获取锁失败的，我们也无需考虑。

在这些成功写入的节点中，最早写入成功的时间 `Tmin` 一定大于 `T1`（因为从 `T1` 之后才发送了请求），而最晚写入的时间 `Tmax` 一定小于`T2`（因为 `T2` 时刻已经获取到了所有节点加锁结果）。那么这个分布式锁最早失效的时间就是最早成功写入记录这个节点的失效时间（因为这个节点过期，可能就会导致不满足 Quorum）。

由于我们无法精确知道 `Tmin`，我们可以转而使用 `T1` 来进行如下推导：

```
  第一个写入成功的Redis节点这条记录的过期时间
= TTL + Tmin
> TTL + T1
> TTL - (T2 - T1)
> TTL - (T2 - T1) - CLOCK_DRIFT
= MIN_VALIDITY
```

由此得到分布式锁的最早失效时间 `MIN_VALIDITY = TTL - (T2 - T1) - CLOCK_DRIFT`。在 `[T2, MIN_VALIDITY]` 这段时间之内，大多数节点的这条记录都没有过期。**换句话说，其他客户端是不可能在这段时间之内往大多数节点写入这条记录，即不可能获取分布式锁。因此 Redlock 能够保证 safety.**

> 推导过程中要引入 T2 和时钟漂移的原因在于，客户端往所有节点写入记录的时间也需要记录在内。

## （二）Liveness Arguments

**Liveness 成立主要依赖以下三方面：**

1. Redis 会根据本地时间进行过期锁的清理

2. 客户端在获取锁失败或者获取成功并使用完资源后时，会往所有节点发送释放锁的命令

3. 当客户端获取锁失败之后，会等待一段时间然后再重试（常见的 back-off 重试，避免并发场景下多个客户端始终无法获取 Quorum）

由于有这几种清理和重试的机制，保证了多个 Redis 组成的分布式锁服务不会出现时钟无法获取分布式锁的情况。

不过 Redis 自己的官方文档中，描述了这样一种场景：如果每次客户端获取到分布式锁之后，在客户端向 Redis 发送释放锁的命令之前，客户端被网络隔离，在锁过期时间 TTL 之前，其他节点无法获取到分布式锁。如果网络时断时续这种情况一直出现，也就会导致整个分布式锁的可用性大大降低。

## （三 ）What if Redis crashed?

**如果 Redis 没有开启任何持久化，当节点 crash 时，Redlock 是否能满足 safety 呢？**

**答案是否定的**。

比如一个客户端在 ABCDE 这 5 个节点中的 ABCDE 上锁成功，成功获取了分布式锁。如果此时 A 进程 crash 并重启，那么其他客户端就可以从 ADE 获取到同一个分布式锁。

想要完全避免这个问题，**一种办法是每次 Redis 都需要把记录落盘**，即开启 `fsync=always`，性能肯定会大打折扣。

**另一种办法就是当 Redis 节点重启之后，只有经过一个 TTL 时间，才能对外服务**。这样也就避免了 A 重启之后再次上锁成功的问题（因为之前的锁一定已经过期）。这个办法的缺点在于如果节点频繁重启，也会大大影响可用性。

然而，当 Redlock 提出之后，DDIA 的作者 Martin Kleppman 就质疑了这个算法，后来 Redis 的作者 Antirez 也下场进行了反驳。两个人都是大牛，到底谁说的更有道理呢？我们下一期「分布式锁」技术科普再继续讨论～

---
**Reference**

[1]万字长文说透分布式锁：https://zhuanlan.zhihu.com/p/403282013

[2]Distributed Locks with Redis：https://redis.io/docs/latest/develop/use/patterns/distributed-locks

[3]Redis 实现分布式锁：https://juejin.cn/post/6975069367574888478

---

NebulaGraph 邀你参加开源之夏🌟⬇️

[开源之夏｜从 NebulaGraph 开启你的图数据库开源之旅！](https://mp.weixin.qq.com/s?__biz=Mzg4OTg0MzY0Mw==&mid=2247516493&idx=1&sn=cf0fac7165210fee057a889c77b6888b&scene=21#wechat_redirect)



为什么需要分布式锁？分布式锁能够保证什么？常见的分布式锁实现方式有哪些？

深入理解分布式锁的原理与实现

**摘要：**

检索增强生成 （ Retrieval-Augmented Generation, RAG ）是一种结合检索与生成的技术范式，能够通过检索相关信息来丰富生成任务的上下文，从而实现更加高效、可解释和可控的知识问答与内容生成。

目前，向量数据库在 RAG 系统中广泛应用，用于存储和检索知识的语义嵌入。图数据库却尚未得到充分的重视，尽管 GraphRAG 等方法强调了图的价值，并在多跳推理和复杂关联场景中获得了关注，但许多实现并未将其与持久化的图数据库结合。这种缺失导致了图技术的潜力未被完全释放。 持久化图数据库的引入，不仅可以提升知识检索的效率，还能自然表征实体之间的关联关系，尤其在多跳查询、复杂推理和大规模知识管理中具有不可替代的优势。

 本文将从以下几个方面探讨如何结合图数据库与向量数据库，构建高效的 RAG 系统：

1. 图数据库如何构建知识之间的关联。

2. 如何将图谱与向量化知识结合，发挥各自优势。

3. 面临的关键挑战（如节约 token 和消歧）及应对策略。

# 一、图数据库在 RAG 系统中的价值

图数据库（如 Neo4j、 NebulaGraph 、TigerGraph）擅长以节点和边的形式存储数据。

**节点**：表示实体，比如“人物”、“地点”、“组织”等。

**边**：表示实体之间的关系，比如“隶属于”、“位于”、“导致”等。
这种结构化存储方式具有以下优势：

清晰的关系表达：实体之间的关联可以显式表示并查询。 例如，“Alice 是数据科学家，她曾在 Google 工作”，可以建模为：

```
[Alice] -[职业]-> [数据科学家]
[Alice] -[曾工作于]-> [Google]
```

**高效的推理能力**：图数据库支持复杂的路径查询和推理。比如：

* 查询“某人是否与某公司存在间接关系”。

* 推理“事件 A 是否可能引发事件 B”。

**可解释性**：通过查询结果可视化，用户能够直观理解知识间的关联逻辑。


# 二、 从知识的自然关联到图表示


## **构建图谱**

**数据来源**：从结构化数据（如数据库表格）和非结构化数据（如文档、网页）中提取实体和关系。

**知识抽取**：利用 NLP 工具、规则或者大语言模型进行实体识别（NER）和关系抽取。

**存储到图数据库**：将提取的实体和关系根据图数据库的存储模型转写对应的查询语句存储为节点和边。

在这个过程中，原始数据、知识片段和实体关系三者的关联同样需要持久化到图数据库中，以支持后续的查询和推理。

上面提到的是一般的构建过程，在一些简单的场景，比如文章、书籍内部的知识关联，可以天然利用目录信息、文件层次结构等构建简单的图谱。


## 动态拓展图谱
随着新知识的获取，可以动态更新图谱，特别地，领域专家应该参与到图谱的构建和校准过程中，以确保图谱的准确性和实用性，在整个 RAG 生命周期里，这是最适合发挥 Human In The Loop 理念的环节。


# 三、结合向量数据库完成 RAG

尽管图数据库在关联关系推理方面表现出色，但它对非结构化数据（如长篇文档、模糊问题）显得力不从心。向量数据库通过语义嵌入技术为模糊检索提供支持，可以弥补图数据库的不足：

**语义检索**： 无需精确匹配关键词，可以通过语义相似性找到相关内容。例如，用户问题“讲述 Alice 的职业经历”，向量数据库能检索到文档片段：“Alice 曾担任 Google 的数据科学家”。

**非结构化数据处理**： 图数据库通常不适用于直接存储大段非结构化文本，向量数据库可以通过将文本转化为向量嵌入来存储它们的语义信息。


> NebulaGraph 5.x 版支持原生的向量存储和检索能力，并且提供 GenAI Ready 的 SDK 从而可以消除整合不同技术栈的挑战。
通过关联图数据库和向量数据库，可以有效结合知识的关联关系和语义信息，从而实现更加高效的知识检索和推理。


**识别用户问题指向性**

用户提出问题后，首先可以利用 nlp 技术或者大模型进行意图识别，以确定用户问题的指向性。

如果指向明确，可以有效提取对应的实体，并利用图数据库进行查询。

如果指向不明确，可以利用向量数据库进行语义检索，以获取相关内容。

**在图数据库中查询关联**

将对应的实体和关系网络、语义信息整合，形成一个完整的上下文。

将提取出的实体作为输入，在图数据库中查询它们之间的关系，或验证某些假设性关系是否存在。

**整合结果**

利用向量数据库返回的非结构化内容（如文档片段）与图数据库的结构化结果结合，形成一个完整的上下文，供生成模型使用。


# 四、基于图数据库构建 RAG 的挑战

在前面的部分，我们主要解决了将图数据库与 RAG 系统结合的问题。接下来，我们将探讨在构建此类 RAG 系统时面临的一些重要挑战。


## 如何节约 token

由于知识之间联系的复杂性，检索结果中包含大量不相关的实体和关系，导致上下文长度增加，从而需要对检索结果进行优化，以节约 token。 解决方案：

**1. 图谱裁剪：**

在查询结果中，仅返回与问题直接相关的实体和关系。例如，针对“Bob 是否与 Alice 相关？”的问题，只返回直接连接 Bob 和 Alice 的路径，而忽略其他不相关的节点。

使用算法（如最短路径算法或社区检测算法）来减少返回的节点数量。

**2. 摘要生成：**

对图数据库返回的结果进行摘要，使用规则或模型生成精炼的知识表示，进一步地，这些结果同样可以进一步持久化，以供后续使用。
3. 层次化问答：

优先检索高层次的概念或关系，若需要更具体的细节，再进行二次检索。

## 如何消歧

知识图谱和语义检索经常会遇到歧义问题，例如同名实体（“Apple”是公司还是水果？）或多义词（“bank”是银行还是河岸？）。

**1. 上下文消歧：**

在向量数据库检索时，利用用户问题的上下文信息，增强歧义词的语义表示。 例如，问题“Apple 的市值是多少？ ”可以通过语义分析明确指代公司，而非水果。

**2. 实体类型约束：**

在图数据库中，对实体设置类型和属性约束。 例如，“Apple”作为公司时，必须有属性“行业=科技”。

**3. 反馈机制：**
在用户交互中，允许用户指定某个实体的含义。例如，用户可以选择“Apple 是公司”或“Apple 是水果”。

**4. 联合检索：**

通过向量数据库和图数据库的联合检索，利用两种方式相互验证实体的含义。例如，通过图谱确认“Apple”是否与“科技公司”相关。

# 五、总结

图数据库擅长描绘知识的结构，而向量数据库补充了语义的细节。在 RAG 系统中，它们各司其职，共同实现了高效、可解释的知识生成，从而可以应对更复杂场景和专业领域下的挑战。



探讨如何结合图数据库与向量数据库，构建高效的 RAG 系统

图数据库 VS 向量数据库？别选错了，真正的答案是这样！

分布式系统中的一致性模型的强弱和之前讲的事物的隔离级别层次有一些共通之处，比如在性能和隔离性/一致性间做取舍。

什么是分布式系统中的一致性？

时钟它为什么又是靠不住的。时钟（clocks）和时间（time）都很重要。

分布式系统中的麻烦事（中）：为什么时钟它不可靠？

我们在这篇文章中探讨了知识图谱，特别是图数据库 NebulaGraph，是如何结合 LlamaIndex 和 GPT-3.5 为 Philadelphia Phillies 队构建了一个 RAG。

7 种查询策略教你用好 Llama Index 和 NebulaGraph 探索知识图谱

分片，Partition，有很多别称。通用的有 Shard；具体到实际系统，HBase 中叫 Region，Bigtable 中叫 Tablet，等等。

DDIA精读｜分布式系统中的副本和分片、KV 分片、分片均衡，以及路由请求

单主模型一个最大问题：所有写入都要经过它，如果由于任何原因，客户端无法连接到主副本，就无法向数据库写入。

DDIA精读｜分布式数据之多副本的主从模型选择

*以下文章来源于木鸟杂记 ，作者穆尼奥*

![几种数据流模型](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231024-1.jpg)

上文[《性能好的编码如何设计？以常见的编码工具 JSON、CSV 等为例》](https://www.nebula-graph.com.cn/posts/encoding-serialization)中，逐一探讨了如何进行编码、如何进行多版本兼容。

在本篇文章中，会结合几个具体的应用场景：数据库、服务和消息系统，来分别谈了相关数据流中涉及到的编码与演化。

# 数据流模型

数据可以以很多种形式从一个系统流向另一个系统，但不变的是，流动时都需要编码与解码。

在数据流动时，会涉及编解码双方模式匹配问题，上文已经讨论，本文主要探讨几种进程间典型的数据流方式：

1. 通过数据库
2. 通过服务调用
3. 通过异步消息传递

# 经由数据库的数据流

访问数据库的程序，可能：

- **只由同一个进程访问**，则数据库可以理解为该进程向将来发送数据的中介。
- **由多个进程访问**，则多个进程可能有的是旧版本，有的是新版本，此时数据库需要考虑向前和向后兼容的问题。

还有一种比较棘手的情况：在某个时刻，你给一个表增加了一个字段，较新的代码写入带有该字段的行，之后又被较旧的代码覆盖成缺少该字段的行。这时候就会出现一个问题：我们更新了一个字段 A，更新完后，却发现字段 B 没了。

![经由数据库的数据流](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231024-3.png)

## 不同时间写入的数据

对于应用程序，可能很短时间就可以由旧版本替换为新版本。但是对于数据，旧版本的代码写入的数据量，经年累月，可能很大。在变更了模式之后，由于这些旧模式的数据量很大，全部更新对齐到新版本的代价很高。

这种情况我们称之为：**数据的生命周期超过了其对应代码的生命周期**。

在读取时，数据库一般会对缺少对应列的旧数据：

1. 填充新版本字段的默认值（default value）

2. 如果没有默认值则填充空值（nullable）

数据处理后，返回给用户。一般来说，在更改模式时（比如 alter table），数据库不允许增加既没有默认值、也不允许为空的列。

## 存储归档

有时候需要对数据库做备份到外存。在做备份（或者说快照）时，虽然会有不同时间点生成的数据，但通常会将各种版本数据转化、对齐到最新版本。毕竟，总是要全盘拷贝数据，那就顺便做下转换好了。

之前也提到了，对于这种场景，生成的是一次性的不可变的备份或者快照数据，使用 Avro 比较合适。此时也是一个很好的契机，可以将数据按需要的格式输出，比如面向分析的按列存储格式：Parquet。

# 经由服务的数据流：REST 和 RPC

通过网络通信时，通常涉及两种角色：服务器（server）和客户端（client）。

通常来说，暴露于公网的多为 HTTP 服务，而 RPC 服务常在内部使用。

服务器也可以同时是客户端：

1. 作为客户端访问数据库。

2. 作为客户端访问其他服务。

对于后者，是因为我们常把一个大的服务拆成一组功能独立、相对解耦的服务，这就是**面向服务的架构**（service-oriented architecture，SOA），或者最近比较火的**微服务架构**（micro-services architecture）。这两者有一些不同，但这里不再展开。

服务在某种程度上和数据库类似：允许客户端以某种方式存储和查询数据。但不同的是，数据库通常提供某种灵活的查询语言，而服务只能提供相对死板的 API。

## Web 服务

当服务使用 HTTP 作为通信协议时，我们通常将其称为 Web 服务。但其并不局限于 Web，还包括：

1. 用户终端（如移动终端）通过 HTTP 向服务器请求。

2. 同组织内的一个服务向另一个服务发送 HTTP 请求（微服务架构，其中的一些组件有时被称为中间件）。

3. 不同组织的服务进行数据交换。一般要通过某种手段进行验证，比如 OAuth。

有两种设计 HTTP API 的方法：REST 和 SOAP。

- **REST 并不是一种协议，而是一种设计哲学**。它强调简单的 API 格式，使用 URL 来标识资源，使用 HTTP 的动作（GET、POST、PUT、DELETE）来对资源进行增删改查。由于其简洁风格，越来越受欢迎。

- SOAP 是基于 XML 的协议。虽然使用 HTTP，但目的在于独立于 HTTP。现在提的比较少了。

## RPC 面临的问题

RPC 想让调用远端服务像调用本地（同进程中）函数一样自然，虽然设想比较好、现在用的也比较多，但也存在一些问题：

1. 本地函数调用要么成功、要么不成功。但是 RPC 由于经过网络，可能会有各种复杂情况，比如请求丢失、响应丢失、hang 住以至于超时等等。因此，可能需要重试。

2. 如果重试，需要考虑幂等性问题。因为上一次的请求可能已经到达了服务端，只是请求没有成功返回。那么多次调用远端函数，就要保证不会造成额外副作用。

3. 远端调用延迟不可用，受网络影响较大。

4. 客户端与服务端使用的编程语言可能不同，但如果有些类型不是两种语言都有，就会出一些问题。

REST 相比 RPC 的好处在于，它不试图隐去网络，更为显式，让使用者不易忽视网络的影响。

## RPC 当前方向

尽管有上述问题，但其实在工程中，大部分情况下，上述情况都在容忍范围内：

1. 比如局域网的网络通常比较快速、可控。

2. 多次调用，使用幂等性来解决。

3. 跨语言，可以使用 RPC 框架的 IDL 来解决。

但 RPC 程序需要考虑上面提到的极端情况，否则可能会偶然出一个很难预料的 BUG。

另外，基于二进制编码的 RPC 通常比基于 HTTP 服务效率更高。但 HTTP 服务，或者更具体一点，RESTful API 的好处在于，生态好、有大量的工具支持。而 RPC 的 API 通常和 RPC 框架生成的代码高度相关，因此很难在不同组织中无痛交换和升级。

因此，如本节开头所说：暴露于公网的多为 HTTP 服务，而 RPC 服务常在内部使用。

## 数据编码和 RPC 的演化

通过服务的数据流通常可以假设：所有的服务端先更新，然后客户端再更新。因此，只需要在请求里考虑后向兼容性，在响应中考虑前向兼容性：

1. Thrift、gRPC（Protobuf）和 Avro RPC 可以根据编码格式的兼容性规则进行演变。

2. RESTful API 通常使用 JSON 作为请求响应的格式，JSON 比较容易添加新的字段来进行演进和兼容。

3. SOAP 按下不表。

对于 RPC，服务的兼容性比较困难，因为一旦 RPC 服务的 SDK 提供出去之后，你就无法对其生命周期进行控制：总有用户因为各种原因，不会进行主动升级。因此可能需要长期保持兼容性，或者提前通知和不断预告，或者维护多个版本 SDK 并逐渐对早期版本进行淘汰。

对于 RESTful API，常用的兼容方法是，将版本号做到 URL 或者 HTTP 请求头中。

# 经由消息传递的数据流

前面研究了编码解码的不同方式：

- 数据库：一个进程写入（编码），将来一个进程读取（解码）

- RPC 和 REST：一个进程通过网络（发送前会编码）向另一个进程发送请求（收到后会解码）并同步等待响应。

本节研究介于数据库和 RPC 间的异步消息系统：一个存储（消息 broker、消息队列来临时存储消息）+ 两次 RPC（生产者一次，消费者一次）。

与 RPC 相比，使用消息队列的优点：

1. 如果消费者暂时不可用，可以充当暂存系统。

2. 当消费者宕机重启后，自动地重新发送消息。

3. 生产者不必知道消费者 IP 和端口。

4. 能将一条消息发送给多个消费者。

5. 将生产者和消费者解耦。

## 消息队列

书中用的是**消息代理（Message Broker）**，但另一个名字，消息队列，可能更为大家熟知，因此，本小节之后行文都用消息队列。

过去，消息队列为大厂所垄断。但近年来，开源的消息队列越来越多，可以适应不同场景，如 RabbitMQ、ActiveMQ、HornetQ、NATS 和 Apache Kafka 等等。

消息队列的送达保证因实现和配置而异，包括：

1. 最少一次（at-least-once）：同一条数据可能会送达多次给消费者。

2. 最多一次（at-most-once）：同一条数据最多会送达一次给消费者，有可能丢失。

3. 严格一次（exactly-once）：同一条数据保证会送达一次，且最多一次给消费者。

消息队列的逻辑抽象叫做 Queue 或者 Topic，常用的消费方式两种：

- 多个消费者互斥消费一个 Topic

- 每个消费者独占一个 Topic

注：我们有时会区分这两个概念：将点对点的互斥消费称为 Queue，多点对多点的发布订阅称为 Topic，但这并不通用，或者说没有形成共识。

一个 Topic 提供一个单向数据流，但可以组合多个 Topic，形成复杂的数据流拓扑。

消息队列通常是面向字节数组的，因此你可以将消息按任意格式进行编码。如果编码是前后向兼容的，同一个主题的消息格式，便可以进行灵活演进。

## 分布式的 Actor 框架

Actor 模型是一种基于消息传递的并发编程模型。Actor 通常是由状态（State）、行为（Behavior）和信箱（MailBox，可以认为是一个消息队列）三部分组成：

1. 状态：Actor 中包含的状态信息。

2. 行为：Actor 中对状态的计算逻辑。

3. 信箱：Actor 接受到的消息缓存地。

由于 Actor 和外界交互都是通过消息，因此本身可以并行的，且不需要加锁。

分布式的 Actor 框架，本质上是将消息队列和 actor 编程模型集成到一块。自然，在 Actor 滚动升级是，也需要考虑前后向兼容问题。



----
**谢谢你读完本文**(///▽///)

如果你想尝鲜图数据库 NebulaGraph，记得去 GitHub 下载、使用、(^з^)-☆ star 它 -> [GitHub](https://github.com/vesoft-inc/nebula)；如果你有更高的性能、易用性、运维实施等方面的需求，你也可以随时 [联系我们](https://www.nebula-graph.com.cn/contact)，获取进一步的帮助哦~

结合几个具体的应用场景：数据库、服务和消息系统，来分别谈了相关数据流中涉及到的编码与演化。

DDIA精读｜如何设计性能良好的编码？你该知道这几种数据流模型

![利用 ChatGLM 构建知识图谱 ](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231020-1.jpg)

# 为什么知识图谱需要大模型

在金融场景中，天然会有大量结构化的数据需要投入大量的人力去生产和维护，而这样的数据又会大量被应用在下游的标签、推荐、风控等场景。比如基金关联的基金经理，基金净值，基金重仓股等信息，需要从各个基金公司的公告信息中进行提取。

做个类比，在 1.0 时代，我们会利用大量的规则和人力去提取和校验相应的数据，但这种方法往往需要针对特定的文本内容去维护各自的规则，成本较高。在 2.0 时代我们可以构建相应的深度学习模型，去辅助完成 NER、实体链接等工作。 **在这个过程中，数据的清洗，标注和训练，往往需要非常专业的标注人员和算法开发参与，而且其准确率需要大量的工作来提高。** 在大模型时代，我们发现 ChatGPT 能以一个相对非常高的准确率去完成各式各样的任务，这也让我们有一个想法，是否可以利用大模型去辅助我们建设知识图谱（毕竟不是啥业务都上得起大模型，一个图谱能解决下游很多任务）。

通过一些实践发现，ChatGPT 的确可以根据海量文本数据自动生成实体、属性和关系三元组等知识元素，从而快速构建大规模的知识图谱。

# 利用 ChatGPT 构建知识图谱

社区里已经有不少利用 ChatGPT 甚至 GPT4 构建知识图谱的案例：

- ChatGPT+SmartKG 3分钟生成「哈利波特」知识图谱
- 使用 ChatGPT 从视频脚本创建知识图谱，使用 GPT-4 作为领域专家来帮助您从视频转录中提取知识

假设我们已经在图数据库中建了一些节点，囊括了所有上市公司，我们的目标是想构建一个关于上市公司的知识图谱，包括董事长，上市时间等信息。
这里推荐修改下面的代码，构建相应的知识图谱：**https://github.com/cocacola-lab/ChatIE**，我们只需将预设的实体类型和关系类型修改成我们需要的种类，就能实现零样本的大规模知识图谱构建，当然能用 GPT4 的话效果更佳。

# 本地部署的 ChatGLM 方案

考虑到本地部署的数据隐私问题，也可以将 ChatIE 中的 ChatGPT 接口换成 ChatGLM-6B，理论上可以接近 ChatGPT 的效果。

但在实际应用中，我们发现 ChatGLM 虽然具备了一定的内容抽取和链接能力，但是生成内容的可控性较差。

比如我们希望令模型按（实体1，实体2，…）或者 实体1 关系1 实体2 \n这样的格式输出结果，可以在大模型的输入中添加：不要编造答案，并严格按照（实体1，实体2，…）的格式回答，不要有额外内容“ 类似的话。

但往往结果中还是有大量不可控的内容，需要做大量的正则匹配去清洗数据。

在后来的尝试中，我们在 ChatGLM 中前置了两轮对话达到了较好的效果。具体的代码 demo 可以参考「利用 ChatGLM 进行金融知识抽取」，具体的效果演示参考下图：

![本地部署的 ChatGLM 方案](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/2023.1019.png)

当然这只是一个初级的 demo，后续还有更多利用 ES 和 NebulaGraph 进行校验和应用的代码，欢迎大家进行讨论。



----
**谢谢你读完本文**(///▽///)

如果你想尝鲜图数据库 NebulaGraph，记得去 GitHub 下载、使用、(^з^)-☆ star 它 -> [GitHub](https://github.com/vesoft-inc/nebula)；如果你有更高的性能、易用性、运维实施等方面的需求，你也可以随时 [联系我们](https://www.nebula-graph.com.cn/contact)，获取进一步的帮助哦~

在实际应用中，我们发现 ChatGLM 虽然具备了一定的内容抽取和链接能力，但是生成内容的可控性较差。

利用 ChatGLM 构建知识图谱 

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-1.jpg)

*编者按：在前文[《以 NoSQL 和 NewSQL 为例，讲解如何分析数据模型和考量查询语言》](https://www.nebula-graph.com.cn/posts/query-languages)中，木鸟同大家讲解了 SQL、NoSQL、NewSQL 的数据模型及查询语言。在本文中，他将会同大家分享图数据库特殊的数据模型及查询语言。*

上文提过的文档型数据库，和本文所说的图数据库，有什么区别？

* 文档模型的适用场景？你的数据集中存在着大量一对多（one-to-many）的关系。

* **图模型的适用场景**？你的数据集中存在大量的多对多（many-to-many）的关系。

下面开始展开讲讲图结构以及对应的图数据库。

# 基本概念

图数据模型的基本概念一般有三个：点，边和附着于两者之上的属性。常见的可以用图建模的场景：

![用图建模的场景](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-3.png)

同构（homogeneous）数据和异构数据，在图中的点可以都具有相同类型，但是，也可以具有不同类型，并且更为强大。

本节都会以下图为例，它表示了一对夫妇，来自美国爱达荷州的 Lucy 和来自法国 的 Alain。他们已婚，住在伦敦。

![同构（homogeneous）数据和异构数据](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-4.png)

有多种对图的建模方式：

* **属性图（property graph）**：比较主流，如 Neo4j、Titan、InfiniteGraph
* **三元组（triple-store）**：如 Datomic、AllegroGraph

# 属性图（PG，Property Graphs）

![多种对图的建模方式](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-5.png)

**Q**：有一个疑惑点，为什么书中对于 PG 点的定义中没有 Type？如果数据是异构的，应该有才对；莫非是通过不同的属性来标记不同的类型？

如果感觉不直观，可以使用我们熟悉的 SQL 语义来构建一个图模型，如下图。（Facebook TAO 论文中的单机存储引擎便是 MySQL）


```
// 点表
CREATE TABLE vertices (
 vertex_id integer PRIMARYKEY, properties json
);

// 边表
CREATE TABLE edges (
 edge_id integer PRIMARY KEY,
 tail_vertex integer REFERENCES vertices (vertex_id),
 head_vertex integer REFERENCES vertices (vertex_id),
 label text,
 properties json
);

// 对点的反向索引，图遍历时用。给定点，找出点的所有入边和出边。
CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);
```

图是一种很灵活的建模方式：

1. 任何两点间都可以插入边，没有任何模式限制。

2. 对于任何顶点都可以高效（思考：如何高效？）找到其入边和出边，从而进行图遍历。

3. 使用多种标签来标记不同类型边（关系）。

相对于关系型数据来说，**可以在同一个图中保存异构类型的数据和关系，给了图极大的表达能力！**

这种表达能力，根据图中的例子，包括：

1. 对同样的概念，可以用不同结构表示。如不同国家的行政划分。

2. 对同样的概念，可以用不同粒度表示。比如 Lucy 的现居住地和诞生地。

3. 可以很自然的进行演化。

将异构的数据容纳在一张图中，**可以通过图遍历，轻松完成关系型数据库中需要多次 Join 的操作**。

# Cypher 查询语言

Cypher 是 Neo4j 创造的一种查询语言。

Cypher 和 Neo 名字应该都是来自《黑客帝国》（The Matrix）。想想 Oracle。

Cypher 的一大特点是可读性强，尤其在表达路径模式（Path Pattern）时。

结合前图，看一个 Cypher 插入语句的例子：


```
CREATE
  (NAmerica:Location {name:'North America', type:'continent'}),
  (USA:Location      {name:'United States', type:'country'  }),
  (Idaho:Location    {name:'Idaho',         type:'state'    }),
  (Lucy:Person       {name:'Lucy' }),
  (Idaho) -[:WITHIN]->  (USA)  -[:WITHIN]-> (NAmerica),
  (Lucy)  -[:BORN_IN]-> (Idaho)
```

如果我们要进行一个这样的查询：找出所有从美国移居到欧洲的人名。

转化为图语言，即为：给定条件，BORN_IN 指向美国的地点，并且 LIVING_IN 指向欧洲的地点，找到所有符合上述条件的点，并且返回其名字属性。

用 Cypher 语句可表示为：


```
MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name
```

注意到：

1. 点 () ，边 -[]→，标签\类型 ：，属性{} 。

2. 名字绑定或者说变量：person

3. 0 到多次通配符：*0...

**正如声明式查询语言的一贯特点，你只需描述问题，不必担心执行过程。但与 SQL 的区别在于，SQL 基于关系代数，Cypher 类似正则表达式。**

无论是 BFS、DFS 还是剪枝等实现细节，都不需要关心。

# 使用 SQL 进行图查询

前面看到可以用 SQL 存储点和边，以表示图。

那可以用 SQL 进行图查询吗？

Oracle 的 PGQL：


```
CREATE PROPERTY GRAPH bank_transfers
     VERTEX TABLES (persons KEY(account_number))
     EDGE TABLES(
                  transactions KEY (from_acct, to_acct, date, amount)
                  SOURCE KEY (from_account) REFERENCES persons
                  DESTINATION KEY (to_account) REFERENCES persons
                  PROPERTIES (date, amount)
       )
```

其中有一个难点，就是如何表达图中的路径模式（graph pattern），如多跳查询，对应到 SQL 中，就是不确定次数的 Join：


```
() -[:WITHIN*0..]-> ()
```

使用 SQL:1999 中 recursive common table expressions（PostgreSQL, IBM DB2, Oracle, and SQL Server 支持）的可以满足。但是，相当冗长和笨拙。

# Triple-Stores and SPARQL

Triple-Stores，可以理解为三元组存储，即用三元组存储图。

![Triple-Stores and SPARQL](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-6.png)

其含义如下：

![Triple-Stores](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-7.png)

仍是上边例子，用 Turtle triples (一种 Triple-Stores 语法）表达为：


```
@prefix : <urn:example:>.
_:lucy     a       :Person.
_:lucy     :name   "Lucy".
_:lucy     :bornIn _:idaho.
_:idaho    a       :Location.
_:idaho    :name   "Idaho".
_:idaho    :type   "state".
_:idaho    :within _:usa.
_:usa      a       :Location
_:usa      :name   "United States"
_:usa      :type   "country".
_:usa      :within _:namerica.
_:namerica a       :Location.
_:namerica :name   "North America".
_:namerica :type   "continent".
```

一种更紧凑的写法：


```
@prefix : <urn:example:>.
_:lucy     a: Person;   :name "Lucy";          :bornIn _:idaho
_:idaho    a: Location; :name "Idaho";         :type "state";     :within _:usa.
_:usa      a: Location; :name "United States"; :type "country";   :within _:namerica.
_:namerica a :Location; :name "North America"; :type "continent".
```

## 语义网（The Semantic Web）

万维网之父 Tim Berners Lee 于 1998 年提出，知识图谱前身。其目的在于对网络中的资源进行结构化，从而让计算机能够理解网络中的数据。即不是以文本、二进制流等等，而是通过某种标准结构化互相关联的数据。

**语义**：提供一种统一的方式对所有资源进行描述和结构化（机器可读）。

**网**：将所有资源勾连起来。

下面是**语义网技术栈**（Semantic Web Stack）：

![语义网技术栈](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-8.png)

其中 **RDF** （ResourceDescription Framework，资源描述框架）提供了一种结构化网络中数据的标准。使发布到网络中的任何资源（文字、图片、视频、网页），都能以统一的形式被计算机理解。即，不需要让资源使用方深度学习抽取资源的语义，而是靠资源提供方通过 RDF 主动提供其资源语义。

感觉有点理想主义，但互联网、开源社区都是靠这种理想主义、分享精神发展起来的！

虽然语义网没有发展起来，但是其中间数据交换格式 RDF 所定义的 SPO 三元组 (Subject-Predicate-Object) 却是一种很好用的数据模型，也就是上面提到的 **Triple-Stores**。

## RDF 数据模型

上面提到的 Turtle 语言（SPO 三元组）是一种简单易读的描述 RDF 数据的方式，RDF 也可以基于 XML 表示，但是要冗余难读的多（嵌套太深）：


```
<rdf:RDF xmlns="urn:example:"
 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
 <Location rdf:nodeID="idaho">
  <name>Idaho</name>
  <type>state</type>
  <within>
   <Location rdf:nodeID="usa">
    <name>United States</name>
    <type>country</type>
    <within>
     <Location rdf:nodeID="namerica">
      <name>North America</name>
      <type>continent</type>
       </Location>
      </within>
      </Location>
    </within>
 </Location>
 <Person rdf:nodeID="lucy">
  <name>Lucy</name>
  <bornIn rdf:nodeID="idaho"/>
 </Person>
</rdf:RDF>
```

为了标准化和去除二义性，一些看起来比较奇怪的点是：无论 subject，predicate 还是 object 都是由 URI 定义，如：


```
lives_in 会表示为 <http://my-company.com/namespace#lives_in>
```

其前缀只是一个 namespace，让定义唯一化，并且在网络上可访问。当然，一个简化的方法是可以在文件头声明一个公共前缀。

## SPARQL 查询语言

有了语义网，自然需要在语义网中进行遍历查询，于是有了 RDF 的查询语言：SPARQL Protocol and RDF Query Language, pronounced“sparkle.”


```
PREFIX : <urn:example:>
SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn  / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}
```

他是 Cypher 的前驱，因此结构看起来很像：


```
(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (location)   # Cypher
?person   :bornIn /        :within*        ?location.   # SPARQL
```

但 SPARQL 没有区分边和属性的关系，都用了 Predicates。


```
(usa {name:'United States'})   # Cypher
?usa :name "United States".    # SPARQL
```

虽然语义网没有成功落地，但其技术栈影响了后来的知识图谱和图查询语言。

## 图模型和网络模型

图模型是网络模型旧瓶装新酒吗？

否，他们在很多重要的方面都不一样。

![图模型和网络模型](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-9.png)

# 查询语言前驱：Datalog

有点像 triple-store，但是变了下次序：(subject, predicate, object) → predicate(subject, object). 之前数据用 Datalog 表示为：


```
name(namerica, 'North America').
type(namerica, continent).

name(usa, 'United States').
type(usa, country).
within(usa, namerica).

name(idaho, 'Idaho').
type(idaho, state).
within(idaho, usa).

name(lucy, 'Lucy').
born_in(lucy, idaho).
```

查询从美国迁移到欧洲的人可以表示为：


```
within_recursive(Location, Name) :- name(Location, Name). /* Rule 1 */
within_recursive(Location, Name) :- within(Location, Via), /* Rule 2 */
                                    within_recursive(Via, Name).

migrated(Name, BornIn, LivingIn) :- name(Person, Name), /* Rule 3 */
                                    born_in(Person, BornLoc),
                                    within_recursive(BornLoc, BornIn),
                                    lives_in(Person, LivingLoc),
                                    within_recursive(LivingLoc, LivingIn).
?- migrated(Who, 'United States', 'Europe'). /* Who = 'Lucy'. */
```

1. 代码中以大写字母开头的元素是变量，字符串、数字或以小写字母开头的元素是常量。下划线（_）被称为匿名变量

2. 可以使用基本 Predicate 自定义 Predicate，类似于使用基本函数自定义函数。

3. 逗号连接的多个谓词表达式为且的关系。

![用基本 Predicate 自定义 Predicate](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/20231011-10.png)

基于集合的逻辑运算：

1. 根据基本数据子集选出符合条件集合。

2. 应用规则，扩充原集合。

3. 如果可以递归，则递归穷尽所有可能性。

Prolog（Programming in Logic 的缩写）是一种逻辑编程语言。它创建在逻辑学的理论基础之上。

# 参考

1. 声明式 (declarative) vs 命令式 (imperative)：https://lotabout.me/2020/Declarative-vs-Imperative-language/

2. SimmerChan 知乎专栏，知识图谱，语义网，RDF：https://www.zhihu.com/column/knowledgegraph

3. MySQL 为什么叫“关系”模型：https://zhuanlan.zhihu.com/p/64731206

----
**谢谢你读完本文**(///▽///)

如果你想尝鲜图数据库 NebulaGraph，记得去 GitHub 下载、使用、(^з^)-☆ star 它 -> [GitHub](https://github.com/vesoft-inc/nebula)；如果你有更高的性能、易用性、运维实施等方面的需求，你也可以随时 [联系我们](https://www.nebula-graph.com.cn/contact)，获取进一步的帮助哦~

图数据模型的基本概念一般有三个：点，边和附着于两者之上的属性。将同大家分享图数据库特殊的数据模型及查询语言。

DDIA 精读｜以 图数据库 为例，讲解如何分析数据模型和考量查询语言

> 以下文章来源于木鸟杂记 ，作者穆尼奥。

![SQL、NewSQL、NoSQL 数据库的数据模型以及其查询语言](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/DDIA%20banner_%E7%94%BB%E6%9D%BF%201%20%E5%89%AF%E6%9C%AC%208.jpg)

> 编者按：在前文《一个优秀的数据系统该具备的三个特性：可靠、可扩展、可维护》中，木鸟讲解了同数据系统相关的优秀特性。本文系《DDIA 精读小册》的第二篇，将原先的“数据模型和查询语言”章节拆分成了上下篇。本文为上篇，着重讲解同 SQL、NewSQL、NoSQL 数据库的数据模型以及其查询语言。

本文围绕两个主要概念来展开。

**1. 如何分析一个数据模型：**

- **基本考察点**：数据基本元素，和元素之间的对应关系（一对多，多对多）
- **利用几种常用模型来比较**：（最为流行的）关系模型，（树状的）文档模型，（极大自由度的）图模型。其中，图模型将作为“数据模型和查询语言”的下篇主角，和大家见面；
- **schema 模式**：强 Schema（写时约束）；弱 Schema（读时解析）

**2. 如何考量查询语言：**

- 如何与数据模型关联、匹配
- 声明式（declarative）和命令式（imperative）

# 数据模型

> “A data model is an abstract model that organizes elements of data and standardizes how they relate to one another and to the properties of real-world entities.” - 摘录自 https://en.wikipedia.org/wiki/Data_model”

数据模型：如何组织数据，如何标准化关系，如何关联现实。

它既决定了我们构建软件的方式（实现），也左右了我们看待问题的角度（认知）。

作者开篇以计算机的不同抽象层次来让大家对泛化的数据模型有个整体观感。

大多数应用都是通过不同的数据模型层级累进构建的。

![如何分析数据模型](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/NoSQL%20%E5%92%8C%20NewSQL1.png)

每层模型核心问题：如何用下一层的接口来对本层进行建模？

- 作为应用开发者， 你将现实中的具体问题抽象为一组对象、数据结构（data structure） 以及作用于其上的 API。
- 作为数据库管理员（DBA），为了持久化上述数据结构，你需要将他们表达为通用的数据模型（data model），如文档数据库中的 XML/JSON、关系数据库中的表、图数据库中的图。
- 作为数据库系统开发者，你需要将上述数据模型组织为内存中、硬盘中或者网络中的字节（Bytes） 流，并提供多种操作数据集合的方法。
- 作为硬件工程师，你需要将字节流表示为二极管的电位（内存）、磁场中的磁极（磁盘）、光纤中的光信号（网络）。

在每一层，通过对外暴露简洁的数据模型，我们隔离和分解了现实世界的复杂度。

这也反过来说明了，好的数据模型需有两个特点：
1. **简洁直观**
2. **具有组合性**

# 关系模型与文档模型

## 关系模型

关系模型无疑是当今最流行的数据库模型。

关系模型是 埃德加·科德（E. F. Codd）于 1969 年首先提出，并用“科德十二定律”来解释。但是商业落地的数据库基本没有能完全遵循的，因此关系模型后来通指这一类数据库。特点如下：
1. 将数据以关系呈现给用户（比如：一组包含行列的二维表）。
2. 提供操作数据集合的关系算子。

### **常见分类**
1. 事务型（TP）：银行交易、火车票
2. 分析型（AP）：数据报表、监控表盘
3. 混合型（HTAP）

关系模型诞生很多年后，虽有不时有各种挑战者（比如上世纪七八十年代的**网状模型** network model 和**层次模型** hierarchical model），但始终仍未有根本的能撼动其地位的新模型。

直到近十年来，随着移动互联网的普及，数据爆炸性增长，各种处理需求越来越精细化，催生了数据模型的百花齐放。

## NoSQL 的诞生

NoSQL（最初表示 Non-SQL，后来有人转解为 Not only SQL），是对不同于传统的关系数据库的数据库管理系统的统称。根据 DB-Engines 排名，现在最受欢迎的 NoSQL 前几名为：MongoDB，Redis，ElasticSearch，Cassandra。

其催动因素有：
1. **处理更大数据集**：更强伸缩性、更高吞吐量
2. **开源免费的兴起**：冲击了原来把握在厂商的标准
3. **特化的查询操作**：关系数据库难以支持的，比如图中的多跳分析
4. **表达能力更强**：关系模型约束太严，限制太多

## 面向对象和关系模型的不匹配

核心冲突在于面向对象的嵌套性和关系模型的平铺性（该词是作者编造，如果有更好的翻译版，欢迎交流~）。

当然有 ORM 框架可以帮我们搞定这些事情，但仍是不太方便。

![NoSQL 的诞生](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/NoSQL%20%E5%92%8C%20NewSQL%202.png)

换另一个角度来说，关系模型很难直观的表示一对多的关系。比如简历上，一个人可能有多段教育经历和多段工作经历。

文档模型：使用 Json 和 XML 的天然嵌套。

关系模型：使用 SQL 模型就得将职位、教育单拎一张表，然后在用户表中使用外键关联。

在简历的例子中，文档模型还有几个优势：
1. **模式灵活**：可以动态增删字段，如工作经历。
2. **更好的局部性**：一个人的所有属性被集中访问的同时，也被集中存储。
3. **结构表达语义**：简历与联系信息、教育经历、职业信息等隐含一对多的树状关系可以被 JSON 的树状结构明确表达出来。

## 多对一和多对多
 
是一个对比各种数据模型的切入角度。

region 在存储时，为什么不直接存储纯字符串：“Greater Seattle Area”，而是先存为 region_id → region name，其他地方都引用 region_id？

1. **统一样式**：所有用到相同概念的地方都有相同的拼写和样式
2. **避免歧义**：可能有同名地区
3. **易于修改**：如果一个地区改名了，我们不用去逐一修改所有引用他的地方
4. **本地化支持**：如果翻译成其他语言，可以只翻译名字表。
5. **更好搜索**：列表可以关联地区，进行树形组织

类似的概念还有：面向抽象编程，而非面向细节。

关于用 ID 还是文本，作者提到了一点：ID 对人类是无意义的，无意义的意味着不会随着现实世界的将来的改变而改动。

这在关系数据库表设计时需要考虑，即如何控制冗余（duplication）。会有几种范式（normalization） 来消除冗余。

文档型数据库很擅长处理一对多的树形关系，却不擅长处理多对多的图形关系。如果其不支持 Join，则处理多对多关系的复杂度就从数据库侧移动到了应用侧。

如，多个用户可能在同一个组织工作过。如果我们想找出在同一个学校和组织工作过的人，如果数据库不支持 Join，则需要在应用侧进行循环遍历来 Join。

文档 vs 关系

1. 对于一对多关系，文档型数据库将嵌套数据放在父节点中，而非单拎出来放另外一张表。
2. 对于多对一和多对多关系，本质上，两者都是使用外键（文档引用）进行索引。查询时需要进行 join 或者动态跟随。

## 文档模型是否在重复历史？

### **层次模型** （hierarchical model）

20 世纪 70 年代，IBM 的信息管理系统 IMS。

“A hierarchical database model is a data model in which the data are organized into a tree-like structure. The data are stored as records which are connected to one another through links. A record is a collection of fields, with each field containing only one value. The type of a record defines which fields the record contains. — wikipedia”

几个要点：
1. 树形组织，每个子节点只允许有一个父节点
2. 节点存储数据，节点有类型
3. 节点间使用类似指针方式连接

可以看出，它跟文档模型很像，也因此很难解决多对多的关系，并且不支持 Join。

为了解决层次模型的局限，人们提出了各种解决方案，最突出的是：
1. 关系模型
2. 网状模型

### **网状模型**（network model）

network model 是 hierarchical model 的一种扩展：允许一个节点有多个父节点。它被数据系统语言会议（CODASYL）的委员会进行了标准化，因此也被称为 CODASYL 模型。

多对一和多对多都可以由路径来表示。访问记录的唯一方式是顺着元素和链接组成的链路进行访问，这个链路叫访问路径 （access path）。难度犹如在 n-维空间中进行导航。

内存有限，因此需要严格控制遍历路径。并且需要事先知道数据库的拓扑结构，这就意味着得针对不同应用写大量的专用代码。

### **关系模型**

在关系模型中，数据被组织成元组（tuples），进而集合成关系（relations）；在 SQL 中分别对应行（rows）和表（tables）。

- 不知道大家好奇过没，明明看起来更像表模型，为什叫关系模型？表只是一种实现。关系（relation）的说法来自集合论，指的是几个集合的笛卡尔积的子集。 **R ⊆（D1×D2×D3 ··· ×Dn）**（关系用符号 R 表示，属性用符号 Ai 表示，属性的定义域用符号 Di 表示）

其主要目的和贡献在于提供了一种声明式的描述数据和构建查询的方法。

即，相比网络模型，关系模型的查询语句和执行路径相解耦，查询优化器（Query Optimizer 自动决定执行顺序、要使用的索引），即将逻辑和实现解耦。

举个例子：如果想使用新的方式对你的数据集进行查询，你只需要在新的字段上建立一个索引。那么在查询时，你并不需要改变的你用户代码，查询优化器便会动态的选择可用索引。

## 文档型 vs 关系型

### **根据数据类型来选择数据模型**

![文档型 vs 关系型图数据库](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/NoSQL%20%E5%92%8C%20NewSQL%203.png)

对于高度关联的数据集，使用文档型表达比较奇怪，使用关系型可以接受，使用图模型最自然。

### **文档模型中 Schema 的灵活性**

说文档型数据库是 schemaless 不太准确，更贴切的应该是 schema-on-read。

![文档型数据库](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/NoSQL%20%E5%92%8C%20NewSQL%204.png)

文档型数据库使用场景特点：
- 有多种类型的数据，但每个放一张表又不合适。
- 数据类型和结构又外部决定，你没办法控制数据的变化。

### **查询时的数据局部性**

如果你同时需要文档中所有内容，把文档顺序存会效率比较高。

但如果你只需要访问文档中的某些字段，则文档仍需要将文档全部加载出。

但运用这种局部性不局限于文档型数据库。不同的数据库，会针对不同场景，调整数据物理分布以适应常用访问模式的局部性。
- 如 Spanner 中允许表被声明为嵌入到父表中——**常见关联内嵌**
- HBase 和 Cassandra 使用列族来聚集数据——**分析型**
- 图数据库中，将点和出边存在一个机器上——**图遍历**

### **关系型和文档型的融合**

- MySQL 和 PostgreSQL 开始支持 JSON。原生支持 JSON 可以理解为，MySQL 可以理解 JSON 格式。如 Date 格式一样，可以把某个字段作为 JSON 格式，可以修改其中的某个字段，可以在其中某个字段建立索引。
- RethinkDB 在查询中支持 relational-link Joins

科德（Codd）：nonsimple domains，记录中的值除了简单类型（数字、字符串），还可以一个嵌套关系（表）。这很像 SQL 对 XML、JSON 的支持。

# 数据查询语言

获取动物表中所有鲨鱼类动物。


```
function getSharks() {
  var sharks = [];
  for (var i = 0; i < animals.length; i++) {
    if (animals[i].family === 'Sharks') {
      sharks.push(animals[i]);
    }
  }
  return sharks;
}
```


```
SELECT * FROM animals WHERE family = 'Sharks';
```

![图数据库数据查询语言](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/NoSQL%20%E5%92%8C%20NewSQL%205.png)

Q：**相对声明式语言，命令式语言有什么优点？**

当描述的目标变得复杂时，声明式表达能力不够。

实现命令式的语言往往不会和声明式那么泾渭分明，通过合理抽象，通过一些编程范式（函数式），可以让代码兼顾表达力和清晰性。

## 数据库以外：Web 中的声明式

需求：选中页背景变蓝。


```
<ul>
  <li class="selected">
    <p>Sharks</p>
    <ul>
      <li>Great White Shark</li>
      <li>Tiger Shark</li>
      <li>Hammerhead Shark</li>
    </ul>
  </li>
  <li>
    <p>Whales</p>
    <ul>
      <li>Blue Whale</li>
      <li>Humpback Whale</li>
      <li>Fin Whale</li>
    </ul>
  </li>
</ul>
```

如果使用 CSS，则只需（CSS selector）：


```
li.selected > p {
  background-color: blue;
}
```

如果使用 XSL，则只需（XPath selector）：


```
<xsl:template match="li[@class='selected']/p">
 <fo:block background-color="blue">
  <xsl:apply-templates/>
 </fo:block>
</xsl:template>
```

但如果使用 JavaScript（而不借助上述 selector 库）：


```
var liElements = document.getElementsByTagName('li');
for (var i = 0; i < liElements.length; i++) {
  if (liElements[i].className === 'selected') {
    var children = liElements[i].childNodes;
    for (var j = 0; j < children.length; j++) {
      var child = children[j];
      if (child.nodeType === Node.ELEMENT_NODE && child.tagName === 'P') {
        child.setAttribute('style', 'background-color: blue');
      }
    }
  }
}
```

## MapReduce 查询

Google 的 MapReduce 模型
- 借鉴自函数式编程。
- 一种相当简单的编程模型，或者说原子的抽象，现在不太够用。
- 但在大数据处理工具匮乏的蛮荒时代（03 年以前），谷歌提出的这套框架相当有开创性。

![图数据库分析数据模型](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/NoSQL%20%E5%92%8C%20NewSQL%206.png)

### **MongoDB 的 MapReduce 模型**

MongoDB 使用的 MapReduce 是一种介于
- 声明式：用户不必显式定义数据集的遍历方式、shuffle 过程等执行过程。
- 命令式：用户又需要定义针对单条数据的执行过程。

两者间的混合数据模型。

需求：统计每月观察到鲨类鱼的次数。

查询语句：

PostgresSQL


```
SELECT date_trunc('month', observation_timestamp) AS observation_month,
 sum(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks' GROUP BY observation_month;
```

MongoDB


```
db.observations.mapReduce(
  function map() {
    // 2. 对所有符合条件 doc 执行 map
    var year = this.observationTimestamp.getFullYear();
    var month = this.observationTimestamp.getMonth() + 1;
    emit(year + '-' + month, this.numAnimals); // 3. 输出一个 kv pair
  },
  function reduce(key, values) {
    // 4. 按 key 聚集
    return Array.sum(values); // 5. 相同 key 加和
  },
  {
    query: { family: 'Sharks' }, // 1. 筛选
    out: 'monthlySharkReport', // 6. reduce 结果集
  }
);
```

上述语句在执行时，经历了：**筛选 → 遍历并执行 map → 对输出按 key 聚集（shuffle） → 对聚集的数据注意 reduce → 输出结果集**。

MapReduce 一些特点：
- **要求 Map 和 Reduce 是纯函数**。即无任何副作用，在任意地点、以任意次序执行任何多次，对相同的输入都能得到相同的输出。因此容易并发调度。
- **非常底层、但表达力强大的编程模型**。可基于其实现 SQL 等高级查询语言，如 Hive。

但要注意：
- 不是所有的分布式 SQL 都基于 MapReduce 实现。
- 不是只有 MapReduce 才允许嵌入通用语言（如 js）模块。
- MapReduce 是有一定理解成本的，需要熟悉其执行逻辑才能让两个函数紧密配合。

MongoDB 2.2+ 进化版，aggregation pipeline:


```
db.observations.aggregate([
  { $match: { family: 'Sharks' } },
  {
    $group: {
      _id: {
        year: { $year: '$observationTimestamp' },
        month: { $month: '$observationTimestamp' },
      },
      totalAnimals: { $sum: '$numAnimals' },
    },
  },
]);
```

----
**谢谢你读完本文**(///▽///)

如果你想尝鲜图数据库 NebulaGraph，记得去 GitHub 下载、使用、(^з^)-☆ star 它 -> [GitHub](https://github.com/vesoft-inc/nebula)；如果你有更高的性能、易用性、运维实施等方面的需求，你也可以随时 [联系我们](https://www.nebula-graph.com.cn/contact)，获取进一步的帮助哦~

SQL、NewSQL、NoSQL 数据库的数据模型以及其查询语言。