最近感悟

原来业务逻辑写在配置文件中，就是低代码，我悟了

为什么他能想到我想不到，是我笨吗，睡眠不足导致智力下降了？我需要休息一年吗？

有时候感觉左眼不是很舒服，感觉是总看屏幕左边看的

同龄人已经都飞黄腾达了，我还是原地踏步，仔细想来，今年刷手机的频率明显比前几年高了，手机也离眼睛越来越近了。

手机成瘾症，我给自己的手机设置了使用时间限制，根本没用，拦不住玩手机的冲动

睡觉前还要玩一个小时手机，脑子总是兴奋状态，嘻嘻哈哈的状态。不看其实也没啥事，就是忍不住想看。然后还主动去刷，去找乐子。感觉明显是上瘾了。

感觉得返璞归真一下，买个辣鸡手机，打开微信都卡的，控制玩手机的欲望

doris案例集

很丰富，长了见识

缓慢变化维度的处理

Slowly Changing Dimension https://en.wikipedia.org/wiki/Slowly_changing_dimension

增加列，增加列属性，增加历史表，感觉不如mongo

我是看这个 So you want Slowly Changing Dimension? 了解到的

有点版本的感觉。麻烦

消息队列设计精要

文章写的很好

ViewStamped replication revisited

Viewstamped Replication Revisited简要翻译

整的挺好，我画个图联系一下mermaid

正常流程

Source file: mmd/vr.mmd:

sequenceDiagram client->>+primary: 发送Request:{client-id,req-no} loop 检查重复 primary->>+primary: 根据id req-no检查重复 end primary->>+primary: op-no++, AppendLog primary->>+backup: 发送Prepare:
{Request,view-no,op-no, commit-no} loop 检查 Prepare Ok: backup->>+backup: {WaitLog,AppendLog}PrepareOK end backup->>+primary: 回复 PrepareOK
commit-no++ loop 检查Prepare响应 primary->>+primary: 回收backup节点的 PrepareOK end primary->>+primary: commit-no++ primary->>+client: 回复{commit-no, result} loop 周期性发送Commit primary->>+backup: {commit-no} 心跳/消费通知 backup->>+backup: 检查 commit-op对应的Log是否落地:
更新状态 commit-no++ backup->>+primary: 回复 CommitOk
commit-no++ end

选举

Source file: mmd/vr-vc.mmd:

sequenceDiagram primary->>+backup1: 周期性发送Commit:
{commit-no} 心跳/消费通知 primary->>+backupN: 周期性发送Commit:
{commit-no} 心跳/消费通知 backup1->>+backup1: 检查 commit-op对应的Log是否落地:
更新状态 commit-no++ backup1-->>+primary: 回复 CommitOk commit-no++ backupN->>+backupN: 检查 commit-op对应的Log是否落地
更新状态 commit-no++ backupN-->>+primary: 回复 CommitOk commit-no++ primary->>+primary: 挂了 backup1->>+backup1: 没有收到primary Commit心跳
超时发起view change backup1->>+backupN: startViewChange alt backup1-->backupN: 收集startViewChange
判断view-no，确认自己是否可以切primary end backupN-->>+backup1: DoViewChange backup1->>+backup1: 根据响应更新本地的view-no
组织已经决定了，由你当primary backup1->>+backupN: ViewChange Finish client->>+backup1: startView on new primary backup1->>+backupN: startView backupN->>+backupN: truncate log
后面就是正常的流程了

故障恢复

Source file: mmd/vr-rc.mmd:

