inline cache技巧
鸽了
鸽了
原文 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 问题的。
最近在网上看到一篇抓堆栈的脚本工具介绍
工具还挺漂亮的,但是我的问题在于
所以有了两个想法
学一下perl,改写成python的工具?搜了一圈perl2python没有工具能用
能不能用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\action | page cache | buffer cache | inode cache | directory cache |
---|---|---|---|---|
O_DIRECT | write bypass | write bypass | write & no flush | write & no flush |
O_DSYNC/fdatasync() | write & flush | write & flush | write & no flush | write & no flush |
O_SYNC/fsync() | write & flush | write & flush | write & flush | write & flush |
sync_file_range() | write & flush | write & flush | no write | no write |
flag和函数的区别是:flag表示每次io操作都会执行,函数是在执行函数的时候触发;
O_Direct优劣势:
关于函数的问题
作者总结
write on a file descriptor opened with O_DSYNC or O_SYNC (prefer O_DSYNC).
结论,推荐使用O_DSYNC/fdatasync()
一些关于随机(写)的性能观察
系统对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%。
整理自 https://wolchok.org/posts/inlining-and-compiler-optimizations/
文章串起来了一些知识,读一读,增加一下见解。当然,学习一下clang/llvm更直接一些,这些都是二手复读
看到网友推荐这篇博客,整理归纳一下 https://martinfowler.com/articles/patterns-of-distributed-systems/
我发现有人翻译了,但是翻译的不全。 https://xie.infoq.cn/article/f4d27dd3aa85803841d050825
这里的分布式系统是指所有的系统,共性问题
Type of platform/framework | Example |
---|---|
Databases数据库 | Cassandra, HBase, Riak |
Message Brokers消息队列 | Kafka, Pulsar |
Infrastructure基础架构元信息管理 | Kubernetes, Mesos, Zookeeper, etcd, Consul |
In Memory Data/Compute Grids网格 | Hazelcast, Pivotal Gemfire |
Stateful Microservices微服务 | Akka Actors, Axon |
File Systems文件系统 | HDFS, Ceph |
这些场景下如何处理数据丢失?解决方案:WAL
另一种异常,进程暂停,可能是内部在忙,没有及时响应,可能是gc引起的延迟等等
Generation Clock 我的理解就是term 推进,老master检测自己不是最新的index,就自动降低身份 也就是Lamport’s timestamp
时间同步问题,ntp是不准的甚至是会出错的,有原子钟方案,也有lamport逻辑时钟方案
(其实原子钟方案比较简单,一个gps原子钟七八万,我之前的老项目用过,这个成本对于互联网公司还好吧,为啥都不用呢,不方便部署么)
首先是WAL 也就是commit log commit log要保证持久性
每个日志要有独立的标记,依此来分段整理,方便写,但是不能无限长,所以要有个Low-Water-Mark标记,其实就是后台线程定期删日志
日志更新就相当于队列追加写了,为了吞吐可能要异步一些
考虑如何实现这样一个kv;
首先kv得能序列化成log,并且能从log恢复
需要支持指定snapshot/timestap恢复,这两种是淘汰判定的标准,也就是一个unit
zookeeper etcd都是这个方案,代码类似下面
public SnapShot takeSnapshot() {
Long snapShotTakenAtLogIndex = wal.getLastLogEntryId();
return new SnapShot(serializeState(kv), snapShotTakenAtLogIndex);
}
//Once a snapshot is successfully persisted on the disk, the log manager is given the low water mark to discard the older logs.
List<WALSegment> getSegmentsBefore(Long snapshotIndex) {
List<WALSegment> markedForDeletion = new ArrayList<>();
List<WALSegment> sortedSavedSegments = wal.sortedSavedSegments;
for (WALSegment sortedSavedSegment : sortedSavedSegments) {
if (sortedSavedSegment.getLastLogEntryId() < snapshotIndex) {
markedForDeletion.add(sortedSavedSegment);
}
}
return markedForDeletion;
}
kafka就是这种方案
private List<WALSegment> getSegmentsPast(Long logMaxDurationMs) {
long now = System.currentTimeMillis();
List<WALSegment> markedForDeletion = new ArrayList<>();
List<WALSegment> sortedSavedSegments = wal.sortedSavedSegments;
for (WALSegment sortedSavedSegment : sortedSavedSegments) {
if (timeElaspedSince(now, sortedSavedSegment.getLastLogEntryTimestamp()) > logMaxDurationMs) {
markedForDeletion.add(sortedSavedSegment);
}
}
return markedForDeletion;
}
private long timeElaspedSince(long now, long lastLogEntryTimestamp) {
return now - lastLogEntryTimestamp;
}
读大多数 判定数据
复制组要保证高可用性 心跳检查,节点间心跳以及自身心跳处理,如果自身僵住需要退位
复制组有主从,涉及到选举算法 zab raft之类
arangodb也是多模数据库,支持文档和图两种,支持mongodb式的操作json语法,也支持类似sql的方法
简单体验一下
在macos上非常好体验,直接brew就能安装
brew install arangodb
brew serivces start arangodb
brew services stop arangodb
注意是有密码的,我这里直接把密码关掉了,参考这个文档, 修改arangodb.conf 把authentication改成false重启就可以了
可以网页访问 http://localhost:8529/_db/_system/_admin/aardvark/index.html#collections
arangodb也提供了命令行 arangosh
备份 https://www.arangodb.com/docs/stable/backup-restore.html
replication appler是什么概念?https://www.arangodb.com/docs/stable/http/replications-replication-applier.html
经典图
可以看到,由于隔离型相关的问题其实都是并发竞争导致的,所以和「多线程安全」问题非常相像,思路和方案也是共通的。 现代数据库系统已经将并发竞争问题抽象为隔离级别(Isolation level)来处理 ,也就是 ACID中的I。接下来我们看一下常见的隔离级别,以及能提供的保证:
这是那个经典论文描述的场景 图片介绍。另外知乎有篇验证文章
PRAM一致性(Pipeline Random Access Memory)完全等同于读你的写、单调写和单调读。如果要追求读后写一致性,只能选择因果一致性。如果你需要完全的可用性,可以考虑牺牲阅读你的写,选择单调读 + 单调写。
线性一致性
我们可以利用线性一致性的原子性约束来安全地修改状态。我们定义一个类似CAS(compare-and-set)
的操作,当且仅当寄存器持有某个值的时候,我们可以往它写入新值。 CAS
操作可以作为互斥量,信号量,通道,计数器,列表,集合,映射,树等等的实现基础,使得这些共享数据结构变得可用。线性一致性保证了变更的安全交错。
顺序一致性,强调顺序,不是必须发生,但保持顺序发生
因果一致性,保证因果顺序,顺序一致性的子集
串行一致性,有条件必严格
最终一致性以及CRDTs数据结构