2018个人计划

技术

  • 分布式欠的债,8.824的最终实验完成,剩余的4到5篇论文要读完。今年上半年读完Designing data intensive applications,伊利诺伊香槟分校的cloud computing的五个课程拖太久今年完成。
  • 架构相关,工作相关的架构自不必说,再读下eric evens DDD,重新读一遍vernon的 实现领域驱动设计,今年读完uncle bob去年的神书clean architecture。posa系列自始自终没有系统的梳理式阅读,今年好好梳理下,产出整个系列的模式相关的笔记。
  • 技术基础。jvm再体系化梳理下,这种东西是学的快忘的更快,垃圾回收算法手册去年没有读完,今年一定要读完,好好读一遍现代操作系统
  • 应用层面,从应用的层面好好读读dockerkubernetes的原理及部分代码的核心实现,实践层面深入熟悉spark。研究区块链

认知

  • 超级版图硅谷钢铁侠枪炮病菌与钢铁
  • 薛兆丰的经济学通识
  • 得到上学习三个专栏
  • 设计领导力

基础

  • 程序员的数学
  • 读完 什么是数学
  • 扇贝听力 刷完 六级听力文章训练
  • 扇贝单词 每周至少刷5天

个人

  • 每周坚持锻炼3次
  • 养成早起的习惯,11点半争取躺下
  • gtd和番茄钟习惯,提高工作效率

2017年度总结

时间真快,年初写年度计划的场景及那份雄心壮志还是历历在目。不过,时间快,不光走的快,变化也是飞快。没想到到了年底一切都变了。

首先,将近三年的创业生涯画上了句号。14年年底的雄心壮志已经凉到了冰点,以至于对未来机会的选择也不免唯唯诺诺。

无论是面试还是跟别人闲聊多少都会聊到创业的得失,无非是得到了综合能力的提升,失去了技术的线性或指数成长。不过,仔细的思考下,那种套路化的回答更多的是一种包装,作为一个标榜有所追求的技术人,失去的远大于得到。

这是一个信息爆炸的时代,个人综合能力的提升(至少对于我这种技术人)通过自驱的获取信息之前可以有一个显著的提升,技术人通常缺乏全局视野,缺乏一定的逻辑判断力,对我而言,创业是扇窗户,打开后我才知道自己的局限,然后便是信息的获取,格局的提升,但事实上,作为一个个体对格局提升的认知直到创业后才意识到显然过去是不合格的,创业对我来说最大的收获是让我清楚的认识到自己的综合素质是很低的,并且有了提升的方向。

然后,技术成长失去的确实实实在在的,实践力,领域深度都有一定的下降,好在中后期实实在在的感受到了这一点,通过一定的自驱弥补了一些损失,细想起来,这也是创业的一段收获,在明显会走技术下坡的路上,唯有自驱能减少下降的斜率!

回到年度的计划,技术完成度不到60%,尤其是深度学习及基础学科这部分。不过仔细想想当时的目标未免不切实际,虽年初开始接触深度学习,但是系统化的学习这个领域需要太多的基础沉淀,这不经过系统的训练是很难完成的,创业后期我明显感到,创业的失败概率极大,大概率还是会回大公司做架构师,所以后期的技术明显转向了架构领域,这导致整个计划的完成度都有很大的偏差。

年尾了,工作也换了,糟心的2007终于没了,希望2018,一切顺利

论文-Mesa

最近换工作,面试时和聊天时,多次聊到OLAP及Google Mesa,正好最近有空,于是就把Mesa论文仔细读了一遍,论文地址为Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing

Mesa是Google在VLDB 2014(Hangzhou)发布的数据仓库解决方案,论文标题为Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing,从论文标题看,Mesa强调跨数据中心、准实时、伸缩性。目前,mesa应用于google的广告业务,处理P级别数据,每秒row updates达到百万两集,每天接收10亿+次检索,返回的数据行在trillion量级。

目标

跟传统的数据仓库相比,mesa有如下的设计目标

  • atomic update:即单个action导致的不同层面的数据更新局部原子性。比如一个ad click,可能影响千级别一致性视图,这个action的数据层面更新要保证原子性
  • consistency & correctnetss: 数据的一致性及正确性
  • availability: 系统是高可用的
  • near real-time update throughput: 高TPS,分钟级的跨view、dc的数据一致性
  • query performance: 高查询性能,99分位响应时间在100ms左右
  • scalability:高伸缩性
  • online data & metadata transformation: schema动态变更

用论文里的描述

Mesa is a distributed, replicated, and highly available data processing, storage, and query system for structured data.

作者解释了为何没有使用BigTable, Megastore, Spanner/F1作为其解决方法。BigTable满足row ACID,无法保证批量更新的原子性;而Megastore, Spanner/F1作为OLTP服务,虽然提供跨dc的数据强一致,但是高吞吐量的数据更新,尤其是峰值更新,支持不好。但是在metadata管理上,mesa使用了BigTable及Colossues, 而跨数据中心的数据同步,则使用了Spanner里用到的Paxos。

数据存储

TODO.

论文-spinnaker

Spinnaker是IBM & Linkedin Team在2011年VLDB发布的一个k/v存储服务,其设计实现基本上就是典型的paxos/raft的rsm(replicated-state-machine)的典型应用,系统实现思路很清晰,比较值得一读。

