原文链接

顾名思义，就是记录key和对应value hash的一棵二叉树。

树的形态

通过每层hash来校验数据块

如果要求严苛，hash函数需要用安全的xxhash之类的。如果要求仅仅是校验 crc即可

原文链接 https://medium.com/@dgryski/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8

加了很多自己的理解

• 没有锁，spdlog是mpmc+锁的模式，nanolog是spsc组合模式

• 二进制日志写入，没有写放大

论文地址 https://www.usenix.org/system/files/conference/atc18/atc18-yang.pdf

这里有一篇介绍 https://zhuanlan.zhihu.com/p/136208506还有很多优化的点子，比如cache miss，比如tsc读时间

鸽了

原文 https://www.fluentcpp.com/2021/02/05/how-stdany-works/

https://www.fluentcpp.com/2021/01/29/inheritance-without-pointers/

我加了个人的理解，大家英文好的去看原文

我感觉看不完了

另外，趁着假期，把知乎收藏夹/微博收藏夹和印象笔记都整理一下

引自 https://ericfu.me/yugabyte-db-introduction/

系统架构

逻辑上，Yugabyte 采用两层架构：查询层和存储层。不过这个架构仅仅是逻辑上的，部署结构中，这两层都位于 TServer 进程中。这一点和 TiDB 不同。

Yugabyte 的查询层支持同时 SQL 和 CQL 两种 API，其中 CQL 是兼容 Cassandra 的一种方言语法，对应于文档数据库的存储模型；而 SQL API 是直接基于 PostgresQL 魔改的，能比较好地兼容 PG 语法，据官方说这样可以更方便地跟随 PG 新特性，有没有官方说的这么美好我们就不得而知了。

Yugabyte 的存储层才是重头戏。其中 TServer 负责存储 tablet，每个 tablet 对应一个 Raft Group，分布在三个不同的节点上，以此保证高可用性。Master 负责元数据管理，除了 tablet 的位置信息，还包括表结构等信息。Master 本身也依靠 Raft 实现高可用。

基于 Tablet 的分布式存储

这一部分是 HBase/Spanner 精髓部分，Cockroach/TiDB 的做法几乎也是一模一样的。如下图所示，每张表被分成很多个 tablet，tablet 是数据分布的最小单元，通过在节点间搬运 tablet 以及 tablet 的分裂与合并，就可以实现几乎无上限的 scale out。每个 tablet 有多个副本，形成一个 Raft Group，通过 Raft 协议保证数据的高可用和持久性，Group Leader 负责处理所有的写入负载，其他 Follower 作为备份。

下图是一个例子：一张表被分成 16 个 tablet，tablet 的副本和 Raft Group leader 均匀分布在各个节点上，分别保证了数据的均衡和负载的均衡。

和其他产品一样，Master 节点会负责协调 tablet 的搬运、分裂等操作，保证集群的负载均衡。这些操作是直接基于 Raft Group 实现的。这里就不再展开了。

有趣的是，Yugabyte 采用哈希和范围结合的分区方式：可以只有哈希分区、也可以只有范围分区、也可以先按哈希再按范围分区。之所以这么设计，猜测也是因为 Cassandra 的影响。相比之下，TiDB 和 Cockroach 都只支持范围分区。

哈希分区的方式是将 key 哈希映射到 2 字节的空间中（即 0x0000 到 0xFFFF），这个空间又被划分成多个范围，比如下图的例子中被划分为 16 个范围，每个范围的 key 落在一个 tablet 中。理论上说最多可能有 64K 个 tablet，这对实际使用足够了。

哈希分区的好处是插入数据（尤其是从尾部 append 数据）时不会出现热点；坏处是对于小范围的范围扫描（例如 pk BETWEEN 1 AND 10）性能会比较吃亏。

基于 RocksDB 的本地存储

每个 TServer 节点上的本地存储称为 DocDB。和 TiDB/Cockroach 一样，Yugabyte 也用 RocksDB 来做本地存储。这一层需要将关系型 tuple 以及文档编码为 key-value 保存到 RocksDB 中，下图是对文档数据的编码方式，其中有不少是为了兼容 Cassandra 设计的，我们忽略这些，主要关注以下几个部分：

• key 中包含
• 16-bit hash：依靠这个值才能做到哈希分区
• 主键数据（对应图中 hash/range columns）
• column ID：因为每个 tuple 有多个列，每个列在这里需要用一个 key-value 来表示
• hybrid timestamp：用于 MVCC 的时间戳
• value 中包含
• column 的值

如果撇开文档模型，key-value 的设计很像 Cockroach：每个 cell （一行中的一列数据）对应一个 key-value。而 TiDB 是每个 tuple 打包成一个 key-value。个人比较偏好 TiDB 的做法。

