0%

Paper-Reading

阅读更多

1 Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age

  1. 为什么现在开始关注many-core架构:随着内存带宽的增长,出现了一些内存级的数据库(广义或者狭义,狭义指的是所有数据完全存在于内存中;广义指的是部分数据以某种形式存在于内存中,比如缓存),对于这些数据库系统,I/O不再是性能瓶颈,能否高效利用好计算机的多个core决定了系统整体的性能
  2. 核心是调度机制:(称为dispatcher),能够灵活的调整pipeline的并发度
  3. 我们的调度程序运行固定的、依赖于机器的线程数,这样即使有新查询到达,也不会出现资源超额订阅,并且这些线程被固定在核心上,这样就不会由于操作系统将线程移动到不同的核心
  4. morsel:data fragment,主要指数据格式,量词,一小部分
  5. morsel-driven调度器的关键特征:任务的分配是在运行时完成的,因此是完全弹性的。即使面对不确定的中间结果大小分布,以及现代CPU内核难以预测的性能(即使工作量相同,性能也会变化)也能有较好的表现
  6. 有一些系统采用了operator维度的并发控制,但是这会引入不必要的同步开销,因为在大部分场景下,operator之间是存在关联关系的,下一个operator需要接受上一个operator的输入,频繁的数据同步操作会带来负增益
  7. morsel-drivenvolcano模型的区别诶是:volcano中的执行单元是相互独立的,但是mosel-driven中不同的pipeline之间是存在依赖的,它们之间会通过lock-free机制来实现数据共享
  8. morsel-at-a-time:一次处理一组数据,随后即进入调度,避免复杂低优先级查询饿死简单高优先级查询
  9. dispatcher的运行有两种方式:其一,用独立的线程或者线程池来完成分发相关的code;其二,每个worker分别运行分发相关的code(take task from a lock-free-queue)
  10. 由于pipeline之间是有依赖关系的,因此,当前驱pipeline完成后需要通知并驱动下一个pipeline,这种机制叫做passive state machine
  11. elasticity:在任何时候可以将core分配给任何查询任务的能力
  12. morsel-driven架构中,取消查询的代价非常低(可能原因是用户取消查询,或者内存分配超限等等异常情况),只需要将查询相关的pipeline标记为cancel,那么所有的worker便不再处理这个查询了(相比于让操作系统杀掉线程的操作来说轻量很多)
  13. morsel-size对于性能来说不是特别重要,通常它只需要保证足够大以分摊调度开销,同时提供良好的响应时间即可
  14. 在一些系统中,那些共享的数据结构,即便是lock-free,也很容易成为性能瓶颈。而在morsel-driven架构中,包含如下几个特点
    • 数据会被切割成一组互补重合的区间,worker工作在某一个区间上,因此cache line基本是和每个区间对齐的,不太可能出现缓存冲突的问题(除非worker从其他worker那边窃取了数据并进行处理
    • 并发度越高,数据结构带来的压力越低(这个怎么理解?)
    • 我们总是可以通过调大morsel-size来降低work-stealing的发生。如果morsel-size特别大,虽然会降低线程的工作效率(本来一份工作可以由多个线程同时处理,比如scan,但现在只由一个线程处理,有些core可能没在工作)。但是随着并发度的提高,这种负增益将会被逐渐抵消(每个core都在工作)
  15. Lock-Free Tagged Hash Table没太看懂
    • The key idea is to tag a hash bucket list with a small filter into which all elements of that partic- ular list are “hashed” to set their 1-bit.
    • Bloom filter相比,优势是?
      • Bloom filter是一个额外的数据结构,而tagged hash table不需要,并且性能开销很低,只需要几个位运算即可
      • 对于大表,Bloom filter体积也会比较大,很难全部加载到cache中(或者只存在于low-level的cache中)
      • 可以直接使用,无需依赖优化器对选择进行一个预测(是否要构建Bloom filter
    • 存储的是tuple的地址而不是对象本身,因此不能使用开放寻址法(为什么???,开放寻址法不能存指针么)
      • 可以通过降低装载因子减小冲突,同时空间开销较小
      • 链表允许存储大小不同的tuple(开放寻址法做不到,为什么???)
  16. NUMA-Aware Table Partitioning
    • 对于需要频繁执行的join查询,最好将其通过同一个key进行散列,这样有更好的locality,避免多个节点之间的交互(shuffle)
  17. 聚合算子的性能与基数分布密切相关(distinct keys),解决这个问题,通常来说有两种途径,一种是基于优化器的预测;另一种就是两阶段聚合,第一阶段做本地聚合,第二阶段做partition聚合,每个partition也有一个hashTable,但是互不重叠
  18. 通常来说,基于hash的聚合算法要比基于排序的聚合算法要更快
  19. 排序也采用了两阶段,难点在于:聚合阶段,如何进行并行聚合且没有同步开销。具体做法是,在第一阶段进行本地排序后,对排序后的数据进行切分,此时需要获取全局的分布信息。这样切分完之后,就可以送往多个不同的节点进行独立的处理(不同节点上的数据也是不会存在重叠的)

progress:5/12 3.3

2 The Google File System

  1. GFS的目标包括:performance(高性能)、scalability(高可扩展)、reliability(高可靠)、availability(高可用)
  2. 在设计中,把失败视为常态而非异常。因此系统必须具备的核心能力包括:持续监控、错误勘探、错误容忍、自动恢复
  3. 管理几十亿个KB大小的文件不是一种好方法,需要重新设计文件格式、I/O操作的块大小等参数
  4. 绝大部分情况下,文件总是追加写入而不是覆盖写入,因此并无随机写入的需求
  5. GFS放宽了一致性模型的要求,从而大大简化了文件系统的设计,降低用户的使用心智
  6. GFS的假设
    • 文件系统由许多廉价的机器构成,并且这些机器容易出错(宕机等)。因此必须能够持续监控自身、探测错误、容错,并且敏捷地从异常中恢复
    • 系统存储少量大文件,大小在100M、1G甚至更大。并且能够基于这些大文件提供高效的操作。小文件肯定支持,但是不会针对小文件做太多优化
    • 工作负载包含两类读操作:大数据量的流式读取以及小数据量的随机读取。对于小数据量的随机读取,性能敏感性应用通常会进行批处理和排序,以稳定地浏览文件而不是来回移动
    • 工作负载支持两类写操作:大数据量的顺序写入以及小数据量的随机写入。其中小数据量的随机写入性能不会很好
    • 系统必须为并发写入提供高效的实现,并且提供明确的语义
    • 可持续的高带宽比低延迟更重要
  7. GFS具有常规文件系统的接口,包括:createdeleteopenclosereadwrite。同时增加了两个新操作snapshot以及record append
    • snapshot以非常低的开销进行文件或者目录树的拷贝
    • record append能够处理大量客户端的并发请求,并且保证其写入的原子性
  8. GFS包含一个master、多个chunkserver以及大量的clients
    • 文件被拆分成大小固定的chunks,每个chunk由一个全局唯一的chunk handler标识,该标识由master签发
    • chunkserverchunk以linux文件的形式存储在本地磁盘上,并且通过chunk handler进行操作。基于可靠性考虑,每个chunk都会存在多个副本,并且分布在不同的chunkserver
    • master中存储了全部的元信息,包括namespaceaccess control、文件与chunk的映射关系、chunk的位置信息等。同时,master也控制着chunk lease、垃圾回收(无用chunk)、chunk迁移等过程。masterchunkserver之间通过心跳包保持通信,用于传递指令以及采集状态信息
    • clientmaster中获取元数据,然后直接从chunkserver中读写数据
    • 无论是clientclient会缓存元数据,但是不会缓存数据)或者chunkserver都不用缓存(这里的缓存指的是GFS层面的缓存),这是由工作负载决定的,大部分的时间都在读写大批量的数据,缓存在这种场景中,用处很小。无缓存降低了系统的复杂度。虽然chunkserver不用缓存,但是其存储是基于Linux文件系统的,Linux文件系统本身是有缓存的,对于频繁读写的数据是有性能增益的
  9. single-master能够有效的降低系统复杂度,并且使得master能够借助全局信息处理诸如chunk替换以及克隆等复杂操作。同时,我们要尽最大努力降低master在普通读写操作中的参与度,避免其成为性能瓶颈。虽然client不从master中读取数据,但是它需要知道从master中获取哪些chunkserver存储了相应的数据,因此client可以缓存这些信息,从而降低与master的交互频率
  10. chunk size是GFS的关键参数,建议值是64MB。大的chunk size包含如下优势
    • 降低了clientmaster的交互频率,如果读取的数据在同一个chunk中,那么直接从chunkserver中读取即可,无需与master交互
    • 使得client的大部分操作集中在一个chunk中,避免多机网络开销
    • 降低了master中元数据的大小,chunk size越大,元数据数量越少,从而使得master将元数据存储在内存中成为可能
  11. 大的chunk size也存在劣势,包括
    • 增大了热点chunk出现的概率。但是对于GFS的预设的工作负载来说,热点不会是主要问题,因为大部分都是顺序读写大批量的chunk
  12. master存储了如下三种元数据
    1. 文件以及chunknamespace
    2. filechunk的映射关系
    3. chunk的每个副本的具体位置信息
    • 所有的元数据都存储在master的内存中,前两种类型也会以日志的形式持久化到本地磁盘上
    • master不存储chunk的具体位置信息,而是在master每次启动或者有新的chunkserver加入集群时主动询问
  13. 对于存储在内存中的元数据,master会对其进行周期性的扫描,主要实现以下功能
    • 实现垃圾回收,清理那些被标记删除的chunk
    • chunk克隆,用以应对chunkserver宕机
    • chunk迁移,实现负载均衡
  14. master不会存储chunk的位置信息,而是在启动时,主动向chunkserver拉取这些信息,master始终保持原信息的有效性,因为它控制着所有chunk的迁移、拷贝等操作,并且与chunkserver通过周期性的心跳包来定期同步状态
    • 采用这种设计的另一个原因是:chunkserver对一个chunk是否在其本地磁盘上有最终解释权,没有必要维护一个master视角下的一致性视图。大大降低了复杂度
  15. operation log记录了metadata的历史变更。master必须确保操作日志落盘后(本机以及用以备份的远程主机),才能返回client
    • master可以通过重放日志来恢复自身的状态
    • 当日志数量超过一定的阈值后,可以通过checkpoint来解决这个问题,checkpoint可以简单理解成某个时刻master内存数据的快照,其数据结构类似B-tree
  16. GFS采用了一种松一致性模型。引入两个概念consistent以及defined
    • consistent:所有客户端看到的数据都是一样的(从任意副本上)
    • defined:所有客户端都能看到引起数据变更的操作具体是什么
    • a serial success mutationconsistent and difined
    • concurrent success mutationsconsistent and undefined
    • failed mutationsinconsistent and undefined
  17. Data mutations包含两种操作write以及record append
    • write:表示往指定的offset写入数据
    • record append:表示往文件最后追加数据。在并发的场景下,至少有一个能追加成功
  18. GFS的松一致性模型保证的约束有
    • 文件命名空间变更是个原子操作
    • a sequence of successful mutations之后,相应的文件是consistentdifined。GFS通过在副本上重放操作来保证defined特性,并且通过版本号来检测那些过时的chunkchunkserver从错误中恢复回来,但是错过了一些变更),这些过时的chunk将不包含在master中。此外,由于client会缓存chunk的位置信息,因此在缓存失效之前可能读到旧的数据,而大部分的文件都是append-only的,因此大概率读到的是不完整的数据而不是错误的数据,又进一步降低了影响
    • 当一个chunk的所有副本均丢失后,chunk才算丢失。在恢复之前,GFS会返回清晰的错误信息而不是错误的数据
  19. 使用GFS的应用,最好使用追加写而不是覆盖写,因为追加写具有更好的性能以及错误恢复能力
  20. 系统被设计为尽量避免与master交互
  21. Leases and Mutation Order
    • 在执行变更操作时,master会挑选出某一个副本作为primary,然后由这个primary决定这一组操作的执行顺序,然后将这个执行顺序同步给其他副本
    • 租赁机制是为了降低master的参与度,避免master成为系统的瓶颈
    • 在执行变更的过程中,master还有可能通过心跳包发送额外的变更请求,或者直接终止变更操作
      • 假设有2个副本A、B,A变更结束,B还在变更,此时master发送终止变更的消息,A和B将如何恢复?
    • 变更操作的整体流程(看论文就行,这里不赘述)
      • 第三步:论文中是由client向所有的replicas推送待写入的数据,这就要求clients必须知道集群中的所有副本情况,才知道发给谁,感觉有点怪。更好的做法是:发给其中某个副本,然后让这个副本同步给其他副本
      • 第六步:如果部分副本变更成功,部分副本变更失败时,怎么回滚?不需要回滚,因为数据有版本的概念,假设有三个副本A、B、C,A、B都写入成功了,chunk的版本号是6;C写失败,版本号还是5。但此时,A和B构成了一个多数派,变更操作成功,并且将版本信息告知master,下次client读的时候,仍然可以从A、B、C三个副本中随机读取,假设选择的是C,但是一看版本号不是最新的,那么就会重新发起读操作,直至读取到最新的数据。此外,失败的副本会有补偿机制来进行修复
    • 如果需要写入大量数据(规模超过chunkSize),client会首先将其拆分成多个小块,但是这多个小块的多次写操作可能不是原子的。因为在写入的过程中,可能会插入其他client的写入操作。最终多个副本上的数据一定是相同的,但是从不同client的视角上来说,变更的顺序可能是不同的。因此此时就是consistent but undefined
  22. Data Flow
    • 控制流与数据流解耦(控制流中不要阻塞等待io事件)
    • 为了最大程度地利用机器带宽,数据被组织在线性的pipeline中,而不是其他复杂的拓扑结构。目的是为了更快的传递数据,而不是将时间消耗在拓扑结构处理中(效果会很好?)
    • 更具体来说,当有数据需要传送到多个节点时,机器只会将数据发送给离自己最近的节点,然后依次类推。如何计算距离:通过ip地址(估计通过网段的差异性来判断距离的远近)
    • 当机器收到数据的同时,就立即将数据forward到其他节点
  23. Atomic Record Appends
    • 传统的写操作,需要提供数据以及写入的offset,并发写无法做同步(为啥???),导致最终结果包含多个client的数据
    • append write中,客户端只需要提供数据,GFS会提供该操作的至少写入一次的原子语义,并且将数据写入的offset发送给client。这与Unix中的O APPEND文件模式相同
    • 如果任何一个副本写失败,客户端都会重试。这就会导致不同副本上的同一个chunk可能包含不同的数据(由于重试导致的重复)。GFS并不保证chunk在字节层面完全一致,它只保证数据至少被写入一次
    • 写操作成功意味着,数据以相同的offset被写入到所有副本的chunk中。这不是跟上条矛盾了么,如何解决?为后续的写操作分配一致的offset,一般来说,就是那个包含重复数据最多的chunk的末尾的offset,这样能够保证相同offset这个语义(会导致chunk中存在空白块)
  24. Snapshot
    • GFS几乎在瞬间就可以生成文件或者目录树的快照,尽量减少在生成期间由于其他变更引入的数据不一致。在实际场景中,会大量使用该功能来创建海量数据的副本(或者副本的副本),以及创建checkpoint
    • GFS使用了Copy-On-Write技术来实现快照
    • master收到了创建快照的请求时,会先回收相关chunk的租赁,于是后续针对这些chunk的写操作都需要与master进行交互。然后master创建该chunk的一个副本
      • 拷贝一份文件或者目录树的元数据,新老两份元数据指向的是同一个chunk
      • 当对副本进行写操作时,才会进行chunk的拷贝动作
  25. master允许同时处理多个请求,并采用适当粒度的锁来保证同步
    1. 与传统文件系统不同,GFS没有为目录提供用于保存该目录下所有文件和子目录的数据结构,也不支持别名(类似于软硬链接)。GFS在逻辑上将其命名空间表示为将完整路径名映射到元数据的查找表。使用前缀压缩算法,该查找表可以保存在内存中
    2. 每个命名空间(文件或者目录)都有一个读写锁。每个操作都需要获取一系列的锁,例如对/d1/d2/.../dn/leaf的操作,需要先后获取/d1/d1/d2/d1/d2/d3、…、/d1/d2/.../dn以及/d1/d2/.../dn/leaf的锁,这里leaf可以是文件也可以是目录
      • 以一个例子来说明锁机制是如何工作的:在创建/home/user的快照/save/user的过程中,创建/home/user/foo文件。首先,快照操作会获取/home/save的读锁以及/home/user/save/user的写锁。文件创建操作需要获取/home以及/home/user的读锁以及/home/user/foo的写锁。因此这两个操作会被串行执行,因为它们都需要获取/home/user这个锁(读写锁冲突)
      • 可以看到,我们在创建文件时,在其父目录上只加了一把读锁,这种锁机制的好处在于,它允许在同一个目录上进行并发操作。例如我们可以并发地在一个目录上创建多个文件。同时,该读锁可以确保目录不被删除、重命名、创建快照
      • 由于namespace包含了非常多的节点,因此读写锁被设计成延迟加载,以及在不用时,锁会被删除
      • GFS会严格保证按照namespace的层次结构依次顺序获取锁,以免发生死锁
  26. Replica Placement
    • GFS集群可以包含多个层级结构。通常一个GFS集群包含成百上千个节点,这些节点可能跨机房部署,因此两台机器之间的通信也可能跨机房。显然跨机房的网络带宽一般小于同机房的网络带宽。因此multi-level分布式架构对高可用、高可靠、高可扩展提出了全新的挑战
    • hunk replica placement policy有两个目标
      • 最大化可靠性和可用性
      • 最大化带宽利用率
    • 为了达到上述两个目的,仅跨机传播副本是不够的,还必须跨机房传播副本,以提高容灾能力。即便一个机房挂了,服务也照样可用。同时跨机传输会带来带宽的开销,因此需要在两者之间做一个权衡
  27. Creation, Re-replication, Rebalancing
    • chunk副本的主要原因有三个:chunk的创建、恢复以及负载均衡
    • master创建一个新的chunk时,需要决定将这个chunk放到哪个chunkserver上,会考虑如下几个因素
      • 挑选一个磁盘负载最低的chunkserver
      • 控制每个chunksever近期创建chunk的数量。尽管chunk创建本身开销很低,但是创建通常伴随着大量的写入操作,因此整体上来讲需要做一个动态平衡
      • chunk跨机房分布
    • chunk的副本数量小于一个阈值时,master会开启副本拷贝的流程
    • 此外,chunk克隆也有优先级。因素包括:缺失的chunk数量
    • 为了避免克隆带来的网络开销,master会在集群维度和chunkserver维度分别限制克隆任务的数量
    • master还会周期性的迁移这些chunk,以获得更好的分布情况,磁盘利用率以及负载均衡
  28. Garbage Collection
    • 当一个文件或被删除后,GFS不会立即进行物理删除,而是记录日志,并且将其名字改成一个隐藏名。同时master会定期扫描所有namespace,并对这些特殊名称且过期的文件(超过一定时间,默认3天)进行物理删除。而在此之前,仍然可以通过这个特殊的隐藏名访问读写文件,或者将其重命名为正常文件
    • chunkserver会与master通过心跳包交换信息,chunkserver会告知master自身存储的所有chunk,而master会告知chunkserver哪些chunk已经可以删除了(没有被任何一个文件关联),chunkserver会在空闲时间删除它们
    • GFS中的garbage collection特别简单,它能够快速确认哪些chunk可以删除,因为master在元数据中维护了file->chunk的映射。同时可以很容易地确认所有chunk副本的信息,任何不在master中记录的副本都可以当成是garbage
    • 与传统的即时删除相比,GFS的垃圾回收有如下优势
      • 简单可靠
      • 定期与chunkserver同步chunk信息,确保信息的正确性
      • 批量写操作,开销低
      • 仅在master空闲的时候进行,避免影响正常业务
      • 容错性更好,由于删除只是写日志以及重命名,当有异常时,可以非常方便的进行错误恢复,比如回滚等等
    • 与传统的即时删除相比,GFS的垃圾回收有如下劣势
      • 存储资源紧张时,可能会存在问题,此时需要调整过期的阈值,让文件尽早物理删除
      • 频繁的创建、删除同名文件可能会占用不同的存储资源
    • GFS允许为不同的namespace设置不同的存储策略,包括副本数量、是否即时删除等等来解决上面的问题
  29. Stale Replica Detection
    • master通过给每个chunk维护一个version,来判断chunk是否是最新的
    • master在垃圾回收时,进行过期副本的处理。因此master仅可简单地认为自己维护的副本都是最新的即可。此外,作为补偿,在进行写操作或者进行chunk克隆的时候,都会校验version
  30. GFS最大的挑战之一就是如何处理频繁发生的组件异常
    • 不能完全信任硬件设备(包括磁盘等)
    • 组件异常可能导致服务不可用,或者数据损坏
  31. High Availability
    • Fast Recovery
      • 无论master或者chunkserver正常或异常终止,都需要在启动时进行信息同步
    • chunk replication
      • 前面讨论到,chunk的不同副本存放在不同机器,以及不同机架上,当chunkserver宕机后,master便会开启克隆任务,确保副本数量不小于某个值(默认3)
    • master replication
      • 处于可靠性考虑,master的状态也会以多副本存储在多个机器上。一个写操作当且仅当其操作日志在当前机器以及所有副本机器上成功落盘后,才算成功
      • 正常情况下,只有一个master提供服务,并管理所有的任务(包括克隆等等)
      • master宕机后,一个GFS之外的监控系统就会在另一台机器上重新拉起master,并且按照日志重建状态即可
      • client需要使用dns、而不是master ip,这样当master发生切换时,client无需感知
      • shadow master会提供读服务(即便primary master宕机)

