分布式和大数据方案备忘

扩容

1. 分布式缓存(tair) 一致性hash存储，2台扩3台，a,b,a,b,a,b -> a,b,c,b,a,c 只用全量迁移2台机器的数据，成本最低
2. 分库分表数据库 (1)先做全量迁移并记录迁移之前老库的位点 (2)全量迁移是整表迁移，这也是要做分表的原因之一 (3)全量做完以后开始做增量 (4)增量追上以后把路由规则切到新库
3. kafka 两种扩容，如果分区开的多只扩机器不扩分区这种可以做到自动迁移，等kafka新机器的isr追上进度即可提供服务。如果扩了分区数，为了保证顺序，必须停写，然后等消费端消费完毕才能扩容
4. rocket mq扩容，目前对于顺序消息必须停写等消费端消费完毕，因为rocket mq的高可用方案是双写，新机器加进来以后没有isr的方案帮助新机器拿到队列里面的数据
5. 分布式文件系统 有name server存在，name server会做动态负载均衡，所以新机器加进来即可自动完成扩容和后面的数据均衡
6. pulsar扩容，在kafka的基础上走一步，把kafka的segments加上元数据管理让一个分区的segments能分散在不同机器上就能做到全自动的迁移和扩容，pulsar的另一个重要特点是存储计算分离原来的broker拆成不存数据的broker和存数据的bookie。但是zk的依赖好像依然是个问题。

热点解决方案

tair hot ring

1. https://yq.aliyun.com/articles/746727
2. 基本思路是hash冲突时尽量减少爬链表的过程，把最热的放到最前，这个移动过程可以通过采样来发动
3. 如果移动链表元素动作较多，并发冲突较多，所以采用ring结构只用移动head指针即可
4. ring结构转一圈后无法判断是否跑完了，所以要对key排序，这样找到比当前key大的就说明再也找不到了，为了加速比较过程，还在key前面加了tag
5. 扩容的时候根据范围拆分，原来tag的范围是0-t，拆分成0-t/2和t/2-t，header也分成两个，也就是个标准的rehash手段

hash+range二级散列方案

Hash(a,b)=Range(Hash(a),Hash(b))

有区分度而且保留了一定的范围查询的能力，https://zhuanlan.zhihu.com/p/424174858

一致性

1. 健康检查类型的数据传播，仅要求最终一致性，所以可以用gossip的方式传播，实现简单
2. 配置型信息存储，顺序很重要，所以需要用paxos或者raft类型的协议存储

megastore

1. entity group类似于分表，但是每个数据中心的entity group是相同的。一个entity group内部是强一致事务，跨entity group可以用2pc做强一致事务但推荐的方式是用消息队列做弱一致事务，论文里描述的一个场景是a邮箱给b邮箱发邮件
2. 高可用性是通过在多个数据中心做paxos写来实现，这种方式的优点是没有master，省去可很多运维上的麻烦。写数据的流程是(1)读取WAL的最后提交位置(2)把要写的数据攒成一个log entry(3)paxos提交(4)把数据合并到big table里面的数据行和索引(5)清理临时数据
3. 存储和查询基本按关系数据库的做法，但是有主从表的概念，比如user和photo，user是主表photo是从表，两个表相关联的数据在物理上也存在一起
4. bigtable可以把同一个cell的数据根据时间戳多版本存储，megastore通过这个特性实现mvcc
5. 有一个coordinator的角色负责记录本地所有paxos写成功的表，通过这个信息尽量保证本地读。这里细节没完全懂，既然是多写，为啥还需要这个角色？
6. paxos write做了优化，每一轮写都会选一个leader做裁决，选leader的原则是leader所在的区域发起的写最多。具体流程是(1)找leader接受要写的数据如果接受就跳过步骤2(2)选一个最高的sequence，并且把要写的数据更新到最新状态(3)让其它的replica接受更新，如果多数接受就成功，否则重做步骤2(4)invalidate coordinator(5)所有replica把数据更新到本地bigtable

基于json的架构1

1.存储基于mysql，每个表只有两个字段id和json块

2.在mysql里面写，在搜索引擎里面读，mysql和搜索引擎基于binlog同步

3.mysql和搜索引擎上面有一个统一数据层负责读写的分发

4.所有领域对象都是json表示，有一个配置中心负责配置规则做校验和搜索引擎的索引字段

5.服务层上面有一个路由和校验层，根据调用的json串做路由

6.读写延迟是个比较大的问题，无法一致性读导致复杂的业务逻辑可能会比较难做，对数据同步工具要求也非常高

uber schemaless

