分布式系统,程序语言,算法设计

go-context-tree-construction.png

概述

Context 是 Go 中一个比较独特而常用的概念,用好了往往能事半功倍。但如果不知其然而滥用,则往往变成 “为赋新词强说愁”,轻则影响代码结构,重则埋下许多bug。

Golang 使用树形派生的方式构造 Context,通过在不同过程 [1] 中传递 deadline 和 cancel 信号,来管理处理某个任务所涉及到的一组 goroutine 的生命周期,防止 goroutine 泄露。并且可以通过附加在 Context 上的 Value 来传递/共享一些跨越整个请求间的数据。

Context 最常用来追踪 RPC/HTTP 等耗时的、跨进程的 IO 请求的生命周期,从而让外层调用者可以主动地或者自动地取消该请求,进而告诉子过程回收用到的所有 goroutine 和相关资源。

Context 本质上是一种在 API 间树形嵌套调用时传递信号的机制。本文将从接口、派生、源码分析、使用等几个方面来逐一解析 Context。

阅读全文 »

早对 LevelDB 有所耳闻,这次心血来潮结合一些资料粗略过了遍代码,果然名不虚传——绝对是不世出的工艺品!如果你对存储感兴趣、如果你想优雅使用C++、如果你想学习如何架构项目,都推荐来观摩一下。谷歌出品,必是精品,更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。

看过一遍如果不输出点什么,以我的记性,定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙,但又不想走寻常路,从架构概览说起,以模块分析做合。读代码的这些天,一直在盘算从哪下笔比较好。在将将读完之时,印象最深的反而是 LevelDB 的各种精妙的数据结构:贴合场景、从头构建、剪裁得当、代码精到。不妨, LevelDB 系列就从这些边边角角的小构件开始吧。

本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构,分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第一篇,Skip List。

需求

LevelDB 是一个单机的 KV 存储引擎。KV 引擎在本质上可认为只提供对数据条目(key,val) Put(key, val), Get(key) val, Delete(key) 操作的三个接口。而在实现上,LevelDB 在收到删除请求时不会真正删除数据,而是为该 Key 写一个特殊标记,以备读取时发现该 Key 不存在,从而将 Delete 转为 Put ,进而将三个接口简化为两个。砍完这一刀后,剩下的就是在 PutGet 间进行性能取舍,LevelDB 的选择是:牺牲部分 Get 性能,换取强悍 Put 性能,再极力优化 Get

我们知道,在存储层次体系(Memory hierarchy)中,内存访问远快于磁盘,因此 LevelDB 为了达到目标做了以下设计:

  1. 写入(Put):让所有写入都发生在内存中,然后达到一定尺寸后将其批量刷磁盘
  2. 读取(Get):随着时间推移,数据不断写入,内存中会有一小部分数据,磁盘中有剩余大部分数据。读取时,如果在内存中没命中,就需要去磁盘查找。

为了保证写入性能,同时优化读取性能,需要内存中的存储结构能够同时支持高效的插入查找

之前听说 LevelDB 时,最自然的想法,以为该内存结构(memtable)为是平衡树,比如红黑树AVL 树等,可以保证插入和查找的时间复杂度都是 lg(n),看源码才知道用了跳表。相比平衡树,跳表优势在于,在保证读写性能的同时,大大简化了实现。

此外,为了将数据定期 dump 到磁盘,还需要该数据结构支持高效的顺序遍历。总结一下 LevelDB 内存数据结构(memtable)需求点:

  1. 高效查找
  2. 高效插入
  3. 高效顺序遍历
阅读全文 »

概览

Dynamo 是一个高可用的 KV 存储系统。为了保证高可用和高性能,Dynamo 采用了最终一致性模型,它对开发人员提供一种新型 API,使用了版本机制,并通过用户侧辅助解决冲突。Dynamo 目标是提供不间断的服务,同时保证性能和可扩展性。由于亚马逊大量采用了去中心化、高度解耦微服务架构,因此对微服务状态的存储系统的可用性要求尤其高。

S3 (Simple Storage Service)是 Amazon 另一款有名的存储服务,虽然也可以理解为 KV 存储,但它和 Dynamo 的目标场景并不一致。S3 是面向大文件的对象存储服务,主要存储二进制文件,不提供跨对象的事务。而 Dynamo 是一款面向小文件的文档存储服务,主要存储结构化数据(如 json),并且可以对数据设置索引,且支持跨数据条目的事务。

相对于传统的关系型数据库,Dynamo 可以认为是只提供主键索引,从而获取更高的性能和更好的扩展性。

