概论@H_403_2@

数据一致性理论@H_403_2@

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. 向量时钟

存储模型@H_403_2@

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

分区与放置策略@H_403_2@

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

海量数据处理@H_403_2@

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

复制与容错@H_403_2@

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

数据压缩@H_403_2@

1. LZO

缓存@H_403_2@

key-value@H_403_2@

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

列向@H_403_2@

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

文档@H_403_2@

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++编写

图@H_403_2@

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@H_403_2@

1. HBase
2. Hive
3. Pig

Newsql@H_403_2@

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

分布式缓存@H_403_2@

1. Memcached
2. MS Velocity

@H_502_379@企业应用@H_403_2@

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

怎么感觉好像以前看过