1.存储基于mysql，cell是基本单元可以是一个json比如乘车基本信息这样的，row_key，column_name，ref_key决定一个cell。一个row可以有多个cell而且不用事先指定。整个表类似于一个三维hashtable row_key->column_name->cell{key1:value1, key2:value2}

2.对cell的操作是基本操作，只能insert不能update或delete，对cell的insert是高版本ref_key覆盖低版本ref_key这样完成update。操作基于cell级别可以有效减少写入数据体积

3.分片存储，每个分片是一个独立的mysql数据库，每个库有一张表存cell实体，每个二级索引用一张表存储，还有一些辅助表。每个cell是实体表的一行，每一行有added_id，row_key，column_name，ref_key，body，created_at，其中added_id是给后面的trigger排序用的，body数据存成压缩的json。这种存储结构是拿多个mysql row拼成一个schemaless的一个逻辑row

4.trigger类似于精卫，有failover，重投这些行为，通过trigger实现异步事件总线，完成类似于行程结束之后付款这样的操作

5.二级索引可以建到cell里面的属性上面，而且支持联合索引，这个感觉是靠索引表实现的。索引也要求有分片字段，索引和cell可能不在一个分片，只做到最终一致，有可能读到旧数据

6.cell存储根据row_key分片，每个存储节点一主两从，尽量读主节点，主从异步复制，读主节点失败会转去读从节点。写主节点失败，会随机找其他分片的主节点写入，但是会告诉客户端这个写入目前不可读，这个叫缓冲写入

7.缓冲写入，写主分片主节点之外会随机挑一个分片的主节点做备份写，在备份分片上的写就是缓冲写，如果主分片主备复制完毕，从节点上出现了新写的数据，worker机器就会把备份分片上的缓冲写数据删掉。相当有趣的解决mysql主备复制问题的方案

8.这个方案有高可用性，扩展性也不错，查询也可以跨维度，感觉比前面的基于json的方案牛逼

缓存使用进化

1.tomcat服务端使用业务对象缓存，web框架对静态页面使用page缓存，浏览器和nginx缓存图片和js这些。缺点是还要走servlet这些，java处理耗cpu，容易到上限

2.动静分离，nginx，缓存服务部署在同一台机器上，静态的数据走缓存，动态的数据由客户端js做csi回源。请求由lvs按一致性hash打进来提高命中率。缺点是管理麻烦，不同的机器间没有互通。

3.统一缓存层，缓存服务单独部署集群，回源采用esi，由缓存服务器找java server回源，这里应该是走比较快的协议。优点是管理方便，而且缓存数据统一互通。失效策略可以有定时，根据tag计算，异步业务消息和监听binlog

4.cdn，先通过dns做路由到最近的cdn节点，cdn如果拿不到数据就找统一缓存层，统一缓存层对动态数据做回源

hbase,lsm tree,列存,kv-store,sstable,skip-list,bloom-filter

1.kv-store是键值对存储，sstable是一种实现方式，特点是按key排序存在内存或者文件里

2.sstable如果没有其它措施读写都会很慢，所以首先有了lsm tree，内存里面L0,然后文件里面L1,L2...一般越来越大. lsm tree一般是写内存，超出大小以后批量merge到磁盘，所以写性能不错

3.说是lsm tree但也可能具体的tree是skip list, skip list加上随机化层数后平衡性不错而且并发的版本加锁比较少,缺点是比较耗内存。skip list一般放内存中，磁盘上还是btree比较好

4.随机查询还是慢，所以用bloom-filter来加速在hfile里面的寻址，通过几个hash函数来快速过滤掉一些不可能有目标数据的hfile

5.hbase的存储建立在上面这些之上，region是分布式存储的最小单元，一个region只会在一台server上，region如果大了就会分裂，region在hdfs上面是个目录。每个列簇对应一个store，一个store里面有一个mem-store和一些文件，这些文件也放在一个目录里面，列簇里面的内容按rowKey排序存在一起，region里面可以有多个store

6.rowKey col1 col2 col3应该是存成 rowKey col1, rowKey col2, rowKey col3 这样

7.hbase称作面向列的存储，存的是列族，但是一般实践都是只有一个列族，列族内的列可以随意修改所以hbase实际上还是行存储。hbase的优势是自动分片，按rowkey查询快，写入快，只能算高级kv数据库。hbase的version一个是确实有场景用得到多版本的数据，另一个是可以用来做mvcc

8.hbase的事务仅仅是针对单行，对于不同行以及单行分布在不同region的情况都无法加锁。hbase有单行的行锁，而且对于单行的读和写可以通过mvcc保证并行度

