如果不能正常显示,请查看原文 , 或返回

Well, Hello There! · Columba M71's Blog

  • 22 Jun 2021
    毕业四年记

    毕业四年记 如果我们不曾相遇 如果我们不曾相遇 我会是在哪里 如果我们从不曾相识 不存在这首歌曲 每秒都活着 每秒都死去 每秒都问着自己 谁不曾找寻 谁不曾怀疑 茫茫人生奔向何地 那一天 那一刻 那个场景 你出现在我生命 从此后 从人生 重新定义 从我故事里苏醒 如果我们不曾相遇 你又会在哪里 如果我们从不曾相识 人间又如何运行 晒伤的脱皮 意外的雪景 与你相依的四季 苍狗又白云 身旁有了你 匆匆轮回又有何惧 那一天 那一刻 那个场景 你出现在我生命 每一分 每一秒 每个表情 故事都充满惊奇 偶然与巧合 舞动了蝶翼 谁的心头风起 前仆而后继 万千人追寻 荒漠唯一菩提 是擦身相遇 或擦肩而去 命运犹如险棋 无数时间线 无尽可能性 终于交织向你... Read more!

  • 11 Jun 2021
    LogStore -- A Cloud-Native and Multi-Tenant Log Database

    LogStore: A Cloud-Native and Multi-Tenant Log Database 0x00 基本内容 这篇Paper是将要发布在SIGMOD ‘21上面一排关于Log存储的一篇。LogStore像是一种特别类型的AP系统,其的基本架构如下图,其架构称之为cloud native的,很多基础的组件依赖于云厂商自己的一些系统。LogStore为一个shared data和shared nothing结合的一个设计,且计算和存储分离。主要的存储使用了对象存储服务。LogStore写入的数据实时可见,因为它将最近写入的数据保存到本地的磁盘上,然后通过Raft来复制多个副本。随着数据的持续写入,本地磁盘上面的数据会最终被上传到对象存储OSS上。 数据保存到本地磁盘上面的时候会以write-optimized row-oriented的存储格式保存,不会建立上面索引之类的。在数据写入OSS之前,LogStore会对其进行重新组织,组织为一种 read-optimized column-oriented indexed的格式,称之为LogBlock,并压缩。这个LogBlock根据不同租户和日志产生时间戳来划分。在主要的组件上,Controller来负责整个集群的管理;Query Layer会根据用户的查询请求生成directed acyclic graph (DAG)模式的一个执行计划。这个查询计划会被划分为sub-queries方法到后面的Execution Layer;Execution Layer要处理最近数据的写入,以及将增长了的本地数据转存到OSS上。查询的时候要负责执行计划的具体执行。后面的存储层直接使用已有的对象存储服务OSS。 0x01 Multi-Tenant 这篇Paper中,从标题和内容都强调了其Multi-Tenant的一些特性。在cloud的环境中,不同的tenant之间的workload差异是很大的,比如大部分的tenant都是较少活动,而少数的tenants贡献了大部分的数据;比如流量的不均衡性特别突出等。因为这样,Paper中中也较多地描述了LogStore在load balance方面的一些设计。因为不均衡的特点突出,LogStore使用根据运行时候的情况来动态负载均衡。负责均衡上关于global traffic control,LogStore使用的方式示意如下图。其会将系统抽象为一个single source/single sink flow network G(V , E),这个network中节点表示某种角色,边表示流量。抽象之后,将load balancing变成了一个最优化的问题,其的目标是最大化从源到目的T的流量,满足的限制条件主要有要最小化请求/流量routes,另外要满足一些容量限制,比如一个节点上的资源利用率不能太高等。 LogStore是根据前面的建模,然后根据其traffic control的算法来算出Router的table,Broker在方法任务到Worker的时候,根据这个table来作出方法任务到哪里的决策。其global traffic control的framework表示如下图。下图的HotSpot Manager实现在Controller这个组件中。其运行的时候,首先是要一个Monitor来获取运行时的一些信息,比如一个tenant的流量f (Ki ),shard的负载 f (Pj ),一个worker节点的负载 f... Read more!

  • 09 Jun 2021
    PolarDB Serverless

    PolarDB Serverless: A Cloud Native Database for Disaggregated Data Centers 0x00 引言 这篇paper也是即将发表在SIGMOD ‘21上面的一篇Paper,关于数据库disaggregation的一个设计。Disaggregation是最近系统方向的一个热点的研究方向,其核心思路是可以理解为各类资源,比如CPU、Memory以及Storage Resource等,分离并独立管理,实现按需分配。在PolarDB这样的cloud native,其本来是一个存储、计算分离的涉及,但是计算节点上面CPU和Memory还是在一起的,进一步Disaggregation的设计就是如何将这个CPU和Memory的资源也分离。这样带来的好处就是资源更新方便贡献,按需调度,可以实现更快的failover(achieves better dynamic resource provisioning capabilities and 5.3 times faster failure recovery speed),同时实现和只存储计算分离方式差不多的信念。但是性能还是有下降的,根据在ChinaSys上的Presentation,基准测试中性能下降在百分之十几。其基本架构的示意如下图所示。 PolarDB的基本架构如下图,其是一个模仿Aurora的设计,但是存在一些不同。其核心是将MySQL写本地的磁盘改成写一个专门开发的分布式文件系统PolarFS。系统运行事务的时候:1. 写入/RW节点只有一个,写操作操作flush redolog到下层的fs之后,事务即可以commit;之后异步将redolog最新的LSN信息广播给其它的read-only/RO的节点;RO节点在收到这个信息之后,从fs拉取新的redo log来在本地重放来实现对本地buffer pool中的数据进行更新;RO也需要将自己目前redolog消费到哪里的信息提供给RW节点,这样RO节点都消费了的redolog就可以安全地删除(要dirty pages被flush到下层的fs)。这个存储层的交互和Aurora存在比较大的差别。一个RO节点如果是snapshot读取一个较老的版本,可以直接读fs中的pages。可见RO节点消费redolog的速度太慢会影响到RW节点。 0x01 基本设计 将CPU和Memory分离,PolarDB Serverless的做法是将将远程的内存作为一个remote memory pool。带来资源利用率提高的同时也带来了几个问题:一个是remote memory还是比不上本地的,这样就需要一种分层的内存设计和预取的机制;另外一个是不同节点可能访问同样的内存资源,就需要一种互斥的机制;还有一个是page数据的加大了网络流量,这里优化为其它类似系统在存储层将redo log异步转化为pages的功能。这里提出来的是一组remote memory access的接口,如下所示: // increases the page’s reference count... Read more!

  • 07 Jun 2021
    Transaction Optimzations in CockroachDB

    Transaction Optimzations in CockroachDB 0x00 Parallel Commit CockroachDB在事务优化方面,在开源的分布式数据库中,是做的比较多的。比如引入了Parallel Commit、Transaction Pipelining、1PC、Non-blocking Transactions等诸多的优化,这些优化好像也影响了后面一些系统的优化策略。以Parallel Commit为例,因为CRDB使用类似于Percolator的2PC的执行方式,其要进行网络交互比较。Parallel Commits操作则使得commit的操作可以异步执行。其优化的思路来自于:一个如果一个事务的所有写入内容都被复制完成之后,2PC的第一步prepare返回了ok,则后面的commit操作是一定能够完成的。所以到了这里就可以先返回成功再去实际地/异步地commit。为了实现这个功能,CRDB引入了一个staging的事务状态,表示一个事务操作的所有写入是否都复制完成了。在Paper[1]中提交到的数据,这个优化取得的效果很明显。其基本思路如下图,其写入的时候: 按照CockroachDB基本的分布式事务流程,会先创建一个事务状态记录,transaction record。CRDB选择在第一个range写入这个状态记录估计也是方便来实现在第一个写入操作的时候和事务状态记录一起创建。在引入了 Parallel Commit 和 Lazy Transaction Record Creation优化之后,这个方式存在了一些变化。如下的一个事务流程,在使用Parallel Commit的时候,第一个操作写入一个key “Apple”。第一次写入操作的时候并不会创建一个事务状态记录,写入这个write intent包含指向事务状态记录的信息此时并不存在。每个write intent会赋予一个唯一的sequence number 。另外在CRDB引入了Transaction Pipelining的优化之后,写入的操作可以在操作没有完成的时候就进行事务后面的操作。在写入第二个key “Berry” 时,操作的过程和写入第一个的一样,如果使用了Transaction Pipelining也不需要等待write intent的写入实际完成。 后面进入事务commit的操作过程。Client在发送了一个client的指令之后,Coordinator会创建一个staging状态的事务状态记录,并在其中记录下这个事务会写入的key列表。在等待写入操作都完成之后即可返回。事务状态为staging且所有写入都完成的时候,实际上就是一种implicitly committed,而事务状态为committed为一种explicitly committed。而对于读操作,遇到了staging状态的事务写入的write intents,读取操作会先确定相关的事务是否在正常进行过程中。这个通过coordinator和状态记录之间的heartbeating来确定。如果是,则读取操作对应的事务会等待。 另外和事务commit相关的优化为1PC 优化,这个优化在很多的2PC方式中都会用到。基本上就是一个事务只会涉及到一个range的时候,就是一个非分布式事务的commit操作,可以直接1PC操作完成。 上面描述的过程,实际上是一个Parallel Commit,Lazy Transaction Record Creation 和 Transaction Pipelining几个优化同时使用的一个操作过程, Transaction Pipelining体现在两次写入操作之间,后面没有依赖于前面的写入可以不用等到前面的写入完成之间操作。Lazy Transaction... Read more!

  • 03 Jun 2021
    Optimzations of Distributed Txn With TSO

    Optimzations of Distributed Transaction With TSO 0x10 TiDB Async Commit 前面提到TiDB使用的方式基本沿用了Percolator的方式,这种方式的一个特点是网络交互次数较多。Async Commit顾名思义就是将2PC中,第2步的commit操作异步化,意味着返回给client就prepare完成即可以了。Percolator的方式中,一个事务的状态有primary key确定,如果要改成异步commit的话,意味着需要在prepare这一步完成之后,就可以知道事务的状态。考虑一个prepare返回协调者就crash的情况:一种情况是协调者知道了事务可以正常commit,但是没来得及commit,也可能参与者都返回了ok但是还没有收到就crash;另外一种情况是协调者收到了不能commit的信息,但是也没有来得及abort。后面其它的操作看到了这个事务遗留下来的信息,需要可以从其中恢复出来,这样就需要: 这个事务是可以commit还是不可以commit。一个操作在看到一个状态不确定的数据时候,就需要知道对应事务所有写入数据的状态。由于之前在非primary key上面保存了primary key,这样继续在primary key的信息里面,保存上这次事务其它的keys,就可以根据这个信息取一一询问。这里可以看出这种方式适合OLTP的应用场景,对大事务不是很适合; 可以commit的时候,和这个事务commit ts是什么。这里对commit ts有两个要求:一个是这个commit ts必须体现事务之间的commit的顺序,另外一个是这个commit ts不能太大,因为后面读操作的时候能改立即读取到committed的数据,又读取操作获取的start ts是从TSO而来,这样要求commit ts不能大于TSO已经分配的ts+1。为了实现这些要求,这里在TiKV上维护了一个max ts,另外在prewrite操作的时候,这个请求携带了一个从TOS获取的prewrite ts。KV的节点在收到请求之后,如果本地的max ts小于这个prewrite ts,需要增大这个ts。KV节点持久化prewrite的数据,并记录下min commit ts为max ts。KV节点给DB节点返回的时候,会带上这个min commit ts。事务commit的时候,选择commits为min commit ts中最大的一个。 对于只读的事务,其操作也会导致KV节点上面的max ts 更新。KV节点接受到只读操作的时候,会根据请求带上的start ts更新增大max ts。这样后面写操作选择的一个min commit ts至少为max ts +1。这样后面的事务commit之后,不会破坏前面的snapshot读操作的snapshot语义。引入了Async Commit之后,如果一个事务知涉及到了一个KV节点,就可以使用1PC的方式。Commi ts用前面同样的方式得出。 另外一个在Async Commit的设计文档中,谈到了其和副本读的一些兼容性。因为现在commit ts可能从KV节点得出(虽然最终的来源还是TSO),而且读操作也会推大节点上的max ts。为例保证读的snapshot语义,需要副本也感知到这些变化,读副本的时候也需要更新这个max... Read more!

  • 27 May 2021
    Distributed Transaction from Research Papers

    Unifying Timestamp with Transaction Ordering for MVCC with Decentralized Scalar Timestamp 0x00 基本思路 这篇paper是关于不使用中心化的TOS服务来实现分布式的MVCC的一种方式。其思路通过前面的一些方式的优化之后其实就可以得出一个大概。Paper是提出了一种不使用vector timestamp,也不使用中心化的TOS的MVCC的实现方式。Paper中描述了使用中心化的TSO实现MVCC的基本思路。其方式前面谈到的使用一个中心化transaction manager实现的思路是一样的,下面是用这篇paper的语言来描述。 // 2PL with global timestamp (GTS) At Oracle: GlobalTS, StableGTS, Queue // monotonic global timestamp, snapshot global timestamp, pending global timestamp INSTALL(gts): add gts to Queue STABILIZE(): // run asynchronously for each gts in... Read more!

  • 19 May 2021
    Distributed Txn Without Centralized Sequencer/TSO

    Distributed Transaction Without Centralized Sequencer/TSO 0x00 Spanner: Google’s Globally Distributed Database 这里总结的是分布式事务在没有一个中心化的Sequencer/TSO下如何实现。关于这个部分,影响最大的也是来自Google的一篇paper,即Spanner在OSDI ‘12上面发表的这篇。其核心思路是在引入了一个不确定的时间区间,然后通过使用atomic clock来尽可能得降低这个不确定的时间区间并保证这个不确定的区间在一个确定的bound内。差值在这个bound之外的timestamp,Spanner就可以直接知道timestamp之间的先后关系,在这个bound之内的,Spanner会在实现上处理这个问题,从而实现了完全分布式的时钟,满足linearizability。Spanner数据保存到分布式文件系统之上,这个和一些开源实现直接使用本地的KV Store存储数据不同。同样其也需要讲这个的key range拆分为更小的的部分,称之为tablet。每个tablet对应到一个paxos group来实现多个副本的存储。在这样的基本架构之上,对于读写事务: 一个paxos group中会有一个leader,处理paxos的一些逻辑之外,其还会维护一个lock table和实现transaction manager的一些功能,这个和事务功能相关。事务读取操作的时候,会讲读取请求发送到对应group的leader,加上一个read lock之后如何读取数据。Lock需要知道放弃事务的client还是存活的,所以会定期发送keepalive的消息来告知leaders事务还是存活的。数据的写入都是先buffer在本地。在commit的时候,使用2PC提交的方式进行:1. Spanner中一个事务会选择一个paxos group的leader作为Coordinator,协调者,然后向所有的所有参与的paxos group的leader发送一个commit的消息,消息中包含选择的协调者的ID以及要写入的数据。非协调者的leader在收到消息之后,先请求write locks,然后选择一个prepare timestamp,通过paxos写入一个prepare record日志。后面每个参与者会通知coordinator其选择的prepare timestamp。选择这个prepare timestamp都是要求必须大于之前赋予其它事务的timestamp,即严格增加的特性。也可以看出Spanner的一个特点是一部分协调的工作是client来完成,client直接广播消息,这个应该是考虑到spanner为广域网/全球部署设计的。 Coordinator同样会申请write locks,但是不会处理prepare phase。在收到其它leader的消息之后,选择一个timestamp作为commit的时间戳。这个commit timestamp必须要 >= 其它leaders选择prepare tiestamp,也要求大于此时它收到过的commit消息时刻的TT.now().latest,还要大于其赋予之前事务的任何timestamp。Coordinator通过paxos写入一个commit记录。此时,commit事务不能马上apply,来完成对事务的commit,还需要一个等待的操作,需要等到TT.after(s)成立之后。之后Coordinator发送commit timestamp给client和其它的participant leaders。每个participant leader在收到这个消息之后,写log记录下事务的结果。然后使用相同的timestamp来apply操作,并释放锁。 Spanner的读写事务中读写操作都需要加上对应的locks,这个应该是为了处理读写事务之间的读写冲突问题。而其另外支持的read-only事务和snapshot -read,都是不需要加锁的,其利用MVCC来实现读写事务和只读事务之间的读写不相互阻塞。这样Timestamp管理是保证事务正确性的重要内容。Paxos group中的leader通过lease来维护一个和不会给后面可能的leader切换之后重叠的lease interval,默认情况下每个lease长度为10s,在一次写入操作时候默认被续约。Leader切换之后,后面的leader需要等待前面leader最大的租约内的时间戳S-max满足TT.after(smax)成立。对于一个写入事务,其使用2阶段锁的方式,timestamp可以在所有锁被获取之后、任何锁被释放之前赋予。Spanner关于tiemstamp更多的一些东西: Spanner是满足external-consistency的系统,可以保证后面开始的事务可以看到先提交的事务的修改。对于tiemstamp,就要求如果一个事务T2开始在另外一个事务T1 commit之后,要求T2的commit时间戳必须小于T1的commit时间戳。即一个事务ti start event和commit event的绝对时间为ti-start-abs-ts和ti-commit-abs-ts。即这样要求t1-commit-abs-ts <... Read more!

  • 11 May 2021
    Distributed Txn With Centralized Sequencer/TSO

    Distributed Transaction With Centralized Sequencer/TSO 0x00 Large-scale Incremental Processing Using Distributed Transactions and Notifications 使用2PC的方式或者是某种2PC的变种方式,与一个中心化的Sequencer,或者是称之为Timestamp Oracle,来作为一个发号器或者是一个全局的时钟,是实现分布式事务的一种方式。很多的这类系统使用的并发控制方式为MVCC,这个中心的全局时钟会和MVCC也强相关。这种方式的一个优点是一些逻辑处理上会比没有中心时钟的要简单,一个缺点是由于事务的进行都需要访问这个中心的时钟,这样系统跨区域部署时候会不太适合。比较。在使用这样的方式的系统中,Percolator这篇Paper是分布式事务设计一般影响比较大一篇,后面很多的设计都是在此的基础上进行变化、改进。Percolator是一种2PC处理分布式事务的方式,其基本的设计核心点有这样的几个: Percolator也是利用一个中心话的Oracle来获取时间戳,实现Snapshot Isolation的隔离级别。在读取开始的时候获取一个时间戳称之为start ts,在事务要commit的时候获取一个时间戳称之为commit ts。读取操作读取到start ts为止的最新的版本,如果读取这个版本带上来锁,则要查看这个锁的情况:如果没有超时则需要等待,等待这个锁超时 or 被解除;如果这个锁超时了可能写这个版本的事务没有成功提交,也可能还没有提交。这里读操作会有一个尝试清除这个锁的操作。利用这种方式来解决写事务故障之后没有清除之前写入数据,加的锁的问题。 Percolator的存储是利用Bigtable,一个分布式的表格系统,Key-Value的value为多列的结构。Percolator利用这个特性, 每个key对应的value又以下这样列:lock列记录锁的情况,对于没有提交的事务这个会记录为primary key的位置,对于primary key记录自己为primary的信息,write列保存已经commited的最大版本,data列记录这个版本对应的数据。另外的notify列和ack_O和事务关系不大。这样Percolator的一个事务的提交与否就是通过primary key来确定来,利用了Bigtable支持单行事务的特点来将其作为一个事务是否commit的一个“开关”,而其它的key就保存这个primary key的信息即可。 这样,Percolator的有写操作的事务写的数据都先缓存在本地。事务commit的时候从其中选出一个作为primary,然后写入数据的时候先写入primary,如何写其它的行。每行写之前要检查冲突,基本的方式是检查一行的write列释放存在版本在[start ts , ∞]之间的commited or 活跃的事务,或者是版本在[0, ∞]之间,即任何加锁的版本,如果存在则由于写写冲突无法提交,地abort,基本方式是清除已经prewrite的数据。Prewrite写入的数据为data 和 lock,lock保存的为primary的信息。这样的设计下面,Percolator事务的状态信息,锁信息都是和数据保存在同样的地方。 在priwrite完成之后进入commit的流程,基本的方式是尝试提交primary行。由于锁可能被其它的操作清除,在提交之后要检查锁是否已经被清除,通过写入write列数据,这行写入write列的数据对用的start ts,这样就可以找到这行数据start ts的版本并从中读取到数据;并删除lock列即完成提交操作。Primary完成提交之后事务即可以完成commit,其它行数据的提交可以异步进行。而读操作看到这些没有提交的行的时候,可以实际上已经提交了,方式是通过其中记录的primary行的信息去获取对应事务的状态。这样相当于把事务状态的信息就记录到Bigtable之中,没有利用其它的组件。 0x01 Omid 的设计 Omid是在HBase上面做的一个支持分布式事务的系统,其系统类似于前面的Percolator,其实现有很多事类似,但区别还是有不少的。Omid中分布式事务的实现也是使用MVCC,实现Snapshot Isolation的隔离级别。在具体的设计上面,Omid有这样的一些特点: 使用中心化的timestamp发号器,称之为transaction status oracle,SO。Omid事务开始的时候,也会去获取一个start ts时间戳,数据读取的时候根据这个start... Read more!

  • 07 May 2021
    FoundationDB -- A Distributed Unbundled Transactional Key Value Store

    FoundationDB: A Distributed Unbundled Transactional Key Value Store 0x00 基本内容 这篇paper描述了FoundationDB整体的一些设计。FoundationDB的基本架构如下。其基本架构和一般的类似相同没有很大的部分,Control Plane负责处理元数据,里面包含多个角色。比如Coordinators其作为哟个Paxos Group存在。其会选举出一个ClusterController,负责监控集群的情况,另外会创建三个进程,分别为 Sequencer, DataDistributor, 和Ratekeeper,分别处理做为一个发好器、监控storage servers的情况以及处理overload protection的问题。在Data Plane方面,这里一个特别是使用了3个组件,和类似的系统对比,多出来一个Log System,LS。LS负责保存来自TS的 Write-Ahead-Log,这个TS为transaction management system (TS),负责处理事务的逻辑。TS中也会有一个Sequencer,另外的足迹为, Proxies 和 Resolvers。TS的Sequencer负责从这里获取read version和commit version的timestamp。Proxies负责处理事务的读写和commit,resolver则主要用于处理事务之间的冲突。StorageServer为一个range分区的存储节点,存储使用的是SQLite的一个修改版本。和多数的类似系统一样,其并发控制也是使用MVCC的机制,另外FDB是没有依赖其它的外部系统的。 0x01 事务 对于一个支持分布式事务的系统来说,其事务处理的流程是一个核心的部分。在FDB中,事务处理的开始由client向一个proxy发送一个请求,获取一个read version开始,即一个read timestamp。这个read version为proxy从sequencer获取,保证每次获取的version都是递增的。在获取了这个timestamp之后,client可以直接向storage servers发送读区请求。而一个写入的数据会暂存到本地的buffer中。在后面commit的时候,将写入的数据,包括read set和write set的信息,发送到一个proxy。Proxy处理事务提交的请求,如果不能提交,向client返回abort的信息,client可以选择重试事务。 FDB commit的流程:1. 从sequencer获取一个commit version(Sequencer chooses the commit version advancing it at a... Read more!

  • 30 Apr 2021
    Vector Quotient Filters, Chucky and Conditional Cuckoo Filters

    Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design 0x00 基本思路 这篇Paper是将要发表在SIGMOD‘21上面一篇关于Filter的文章。Vector Quotient Filters的设计也是使用多个hash函数的设计,每个hash用于寻址一个block,称之为mini-filter。每个mini-filter在内部被划分为多个buckets,bucket保存fingerprint。对一个hash函数计算而来的一个hash值,其拆分为一个logb-bit 的bucket index,以及一个r-bit fingerprint。设一个key到一个bucket的映射关系为β (x ),到一个fingerprint的映射为f(x),添加一个key的过程就是将f (x ) 到bucket β (x )的过程,这样就可以从f(x)和β (x )恢复出f(x),即根据一个fingerprint保存的问题恢复出其完整的hash值。Mini-filter的基本结构如下,可以看出每个item x/key可以选择的block为2个,每个blocks中分为两个主要的部分:第一个部分为metadata bits,另外一个为fingerprint bits。在这样结构上的基本操作: 一个min filter的metabits部分保存一个(b+s)-bit bucket-size vector,一个最多支持s个fingerprint。另外的fingerprint bits部分就是保存实际的值。这样设计的一个原因是如果直接使用保存s个rbit的fingerprint的,那么hash冲突就很难处理,每个位置只能保存一个fingerprint。而如果使用固定大小bucket的话,空间利用率会很低,因为很难bucket里面的数据都塞满。这里通过metadata bits和fingerprint bit的组合来实现一个逻辑上不定大下的bucket。每个bucket的边界划分则是根据metadata bits来的,可以从其中看出来,metadata bit中bit 1表示一个bucket边界,前面多少个0表示这个bucket里面有多少个fingerprint。由于metadata bit都是1bit的,消耗内存不大。 所以在这样的结构上面,定义一个select操作,和一些succinct结构类型。select(m,i)表示在bit串m上第i个1的位置,比如select(001000000,0)=2。这样第j个bucket出现的第一个fingerprint的位置为select(m,j−1)−j。对于j > 0 的情况其fingerprint的范围为[select(m,j−1)−j+1,select(m,j)−j),为0时候,开始index为0。这些计算可以通过x86 PDEP之类的特殊指令直接计算。添加一个key的时候,先尝试讲对应的fingerprint fp添加到bucket b,fp选择的位置为select(m,b)−b,后面的数据也顺序往后移动。选择bucket的时候,有2个候选位置,选择更加空的一个。如果都满了会导致添加失败。这个可能添加失败的特性在一些情况下会是一个问题。 Vector... Read more!

  • 25 Apr 2021
    YugabyteDB -- A Distributed SQL Database

    YugabyteDB: A Distributed SQL Database 0x00 基本架构 YugebyteDB,YDB,也是一个开源的NewSQL的设计,和前面的CockroachDB有很多类型的地方,也有很多不同的地方。YDB和CRDB、TiDB之类的一样,总的来说还是模仿F1和Spanner的一个设计,总体架构上也分为实现SQL功能的查询层,YDB这部分称之为Query Layer,实现分布式存储功能的存储层,YDB这部分称之为DocDB。不同的是,YDB查询层和存储层部署的时候就是在同样的节点上面的,没有进行物理上的分离。YDB中对于一个table,也是划分为若干的tablet来保存,划分的方式只是range or hash的方式,一个tablet包含不同的一些部分。在YDB分布式事务的实现也是使用HLC,使用MVCC的方式,实现snapshot和serializable的隔离级别。YugabyteDB的一些特点: YDB使用的在实现上使用了C/C++,理论上可以比一些使用Golang的有更好的实现上的一些优化空间?在Query Layer,支持兼容PostgreSQL的SQL语言外,还支持Cassandra使用的一种CQL。YDB也就是不仅仅支持SQL的模型,还支持文档的模型。兼容PostgreSQL是因为SQL相关的实现好像就是直接从PostgreSQL改来的。总的查询相关的称之为YQL。存储层则使用了RocksDB作为存储。YDB查询层和存储层实际上是部署在一起的,部署在一起称之为Tablet Server。这个是和其它类型数据库一个不同的地方。其特点也可以在下面的关于事务的部分看到。 YDB中无论是SQL的模型还是文档的模型,最后都会被表示为Key-Value的形势保存到RocksDB中。其编码KV到方式如下图。Key中包含了3个部分,DocKey子部分包含一个16bit的hash,这个16bit的hash也涉及到YDB一个设计特点。以及主键key,可能使用hash划分 orrang划分的方式。另外SubKey部分对应到tuple中的列。最好的部分为hybrid time 加上write id,这个write id作用在后面会提到。YDB在使用RocksDB的时候只是简单的利用了其key-value存储的功能,好像其持久化保证的WAL,以及事务都不需要,有YDB自己来保证。 这里YDB的一个设计特点是其tuple中每个列都会对应到一个key-value,和一般整个tuple作为一个value的方式不同。可以猜测一下其优点是更新的时候可能可以选择更新,读取部分数据时候额外开销更小,而缺点是可能导致保存的数据量变大,要读取全部的数据时候开销增加。存储数据量可以利用RocksDB的前缀压缩的功能,可能实际上带来的开销不会很大。另外key前面16bit的hash表明了YDB涉及的时候,即使是range分区的方式,也是先使用hash的方式讲整个tablet partition到一定数量的分区,如何在划分为tablet。为一个两层的划分方式。其优点可以看得出来,在一个CRDB和YDB对比的blog[3]中也有提到,hash的优点是在处理一些热点问题时候会有明显的优势;在写入顺序的workload中,其能力上限会明显高于只使用range分区的方式,只使用range分区的方式,顺序写入数据一般有个能力上限,而这个上限基本上就是单机的能力。Hash + range的方式的话scan的性能很显然是很难比得上只使用range的。 0x01 Two Layers YDB的一个特点是在Query Layer支持多种的协议,兼容PostgreSQL和Cassandra。其查询部分的功能实现为YQL,和存储部分的DocDB部署在同一个TServer中,YDB关于Query Layer除了同时支持PostgreSQL的SQL以及Cassandra的CQL,相关的资料并没有很多的描述。在CRDB和YDB一篇对比的文章[3]中,也将到了YDB的查询层的一些问题。CRDB的查询层实现为一个 fully-distributed SQL engine,包含了为分布式查询做的各种优化。而YDB直接从PostgreSQL改,为其增加了访问存储层的LSM-Tree的实现,这些访问方式实现在下层的DocDB distributed KV之上。CRDB将其描述为在一个巨大KV系统上实现单体数据库,而不是一个分布式数据库(Rather than a distributed SQL database, Yugabyte can be more accurately described as a monolithic SQL... Read more!

  • 21 Apr 2021
    Key-Value Store in Production

    Evolution of Development Priorities in Key-value Stores Serving Large-scale Applications: The RocksDB Experience 0x00 Resource Optimization 这篇Paper主要是Facebook发表的一片关于RocksDB开发、使用过程中的一些经验总结的文章。其内容主要包含了比如RocksDB资源优化方面为何从write amplification转向优化space amplifiction、CPU利用率、以及对一些新技术看法的内容,其次是一些使用总结: 写放大是LSM-tree存在的一个问题,不够其实无论是B-tree和LSM-tree也好,都会存在写入放大的问题,特别是写入为随机的key写入的时候,这个放大是很难避免的。优化写入放大也是最近一些关于LSM-tree优化的研究的一个方面。在RocksDB这里起初写入放大的优化是RocksDB在优化方面的主要目标之一。为此,RocksDB之前加入了加入Tiered Compaction的方式。在一些应用场景下面,这个可以将写入放大有Leveled Compaction方式的10–30优化到4-10。Paper中提到,对应一些常见,比如value比较大的情况,将value单独存储也是降低写入放大一种可行的方式。这个功能这个正在准备加入到RocksDB中,称之为BlobDB。 随着RocksDB这些年的的发展,发现很多情况下space utilization变得更加重要。实际上,一般应用对于不会利用完硬件的写入寿命,以及写入的负载也没有太多的约束。也就是在很多情况下,写入不会利用完硬件的性能。这个时候优化space显得更加有价值。Rocks通过使用更加激进的Compaction方式减少空间使用带来的收益更多,另外由通过加入Dynamic Leveled Compactio的功能来实现可以动态调整每层的大小,来获取更多的回收掉dead data的机会。减少空间的使用,可以优化成本的问题。 in a random write benchmark: Dynamic Leveled Compaction limits space overhead to 13%, while Leveled Compaction can add more than 25% . Moreover,... Read more!

  • 10 Apr 2021
    Database Lock Optimizations

    Efficient Locking Techniques for Databases on Modern Hardware 0x00 基本内容 这篇paper是关于数据库上lock的一些优化,这些内容是在Shore-MT上面做的,可能和Shore-MT的实现也有一定的关系。这里讨论了range locking、intent locks和deadlock detection以及early lock release的一些优化。 Range locking的一些优化讨论了一些范围锁的内容。上图表示了range lock的一些类型以及其不同类型所之间的互斥关系。其中N表示not lock,而例如 ‘SX’ 表示‘key shared, gap exclusive’,其它类似。这里的一个优化是modes做得很细,优化了之前一些lock方法有些情况没有足够优化的情况,比如缺少‘RangeS-N’ (N stands for ‘not locked’)这样的模式。这种模式在有[10, 20, 30]这样的记录中查询`Select * From T Where T.a = 15时,可以在10上加一个NS-mode (key free, gap shared)的锁,这样key加的是N lock,即没有lock。类似的之前的方案也没有 ‘RangeS-X’ 和‘RangeX-N’ 这样的模式。在这里,一些操作的加锁的方式如下: 对于点查询/添加。以下面的查询为例,先找打对应的leaf page,这个时候持有leaf page的S... Read more!

  • 18 Mar 2021
    RAID and More

    RAID+: Deterministic and Balanced Data Distribution for Large Disk Enclosures 0x00 基本思路 这篇Paper是关于一种新的RAID的方式。随着磁盘的容量的增大,经典的RAID在性能和恢复能力上面已经不太适应了。之后就出现了RAID 2.0。这篇也是使用将数据stripe之后保存到磁盘上面的方式,其特别是利用Latin-square方式,可以得到一个确定性的数据分布方式,与下图所示的使用随机分配data stripe的方式不同。 Latin-square的一个例子就是数独。RAID+这里使用的是多维的。一个例子如下图。n为一个二维的矩形的长度,k表示有几个这样的square。这些squares为正交的定位了每个sqaure对应的位置值都不同。这里如果每个sqaures都是正交的,称之为a set of mutually orthogonal Latin squares (MOLS)。这里可以得到,对于一个n,最多有(n − 1) 个MOLS,最大在n为一个质数的幂的时候。在这种情况下,通过 $L_i(0 < i < n)$ using $L_i[x,y] = i·x+y的方式填充。满足这样数字要求的在4到128之间有4,5,7,8,9,11,13,16,17,19,23,25 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71,... Read more!

  • 08 Mar 2021
    Start-Time-, Multi-Queue-, Device-Direct- Fair-Queuing

    Start-Time Fair Queueing and Its’ Variants 0x00 Start-Time Fair Queueing Fair Queuing是一种常见的QoS、调度的方法。以Weighted Fair Queuing为例,其会为每个请求附加上两个tags,stat tag和finish tag。两个tags按照如下的方式定义: \(定义p_f^j, l_f^j分为flow\ f的第j个packet和这个packet的长度.\\ 则S(p_f^j) = \max\{v[A(p_f^j)], F(p_f^{j-1})\}, j \geq 1 \\ F(p_f^j) = S(p_f^j) + \frac{l_f^j}{\phi_f}, j \geq 1. \\ 另外F(p_f^0) = 0, v(t)定义为 \frac{dv(t)}{dt} = \frac{C}{\sum_{j \in B(t)}{\phi_j}}. \\\) C为服务的整体容量,B(t)为backlogged flows的集合,即有要调度packets的flows的集合。调度的时候按照finish tag的升序调度。WFQ的一个问题就是v(t)的计算问题。Start-Time Fair... Read more!

  • 01 Mar 2021
    Key-Value Store with New Hardware

    ROART: Range-query Optimized Persistent ART 0x00 基本思路 这篇Paper出自清华,是关于ART在NVM上面范围查询的优化。ART是一种优化版本的Radix Tree,主要是使用不同大小的node来减少内存、路径压缩来减少内存的使用。这里针对NVM环境上ART范围查询优化提出了3个方面的优化: Leaf compaction:lead compaction的思路是将一些leaf接口压缩保存到其上面的inner节点中,思路如下图。这里的lead compaction将一些对leaf结点的指针压缩到leaf array中。这个更像是一种实现上的优化,如下图所示,如果一个leaf array包含m个leaf指针,如果一个结点下面的一个subtree,包含的leaf结点数量小于m,就可以将这个subtree压缩保存到这个结点的leaf array中。这里通过将一些leaf结点和上层的结点保存一起,可以优化range查询的性能。 ROART这里ART的整体结构没有改变,原来的ART添加、查找和删除算法也没有太大的变化。这里leaf array里面的数据是没有排序的,所以查找操作如果查找到了了leaf array,需要一个遍历对比的操作。这里使用了一些hash table中使用的优化方式,将一些bits的hash tag保存到指针中。利用了现在的指针只使用了48bit的特点,将高16bit保存为key的一个hash值,对比的时候可以先对比这个来避免取回实际的key做比较操作,这个是比较常见的一个优化。添加的时候需要考虑到leaf array可能满来,满来的话需要一个silit操作,基本方式也是将原来结点中的leaf array取出来根据radix tree要满足的一些特性来分裂操作。 Minimizes persistence overhead,减少持久化开销主要是优化ART node的结构。ART基本的node结构如下,ROART通过使用entry compression (EC)的方式将N4, N16, 和 N48类型的几个字段优化到8byte的空间,比如使用讲不同的字段压缩包村到一个8byte值中的方式,比如使用|empty: 8-bit | key: 8-bit | pointer: 48-bit|的方式来分配64bit的空间。另外的一个是通过Selective Metadata Persistence减少需要持久化的元数据。比如一些可以通过其它部分恢复出来的数据就不要去保证持久化,而是通过维护一个全局的generation number (GGN)(每次启动自增)和每个结点维护一个generation number,在对比上的情况下说明结点元数据非最新,需要恢复处理。而恢复处理之后,会将结点的GN更新为GGN。还有就是split操作过程中的一些减少sfence的优化。这里实际上就是一种类似epoch的机制。 Fast memory management。具体方式参见论文。由于NVM作为内存管理的话,分配带来持久化的开销也是需要优化,这里减少这个开心的思路是直接不去持久化分配相关的元数据。恢复重启之后,这里需要使用check操作检查处理那些被分配来但是实际使用的空间。ROART的内存管理基本思路是全局pool加上thread-local pool的2 layers的设计。全局的first... Read more!

  • 24 Feb 2021
    Facebook's Tectonic Filesystem

    Facebook’s Tectonic Filesystem: Efficiency from Exascale 0x00 基本架构 这篇Paper是关于Facebook的一个分布式文件系统,Tectonic。这种类型的分布式文件系统最经典的设计为GFS。但是GFS的设计存在一些取舍,这些tradeoff可能在今天就不是很适合了。所以近些年出现另外的分布式文件系统的设计,其特点比如使用分布式的Key-Value or 数据库等代替取代GFS中使用逻辑上单个的Master,元数据保持到内存中的设计;使用分布式的存储池系统来代替Chunk Store。总体上元数据和数据的存储都变得更加解耦,都是用更加通用的分布式存储系统,而这个Distributed FS更加聚焦在维护文件系统的语义上面。Tectonic 也是一个类似的设计。Tectonic整体的架构为见1. 元数据通过hash partition的方式保存到一个分布式的key-value store中,2. 数据保存到一个分布式blob store中,3. 另外在multitenant有不少的一些内容。 Tectonic的总体架构如上图所示,在Tectonic中: Chunk Store就是一个一般的Object Store,其保存了数据的Chunks,其由文件的Blocks组成。Paper中这里描述的是 Chunks make up blocks,paper这里描述的简短,不是很清楚。从上下文来看,应该是Tectonic中的文件系统又一些blocks组成,block在chunk store中,一些block组成来一个chunk。也就是chunk作为chunk store层面的抽象,而block为FS层面的抽象。而在操作的时候,block做为单个的逻辑单元和持久化单位。而Chunk Store更像是一个Block Store,一个Chunk最终保存到storage node的文件系统之上。这里storage node来保存chunk,而不是使用裸盘等更加激进的方式。做这样的一个Chunk Store会有不少的内容,但是paper中对这里没有多少的描述; Block写入的时候会被EC之后写入,根据EC编码RS(r,k)的配置将数据拆分为r个data chunks和k parity chunks,在保存到不同的fault domains内。对于不同类型的数据,会选择不同的EC配比。这里对于短生存时间的文件,会使用更小的配比,比如3+3。Client直接写入Chunk Store。写入chunks选择那些磁盘在考虑了fault-daomins之外,也不是随机选择的,而是会维护一些固定数量的Copysets,在data unavailability和reconstruction load之间取一个平衡。因为如果是随机选择的,即copysets数量非常多,较短时间内有多个disks故障的情况下丢失数据的可能性会更大,而copysets太少的话,数据恢复的带宽受限; 元数据转化为key-value的形式保存到一个分布式KVS中。映射方式对于文件路径上的信息,就是id+name的方式,通过不变的id加上变的name组合,方便rename的操作。对于文件的数据,通过file id映射到block id,在通过block获取到保存到哪里的chunks的消息。这个kvs使用的是其ZippyDB。在数据分区上,这里选择了和一般不同的hash分区的方式,其优点之一是可以避免掉一些热点的问题; 在上面的元数据和数据不同的服务之外,还有诸多的后台服务,比如rebalance、GC和一些后台数据收集和数据检查的一些服务。这些里面有不少在工程实现上,也应该是比较麻烦的,比如GC,paper中对这些没有描述。 0x01 Multitenancy 这里后面就花了较大的篇幅来介绍Tectonic... Read more!

  • 17 Feb 2021
    Stacked Filters and Xor Filter

    Split Block Bloom Filters 0x00 Block Bloom Filters Block Bloom Filter是用了解决一般的Bloom Filter其Cache不友好的问题的。 Block Bloom Filter基本思路是将一个key要设置的bits都弄到一个block中,这个block一般根据cache line的大小来设计,比如一般的cache line大小为64bytes,512bit。Block Bloom Filter就可以看作是一个一般的Bloom Filters的一个数组,其添加/查询可以看作是现从Bloom Filters的数组里面找到一个Bloom Filters,然后设置这个Bloom Filters。这样就是Block Bloom Filters的第一个hash函数用于确定选择哪一个block,后面的hash函数用于选择一个block中的那些bits。其添加算法可以描述如下。 void block_insert(block b, uint x) block masked = mask(x) int bits_num = sizeof x * 8 for i in [0..7] for j in [0..(bits_num-1)] if... Read more!

  • 15 Feb 2021
    Perceptron Branch Predictor and More

    Dynamic Branch Prediction with Perceptrons 0x00 基本内容 这篇Paper是关于使用Perceptron,感知机来做分支预测的。根据目前找到的一些资料,基于Perceptron和TAGE模式的分支预测是现在的高性能CPU里面很常用的分支预测方式。通过Perceptron做分支预测的方式基本思路是将一些参数值,每个计算一个weight,这里是实际上对于每个参数都是一个一元一次方程。对歌weight对应一个简单的Perceptron。其表示如下: \(\\ y = w_0 + \sum_{i=1}^n x_i \cdot w_i.\) 在这里做分支预测的时候,x-i的取值只会是-1 or 1,对应到分支不跳转 or 跳转。每个x在运行的时候训练出一个对应到w,然后根据上面的式子计算出y,如果结果为负数,则branch不会跳转,否则认为其会跳转。剩下的几个问题就是: 1. x从哪里来?2. 如果训练w。对于第一个问题,x-i实际上就是 global branch history 中对应的bits。对于第二个问题,其训练的方式为,令t = -1 if branch not-token else 1,定义另外一个阈值a。训练方式: if sign(y) != t or |y| <= a then for i := 0 to... Read more!

  • 13 Feb 2021
    Analyses and Optimizations for Tail Latency

    Tales of the Tail: Hardware, OS, and Application-level Sources of Tail Latency 0x00 基本内容 这篇paper是一般的client-server模型下面服务的一些关于tail latency的分析。这里讨论的主要是一些请求排队带来的影响。排队的模型使用A/S/c的方式表示,A表示请求等待的分布,S表示服务时间的分布,而c表示处理请求的workers的数量。一般情况下要求处理请求的速度在较长时间内的平均大于请求达到的平均,否则会导致排队的队长无限增长。在paper的数据中,其测试了单核和多核的情况下,一个echo rpc server、memcached服务和nginx服务在不同情况下请求的tail latency。paper中给出的测试方式从请求的network packets从到达网卡被网卡驱动处理,进入到kernel的TCP/UDP协议栈处理逻辑,到调度应用线程到一个CPU核心上面运行,到应用线程使用syscall从kernel中读出取钱,到用户线程处理完成然后调用syscall回复数据,到数据包被网卡驱动通过网卡发送几个过程分别计时。使用的echo rpc server、memcached和nginx三个服务中,echo rpc server使用的是多线程的模式,即每个请求启动一个新的线程来处理,而memcached的模型是固定线程数量的处理方式,而nginx则是 event-driven的架构。得出了这样的一些基本结论: 在FIFO/先到先处理、LIFO/后到先处理,两种方式都放到一个全局的队列的排队方式下,FIFO的方式有更低的tail latency,LIFO方式的tail latency要差一些,但是其median latency,即中位数延迟表现更好。另外的两种模式是random worker和random request的一些统计,其中random worker的方式每个worker有一个FIFO队列,每个work处理自己队列里面的任务,而random request的方式为一个全局的队列,每个worker从这个全局的队列中取task(不考虑其任务添加进来的顺序),两种random的方式其tail latency都比FIFO的更差,但是median latency更好。同样的结论在后面的一些ZygOS的论文上面也有提到。 在单核的情况下,其它的Background Processes是一个造成tail latency的主要原因之一。一般情况下user-level的进程有相同的优先级,在只有一个CPU核的情况下容易造成资源的争抢。考虑到一般的Linux Kernel使用CFS调度的方式,其调整优先级能够对tail latency影响很小。在使用Linux实时调度器的情况下,对tail latency的提升很明显。因为Linux总是会优先处理实时进程,而CFS这样的方式调度不同优先级进程/线程的时候,其执行顺序和优先级没必然关系。CFS使用的调度方式是一种非FIFO的方式,而调度实时进程的时候可以使用FIFO的方式。 在多核的情况下,rpc server表现出更好的tail latency,而memcached和nginx则没有。Paper中认为rpc server的模型更像是一个random request的方式,而其它两个更像是一个random worker的方式。使用一个global的queue可以有更好的tail latency表现。通过将使用的传输协议由UDP改为TCP,memcached也可以切换为类似于使用global queue方式的处理模型。而nginx要向改为类似这样的模型,paper中使用的方式是client端美发送20-40个请求之后关闭连接,然后重新连接。 另外影响tail... Read more!

  • 01 Feb 2021
    Distributed Consensus Revised

    Distributed Consensus Revised 0x00 引言 这篇《Distributed Consensus Revised》是一篇博士论文,因为某个大佬的点赞以此被更多人知晓。其讨论的还是Distributed Consensus算法的一些优化设计的讨论。在paper的前面,讨论了一个简单的Signal Acceptor,即只有一个Acceptor的一个Consensus算法,和Classic Paxos的一些特性。其总结了Classic Paxos这样的几点Properties,这里的epoch应该是一般的proposal id的含义: Property 1. Proposers use unique epochs for each proposal. 即每个proposal会有独特的epcoh。 Property 2. Proposers only propose a value after receiving promises from ⌊n/2⌋ + 1 acceptors. 收到了大部分的acceptors的回复,这样就能保证之前有更大提案号proposal会被这次知道,以及chosen的value也会被这次操作知道。 Property 3. Proposers only return a value after receiving accepts from... Read more!

  • 27 Jan 2021
    Rate Adaptation to Video Streaming

    A Buffer-Based Approach to Rate Adaptation: Evidence from a Large Video Streaming Service 0x00 引言 这篇Paper讨论是一个基于buffer的视频流传输的速率调整方案。视频在互联网流量占比越来越高,这个速率调整策略也是一个研究很多的问题。adaptive bit rate selection,即ABR,播放视频的bit rate根据目前的网络情况进行自适应的调整。Buffer-Based的方式基本思路是预先下载一部分视频到一个buffer中,buffer会有一个容量。下载视频的bit rate根据buffer占有的比例来进行调整,直观的思路是如果目前buffer占用比较高的时候,就可以选择下载bit rate更高的视频,buffer占用地的时候表面目前网络速度不理想,可以选择下载bit rate更低的视频。而这里提出的思路则是在这样的基本方式上面进行的一些优化。其基本的模型如下,buffer保存的视频会根据其以秒计的视频时长来计算,每次播放的时候为播放一个unit,client下载视频的时候以chunk的粒度下载。这个chunk为固定时间长度的一段视频,在paper中这个chunk的视频长度为4s。这样同样的视频,bit rate越大,这个chunk的bytes也越多。 之前这样的根据buffer占用调整bit rate为这样的一个模型:某时刻系统的capacity,即下载视频的速度表示为C(t),其video rate表示为R(t),其目标是实现一段时间内这个R不要超过C,有能尽量使用更大bit rate的视频。这里使用一个chunk传输的速度来估计一个时刻的capacity,C'(t)。这里估计下载什么样bit rate的视频的时候可能还要考虑到buffer的占用,这个adjustment factor表示为F(B(t)),即根据buffer占用加上一个调整的参数。通过这样的选择video rate表示为R(t) = F(B(t))C'(t)。如果目前的网络是足够的,可以选择R(t) = C'(t)这样bit rate的视频。 在一个时刻网络不够用的情况下,最好是在目前的chunks被播放完成之前,后面的chunk就被下载下来了。paper中先距离一个简单的例子,如果目前buffer里面只有一个chunk,这样就要去VR(t)/C(t) < B(t),这里使用VR(t)表示下载的chunk大小,in bytes(VR(t) = R(t) * V, 每个chunk为V秒长度)。B(t)即表示目前buffer里面的还能个播放的时间。即要求R(t) < (B(t)/V)*C(t),这个有前面式子变换话速率的表示而来。又根据前面F(B(t))和R(t), C’(t)的关系,可以得出F(B(t)) < (B(t)/V)(C(t)/C'(t)),这个要求对于所有t都成立。这样如果C(t)/C’(t)由于网络速度变化大,造成这个比值很小的话,这样选择的F(-)只能选择很小的一个值,从而导致有C’(t)选择R(t)的时候作出选择很低bit... Read more!

  • 19 Jan 2021
    The IBM z15 High Frequency Mainframe Branch Predictor

    The IBM z15 High Frequency Mainframe Branch Predictor 0x00 基本内容 这篇Paper对IBM z15处理其内部的一些结构进行了比较多的描述,比较详细描述了z15的 Branch Predictor,分支预测器的设计。z15是一种非常非常高端的CPU。Paper中给出了其pipeline的示意图。z系列的使用的指令集是一种CISC的指令集,和一般的CPU一样,其也会将指令集转化为一种RISC风格的内部指令去执行。z15有4 level的cache,Level 1和2都是每个CPU核心私有的,而且都是指令缓存和数据缓存分开的,L3为有12个核心的central processor (CP) chip共享,每个256MB,然后每4个通过一个system control (SC) chip通信,这个SC还可以和其它的system drawer通信。这里还维护了另外的一个L4的缓存,大小应该是960MB。 Each of the four CP chips per system drawer communicate with a system control (SC) chip, which in addition to enabling communication across up to 5 drawers... Read more!

  • 16 Jan 2021
    GPPM, L-TAGE and Perceptron-based Branch Predictors

    A PPM-like, Tag-based Branch Predictor 0x00 基本思路 TAGE Branch Predictor是目前很多CPU使用的Branch Predictor,比如使用 TAGE Branch Predictor 和 Perceptrons Branch Predcitor的组合。TAGE即TAgged GEometric length predictor。这篇Paper提出的是一个很接近TAGE的Branch Predictor。其基本结构如下图,其核心思路是使用不同的历史长度来index不同的bank,发现branch在不同历史长度上branch之间的相关性,以实现比使用单一历史长度更好的效果。其有1+4个banks,其中bank 0直接使用branch地址最低的12bit来index,这样看作是一个不考虑branchs之间相关性只考虑自身倾向性的一个预测bank。bank 0是一个bimodel predcitor,实用3bit的counter加上1bit的meta bit,m bit被meta predcitor实用。另外的4个实用3-bit的counter和8-bit的组合,另外还有一个u bit,即useful bit。 不同的bank实用不同的历史长度,分别是10,20,40 和 80bit的global history。在global history长度超过了index需要的长度的时候,实用折叠的方式而不是直接截断,比如实用40bit历史的时候,index实用 pc[0 : 9]⊕h[0 : 9]⊕h[10 : 19]⊕h[20 : 29]⊕h[30 : 39]这样的方式得到(⊕ 为 xor)。获取预测值的时候,5个banks同时预测,高4个的bank的处理index到一个entry外,还会根据tag和PC+history的hash进行比较,匹配了的才是命中。在命中了的bank的结果中,选择bank实用历史消息最长的那个的结果。 更新的时候,3-bit counter的更新只更新提供了最终预测结果的那个。预测正确+1,错误则-1。如果预测错误,设最终实用的bank为X,如果X... Read more!

  • 14 Jan 2021
    Tow-Level Branch Predictor and its Optimizations

    Two-Level Adaptive Training Branch Prediction 0x00 基本内容 分支预测对CPU的性能影响非常大。一般来说,分支的跳转与否都有明显的规律,对于一个分支来说其跳转与否的倾向性是很明显的,这样的情况下预测下一次分支跳转与否可以通过记录前面这个分支跳转与否就可以预测,这样的方法就能实现比较高的预测准确率。基本的方式比如使用饱和技术器的方式,最常见的就是使用2-bit的饱和计数器。这样的方式是让简单,但是很有效,后面的branch predictor的设计都会有这样的思路。在此基础之上,Two-Level的是改进了简单的2-bit计数器不能识别更加复杂的pattern的缺点。基本思路如下图:这里2-level的意思是,通过一个PC找到一个Branch History Register,然后在通过这个BHR的值去寻值Pattern Table/PHT里面值,得出预测的结果, Since the history register table is indexed by branch instruction addresses, the history register table is called a per-address history register table (PHRT). The pattern table is called a global pattern table, because all the history registers access... Read more!

  • 11 Jan 2021
    Scaling Replicated State Machines with Compartmentalization

    Scaling Replicated State Machines with Compartmentalization 0x00 基本内容 这篇Paper相比较是一篇干货较多的,主要的内容是针对Multi-Paxos的这样的Distributed Consensus算法存在的bottlenecked提出一些优化方案,获得了比较明显的性能提升(compartmentalize MultiPaxos to increase its throughput by 6× on a write-only workload and 16× on a mixed read-write workload)。Compartmentalization的基本思路是将功能划分,是一种优化的方式,而不是一种Consensus Protocol,所以具有一定的普遍适用性,而Paper中的例子主要用的是MultiPaxos。Paper中先分析了MultiPaxos存在的bottlenecks: 增加proposers的数量不能提高性能。Cli

返回