分布式相关理论

CAP原则(参考维基百科)

  • 三选二,一般来说分布式场景下是在保证P的前提条件下CA二选一

    • 分布式架构设计必须考虑到网络环境的不良
    • 基本定义来源

    The choice is really between consistency and availability only when a network partition or failure happens;

  • P(Partition Tolerance):分区容错性

    • 定义英文原文

    The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes

    • 例:数据中心间断网了,集群相当于被割裂为多个子网(network partition)
  • 实例组合(各方说法不一,待证实!)

    • CA:Google Bigtable
    • AP:Amazon Dynamo/Cassandra
    • CP:HBase
    • MySQL:关系型数据库本身事务功能象征强一致性,MySQL Replication方案具体有[不同的实现][1]分属CA和AP

单机存储系统

单机存储系统就是哈希表、B树等数据结构在磁盘、SSD等持久化介质上的实现

结构背景

  • 数据中心网络中心拓扑:接入层、汇聚层、核心层
  • Hadoop HDFS默认存储三个副本

存储引擎

哈希存储引擎(增删改,随机读,键值系统)

  • Memcached、Redis

  • Bitcask

    • 键值Key-Value,仅支持追加操作,写操作只追加不直接修改老数据
    • 任意时刻只有一个文件可写,老文件只读不写
    • 合并(Compaction)
      • 对同一个key的多个操作只保留最新一个
      • 老数据扫描成新数据文件,没有冗余

B树存储引擎(增删改,随机读,顺序扫描,键值系统,关系数据库)

  • MySQL InnoDB
    • 聚集索引组织成B+树
    • 每个页面对应B+树一个节点,叶子节点保存每行的完整信息,非叶子节点保存索引信息,根节点常驻内存
    • 缓冲区
      • LRU(痛点:全表扫描导致大量页面被替换出缓冲区)
      • LIRS(缓冲池分二级,热数据进入第二级,第一级还是LRU,进入标准:时间 / 次数

LSM(Log Structed Merge Tree)存储引擎

  • 增删改查都被看成一种操作

  • 写特性比较,稍微牺牲一些性能

  • 对数据的修改增量保持在内存中(假定内存足够),达到指定限制后将修改批量写入磁盘,读取时合并磁盘中的历史数据和最近的修改操作

  • Google Bigtable(有不少结构与LevelDB相似,毕竟都是Google家的,底层GFS)

  • Google LevelDB

    • 内存:MemTable、Immutable MemTable(磁盘内容)
    • 磁盘文件:当前(Current)文件、清单(Manifest)文件、操作/提交日志(Commit Log)文件、SSTable(记录操作而不是结果,文件按记录的主键排列,MemTable达到一定大小后Dump而成)
    • 操作:修改操作先写入日志,成功后应用到MemTable
  • Facebook Cassandra


数据模型

关系型数据库挑战

  • 事务,位于不同服务器要满足ACID特性需要两阶段提交协议,性能低

    • 写时复制(COW)
    • 多版本并发控制(MVCC):不存在相互关联的事务得以并发处理
  • 联表,设计要求满足范式要求,如不允许某些冗余设计等,而为了避免多表关联操作冗余设计常见

  • 性能,关系数据库一般是B树引擎,更新操作不如LSM,仅基于主键的查询不如KeyValue

非关系型数据库挑战

  • 缺少统一标准

  • 运维复杂,生态不丰富


事务

Lost Update Dirty Read Non-Repeatable Read Second Lost Update Phantom Read
Read Uncommitted Y Y Y Y Y
Read Committed N Y Y Y Y
Repeatable Read N N N N Y
Serializable N N N N N
  • 更新丢失本质上都是该串行化的事务(即事务A的结果应该是事务B的最初读取)最初并行读取了同一个结果,区别在于第一类是回滚覆盖,第二类是提交覆盖

  • Write:(Second)Lost Update
    Read:Dirty Read、Non-Repeatable Read、、Phantom Read

  • 注意这里Repeatable Read是在一个事务内重复读一项数据保持一致,是***一项***不是整体,之所以Phantom Read为none是因为Phantom Read更多指查询的结果集会多出***新的项(别的事务带来的)***


并发控制

数据库锁

  • 死锁:超时控制、等待条件成环检测 ==> 回滚其一

写时复制

  • B+树:拷贝从叶节点到根节点,修改拷贝节点,切换根结点指针,

  • 多个写时操作冲突,同时只允许一个

  • 读操作不用加锁

多版本并发控制

对每行数据维护多个版本,无论事务时间多长都能提供最初的数据

MySQL InnoDB

每行维护"修改"、"删除"两个隐藏列,值为版本号(对应事务号)

  • 常规操作

    • SELECT:行修改号<=事务号 && (行删除号 不存在 || >=事务号),因为删除号<事务号说明已经逻辑删除,修改号>事务号说明后面的事务修改了值,在Repeatable Read情况下后面的修改不应该影响到现在的读取
    • INSERT:行版本号更新为事务号
    • DELETE:行删除号设为事务号,标记逻辑删除
    • UPDATE:把原来的行复制一份,并设当前事务号作为修改号(会留下同一个行不同修改号的多行数据,此处可以思考一下在多余的行被回收完前,SELECT和UPDATE时会选择哪个行)
    • MVCC读数据时不需要加锁,但需要定时清理多余的版本
  • 故障恢复:重做日志

    • REDO日志:checkpoint技术定期将内存中的数据转储到磁盘中,为了在checkpoint期间支持写操作,文件中一般存储日志回放点索引,对于非幂等性操作则将内存结构快照一起存入checkpoint
    • UNDO日志
  • 压缩算法:核心是找重复数据,压缩比和效率

    • 列式存储:对于某些数据类型非常适用(例:男女类型,位图索引,男1001表第一第四行为男)

Written with StackEdit.