9.hbase这种存k-v的叫面向列的存储，这种存储的好处是本质上是k-v store可以很灵活的动态添加列，某些列可以很稀疏不占空间，而且可以做lsm-tree结构。kudu这种光存value然后靠偏移量去定位，优点是可以做高压缩比，范围scan很快，这种结构一般要求schema固定有了类型才好算偏移量选择压缩算法，这种结构感觉做lsm-tree也超复杂

hbase row-key

1.hbase region拆分方式是按row-key的range进行拆分

2.row-key太长的缺点是消耗内存和磁盘空间，sstable方式决定

3.row-key简单单调递增会带来当前region读写热点问题以及之前拆分的region很少有机会再被访问的问题

4.热点的解决方案(1)预分区(2)随机散列，缺点是再也无法范围扫描，根据row-key的部分条件扫描也无法弄(3)加hash运算出来的前缀，优点是还可以范围扫，缺点是每次扫都是多机器而且代码稍麻烦

5.row-key可以存字段信息，并且当做查询条件，比如<userId>-<date>-<messageId>这种组合然后查userId 00005 的数据，支持左前缀。这种方式感觉消耗存储而且row-key设计的不好以后不好改
6.还有一种比较诡异的玩法，因为hbase能随意添加列，所以对于用户收到的邮件这种聚合，可以一行，每封邮件一列但是列名不同，通过列名做索引

Cassandra

1.数据存储模型也是bigtable的模型，map<row-key, map<column-key,value>>

2.memtable+sstable+commitlog

3.分片方式是一致性hash，节点的状态是通过gossip协议点对点传播，所以没有了master-server这样的角色，少了单点问题，也不会有hbase region分裂时候的可用性问题，tidb通过raft+状态机解决分裂时的可用性问题

4.高可用的方案是wrn，优点是比较灵活可配置
5.cassandra没有使用vector clock，原因在于本质上cassandra是kv型数据而dynamo是文档型数据，所以cassandra可以用update a=xxx where b=yyy这样的方式单独的更新属性，这样大多数merge就可以避免了

Dynamo

1.大模型上和Cassandra非常相似，也是一致性hash分片，节点的状态也是gossip协议传播，也使用了wrn

2.高可用上面有两招，临时的不可用会找另外一台机器做暂存，等恢复以后再把数据拷贝回来。如果机器挂掉时间比较长，会异步数据恢复，副本之间的数据不一致快速检测和恢复使用的数据结构是Merkle Tree

3.vector clock，某些节点宕机恢复以后或者网络发生partition的时候可能出现版本分叉，比如版本1的基础上出现了版本2和版本3两个不同的修改，客户端读到这个分叉版本的时候需要自己去裁决选择一个版本或者合并，然后再把新版本写回去

4.Dynamo的特点是比较简单轻量，最终一致

td-sql

1.要解决的是mysql异步主备同步可能丢数据的问题

2.最原始的是主挂了停用，捞业务日志补偿备

3.k-v存储加黑名单，主挂了只是没有同步好的黑名单不可用

4.td-sql，一主两备为一组，写主只有binlog到达一备才算写成功，主挂了按binlog最后更新时间选新主

Elasticsearch

1.任意维度的联合查询比mysql强大很多很多

2.term-index(前缀树)->term-dictionary(排序)->position-list

3.多条件合并也就是多个position-list合并，可以通过在position-list上面建skip-list然后合并skip-list，或者直接内存bitset合并

4.skip-list的一种压缩方式是记录delta，bitset的一种压缩方式是模一个65536然后记录商和余数
5.在聚合查询上有和mysql类似甚至更好的能力，因为es又引入了doc_values

6.doc_values是正排索引+列存，比如查年龄18岁的平均身高，先用倒排查到18岁的所有doc_id，再拿doc_id到正排索引里面去匹配然后计算，因为正排是列存的而且还压缩了的所以一次性load进内存进行比较，这样想着感觉好牛，还没完全想明白，要比较详细的了解一下底层的数据结构。通过doc_id拿doc_value的过程是fetch过程，因为要从一堆文件里面定位doc_id所以这个过程其实也很耗时间。

7.es5之前数值索引都是先转换成string然后用前缀fst的方式索引查询，这样的问题是range特别慢，在前缀树上面找range要递归，es6使用了bkd-tree，也就是lsm-tree版的kd-tree，不用b-tree是为了兼容数值型和多维类型的查询。kd-tree的速记方式是二叉树，第一级按第一个维度排序，第二级按第二个维度排序。。。查找的时候也是一个一个维度拿来查

8.es的多条件查询是取交集的形式可能会比较慢，如果配合mysql的查询扫描方式会有很大提升