3 Bigtable: A Distributed Storage System for Structured Data

  1. GBT的目标包括
    • 适用范围广
    • 高可扩展
    • 高性能
    • 高可用
    • 高可靠
  2. GBT不完全支持关系型数据模型。相反,它提供了一种简单的数据模型,但是支持对数据的布局以及格式进行动态修改
  3. Data Model
    • 一个稀疏的、分布式的、持久化的、多维度的、有序字典
    • key可以是行、列、时间戳等等
    • value是一个不能修改的字节数组
    • Rows
      • GBT中的行键是string,针对行键的读写操作都是原子的
      • GBT通过行键值的字典序维护数据
      • row range会动态分区,每个分区叫做tablettablet是分布和负载均衡的最小单元
      • client通过指定row key可以获得很好的locality
    • Column Families
      • column families主要用于访问控制
    • Timestamps
      • GBT中的版本通过时间戳进行索引
      • 为了避免版本号的不断累积,GBT提供了版本号的回收机制(仅保留最后n个版本或者仅保留最新的版本等等)
  4. Building Blocks
    • SSTable使用了一种持久化的、有序的、不可变的字典,keyvalue都是byte string
    • SSTable内部使用了blocks来存储数据,并且提供了索引来加速查询,减少磁盘访问频率
    • GBT依赖一个高可靠、持久化、分布式的锁(Chubby
      • Chubby提供了namespace,包含了目录和文件。每个文件可以当做一个锁来使用,文件的读写都是原子的
      • Chubby client会在会话中保存租约信息,当租约过期时,会释放所有占有的文件以及目录
      • Chubby client可以注册回调来感知数据变更以及租约信息
      • 一旦Chubby不可用,那么GBT也变得不可用
    • GBT使用Chubby来完成如下事情
      • 确保同时只有一个master
      • 存储GBT数据的引导程序位置
      • 用于tablet service的服务发现以及tablet service死亡后的清理工作
      • 存储GBT的schema信息
      • 存储权限控制相关的数据
  5. Impletation
    • GBT包含3个核心组件
      • 支持各种语言的client-sdk
        • 与大多数单master的分布式系统类似,client仅在必要时才与master进行通信,大部分时候都直接与tablet server进行交互
        • 在GBT中,client不依赖于master就能获取tablet信息,这进一步降低了master的负载
      • 一个master
        • 将表分配给tablet server
        • 负责管理tablet server的生命周期
        • 负责tablet server的负载均衡
      • 多个tablet server,并且支持扩缩容
        • 负责管理一组tablet,大约10-1000
        • 负责响应读写请求
        • tablet过大后,拆分tablet
    • Table Location
      • GBT使用一个三层类似于B+-tree的树形结构来存储Table Location Information
        • 存储在Chubby
      • 第一级是一个文件(存储在Chubby中),该文件包含了root table的位置信息。root table中存储的是各个tabletMETADATA table中的位置,每个METADATA table包含了User tablet的具体位置。此外,root tableMETADATA table中的第一个tablet,但是它被特殊对待了,它永远不会分裂,确保层级永远是三层
      • METADATA table存储的是由tablet相关信息(table identifierrow end等信息)经过编码得到的一个keyMETADATA table中的每行大约1K的内存。假设内存128M的话,三级的结构可以存储(1281000)2234(128 * 1000)^2 ≈ 2^{34}tablet
        • METADATA table存在哪?
      • client会缓存tablet location。当发现缓存不存在,或者缓存信息有问题时(如何发现有问题?),会重新获取正确的信息。此外,client在获取table location时,会多获取一些(即便用不到),这样下次访问tablet时,可能直接就命中缓存了
    • Tablet Assignment
      • 一个tablet在同一时刻只能分配给一个tablet server
      • master负责tablet在不同tablet server的调度
      • GBT通过Chubby来追踪tablet server,每当tablet server启动时,都会在Chubyy的特殊目录下创建文件(锁)。master通过监视这个特殊目录来发现并管理table server
      • master在启动时会做如下步骤
        1. 尝试获取一把特殊的锁(避免多个master)
        2. 扫描Chubby获取所有活跃状态的tablet server
        3. 与每个活跃的tablet server通信,获取相关的tablet信息
        4. 扫描METADATA tabble,获取tablet的分配情况
      • tablet当数据过大时,会分裂成两个tablet,或者两个较小的tablet会合并成一个大的tablet,并且tablet server会将这些变更信息同步给master,同步的信息丢失也没关系,假设master仍然感知的是老的tablet,当要求对这个tablet进行读写操作时,也会再一次进行信息的同步
    • Tablet serving
      • tablet的持久化信息存储在GFS中(这部分信息参考论文中的原图Figure 5),涉及到的组件包括
        • memtable(mem),存储最近更新的数据
        • tablet log(GFS),用于记录更新操作的的commit log
        • SSTable Files(GFS),存储tablet的数据
      • 对于更新操作,先写commit log(包含redo log),最近的更新会存储在memtable
      • tablet恢复:tablet server首先从METADATA table中读取该tablet的元信息,该元信息包含一系列的SSTables,而SSTable包含了一系列的tablet以及redo pointredo point指向commit log(可能包含数据)。tablet server根据这些信息就可以重建memtable
      • tablet server接收到读操作时,它会在memtableSSTable上进行合并查找,因为memtableSSTable中对于键值的存储都是字典顺序的,所以整个读操作的执行会非常快
    • Compactions
      • 随着写入操作增多,memtable的大小也随之增大,当其达到一个阈值后,memtable会转换成SSTable,并且写入到GFS中
      • 这种micro-compaction有两个目的
        1. 缩小table server的的内存占用量
        2. server从宕机中恢复,并要恢复之前的数据时,可以减少从commit log中读取的数据量
      • 在进行compaction的过程时,仍然可以进行读写操作
      • merging compaction会周期性地将一小部分SSTable以及memtable写入到一个新的SSTable中,操作完成后,原来的SSTable以及memtable可以被丢弃
      • 将所有SSTable写入一个新的SSTable中的过程叫做major compactionnon-major compaction产生的SSTable可能包含某些条目的删除信息,这些条目的数据还存储在其他SSTable中。因此major compaction可以消除这部分数据。GBT会周期性的对所有table执行major compaction过程
  6. Refinements
    • Locality groups
      • client可以将一组column family作为一个locality group
      • 通常,将不会一起访问的column family分离到不同的locality group中可以实现更高效的读取
      • 每个locality group支持独立设置参数。例如声明某个locality group直接在内存中存储,这个locality group中的数据会延迟加载进内存,一旦在内存中存在后,就可以避免磁盘访问,进一步提高效率。在GBT内部,METADATA table中存储的location column family就使用了这个功能
    • Compression
      • client可以控制SSTable中的某个locality group是否需要压缩,若需要压缩,可以指定压缩算法
      • 尽管独立压缩会增加复杂度以及降低空间利用率。但是某一部分不压缩的数据,可以提高读取的效率
      • 大部分的client会采用two-pass的压缩方案
        • first pass:采用Bentley and McIlroy’s scheme,对长string进行压缩
        • second pass:采用快速压缩算法,在数据的16 KB小窗口中查找重复项
      • two-pass不仅及其高效,而且压缩效率很高,能够达到10-1
    • Caching for read performance
      • 为了提高读性能,tablet server使用了两级缓存,分别是scan cache以及block cache,其中scan cachehigh level cache,存储的是SSTable接口返回的键值对;block cachelow level cache,存储的是从GFS读取到的数据
      • scan cache对于那些需要重复读取数据的应用来说十分友好
      • block cache对于那些需要读取相关信息的应用来说十分友好
    • Bloom filters
      • 用于减少磁盘访问的速率
    • Commit-log implementation
      • 如果每个tabletcommit log都单独记录在不同的文件,那么会出现大量文件同时写入GFS的情况。因此,GBT中的实现是,多个tabletcommit log共享同一个日志文件
      • 使用同一个日志文件可以显著地提升性能(为啥???),但同时增大了恢复的复杂度。当一个tablet server宕机后,该机器上的所有tablet会被打散到其他tablet server中,因此,其他tablet server都需要全量读取一遍这个日志文件来进行数据的恢复(因为不知道某个tablet相关日志记录的具体位置)
      • 为了解决单日志文件造成的恢复时需要读取多次日志文件的问题。GBT会首先先对日志中的记录进行排序(table, row name, log sequence num)。于是同一个tablet的记录就会连续存储,通过少量的磁盘访问就可以全部读取出来
      • 此外,写日志可能会因为各种原因而失败,比如宕机、网络隔离等等。为了提高可用性,每个tablet server都由两个线程,每个线程写独立的文件。同一时刻只有一个线程是活跃状态。如果处于活跃状态的线程写入出现问题,那么会切换到另一个线程进行写入。日志条目包含序列号,以允许恢复过程消除由此日志切换过程产生的重复条目。
    • Speeding up tablet recovery
      • master要将某个tablet从一个tablet server迁移到另一个tablet server中时,第一步,会进行第一次压缩(减小数据量),且此时tablet server仍在提供服务;第二步,tablet server会停止对该tablet的服务;第三步,再进行一次压缩操作,因为在第一次压缩时,可能有新的数据变更产生;第四步,其他tablet server读取该tablet来重建tablet
    • Exploiting immutability
      • 由于SStable是不可变的,因此读取SSTable是不需要同步措施的。并发控制实现起来非常简单
      • 唯一可读可写的数据结构,存储在memtable中,为了降低冲突的可能性,采用了COW的技术
      • 由于SSTable是不可变的,清理删除的数据转变成了垃圾收集器收集过时的SSTable
      • 由于SSTable是不可变的,因此tablet的拆分变得很容易,因为child tablet可以共享parent tabletSSTable而无需拷贝

4 MapReduce: Simplified Data Processing on Large Clusters

  1. Abstract
    • map用于产生一组key/value
    • reduct用于合并具有相同keykey/value
    • GMR会处理数据的分区、执行调度、异常恢复、节点通信等等细节问题。这允许用户在无任何并发和分布式的经验的前提下,就能够利用好大规模的资源来进行计算
  2. Programming Model
    • GMR library暴露两个函数MapReduce
      • Map function(由用户编写),负责产生一组key/value。然后GMR library会将具有相同keypair输送到Reduce function
      • Reduce function(由用户编写),负责接受一个key以及一组value,并将其合并成一个或少量value
    • Types
      • GMR只处理string,用户负责在string和正确的类型之间进行转换
  3. Implementation
    • MapReduce大致包含如下几个步骤
      1. 用户程序中的MapReduce库函数将数据源拆分成16M-64M的多个小块
      2. 总共有Mmap task以及Nreduce taskmaster根据负载情况,将这些task分配给worker
      3. map worker收到map task后,将输入数据解析成键值对(key/value pair),并将其作为输入传入用户自定义的Map function,然后产生中间键值对,并缓存在内存中
      4. 上一步被缓存在内存中的中间键值对会通过partitioning function分成R个分区,并写入本地磁盘,这些数据的位置信息会被传送给master,后面的Reduce过程会用到这些信息
      5. reduce worker收到reduce task(包含上一步提到的位置信息)后,会发起远程调用,读取远端机器(map worker)上的中间键值对。读取完毕后,会根据键值进行排序,相同键值的会进行聚合(链表的形式)
      6. reduce worker对排序后的键值对进行遍历,并将每个key/value set送入用户自定义的Reduce function,其结果会追加到final output file
      7. 当所有map task以及reduce task处理完毕后,master会唤醒用户程序,并将结果返回给该程序
    • Master Data Structures
      • master会存储每个map taskreduce task的状态(空闲、处理中、完成)
      • master是将中间文件区域的位置从map task传播到reduce task的管道。因此,对于每个完成的map taskmaster会存储map task产生的中间文件的位置和大小,并且将这些信息推送给正在执行的reduece task
    • Fault Tolerance
      • Worker Failure
        • master会周期性地ping每个worker
        • failed worker上的map task以及reduce task会被发送到其他空闲的worker中进行重新计算
      • Master Failure
        • master会周期性的记录checkpoint,当master宕机后,一个新的机器会从最新的checkpoint中恢复
      • Semantics in the Presence of Failures
        • 当用户提供的mapreduce操作是它们输入值的确定性函数时,我们的分布式实现产生的输出与整个程序的无故障顺序执行产生的输出相同。GMR通过map task以及reduce task的原子提交来实现这个属性。每个task会将其结果保存在私有的临时文件中
        • map task完成时,会发送一条消息到master,告知其文件的位置。若master此前已经收到过该消息了,那么会直接忽略当前消息
        • reduct task完成时,会将私有的临时文件重命名为一个全局文件,当多个reduce task在不同机器上执行时,GMR中的原子重命名操作会保证只有一个会成功
    • Locality
      • master更倾向于将map task调度到包含更多相关输入的机器上,或者相关输入距离最近的机器上(比如相关输入位于同一个交换机下的不同机器)。这样能够极大程度地降低网络资源的开销
    • Task Granularity
      • map-task会被切分为更小的M份,而reduce task会被切分为更小的N份。理论上MN的大小要远远大于机器的数量。这样能够获得更均衡的负载,也能够提升异常恢复的速度
      • 如何确定MN的具体数值呢?有如下几点考量
        1. 这些任务的信息必须能够保存在master的内存中
        2. M与输入的总量有关,最好将输入文件的大小控制在16M-64M之间
        3. N是机器数量的几倍(2-3倍)
    • Backup Tasks
      • MapReduce的整体耗时与最慢的task密切相关
      • GMR提供了一种机制来解决这个问题,在任务完成后,master会将尚未结束的任务分配给这台机器,称为backup-task。一旦original-task或是backup-task完成,那么该任务就算完成

4.1 参考

5 Efficiency in the Columbia Database Query Optimizer

6 Fast Selection and Aggregation on Encoded Data using Operator Specialization

7 Shared memory consistency models - A tutorial