概论

数据一致性理论

1. CAP
2. 最终一致性：
   1. 因果
   2. 读自己的写
   3. 会话
   4. 单调读
   5. 时间轴（单调写）
3. ACID/BASE
4. 一致性实现技术
   1. Quorum系统NRW策略
   2. 2PC（缺点：阻塞协议）
      1. 3PC：引入‘超时’
      2. 变种：树形2PC 动态2PC
   3. 时间戳
   4. Paxos
      1. 3种角色：提议者（proposer）、批准者（acceptor）、学习者
      2. 选择唯一的提议：一个批准者选择第一个提议 => 多个批准者进行超过半数（保证了只有1个选中）投票
      3. 一个批准者可以批准多个提议（使用版本号），只要它们内容相同
         1. =>如果一个提议被选中，那么以后任何提议者都只能提出相同值的提议（强一致性？）
      4. 版本号n的‘准备请求’？=> (n,v)提议
      5. 批准者可以接受版本号为n的提议 iff 它没有响应过版本号大于n的准备请求*
      6. * 如何让学习者主动获取最新提议？可让学习者充当一个提议者
      7. * 系统需要选出某个提议者作为唯一的提议者（防止不同的提议者互相竞争用尽版本号资源/死锁）
         1. p38 ZooKeeper使用这种策略，称为‘领导选取’
      8. me：真烦，感觉总是会有漏洞，可以使用同步协议吗？
   5. 向量时钟

存储模型

1. CouchDB用JSON格式存储吗？那它怎么高效索引？
2. GraphDB用C#开发？

分区与放置策略

1. 分区：范围（基于比较操作？）、列表（基于离散的值，集合？）、Hash（某种非线性映射？怎么保证均匀分布？）
2. 放置：顺序、随机
3. 一致性Hash：引入‘虚拟节点’解决LB
   1. 所谓的‘虚拟环’可以理解为Hash值经过了模运算？
   2. 实际上，‘虚拟节点’与物理节点之间可以采用（固定的？）非线性映射，只要能够适应实际的数据即可

海量数据处理

1. MaReduce
2. MS Dryad
   1. Cosmos
   2. SCOPE
   3. DryadLINQ

复制与容错

1. 海量数据的复制策略
   1. Dynamo：优先列表？
   2. CouchDB：（似乎挺适合文档同步？不过对小数目的文件，没有网盘好用）
   3. PNUTS：主从模式，更新提交到YMB后异步复制，‘修改操作呈现很强的局部性’？
2. 海量数据的故障发现与处理
   1. Dynamo：Hinted Handoff？

数据压缩

1. LZO

缓存

key-value

1. redis
   1. v1.2：有序集合，ZRANGE
2. LinkedIn的Voldemort*

列向

1. BigTable
2. Hypertable
   1. Hyperspace（~Chubby）
   2. RangeServer
   3. DFS Broker
   4. 只能按主键查询 => 索引：再建一张表
   5. HQL
3. Cassandra
   1. 一致性Hash：Token、Range、Partitioner
   2. Gossip协议
   3. 备份机制：机架感知
   4. 读写机制：0 ANY 1 QUORUM ALL

文档

1. CouchDB
   1. 历史：IBM的Damien Katz，C++ Append Only --> Erlang --> XML换成JSON，JS查询引擎 --> 支持Map/Reduce
   2. Futon
   3. MVCC：一个HTTP连接打开一个快照视图
   4. Design文档
   5. 存储结构：B+树，ID和序列号作为key
   6. 数据一致性机制：2个‘文件页脚’？
   7. 分布式：CouchDB Lounge？
2. MongoDB
   1. 性能比CouchDB好
      1. 二进制协议
      2. 内存映射
      3. 面向集合的存储，同一集合中有序
      4. 直接修改，非MVCC
      5. C++编写

图

1. Neo4j
   1. p257 图遍历的速度是常数，和图的规模无关？
2. GraphDB C#写的就算了
3. OrientDB（文档+图？）

1. me：如何实现一个通用的B+树文件存储引擎，并支持大规模并发访问事务？
   1. 如何进一步在上面叠加一层GIS 2D查询，乃至更广泛的k-d层次索引？
      1. 并发下的性能：GeoHash？
   2. 如何在GIS 2D查询上再次叠加‘路径规划’功能？
   3. 现有的基于PostgreSQL的GIS插件功能和性能如何？
   4. 如何引入外部的矢量地图生成模块？（这应该是ArcGIS的核心功能？）

基于Hadoop

1. HBase
2. Hive
3. Pig

NewSQL

1. MySQL Cluster
   1. 不是万能的：较大的JOIN性能不好、只支持读提交隔离级别
   2. 部署和调优困难
2. sharding vs 分区（？？）
   1. 用单独的DB保存数据库配置（O,i remember...）
3. VoltDB（内存数据库）

分布式缓存

1. Memcached
2. MS Velocity

企业应用

1. Instagram
2. Facebook对HBase的使用
3. 淘宝OceanBase

怎么感觉好像以前看过