9.lucene有内存buffer和磁盘segment(可以看成一个独立的子索引)类似lsm tree所以写入高效，但是不能实时查询是因为要给segment建倒排索引，这一步是buffer刷成segment的时候做的所以只能准实时，通过这个lsm tree可以做id到doc的查找

10.es扩展了lucene加了一些系统字段，_uid主键，_version，_seq_no，_source来支持update，_field_names支持稀疏列判断，_routing数据分布，利用的是lucene本身的能力很cool
11.es有个transLog有点像metaq，持久性保证需要每次请求刷盘，如果要实时性可以从transLog查数据，查transLog只能byId，根据倒排索引查询只能准实时。log写放在内存写之后，一个是防丢数据一个是实时查询
12.lucene不支持update，es支持的方式是在内存里面merge成一个新doc，然后add到lucence里面去，其中version起乐观锁的作用
13.海选，粗排，精排，海选一般是根据记录某属性做简单分层，粗排一般做简单算分排序召回1000到2000数据，精排可以有比较复杂的运算做出最终排序

TIDB

1.sharding策略有两种range和hash，range优势是范围扫描和扩容缩容比较好做，tidb使用的这种，缺点是顺序写热点。hash没有顺序写热点问题但无法做范围扫(不过实际业务中的一些加了分库键的范围扫还是可以的)，还有就是扩容缩容比较麻烦容易导致较大抖动

2.tidb使用的是多raft-group，就是说每个shard(region)是一个group

mvcc & read skew, write skew

1.time oracle为了解决外部一致性问题，试想如果没有中央协调器，怎么能做到准确的读到一个事务的完整状态？很可能部分节点写完成了，部分节点还没有。而节点很多的分布式环境一个中央协调器又会成瓶颈，所有就需要一个全局的事务id来界定事务所以有了time oracle

2.write screw 两个不同的银行账户各有100块钱，约束是总钱数必须不小于100，两个事务都是先做检查然后取100，mvcc并发状态下两个事务都不违反约束又不会有mvcc冲突。stm内存锁的解决方案是进入事务前都把所有的资源都加个读锁，但是分布式协调器的情况无法统一加锁，所以才有了google的time oracle的方案  

3. percolator没有对read加锁，所以只是一个snapshot isolation，而couchdb这样的对read加锁实现的是serializable snapshot isolation隔离级别，但有性能代价

4.read screw r1[x], w2[x], w2[y], c2, r1[y], c1 or a1

5.引发的问题称作事务的外部一致性

时钟策略

1.逻辑时钟，每台机器维护本地序列号，如果一个事务跨机器从机器1传递到机器2，机器2会比较机器1传过来的序列号和本地的最大序列号取最大的，不同机器的数据只要在事务中形成交叉就相当于建立了逻辑关系。这种方式的缺点是不同事务如果没有数据交叉可能序列号的gap会很大。

2.hlc，物理逻辑混合时钟，在物理时钟不变的情况下新事务只增加逻辑时钟，如果物理时钟变了就跟着最大的物理时钟走。这样相当于用逻辑时钟来校准物理时钟，但不同事务又能通过物理时钟比较大小，但是hlc也无法完全做到不同的没有数据交集之间的事务之间的因果律。

Percolator

1.Percolator是为了补充map-reduce全量离线计算的不足而产生的增量索引系统，首要的优势就是增量计算时效性好。增量计算和全量计算的区别在于全量计算丢弃之前的所有计算结果全部重来，而增量计算会根据新的数据去查找之前相关联的计算结果，然后在之前的计算结果上做局部运算。计算的可加和性是增量计算是否便于实施的关键

2.为啥需要事务？爬虫从多个url抓到了相同的内容，只需要将pagerank最高的url加到索引，但是每个外部链接也会被反向处理，让其锚文本附加到链接指向的页面，指向复制品--pagerank低的那些页面的链接必要时也会被修改指向pagerank最高的url。这里就涉及到正向索引，反向链接锚文本和指向复制页面链接等几个状态的修改，所以需要一致性事务。还有一个可能的原因是一个文档的pagerank，内容hash这些可能不是放在一张表里面而是分开存放的

3.percolator的问题域特点是海量数据和延迟容忍度相对高，延迟容忍高所以对脏锁清理可以比较懒惰

4.percolator也是2pc事务但是和传统的2pc事务最大的差异点在于没有中央协调者，而这个特点带来了极大的可伸缩性

5.能做到无协调者的几个关键因素是，mvcc快照隔离级别，bigtable的mvcc单行事务和可扩展性存储，轻量的统一时间戳提供者