为了实现可扩展性和高可用性,并保证最终一致性,Dynamo 综合使用了以下技术:

  1. 使用一致性哈希对数据进行分片(partition)和备份(replicate)。
  2. 使用版本号机制(Vector Clock)处理数据一致性问题。
  3. 使用多数票(Quorum)和去中心化同步协议来维持副本间的一致性(Merkle Tree)。
  4. 基于 Gossip Protocol 进行失败检测和副本维持。

实现上来说,Dynamo 有以下特点:

  1. 完全去中心化,没有中心节点,所有节点关系对等。
  2. 采用最终一致性,使用版本号解决冲突,甚至要求用户参与解决冲突。
  3. 使用哈希值进行数据分片,组织数据分布,均衡数据负载。
阅读全文 »

1591539058644.jpg

儿时初学“让我们荡起双桨”,只感觉旋律朗朗;年岁稍长,偶尔哼起,三言两语,味出千万意境;后来,求学帝都,游北海,正是“湖面倒映着美丽的白塔,四周环绕着绿树红墙”,光阴荏苒,不变的是文字的生命力。

歌词为乔羽先生所做,很多脍炙人口的名作皆出自其手:《我的祖国》、《难忘今宵》、《爱我中华》。词分三段,层层递进。第一段写划船之景,寥寥几句,首尾勾连、推近及远、勾勒出四合景象。第二段写欢快之情,童真昂扬,心情轻快,描绘出饱满的童趣。第三段继而升华,设问如此美景、如此生活、如此时代,如何得来?尔后戛然而止,语已尽而意无穷。

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第六节课笔记,是 Raft 论文讲解的第一部分,主要总结了容错的几种类型以及 Raft 中的 Leader 选举相关内容。

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第五节课笔记,包括两部分:第一部分由一个助教讲了 lab2 中将会用到的一些 go 的源语、设计模式和实践技巧,包括内存模型、goroutine和闭包、时间库、锁、条件变量、channel、信号、并行和一些常用工具等等。第二部分是由另两个助教梳理了下 raft 中常遇到的一些 bug 和调试方法。

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第四节课笔记,VM-FT。

备份——容错

失败(Failue)

如何定义?在其他电脑看来,停止对外提供服务。
通过备份/副本(Replication)
可以解决:宕机(fail-stop),比如 CPU 过热而关闭、主机或者网络断电、硬盘空间耗尽等问题。
不能解决:一些相关联(correlated,主副本机器会同时存在)的问题,比如软件 Bug、人为配置问题

前提

主从备份可以工作的一个假设是,主从机器的出错概率需要时独立的。
比如说:同一批次机器、同一个机架上的机器,出错概率就存在强正相关特性。

是否值当

需要对业务场景和所需费用考量,是否真的需要进行 Replica。比如银行数据就需要多备份,而课程网站可能并不需要。

阅读全文 »

目标

充分利用现代存储 SSD 的性能,在提供同样 API 的情况下,显著降低 LSMTree 的读写放大,以提高其性能。

背景

在传统磁盘上,顺序 IO 的性能大概是随机 IO 的 100 多倍,LSMTree 基于此,将海量 KV 的随机读写实现为内存随机读写+顺序刷盘+定期归并(compact),以提高读写性能,尤其适用于写多于读时效性比较强(最近数据最常访问)的场景。

wisckey-lsm-tree.png

阅读全文 »

博客本来用的是 github pages,但貌似由于百度爬虫太疯狂,被 github 给 ban 掉了。根据 marketmechian 的数据,在中国大陆搜索引擎界,百度还是占了半壁江山:

  • Baidu: 67.09%
  • Sogou: 18.75%
  • Shenma: 6.84%
  • Google: 2.64%
  • bing: 2.6%
  • Other: 2.08%

而作为一个中文博客,还是希望能够被更多的国内用户看到,因此一直在寻求一个使得百度爬虫自动爬取博客的方法。偶然间在浏览博客时,看到了有人在推荐 zeit.co 这个托管平台,使用了下,发现真是个非常棒的静态代码托管+CI Serverless Function 平台,在这里推荐给大家。

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第三节课笔记,GFS。

概述

存储(Storage)是一个非常关键的抽象,用途广泛。

GFS 论文还提到了很多关于容错、备份和一致性的问题。

GFS 本身是 Google 内部一个很成功的实用系统,其关键点被很好的组织到一块发表成为了学术论文,从硬件到软件,涵盖了很多问题,值得我们学习。

想详细了解 GFS,也可以看我之前的 GFS 论文笔记

阅读全文 »