Spinnaker主要针对一个datacenter内的数据同步,考虑到datacenter内的网络分区概率极低,Spinnaker严格上说是一个CA系统。它采用3-way replica,跟传统的最终一致性的存储系统做对比,Spinnaker在读操作上甚至要更快,而在写操作上,它也只是有5-10%的性能损失。

数据模型

Spinnaker的数据模型及API跟Bigtable及Yahoo PNUTS非常类似,数据基于row及table组织,基本是如下的pattern:

row key -> { col name : col val, ……}

Data Model

作为k/v存储,其数据格式显然也没有做预设的schema,基于col name & col val来进行schema的变更;由于其数据模型里没有column family,其查询便利性上较之Bigtable还是有些差别。

基本APIs

  • insert
  • delete
  • get
  • test_and_set

前三个api自不必说,基本就是常规的kv操作;对于test_and_set, 由于数据存在版本,client端可以基于version做conditionalPut、conditionalDel等操作,从而实现test_and_set语义;

比如conditionalDelete(key, colname, v),只有当前数据版本为v时,才进行delete操作。

架构

数据分布层面,Spinnaker基于key-range进行分布;一个range内的数据集的多个replica集合叫cohort,cohort基于chained-declustering方式进行replica逻辑关联。

上图就是一个典型的数据分布架构,为了系统简化直接基于Zookeeper来做meta-data管理;

Cluster

对于单个节点,节点通过模块话组织进行数据commit, membership管理, election等动作,具体如下图:

Node

Replication Protocol

Spinnaker协议跟Raft, Zab比较类似,采用基于选举的paxos-like方案,其协议分为两个阶段:

  • p1: leader election
  • p2: quorum (using multi-paxos)

简单来说就是,首先选出cohort leader(leader crash会重新选举), 然后log发送给cohort leader,leader基于multi-paxos协议进行quorum的log一致性同步(注意此时节点未做commit,也就是未commit到RSM中)。 多数派节点ack后,leader commit然后返回client,之后发出async commit操作通知节点进行commit操作。

Protocal

显然在这个时序里,leader返回之后时间点,client->get(),到follower节点是可能拿到过期数据的,而leader节点是可以拿到最新数据。这就是Spinnnaker里的timeline consistency。

恢复

每个节点为所有的partition数据维护一个共享log(规避随机写问题),类似write-ahead-log,确保数据的可恢复性。

如果follower挂掉后又重新加入

  • leader传输log给follower,follower会追进度
  • 直到追上后,follower投入运行

如果leader挂掉

  • 触发p1的election
  • leader会重新propose所有的uncommited消息
  • 如果是quorum,开始update

需要指出的是,重新选举后leader会将所有的uncommit log进行重新的分发,这一块跟Raft协议有了比较大的简化,不确定正确性是否理论严格。

分布式一致性简史

来自 https://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html

第一个一致性问题是从 Lamport 大神的 1978年Time论文指出,虽然他没有明确提出consensus or agreement的概念, 但他提出了分布式状态机的概念(复制状态机, RSM), 一组确定状态机,从相同初始状态开始,确保他们以相同顺序处理相同消息,可以确保每个状态机都是其他的状态机的副本。 关键是,哪个消息是下一个需要处理的消息,达成一致, 这就是一致性问题。

1979年 Jim Gray描述了2PC,但是2PC会Block,随后,Dale Skeen在1981年提出3PC, 但是找到好的3PC算法花了近25年。

1985年 著名的FLP Impossiblility被提出。 即一个异步系统即使只有一个进程出错,分布式一致性也不可能达到。跟海森堡的测不准原理有些神识。此时 Consensus变成,让一系列处理器在一个value上达成共识的问题。 核心是没法区分,是低速执行,还是终止。

这时,人们意识到分布式算法有两个非常重要的属性, safety liveness 前者:坏的事情不会发生,后者:好的事情最终会发生。

虽然,2pc保证safety,但是liveness非常不好。

同时:分布式系统被分为同步,异步两种, 同步看做异步的特例, 它的消息传输时间有上界。

1982年 Byzantine Generals Problem: 进程会说谎。

1986年,一致性和事务聚在一起。 最好的一致性算法是Byzantine Generals,但是代价太高,根部无法用于事务处理。

1987年 Jim Gray, 指出分布式事务是一个新的一致性问题,不是bg的退化版本,分布式事务是uniform consensus(2010年) 所有进程必须在一个value上达成一致,即使是那些出错进程。

进入90年代,曙光来临:

  • 1990年 Lamport提出 Paxos

  • 1996年 Lampson引用Paxos

  • 2001年 Lamport 发表 Paxos Made Simple

Paxos及Paxos-like的出现,大有一统分布式一致性的趋势。

而针对分布式系统的同步异步问题,人们发现:系统简单划分同步异步有些宽泛

1988年 Dwork Lynch Stockmeyer定义了部分同步系统:

进程已给点bound的速率运行,消息传输时间有界,但边界的实际取值无法得知
处理速度和传输的边界一直,只是在未来某个未知时间开始。

2005年 Lamport Jim Gray将Paxos应用的分布式事务提交中, 用于容错,解决block问题。进行了整体融合。