sequenceDiagram recover->>+primary: 通知其他节点我挂了:
{recover-no,self-no}
{ 自身id/recover请求id(要有区分) recover->>+backupN: 通知其他节点我挂了:
{recover-no,self-no}
{ 自身id/recover请求id(要有区分) primary->>+recover: recoveryResponse{view-no, recover-no}
{log-no, op-no,commit-no} backupN-->>+backupN: 检查自身是否normal
决定是否回复响应 backupN->>+recover: recoveryResponse{view-no, recover-no} loop recover-->recover: 收集recoveryResponse
如果recover-no不匹配要拒绝
如果期间viewChange直接失败
更新log end client->>+primary: 请求 client-->>+client: 挂了重启 client->>+backupN: 拉取request-no client->>+primary: 拉取request-no client-->>+client: request-no+=2 note over client:+2是因为可能存在一个宕机前
发送的request还未到达
且这样的请求至多有一个。

需要优化的点

  • 文件同步根据log会很慢，-> 根据checkpoint同步
  • 增加witness
  • 批量提交batching
  • 引入lease，主读
  • 忽略读到旧数据，可以读备

重新上下架的流程我没写

innodb ReadView https://zhuanlan.zhihu.com/p/642981673

这周看到两次了，画个图

Source file: mmd/inno-readview.mmd:

sequenceDiagram client1->>+innodb: T1 innodb->>+innodb: [min-txn-id,max-txn-id)
没有其他事务{} client2->>+innodb: T2 innodb->>+innodb: [min-txn-id,max-txn-id)
{txn-t1} client3->>+innodb: T3 innodb->>+innodb: [min-txn-id,max-txn-id)
{txn-t1,txn-t2} innodb-->>+innodb: T1，T3 commit client4->>+innodb: T4 innodb->>+innodb: [min-txn-id,max-txn-id)
{txn-t2,txn-t3}
能看到T1结果 innodb-->>+client1: T1 成功 innodb-->>+client3: T3 成功 innodb-->>+innodb: T4 commit innodb-->>+client4: T4 成功 innodb-->>+client2: T2 成功

本质是基于窗口的检查，而不是实际commit的时间戳

引自seven

（1）当记录的 txn_id 等于当前事务id（txn_id = creator_txn_id）时，说明版本链中的这个版本是当前事务修改的，所以该记录对当前事务可见；

（2）txn_id < min_txn_id，说明版本链中的这条记录已经提交了，所以该快照记录对当前事务可见；

（3）txn_id > max_txn_id，说明这条记录是当前事务启动后启动的新事务，该记录对当前事务不可见。

（4）min_txn_id <= txn_id < max_txn_id，首先比较txn_id是否在m_ids 数组中，如果不在说明当前事务开启之前，txn_id对应的事务就将数据修改并提交，所以该记录行的修改对当前事务可见。其次，如果txn_id在m_ids中，说明txn_id对应的事务是和当前事务同时启动的，所以该记录行的修改对当前事务不可见。

RR和RC的区别在于，对于RR在事务启动的时候即生产了可见性视图（ReadView），同一事物中的select都复用事务开启时的可见性视图。而对于RC隔离级别来说，每次select都会生成一个新的ReadView来进行可见性判断。

分布式mysql需要做的就是把txn-id和全局GTS时序绑定

不过其他DB的实现已经脱离txn-id直接用timestamp了。也得有个时间窗吧？

libgavran

写的挺好，数据库学习入门

这里标记个TODO

https://github.com/ayende/libgavran

Modeling Polymorphic Associations in a Relational Database

原来的表

create table acl(
  id serial primary key,
  resource_type varchar not null,
  resource_id integer not null,
  -- other fields omitted
  unique(resource_id, resource_type)
);
select *
from acl
where resource_type='document'
  and resource_id=42;

问题，resource_type没有限制。给个星星设计，加限制


create table acl_document(
  acl_id integer not null unique references acl,
  document_id integer not unique null references document
);

create table acl_image(
  acl_id integer not null unique references acl,
  image_id integer not null unique references image
);

select acl.*
from acl
  join acl_document on acl_document.acl_id=acl.id
where document_id=42;


create table acl(
  id serial primary key,
  document_id integer references document,
  image_id integer references image,
  file_id integer references file,
  report_id integer references report,
  -- other fields omitted
  check(
    (
      (document_id is not null)::integer +
      (image_id is not null)::integer +
      (file_id is not null)::integer +
      (report_id is not null)::integer 
    ) = 1
  )
);

create unique index on acl (document_id) where document_id is not null;
create unique index on acl (image_id) where image_id is not null;
create unique index on acl (file_id) where file_id is not null;
create unique index on acl (report_id) where report_id is not null;

清晰，就是麻烦

The C++ Type Loophole (C++14)

经典的友元函数注入

template<int N> struct tag{};

template<typename T, int N>
struct loophole_t {
  friend auto loophole(tag<N>) { return T{}; };
};

auto loophole(tag<0>);

sizeof(loophole_t<std::string, 0> );

statc_assert(std::is_same< std::string, decltype( loophole(tag<0>{}) ) >::value,"same");

这玩意属于缺陷，说不定以后就修了

StarRocks 源码解析

挺不错

https://blog.bcmeng.com/post/starrocks-source-code-1.html

这哥们总结的很好 https://blog.bcmeng.com/post/starrocks-source-code-1.html

还有这个 https://blog.bcmeng.com/post/dpa.html

https://blog.bcmeng.com/post/dpa.html

https://blog.bcmeng.com/post/starrocks-look-up.html

BPF工具分析

系统调用分析

./syscount -t xxx -i 1 -L
perf trace -t xxx -e syscalls:sys_enter_* -- sleep 600 > perf_trace.txt
bpftrace -e 't:syscalls:sys_enter_epoll_wait /comm == "spp_call_center"/ { @[comm, pid, tid] = hist(args->timeout); } i:s:1 { time(); print(@); clear(@); }'

bpftrace -e 't:syscalls:sys_enter_epoll_wait /tid == xxx/ { @ = hist(args->timeout); } i:s:1 { time(); print(@); clear(@); } i:s:600 { exit(); }'

epoll_wait timeout 参数动态优化 是一个关注点，根据业务的经验值来调整

  • 如何统计？每次加一个时间点，同时排序 -> 堆排
  • 根据每个任务index保存自己的时间（需要有个时间标准，这玩意不能太慢，不然成瓶颈了），然后计算这个超时时间，最大10ms，每次epoll_wait设置一次

哪个好？第一个通用，第二个具体，但可能涉及时间调用gettimeofday？

得缓存一下，比如一个后台线程周期更新存tls里，epoll_wait设置这个时间点时候直接读tls对象，加一层避免直接系统调用

Comparing Queuing Strategies in Distributed Systems

这个图挺直观

Linux删除文件过程解析

删除文件可能有大量inode操作，如果删除的大文件影响更严重，如何缓慢删除？看这个9SO](https://serverfault.com/questions/814029/how-can-i-slowly-delete-a-large-directory-hiearachy-to-reduce-disk-i-o-load)

ionice -c3 rm -rf $NAME

但是程序里用的是fs::remove接口，这种有办法放慢吗？只能手写遍历，删一个sleep一下？

Kudu: Storage for Fast Analytics on Fast Data

列存+行存，之前见过一个，什么tellstore，这个kudu是有文件落地的，facebook对这个存储研究很多，还有基于kudu的raft

架构也是metaserver+ data server的模式 data server三个数据结构，memrowset是b-tree memrow只有一个可写

类似rocksdb memtable刷盘策略，同理，也不支持删除，支持版本覆盖删（MVCC说是）

diskrowset分两部分，base 和delta。base是列存，delta是memrowset的文件形式，存(rowoffset, timestamp, value)，通过compact和base合并成新的base

查询的时候先访问base，再通过rowoffset找delta的改动，然后合并成一个新的

（这读写性能能好么？最低一个文件IO，最高O(deltaFileNum)个文件IO，这要扫起来还得了，写入是并发写masstree）

但这个存储对于raft来说，还真挺合适

  • 一段时间的数据，checkpoint传输也足够紧凑
  • masstree并发写，比普通的map有局部性收益和空间收益（trie），masstree vs concurrent hash map，谁的写入性能更好呢？感觉是hashmap，毕竟masstree定位是对数复杂度

一般raft的实现是数组 + hash map来管理数据，文件的kv是顺序的，顶多做一下kv分离。和kudu比重放优势很低。kudu最大的优势就是重放快了，数据结构落盘简单，回滚也简单。

trie这种数据结构，对于raft的回滚需求是非常快的，省掉遍历index比较每条记录的问题

tikv他们用类似bitcask的思路实现了一个raftengine。那个是hashtree。不是hashmap。有没有借助hashmap实现的raft，比如基于fasterkv实现一个raft？

这里标记一个TODO后面再思考思考

Meta MySQL Raft 的创新点与使用场景

没怎么看懂，好像副本需要特别多，然后成员分组，然后异地的多个组，选主要取交集？看不懂

gap buffer

就是长一点的buffer，文本编辑器用

一个实现 https://github.com/lazyhacker/gapbuffer/blob/master/gap_buffer.h

FSST: Fast Random Access String Compression

也是字典压缩 https://raw.githubusercontent.com/cwida/fsst/master/fsstcompression.pdf

优点在于构造的字典，是根据数据来构造的，不是全局的，能更优秀

针对单条压缩，非二进制数据（json xml网址邮箱）有优势。值得测一测。这个玩意是TUM的论文

chatgpt老师 的总结

FSST是一种字符串压缩算法，它利用列中经常出现的子字符串进行压缩。该算法的关键实现细节包括： 1. 基本思想：FSST通过将长度为1-8的子字符串替换为1字节的编码来实现快速而有效的字符串压缩。 2. 符号表构建：FSST使用一种基于遗传算法的自底向上的方法来构建符号表。该算法能够根据给定的数据集找到一个好的符号表。 3. 压缩速度优化：为了使压缩过程更快速，FSST利用了AVX512 SIMD指令集等技术。 4. 解压缩速度：FSST提供快速的解压缩算法，平均每字节2个周期（或每核心1 GB/秒）的解压缩速度。 5. 随机访问能力：与LZ4相比，FSST支持有效的随机访问，即能够在不解压缩数据块的情况下访问个别字符串。这使得FSST在数据库系统等应用中特别有用。 总之，FSST通过优化符号表构建、压缩速度和解压缩速度等方面的实现细节，实现了快速、高效的字符串压缩，并能够支持随机访问能力。

How ScyllaDB Distributed Aggregates Reduce Query Execution Time up to 20

就是计算均摊，类似count minmax这种，可以MPP。感觉就是OLAP的技术拿过来用一用，一个协调者调度节点计算收集数据

neondb

怎么share log？

感觉这个架构很复杂

pageServer + LogKeeper + 存储 + proxy

我在想做一个真 多模型架构，大概就是proxy + 计算 + 存储 这个样子，和他这个差不多

计算下沉到存储也可以，但存储本身承担了Log同步的责任了，又加个计算，感觉太重了

或者gateway规格足够大，内存多一点，最好能把过滤的能力推到存储层，然后gateway能把中间结果尽可能存下来

或者gateway和其他gateway/新增的计算节点沟通，子查询并发，把计算能力扩出去。

感觉多一层计算非常麻烦。本身gw+dbs+cp这一套就很复杂了

再加cache/pageserver + logkeeper + compute

要了老命了

openai老师 https://openaikey.xyz/

Announcing Amazon Keyspaces Multi-Region Replication

亚马逊的cassandra。多主，多地副本可读写，自动异步同步写，猜测CRDT

Paper Notes: Distributed Transactions at Scale in Amazon DynamoDB

OCC + 2PL

这怎么scale？

读写都有时间戳

写，OCC 时间戳拦截

Source file: mmd/DynamoDB-write.mmd:

sequenceDiagram client->>+coordinator: Write,timestamp coordinator->>+coordinator: 写写冲突检测,如果有写入请求取消 coordinator->>+datanodeN: 写入所有datanode节点 2PC step1 Prepare datanodeN->>+datanodeN: 写入冲突判断，
判断当前key的上次更新ts > 写入ts
决定是否写入/拒绝 datanodeN-->>-coordinator: 2PC Prepare Ok Accept/Reject Ok coordinator->>+coordinator:检查所有节点Prepare OK
失败取消Txn，否则开始发起确认 coordinator->>+datanodeN: 写入所有datanode节点
2PC step2 Execute datanodeN->>+datanodeN: 写入数据,LSN++ datanodeN->>+coordinator: 2PC Execute Ok coordinator->>+coordinator:检查所有节点Execute OK，失败取消Txn coordinator-->>-client: 写入成功

读，读两次

Source file: mmd/DynamoDB-read.mmd:

sequenceDiagram client->>+coordinator: Read,timestamp coordinator->>+coordinator: 读写冲突检测,如果有写入请求取消 coordinator->>+datanodeN: 读取所有datanode节点 2PC step1 Prepare datanodeN->>+datanodeN: 拿到数据和LSN datanodeN-->>-coordinator: 2PC Prepare Ok Accept/Reject Ok coordinator->>+coordinator:检查所有节点Prepare OK
失败取消Txn，否则开始发起确认 coordinator->>+datanodeN: 再次读取所有datanode节点
2PC step2 Execute datanodeN->>+datanodeN: 拿到数据和LSN datanodeN->>+coordinator: 2PC Execute Ok coordinator->>+coordinator:检查所有节点Execute OK，失败取消Txn
检查LSN是否变化，变化则取消txn coordinator-->>-client: 读取成功

崩溃怎么办？其他节点把事务信息同步一下。中心节点不需要关注节点挂，如果事务因为节点挂失败，那就失败

显然这个读两次是能优化的，第一次读带上时间戳就行了

笔者猜测，内存维护一个[key, ts, [value,LSN]]，人家说了没用额外的数据存，那肯定cache住了，不然没时间戳信息

非事务读写？分配给小于事务的时间戳，也就是旧的时间戳

  • 如果事务失败，不影响非事务的读写
  • 如果事务成功，非事务写等于no-op，啥也不干
  • 时间戳非常巧，相同了，怎么办？直接写，认命
  • batch写，把同一个存储节点的写收集一起写

感觉有点意思，但不多

从 Elasticsearch 到 Apache Doris，10 倍性价比的新一代日志存储分析平台

加了倒排索引，大家都在蚕食别的领域

百亿数据百万查询——关系链架构演进

hash kv硬扛，客户端加localcache，不准无所谓，前排关系基本不会变

B站分布式KV存储实践

其实都差不多，和基本的control plane + data plane(gateway + database server + cache)模型比，差异:

没有gateway更新路由，客户端从metaserver拿 （没有名字服务，metaserver作为名字服务？）

按照第一种模型，分裂信息同步给gateway就可以了，客户端连接gateway自动感知变动，gateway也可以无限扩，分片信息暴露给客户端，那么客户端也得实现一套，而不是用原声协议

metaserver负责维护control plane职责，维护数据，以及变更（分裂/路由维护）

binlog 订阅来实现多活 就CDC，多活的问题是检查key冲突

健康监测，如果metaserver检测不到/误判/网络分区等，尽可能通过副本转发一下检测信息

—— 名字服务呢？保证名字服务稳定，只要有网就能注册上，就用不上这种场景了吧

rocksdb使用经验

  • 旧key太多 periodic_compaction_seconds — 也可以统计deletekey 然后主动触发
  • scan慢查询 CompactOnDeletionCollector 可以
  • 大量delete + scan导致 L1 被迫多次参与compaction 增加写放大 关闭CompactOnDeletionCollector

—– 话说这种场景是不是bug，按理说L1不应该触发CompactOnDeletionCollector的compaction

  • ratelimiteer限制写

基于此rocksdb 在5.9以后为 NewGenericRateLimiter 添加了 auto_tuned 参数， 可以根据当前负载自适应调整限速。 需要注意的是，该函数还有一个参数 RateLimiter::Mode 用来限制操作类型，默认值为 kWritesOnly, 通常情况该模式不会有问题， 但是如果业务存在大量被删除的数据，只限制写可能会导致compaction的时候造成大量的读io

需要关注这个，还有点意思

Lethe 如何优化 LSM-Tree delete 难题

代码在这里 https://github.com/BU-DiSC/lethe-codebase

感觉和eventlisten统计删除key差不多？

在存储层，加了个 Key Weaving Storage Layout 把删除信息放到sst里，加了个delete key，用来快速 deleteRange

和rocksdb的deleteRange有啥差别？deleterange是写一条记录，这种能高效定位合并文件

需要复现对比一下

B站动态outbox本地缓存优化

通知模式，通知告诉客户端变了，客户端异步慢慢拉取，构建一个列表，避免全量拉取一圈。

Redpanda’s official Jepsen report: What we fixed, and what we shouldn’t

这个测试挺有意思

完美哈希函数性能盘点

取决于数据规模。当KEY的数据的规模比较小的时候，经典的CMPH- CHD算法和PTHash表现平分秋色，甚至在百万级别的数据上，CMPH- CHD算法还有一些优势。但是当数据规模到达千万级别时，CMPH实现的CHD算法则落后相当明显。因此如果你的业务KEY的规模比较大，因此可以考虑将自己的算法从CMPH上迁移到PTHash

https://github.com/jermp/pthash 比较无敌。全量离线构建是不是这个更好一些？不知道支持磁盘不

https://github.com/PeterRK/fastCHD之前也看见有人用过，纯内存