分布式事务：2PC & MVCC

和 TiDB/Cockroach 一样，Yugabyte 也采用了 MVCC 结合 2PC 的事务实现。

时间戳

时间戳是分布式事务的关键选型之一。Yugabyte 和 Cockroach 一样选择的是 Hybrid Logical Clock (HLC)。

HLC 将时间戳分成物理（高位）和逻辑（低位）两部分，物理部分对应 UNIX 时间戳，逻辑部分对应 Lamport 时钟。在同一毫秒以内，物理时钟不变，而逻辑时钟就和 Lamport 时钟一样处理——每当发生信息交换（RPC）就需要更新时间戳，从而确保操作与操作之间能够形成一个偏序关系；当下一个毫秒到来时，逻辑时钟部分归零。

不难看出，HLC 的正确性其实是由 Logical Clock 来保证的：它相比 Logical Clock 只是在每个毫秒引入了一个额外的增量，显然这不会破坏 Logical Clock 的正确性。但是，物理部分的存在将原本无意义的时间戳赋予了物理意义，提高了实用性。

个人认为，HLC 是除了 TrueTime 以外最好的时间戳实现了，唯一的缺点是不能提供真正意义上的外部一致性，仅仅能保证相关事务之间的“外部一致性”。另一种方案是引入中心授时节点（TSO），也就是 TiDB 使用的方案。TSO 方案要求所有事务必须从 TSO 获取时间戳，实现相对简单，但引入了更多的网络 RPC，而且 TSO 过于关键——短时间的不可用也是极为危险的。

HLC 的实现中有一些很 tricky 的地方，比如文档中提到的 Safe timestamp assignment for a read request。对于同一事务中的多次 read，问题还要更复杂，有兴趣的读者可以看 Cockroach 团队的这篇博客 Living Without Atomic Clocks。

事务提交

毫不惊奇，Yugabyte 的分布式事务同样是基于 2PC 的。他的做法接近 Cockroach。事务提交过程中，他会在 DocDB 存储里面写入一些临时的记录（provisional records），包括以下三种类型：

• Primary provisional records：还未提交完成的数据，多了一个事务ID，也扮演锁的角色
• Transaction metadata：事务状态所在的 tablet ID。因为事务状态表很特殊，不是按照 hash key 分片的，所以需要在这里记录一下它的位置。
• Reverse Index：所有本事务中的 primary provisional records，便于恢复使用

事务的状态信息保存在另一个 tablet 上，包括三种可能的状态：Pending、Committed 或 Aborted。事务从 Pending 状态开始，终结于 Committed 或 Aborted。

事务状态就是 Commit Point 的那个“开关”，当事务状态切换到 Commited 的一瞬间，就意味着事务的成功提交。这是保证整个事务原子性的关键。

完整的提交流程如下图所示：

另外，Yugabyte 文档中提到它除了 Snapshot Isolation 还支持 Serializable 隔离级别，但是似乎没有看到他是如何规避 Write Skew 问题的。

参考

1. Yugabyte DB
2. Yugabyte DB Documents
3. Living Without Atomic Clocks - Cockroach Labs
4. https://ericfu.me/yugabyte-db-introduction/

最近在网上看到一篇抓堆栈的脚本工具介绍

工具还挺漂亮的，但是我的问题在于

1. perl写的，还依赖魔改ag，首先我看不懂，其次部署使用稍微有点成本(我看评论区有人帮忙打包)，然后是参数费解有点学习成本
   1. 主要是我看不懂，不是我写的，我可能就只会简单的查
2. 调用细节可能不够清晰，虽然足够用了

所以有了两个想法

1. 学一下perl，改写成python的工具？搜了一圈perl2python没有工具能用

2. 能不能用clang的工具？

PS：如何导出compliation database，也就是compile_commands.json

我折腾了半天导出，但是我根本用不到，这里把折腾记录放在下面

compilation database是clang/llvm的一个功能，作为一个语言后端支持language support protocol，需要有能力导出符号

所有的标记符号可以汇总成这个compilation database (clangd就是这个功能，对解析好的compilation database进行服务化，支持IDE的查询)

背后的技术是libclang，也有很多例子，这里就不展开了，可以看这个链接

既然都能支持IDE，难道还不能支持简单的函数调用查看，调用图生成吗，我似乎找到了新方案

但是这些方案都躲不开编译一遍，虽然只是简单的parser一遍，没有那么慢, 后面如果有时间，改写成python更好一些

如果编译环境是bazel，有https://github.com/grailbio/bazel-compilation-database支持

简单来说，就是改项目的BUILD和WORKSPACE

BUILD要加上