6.percolator的表的一行内容是，C:data(实际存储的数据)，C:wirte(控制数据可见性是否commit)，C:lock(事务用的锁)，C:notify(通知机制用，避免全数据扫描)，C:ack(防止重复通知)

7.mvcc和乐观锁的区别在于mvcc可能是多行的一个统一的状态，比如事务1写了行a然后去读取行b，这中间事务2写了行b，那事务1应该是读取事务2写之前的版本，所以这里就需要有时间戳比较或者版本号。而乐观锁只是锁定一行就行了。单机版的mvcc时间戳比较容易做，而分布式的mvcc就需要time oracle

8.论文中代码需要注意的几个点(1)被实现的Transaction是分布式事务，调用的bigtable::StartRowTransaction是bigtable单行事务 (2)oracle.GetTimestamp()是取统一时间戳
(3)注意区分代码中读写数据的时候"lock"，"data"，"write"几种不同的标签 (4)Get方法最有意思的是先去读一下当前row的锁，如果读到了就可能清理过期的锁这也是因为没有协调者所以只能靠读的时候清理锁 (5)数据提交过程类似2pc分两步，第一步Prewrite写入数据和锁信息，这一步可能会发生冲突而失败，第二步真正让数据可见也就是写入"write"列并且会把锁擦除。(6)注意每次写入的时候会选一个Primary Record，这个玩法类似传统2pc Primary写入成功作为如果发生异常后面的客户端判断这个事务该回滚还是该提交的标志。(7)提交的时候擦除锁是一个一个进行的，所以Get()方法碰到锁的时候有一个等待，这样就不会读到部分成功的状态

9.time oracle通过定期分配一个时间范围放在内存的方式避免磁盘io，worker也有定期批量从time oracle获取时间戳的机制，这样time oracle单机tps近两百万，这个地方无法得知更多细节但是思想大致能懂

10.数据触发器这点上使用的是弱一致的通知语义避免锁占用时间太长，而实现通知语义使用的是线程范围扫描，有两个提高性能的点，一个是使用notify列减少扫描数量(因为有变更的毕竟是稀疏的)，第二个是后面的线程扫描和前面的线程冲突的时候会再做一次随机选择避免公交车效应，这里对细节不是很清楚

11.Percolator处理一个文档需要50个bigtable操作，rpc多，所以使用了很多微batch等待打包rpc请求，还有通过对一行数据的预读的方式提高性能

spanner

1.和percolator最核心的区别是spanner是全球分布的而且是一个数据库，所以不能用单一的time oracle，数据时效性也比较重要所以必须有事务协调者

2.多个time server就意味着时间差异，spanner使用了原子钟+gps保证time api高可用而且时间误差非常小，多台time server之前会互相做时间校对，而且每个时间客户端也会从多台time server拉取时间获取综合值

3.有了时间误差就有了置信区间的概念，从time api取得的时间是有误差区间的，所以分配时间戳的时候会把误差区间考虑进去从而保证事务之间的绝对时间顺序关系，甚至会采取等待的方式

4.数据高可用是采取带leader的paxos变种实现的，最基本的单位是tablet(类似于数据库表)，每个tablet的几个replica形成一个paxos group，replica的数量和分布都灵活可配置。读写发生在多个paxos group就形成了分布式事务

5.spanner牛逼的一个地方是数据分片会很灵活，Spanner底层存储的是有序的KeyValue集合，在数据模型上，细化了directory这个概念。一个directory是连续的一组KeyValue，比如user_id=1的用户和他所有的相片信息就组成了一个directory，多个directory组成一个tablet，但又不像bigtable那样每个tablet里面的主键都是连续的按范围划分的。而是通过placement server做动态调整，把经常一起使用的向物理位置近的地方放，做到尽量优化

6.分布式事务采用的是2pc+mvcc的方式实现，每个事务都会有协调者，协调者的选举应该也是和高可用的leader选举类似。剩下的核心点就是怎么控制time api的误差来做到先提交的事务先可见。之前有个疑问是为啥不用协调者生成事务id，这是因为协调者可能会经常变，而且不同事务的协调者可能不是一个

7.spanner的数据模型还是google最常用的基于嵌套结构的半关系型模型，spanner tablet的存储是类b tree，这个细节会有什么影响还需要后续了解

google dremel

1.第一个核心问题是通过列的方式存储嵌套的数据结构，所以有了r,d的数据描述和有限状态机的数据读取形式

2.r代表当前记录和上一条记录在哪个嵌套深度有公共节点，d代表当前记录walk到根节点需要走过的记录数，d对有内容的节点其实意义不大因为都应该是一样的但是对null意义比较大，能还原出null所在的层级，通过r和d就能完整的还原出整个层次结构

