BigTable
技术选型:
| NoSQL Database | Company |
|---|---|
| BigTable | |
| HBase | Yahoo(Open source of BigTable) |
| Cassandra | |
| DynamoDB | Amazon |
Scenario
分布式数据库
Service + Storage
数据是以一个表结构的方式来存储的, 数据最终都会存放在文件中.
查找数据
直接在硬盘中对数据进行排序 (外排序), 并且在硬盘中二分查找.
修改文件内容
有三种方案:
-
直接在文件里面修改: 很难做到直接修改内容, 如果原来是 4 个字节, 现在修改成为 8 个字节, 那么之后的内容都需要移动位置.
-
读取整个文件, 修改好后, 删除源文件, 写入新文件: 非常耗费时间
-
不修改, 直接 append 操作追加一条记录在文件末尾: 非常快.
BigTable 为了写优化选择了直接 append, 这样就会引入两个问题:
-
读取数据怎么识别哪个是最新的记录?
-
append 操作破坏了顺序, 怎么二分查找?
读取数据怎么识别哪个是最新的记录?
时间戳最大的那个就是真正的数据
没有顺序怎么二分?
每一个文件被分为几个块, 前面每一个块都是有序的, 而最后一个块没有序. 如果最后一个块被写满了, 那么就将其排序, 再新开一个块供新数据写入.
块会越写越多, 会有很多重复的情况. 所以我们要定期进行 k 路归并.
怎么把最后一个文件块从无序变成有序?
有三种解决方案:
-
全部读取到内存中来排序
-
硬盘外部排序
外部排序: 当要排序的内容大小远远大于内存大小时, 需要使用硬盘来辅助排序. 先将要排序的文件分成 n 份, 使其一份可以写入到内存中, 分别将这 n 份文件读入到内存中排序, 然后再写会硬盘. 接着使用 k 路归并排序(合并 k 个已经排序好的文件) k <= n, 使用多次 k 路归并排序后, 即可得到最终完全排序好的文件.
- 一开始就将最后一个块的文件存放内存中
这里有一个配置, 那就是一个文件块基本都是 64MB 或 128MB 或 256MB, 这样内存中就完全可以存放得下. 所以 一开始就将最后一个块的文件存放内存中 这种方法节省从硬盘读取的时间, 是最为省时的解决方案.
完整的写入过程
graph TB A(client) --> |"写入"| B(Service) B --> |"写 log"| G(Disk) B --> E("Memory Sorted List(Skip List)") E --> |"块写满"| H(生成 Bloom Filter 和 B+ Tree) H --> F(只序列化, 不需要排序, 因为插入过程一直在维护跳表) F --> |"写入磁盘"| D(Disk)如果机器挂了, 内存没了怎么办?
在写入数据的时候写 log.
完整的读出过程
graph TB A(Client) --> |"读取"| B(Service) B --> |"先读内存中的文件(Sorted List)"| J(Memory) J --> |"查找跳表(内存中的文件 Sorted List 是用跳表存放的)"| K{"找到了?"} K --> |"是"| L(END) K --> |"否, 从最后一个硬盘块开始"| C(Disk) C --> |"读出块的 Bloom Filter 和 B+ Tree 索引"| F(Bloom Filter) F --> |"过滤"| G{存在?} G --> |"否"| H(END) G --> |"是"| I(B+ Tree 索引) I --> |"找到磁盘位置区间, 读取到内存中"| D(Memory) D --> |"二分查找"| D D --> E{"找到了?"} E --> |"没找到, 读上一个块"| C E --> |"找到了"| END(END)改进措施?
可以在内存中用 B+ 树来做索引, 索引是字符串, 索引值为磁盘中的位置, 由于文件是已经排好序的, 所以这样可以减少二分搜索范围, 加快查找速度.
可以用 BloomFilter 来做前置的过滤, 看看这个 key 是否在文件中.
一个数组(bits)长度为n, 多个 hash 函数, 初始化的时候将每个 hash(key)%n 的位置标记为 1. 在查找的时候, 查找每个 hash(key)%n 的位置是否都是1. 如果都是1, 那么可能存在也可能不存在; 如果有0, 那么一定不存在.
那么 Bloom Filter 精确度跟什么有关系?
-
hash 函数个数越多, 精确度越高(不一定, 函数个数越多占用其他位越多, 应该是一个倒 U 型曲线)
-
位数组长度越多, 精确度越高(确信)
-
加入字符串数目越少, 精确度越高(确信)
一些术语
SSTable: Sorted String Table, 就是指的是硬盘中排好序的文件块.
Sorted List: 在内存中存放的文件块, 是用跳表存放的.
Skip List: https://github.com/petegoodliffe/skip_list
SSTable: http://bit.ly/1kqwrFe
Sharding
使用水平 Sharding, 根据 RowKey 来作为 sharding 的依据.
graph LR F(Client) --> |"1 Read OR Write: Rowkey"| A(BigTable Master) A --> |"2 Redirect to slave server"| F F --> |"3 Read OR Write"| C B(Slave Server) --> |"Heart beats"| A C(Slave Server) --> |"Heart beats"| A D(Slave Server) --> |"Heart beats"| ABigTable + GFS
BigTable, GFS 都不是开源产品. GFS 对应 HDFS(Yahoo), BigTable 对应 HBase(Yahoo)
将 BigTable 的文件存放到 GFS 中. 比如 HBase 就是使用 HDFS 作为底层的文件系统.
读写资源竞争
需要一个分布式锁服务器, 选型 Google: Chubby, Yahoo: Zookeeper.
graph TB A(Client1) --> |"1 Write request, lock the special Rowkey"| C("锁服务器") C --> |"2 Succeeded"| A A --> |"Write"| D(BigTable Master) B(Client2) --> |"3 Read request, lock the special Rowkey"| C C --> |"4 Failed, key is locked"| B扩展
LevelDB + LSMTree 可以看看.
标签：文件,--,BigTable,内存,排序,硬盘 From： https://www.cnblogs.com/geraldkohn/p/17091089.html