基础：
hash（id.offset,length,value,crc,version)，快速恢复单独索引文件
读不加锁：写时复制 /mvcc
写时复制：拷贝，修改拷贝节点，原子切换指向新节点
哈夫曼编码，动态字典
一致性从客户角度：读写一致，会话，读单调，写单调。起码要保证支持。存储系统可以考虑强一致性或最终一致性。
性能分析
1. 生成一张有 30 张缩略图（原始大小 256K）的页面时间：
a. 顺序操作，从磁盘读 + 压缩 30*10ms+30*256K/30Mps=560ms
b. 并发：一次发送 30 个 18ms
2.1G 4B 整数快排
2^28 * log(2^28) * 1/2(一半交换) = 21s。每次分割都要扫描一遍内存 28*1G/4Gps = 7s 和 28s
3.bigtable 1k 数据
随机读（缓存不命中）先从 GFS 读 64K 磁盘 IOPS*10 块 每个 100. 理论 1000qps/s 折损为 300 因此:1k*300ps
内存随机读 cpu 限制按照 10W，内存开销大折损 2 万 =》20Mps
故障检测：心跳（问题是网络断了但是 B 仍然提供服务），租约
——————————————
分布式文件系统
GFS
chunck 服务器：按照每个 chunck 授权刚给 CS租约 成为主 chuck（多副本都成功才行），chunck 内部修改
客户端 库文件形式，从 master 获取路由，直接访问 chunck 服务器，缓存元数据
master 元信息，所有控制（chubby 主备），文件到 chunck 还是在主
文件追加：流水线；分离数据流和控制流。S1,S2,S3，1,2 同机房，控制流 1 =》2=》3 而不是 1 =》3=》2
master 单点瓶颈？
每个 chuck 64M（一般都是大文件，K~M，id 为 64b），3 份，压缩后 chunk 元数据小于 64B。1PB:1PB3/64M64=3G。
chunck 分配，迁移，负载均衡都要限速。分配：磁盘利用率低 + 最近频次防止压垮 + 多机架分配
——————
TFS
写少读多，每次修改在 master 无压力
小文件问题。读目录超级快，inode，实际内容 =》逻辑图片共享一个物理文件 ，抛弃目录树，直接 blockid+offset 定位。
去重：单独键值系统 MD5客户端返回带着 blockiid 去 nameserver 查机器。再带着 offset 去机器定位
——————
haystack 2000 亿图片
haystack 目录（照片 id 到物理卷轴路由）=》haystack 物理卷轴 100G，只追加（单机元数据内存中，每个占用 20 字节：8T/80K*20=2g）
目录量太大，memcache+mysql sharing 集群
——————
CDN
L1chache->l2chache-> 服务器本身 cache->tfs。LVS+NGINX=》
——————————
上述基本都是单层路由。若不够可以两层
——————————————————————————————
分布式 KV
数据分布和负载均衡：自治 gossip，种子节点
若机器被判定临时失效，选一台机器新数据分到这儿，恢复后将数据回传。若永久失效，则进行数据同步，利用 merkle 树（每一段一个 merkle 树，只需要同步从根到叶子节点不同的，叶子节点为文件内容的 hash 值，非叶子节点为其子节点组合的 hash 值）
NWR 机制：N 为副本数量，W 为写至少几份，R 为读至少几份。R 读出来有多份情况，冲突用向量时钟由客户端解决或者覆盖，异步读取覆盖
——————————————————————————————
分布式 table
dbproxy
proxy: 解析 dql, 路由，读写分离，排序，分组
zk: 维护 db 路由，选主
常驻进程：实时监控等
扩容：成倍扩
——————————
bigtable
数据：每行的每一个列（或列簇）构成一个 cell
架构：在 GFS 上添加一层分部署索引层 +chubby 分布式锁
客户端：从 chubby 获取元数据，与子表直连（缓存和 prefetch。过期需要取六次，正常三次）
master：分配子表给子表服务器，指挥合并 / 分裂 / 监控 / 负载均衡 / 故障恢复（只有主在 chubby 的互斥锁失效才能切换）
子表：
chubby: 保整只有一个 master，配合 master 发现子表，存储访问控制信息（两地三数据中心五副本）
元数据也存表中，二级：子表 128M，元信息 1K。量级：(128M128m/1k)128m/1k=2048PB。引导信息（根表位置）=》根表 =》元数据（子表位置，sstable 及操作日志文件编号，日志回放点）
复制一致（全局唯一 id 去重）与容错（定期检查锁有木有问题之类的）。单机存储：sst（想为啥分多层就是写入更快，合并怕影响，写少的话一层，都的话多层）
————————————
megastore
在 bigtable 上支持 sql
客户端：映射操作，事务，并发控制，基于 paxos 的复制，请求发送给复制服务器
复制服务器：接收客户端请求转发到所在机房的 biftable 实例（用于解决跨机房连接数过多问题）协调者：存储是否处于最新状态，用于实现快速读
事务：redolog 写完就可以算成功，若写失败读之前要回放。夸实体组用两阶段 + 分布式队列
写事务流程：同一实体组乐观锁串行化（同一实体组同时更新少，同一个 uid 之类的）
协调者单点（从 chubby 获取锁，失效忽略协调者）
单副本，协调者较复杂，SSD 不支持，只有实体组内部 ACID
————————————
spanner
数据模型。主表包含附表。比如
部署：协调者（主备,paxos），参与者（主备，paxos）
同步：每个子表上运行一个 paxos 状态机 ，主副本默认寿命 10s 全局事务 id:oracle 数据库生成，谷歌时钟器，会返回误差 -4~4e，时间每个都加 4e 即可
事务读写：夸 paxos 组两阶段提交：
prepare：客户端发往多个 paxos，协调者主发起 prepaare 协议，参与者主需要锁住数据。
commit：协调者主发起 commit，参与者主执行提交并解除锁定数据，当前时间戳作为提交版本