3.只存储叶子节点的数据，读取过程是通过有限状态机在不同列之间跳转读取来还原嵌套结构

4.查询的时候好像也没有什么大招，就是先还原出嵌套结构，然后过滤，但感觉这个顺序可以穿插起来如果是单条件查询感觉还是没有什么好招去加速
5.嵌套的数据结构和关系型一对多多层关联相比，保留了数据关系，跨层关联的时候比如查询Country是xxx的name有多少个，关系型数据库就是三层join，而嵌套型结构需要遍历的数据会少很多，在dremel里面可能是先查一下Country列，然后根据r和d判断一下对应的name就可以了，都不一定要走中间language层。嵌套型的缺点是可能会有大量数据冗余，视具体情况而定

Durid

1.实时olap，亚秒级查询，实时数据导入立即能查到，不支持join，列存，有时间序列数据库的特点，带上时间查询会方便寻址  

2.olap基本理论，列按照职责划分timestamp column(时间戳)，dimension columns(过滤或者聚合的维度)，Metrics(聚合和计算的基本数值)

3.durid不存基本数据而是在数据导入的时候预先对数据做各个维度的first level roll up即预先做好基本聚合，是典型的molap，这个和工作中遇到的数据应用场景完全吻合

4.durid分实时节点和历史节点，实时节点定期merge到历史节点，查询也可能merge实时节点和历史节点的数据

5.segment是存储的基本单位代表一个时间窗口内的数据，Segment文件名称的格式:dataSource_interval_version_partitionNumber

6.完全的列存，只保存列值不保存row-key，会采用字段表的方式压缩，还有位图信息做过滤筛选

Kudu

1.融合oltp和olap，hbase，cassandra这些大范围scan性能有限，纯列存数据库随机读写性能差。kudu大范围scan性能高，随机读写性能不太差

2.真正的列存而不是sstable，schema固定，数据有类型。有一个隐性的行号列，通过这个行号列来定位列里面的记录

3.分区方式是hash+range结合，兼顾范围扫描和避免局部热点

4.RowSet是最小存储单位，又分为MemRowSet和DiskRowSet，内存中用的是行存储刷到硬盘中使用的是列存储。Kudu的存储是base+delta的形式不同于lsm，lsm永远先写MemStore，Kudu是insert先进mem但是update可能会直接写到disk，lsm的key对应的值可能在多个store但是kudu的只会在一个RowSet的范围内，虽然可能同时在MemRowSet和DiskRowSet甚至delta file里面  

5.一个RowSet只有一个MemRowSet，数据insert的时候都会进MemRowSet，实现是一个并发优化过的b+ tree。RowSet有一个DiskRowSet(base file)和多个DeltaFile(undo，redo record)

6.DiskRowSet是列存，会被切成多个page而这些page通过b tree管理，也用了bloom filter来加速对pk的查找。DeltaStore也分Mem和Disk，会组织一个map，key是(row offset+timestamp)，value是rowchangelist。update的时候会先通过bloom filter和b tree从DiskRowSet里面找到记录的offset，然后在delta file对应的offset的位置写入值

7.kudu也支持mvcc以及external consistency，也有类似于time oracle的hybrid time

Calvin

1.解决事务并发冲突的办法是让事务根本无法并发，把所有事务做一个全局排序变成确定性的，有一个关键点是batch，不然无法做依赖排序

2.许多sequencer拦截所有的事务请求然后保存到局部一点的存储并同步到其它sequencer对应的存储，这些存储又被一个中央的meta存储管理

3.很多scheduler并行去执行这些事务，如果所有事务单线程执行当然不会出错但效率太低，我的理解是scheduler会分析这些事务的数据依赖，然后尽量并行它们。这个方案给我的感觉有点类似oz的思想

图数据库  

1.索引存储的方式是用顶点+邻接表的方式存储，所以邻接表拿到顶点列表，以及通过顶点拿边都是O(1)的时间，所以就很快了。而mysql join找相邻顶点列表，以及通过顶点找边都要扫表    

2.比如有一个user表，一个item表，要存储好友关系和购买关系，就会有一张friendship表和一张purchase表。这个存储方式和关系数据库里面自己建表的方式区别不大，但是在查询的时候我理解图数据库是用图搜索的方式推进的而关系数据库是通过join实现的，所以在查询多层关系(>3)的时候图数据库性能有指数级别优势

向量化执行引擎

相关的两个关键字是列存和SIMD，SIMD是多个操作数组成向量一个指令完成多个操作数运算。向量化执行引擎充分利用SIMD，而只有列存的情况一列数据才会很容易load成向量利用SIMD进行操作