## Replace workspace_name and dir_path as per your setup.
load("@com_grail_bazel_compdb//:aspects.bzl", "compilation_database")

compilation_database(
    name = "compdb",
    targets = [
        "yourtargetname",
    ],
)

这里target写你自己的target，可以多个target分割，name随便，这里我写成compdb

然后WORKSPACE要加上

http_archive(
    name = "com_grail_bazel_compdb",
    strip_prefix = "bazel-compilation-database-master",
    urls = ["https://github.com/grailbio/bazel-compilation-database/archive/master.tar.gz"],
)

最后编译

bazel build //path/yourtargetnamedir:compdb

就生成compile_commands.json了

其他编译环境，用bear

bear本身支持macos和linux，尝试命令行安装一下，安装不上的话源码安装

如果是makefile系列的编译系统，直接

bear -- make

就可以了，这里以memcached为例子

用python解析

PS：

如果遇到报错

    raise LibclangError(msg)
clang.cindex.LibclangError: dlopen(libclang.dylib, 6): image not found. To provide a path to libclang use Config.set_library_path() or Config.set_library_file().

说明找不到libclang，需要指定一下，比如

export DYLD_LIBRARY_PATH=/usr/local/Cellar/llvm/11.0.0/lib/

这篇文章很有干货，整理一下 https://www.evanjones.ca/durability-filesystem.html

flag和函数的区别是：flag表示每次io操作都会执行，函数是在执行函数的时候触发；

O_Direct优劣势：

• 优势：直接绕过page cache/buffer cache，节省操作系统内存；使用O_DIRECT方式提示操作系统尽量使用DMA方式来进行存储设备操作，节省CPU；
• 劣势：字节对齐写（logic block size）；无法进行IO合并；读写绕过cache，小数据读写效率低；

关于函数的问题

• fsync遇到过bug ，fsync可能报错EIO，系统没把脏页刷盘，但数据库层认为刷完了，导致这段数据丢了 https://wiki.postgresql.org/wiki/Fsync_Errors
• sync_file_range这里有个原理 ,不刷元数据！rocksdb会用这个来刷盘，看这个注释，额外再用fdatasync。除非你知道你在做什么，否则不要用这个api

作者总结

• fdatasync or fsync after a write (prefer fdatasync).

• write on a file descriptor opened with O_DSYNC or O_SYNC (prefer O_DSYNC).

• pwritev2 with the RWF_DSYNC or RWF_SYNC flag (prefer RWF_DSYNC).

结论，推荐使用O_DSYNC/fdatasync()

一些关于随机(写)的性能观察

• 覆盖写比追加写快(~2-100% faster) 追加写要原子修改元数据。
• 和system call相比，用flag更省，性能更好(~5% faster)

page cache

系统对page cache的管理，在一些情况下可能有所欠缺，我们可以通过内核提供的posix_fadvise予以干预。

#include <fcntl.h>

int posix_fadvise(int fd, off_t offset, off_t len, int advice);

posix_fadvise是linux上对文件进行预取的系统调用，其中第四个参数int advice为预取的方式，主要有以下几种：

POSIX_FADV_NORMAL 无特别建议 重置预读大小为默认值 POSIX_FADV_SEQUENTIAL 将要进行顺序操作 设预读大小为默认值的2 倍 POSIX_FADV_RANDOM 将要进行随机操作 将预读大小清零（禁止预读） POSIX_FADV_NOREUSE 指定的数据将只访问一次 （暂无动作） POSIX_FADV_WILLNEED 指定的数据即将被访问 立即预读数据到page cache POSIX_FADV_DONTNEED 指定的数据近期不会被访问 立即从page cache 中丢弃数据

/proc/sys/vm/dirty_writeback_centisecs：flush检查的周期。单位为0.01秒，默认值500，即5秒。每次检查都会按照以下三个参数控制的逻辑来处理。

/proc/sys/vm/dirty_expire_centisecs：如果page cache中的页被标记为dirty的时间超过了这个值，就会被直接刷到磁盘。单位为0.01秒。默认值3000，即半分钟。

/proc/sys/vm/dirty_background_ratio：如果dirty page的总大小占空闲内存量的比例超过了该值，就会在后台调度flusher线程异步写磁盘，不会阻塞当前的write()操作。默认值为10%。

/proc/sys/vm/dirty_ratio：如果dirty page的总大小占总内存量的比例超过了该值，就会阻塞所有进程的write()操作，并且强制每个进程将自己的文件写入磁盘。默认值为20%。

ref

• linux IOhttps://www.scylladb.com/2017/10/05/io-access-methods-scylla/ 这几个图画的还行。不过原理也比较简单。不多说
• page cache https://www.jianshu.com/p/92f33aa0ff52