KAD(Kademlia)算法

1.这是一个分布式hash的算法，可以参见文章https://www.jianshu.com/p/f2c31e632f1d  

2.首先是存储内容按hash值尽量均匀分配存储到多个节点，并且有冗余备份

3.算法的核心是怎么寻址，地址不可能在每个节点全量存储，所以每个节点只能存部分地址，这种情况寻址肯定是跳多个节点。整个算法的亮点是发明了一种xor距离的概念，xor距离带来了距离分层2^0, 2^1, 2^2 ...在相同层次k的节点之间的xor距离必定小于2^(k-1)。所以这样带来的结果是最多k次寻址就可以找遍2^k个节点，而且每个节点的地址表理论上存k个地址就够了

IPFS(星际文件系统)

1.对标http，http是中心化存储，ipfs是真正意义上的分布式文件存储。而且由于merkledag的数据结构，可以做到分布式环境下的去重。  

2.个人理解的核心是把文件拆成块使用merkledag数据结构存储，可以起到文件寻址，去重，防篡改等类似区块链的效果，然后对每个块使用KAD算法做分布寻址。  

3.在应用上增加激励机制来鼓励分享这样会有很多应用的想象空间。

Succinct Trie

1.高压缩trie tree，succint数据结构是一种高压缩数据表示方法  https://www.jianshu.com/p/47a61caa6490

2.succint主要是用位图的方式表达了树的结构关系，核心在于rank1(0)和select1(0)两种操作分别代表第position[0 ... x]中1(0)的个数和第x个1的position。对树的编码方式是节点r有0个子节点就是0，有1个子节点是10，2个子节点110 ... 然后按广度遍历的方式放置成一个bitmap

参考文章https://www.jianshu.com/p/36781efac8e9  

3.树的子节点或者父亲节点都能用rank和select两种操作简单表达出来

4.Fast Succinct Tries分sparse和dense两种，dense一般在trie上层因为上层一般比较满，sparse在下层。dense每个节点，1层放所有字符比如a-z的bitmap，2层bitmap放有没有子节点，3层bitmap放是否是前缀结束，4层是合法前缀对应的值。查询的时候2层用来做tree导航。sparse结构每个节点，1层放字母的二进制，2层用一位表达是否有子节点，3层表达是否是父节点的第一个子节点，4层放合法前缀对应的值。2,3层用来做tree导航。

5.Fast Succinct Tries点查比bloom filter差，范围查好很多

Fractal tree(toku db)

1.mysql(innodb) pk 顺序插入快，随机插入慢。原因是随机插入可能造成节点分裂写放大，存储不连续碎片化。

2.mysql有插入缓冲的解决方式只能针对非主键，大致做法就是增加一个缓冲区，批量刷出。

3.fractal tree的解决方案，结构上类似b+ tree，但每个节点都带msg buffer。插入操作的时候先找到某个节点对应的msg buffer然后放进去就ok了，后台线程异步刷出去。怎么找这个节点的细节还不太清楚。查询的时候需要合并整个查询路径上的msg buffer上面的信息，所以会比较慢。

RAFT

1.通过广播消息+timeout选master，拿到多数票胜。

2.只写master，写了之后记wal日志然后广播到其他节点，拿到多数日志算提交记录commit日志并返回，否则回滚。这里wal日志和commit日志也可以合并。

3.新节点通过master的commit日志来追进度达到一致状态，也可以通过定时的snapshot快速追状态。

存算分离

1.解决成本问题，比如双11只是计算突然飙升但是存储没有太大增加，扩容性价比太低

2.存算一体数据库扩容故障恢复要搬数据(多数情况)，恢复时间长

3.存算分离可以使用比一体式方案大很多的存储，大幅度减小分布式事务分布式查询的概率

4.mysql存算分离不是简单的把本地存储换成云存储，需要有存储引擎的较大改变，比如Aurora,polardb,cynosdb。但似乎存算分离的数据库还是单实例数据库，并不能算分布式数据库。

polardb的分布式应该是在存算一体的基础上附加了分布路由和事务

5.这样做的原因是(1)大量存储空间浪费，page+各种log*主备实例数*云盘三副本(2)本地io变网络io各种性能消耗，带宽消耗

6.db即redo log，只保留一份redo log，其他所有的数据都可以从redo log恢复。写入操作只要redo log落存储层就算成功。redo log被分成多个segment来实现扩展性，log和data遵守一致的分片策略。存储层有能力从log恢复出数据页(传统数据库是计算层做的)，计算层读取缺页的时候可以直接从存储层读取

7.计算层依然分主从，但主从都从统一的存储读取。计算层完全无状态，可以快速恢复。

8.CynosStore存储的特点，第一是非对称读写，（写的是日志、读的是数据）。第二是异步写，同步读。第三并发写入、日志串行化。第四是支持两层，块设备层、文件系统层。第五能接入任何基于日志先写的存储系统。第六是存储分布式化

RoaringBitMap

1.主要为了解决bit map稀疏时浪费空间较大的问题，比如32位数的bitmap存储是512M，但如果数很少会比较浪费

2.Roaring Bitmaps把32位数的空间划分成2^16个桶，每个桶最多可以存放2^16个数，刚好覆盖整个空间，桶里面存的是数字的低16位

3.保存一个数的时候用数的高16位作为桶的编号，如果桶内的数较少少于4096，就存成array，这样比较省空间，比如只有4个数就只用存4*2个字节，array动态扩容。如果数较多就会存成bitmap，2^16个bit是8KB的空间

4.如果存满是65536*8K=512M，和bit map相同。参考不深入而浅出的Roaring Bitmaps原理

5.64位不能简单像32位那样搞2^32个桶因为一个2^32的数组占用空间已经很大了。一种做法是前32位用红黑树存，更好一些的做法是前48位用art tree存，后16位还是放在一个个桶里，art tree可以认为是可变长的tried tree，每层的节点数可以是4个，16个，48个或者256个。

Z-order Index

1. 参考Z-order是如何提升查询性能100倍的
2. 解决的问题还是b tree多维度索引必须前缀匹配的问题，z-order的思路是把多维的信息压缩成一维的顺序，而且每个维度平等，尽量保证局部性
3. 压缩下来的效果的例子(a1,b1),(a1,b2),(a2,b1),(a2,b2),(a2,b3),(a2,b4),(a3,b1),(a3,b2)...
4. 二维信息压缩的方式，将x和y表示为二进制以后，每个bit位相互插值即可产生Z-Address
5. 这样做的好处是多个维度查询都能获得不错的性能，但缺点是单一维度没法获得极致的性能了，这可能也是clickhouse没有使用z-order的原因
6. 本质是一位有序路径上尽量保证高维度上的局部性，Z-order的Z字形路径其实还不完美，还有希尔伯特曲线路径等等

向量检索

1. 向量索引对LLM有用，因为LLM context不能太长(内存，计算复杂度，长期依赖)，向量化可以储存context知识，相当于LLM的一份外存
2. 一种比较优秀的向量检索算法是scann
3. 算法的主要思想是，近似计算，信息压缩，分片查询
4. 首先是Vector quantization，快速理解可以看矢量量化，把高维(d)向量拆成M块，对每一块做KNN选256个中心点(8位)，然后把每一块数据替换成0-255中间的一个，这样原来的数据变成了M个byte。原来的内积相似搜索O(Nd)变成现在的O(256*d+MN)，M<<d
5. 同样通过K-means把把空间划分成多个部分，看查询点q处于哪个部分，然后只比较那个部分所有的点就好了
6. 在这些的基础上scann提出了各向异性量化损失函数提升计算精度，细节没太懂基本思想是和传统的内积损失函数比，增加了和向量方向相同的权重，降低正交方向的权重

XOR Filter&Ribbon Filter

1. xor filter 比Bloom Filter节省25%空间！Ribbon Filter在Lindorm中的应用
   
2. bloom filter的主要问题是空间占用较大1.52n(n=log...)所以有了省空间付出额外cpu的xor filter(1.23n)
3. xor filter的主储存是m=1.23n个元素的数组，每个元素r位。查找的时候对于key，算三个hash到数组三个位置拿出三个r位的元素做xor，xor的结果用来和footprint(key)做比较，不相等就确认false
4. footprint函数怎么来的还不太清楚，已有footprint函数和3n个hash函数的情况下构建xor filter的过程大致是每个元素找不和其他元素hash后发生位置冲突的位置，重复这个过程直到所有元素放进数组(如果找不到了就换hash函数重来)。最后插入的item位置直接设置对应footprint函数的值，然后开始反推其他item位置对应的hash值(用已有hash xor footprint)
5. ribbon filter是在xor基础上进一步优化空间，基本思路是类似的，主要的区别在于三个hash函数的结果是一个向量，filter数组是一个0,1矩阵，filter的过程是计算矩阵乘法。filter构建的过程是高斯消元法(解多元一次方程组)
6. ribbon filter的filter数组是列存，过滤时不需要一次全部加载可以一列一列计算有短路逻辑
7. ribbon的r是7而xor是8所以ribbon的存储是1.101，之所以能做到是因为矩阵信息更密集？