记录学习过程中的点点滴滴
分布式数据存储
Jeff Dean谈如何在大型在线服务中做到快速响应
七 19th
之前在公司内网看到fanli分享过该类的内容,里面提到了backup requests和canary requests,印象比较深刻,也是深有体会,
所以这里就转载下这篇文章,以便后续加深理解。
原文:
Jeff首先以Google的搜索服务为例,说明了何为大扇出服务(Large Fanout Service),即一个搜索请求需要有大量子系统(Web、新闻、图像、视频、博客等等)参与其中,以便提供更丰富的搜索结果。在Google,基本不 会为特定的服务提供特定的机器,而是将服务都部署在一个机器池中,这被称为共享环境(Shared Environment),Google的共享环境大致会包含以下几个部分——Linux、调度系统、文件系统ChunkServer、多种其他系统服 务、Bigtable Tablet Server、随机MapReduce任务、CPU密集型任务以及随机应用。它的好处是可以极大地提升利用率,但同时也会带来诸多无法预测的问题,比如网 络拥塞等等。尤其是响应时间的长尾现象比较明显,一次请求的平均响应时间是10毫秒,但是却有99%ile的响应时间大于1秒,在大扇出服务中,如果需要 调用100台服务器获得最终结果,那有63%的请求耗时会大于1秒。
(备注:99%ile的含义:%ile means the percentage of people ranked below you)
针对延时问题,有些基本的降低延时的技术:
- 定义不同的服务级别,针对服务器上的请求队列和网络流量设定优先级。
- 减 少线头阻塞(head-of-line blocking),将大的请求打散成一系列小请求;比如,一个读请求需要读取64MB数据,而另有一个100KB的读请求必须等前者完成了才能得到处 理,此时可以将大请求分为多个小请求,以便100KB的那个请求能及时得到处理。
- 管理好昂贵的后台活动,比如分布式存储系统中的日志压缩就算昂贵的后台活动,此类活动可以考虑在负载低峰期去执行。
Jeff指出,我们要做的事就是基于一堆不可靠的资源打造一个可靠的整体,基于一堆无法预估的资源打造可以预测的整体。在延时处理方面,Jeff将对应的技术分为两大块:
- 跨请求适应(cross request adaptation),通过检测最近的行为,采取一些措施来优化后续的请求处理,通常会和负载均衡有关,生效时间大约是十几秒到几分钟。
- 同请求适应(within request adaptation),在当次请求中,对响应较慢的子系统采取一些措施,以改善本次请求的整体响应时间,通常是立刻生效的。
随后,他分别就两类技术进行具体展开说明。
libmemcached的retry_timeout问题分析
三 26th
最近在线上中遇到使用libmemcached的svr连接memcached间隔性的出现47错误,每次在2s的时间内大量出现,
其宏定义为MEMCACHED_SERVER_TEMPORARILY_DISABLED,表示memcached临时性不可用.
- 当某个时刻,某台memcached机器出现连接超时情况时,会将server的状态标识为MEMCACHED_SERVER_STATE_IN_TIMEOUT
- 在接下来的retry_timeout(默认为2s)的时间内,libmemcached将不会重新连接该memcached,总是直接返回47错误码,表示服务临时不可用
我们遇到的情况就是当某个时刻网络抖动(这个在跨机房通信应该比较常见),可能会是在ms级的,但是libmemcached会直接将该server不可用,并且在2s内不再重试。这里就是所谓的“快隔离、慢恢复”的理念,会在2s内导致该memcached不可用,出现大量47错误的原因。
可以通过MEMCACHED_BEHAVIOR_RETRY_TIMEOUT将retry_timeout设置为1s来减少网络抖动的影响,但是不能设置为0,最少是1s.
Hadoop MapReduce学习笔记1
十二 14th
Hadoop MapReduce是比较经典的Master/Slave架构设计,系统主要包括两大模块:
- JobTracker : 也就是我们所说的Master, 包括资源管理功能和作业调用功能;
- TaskTracker : Slave模块,或者称为Worker,任务执行的节点;
JobTracker中资源管理
- Hadoop以slot(槽位)代表计算资源,包括一定的内存和cpu核,具体细分为Map Slot和Reduce Slot,一个Task可占用多个slots;一个TaskTracker可划分多个slots(可配置), slots间的资源隔离目前hadoop做的不是太好;
- TaskTracker作为具体的执行单元,采用pull的的方式拉取任务,TaskTracker会定期的向JobTracker发送心跳,心跳的信息包括:我还活着,TaskTracker中运行的task的状态,如果有空闲的slots的话,向JobTracker表明我有空闲资源,JobTracker以心跳应答的方式向TaskTracker分配新的Task;
- JobTracker不会主动的和TaskTracker联系,只会接收心跳,然后再应答中向TaskTracker发送指令,如启动Task, 杀死Task;如果长时间未收到TaskTracker的心跳,表明TaskTracker可能已宕机,则会重启TaskTracker上已经分配的任务到其他的TaskTracker中;
- 任务的调度策略:默认简单任务调度策略FIFO,可用户自定义任务的调度策略;
JobTracker中的作业控制
- Hadoop将作业分为三个层次:
- 作业: 用户提交的作业,使用JobInProgress控制作业的运行状态,包含多个Tasks
- Tasks: 包括Map Task 和 Reduce Task: 使用TaskInProgress控制任务的运行状态,可能包含多个Task Attempt.
- Task Attempt : 某个Task的运行一次尝试,这里采用的类似two-phase commit的协议,因为jobtracker可能会针对同一Task启动两个Attempt(谁先执行完,使用谁的计算结果,并把另外一个杀掉),然后才会提交task attempt的结作为Task的计算结果,在TaskTracker中执行.
- JobTracker会从TaskTracker的心跳汇聚TaskAttempt的运行状态,然后调度未完成的task,分配给TaskTracker.
redis中常用数据结构介绍
四 13th
1. 常用数据结构
dict
在redis中最基本的三个数据结构是dict 、adlist和sds,其中dict是redis中最重要的数据结构了,其key-value的映射关系就是通过dict来实现的,dict的内部实现是hash table,这个哈希表的大小是动态增加或减少的,主要是依据哈希表中的元素个数;同时哈希表适用链接法来解决哈希冲突的,具体实现在dict.h和dict.c文件中;
adlist
adlist(a generic doubly linked list)双向链表,这个数据结构在redis中用的也比较多,包括像当前保存的客户端连接或者是value对应是list的实现等,都是用的adlist,这个应该来说比较简单,具体实现在adlist.h和adlist.c;
sds
还有一个比较基本的数据结构就是sds(dynamic string),对字符串处理的简单封装,具体细节实现在sds.h和sds.c中,有一篇文章是介绍sds的实现的,点击这里
更多 >

redis中sorted set的实现原理
四 12th
从redis 1.1版本,redis开始支持sorted set(有序集合),今天在看redis源码时,具体看了它的实现;
关于ZSET的具体用法:http://redis.io/commands#sorted_set
ZSET的实现用到了两个数据结构:hash table 和 skip list(跳跃表),其中hash table是具体使用redis中的dict来实现的,主要是为了保证查询效率为O(1) ,而skip list(跳跃表)主要是保证元素有序并能够保证INSERT和REMOVE操作是O(logn)的复杂度。
关于skip list这里简单介绍下:skip list是链表的一种特殊形式,对链表的一种优化;保证INSERT和REMOVE操作是O(logn)的负载读,而通用链表的复杂度为O(n);
关于skip list的详细介绍请参考下面这篇文章:
http://blog.csdn.net/caoeryingzi/archive/2010/11/18/6018070.aspx
sorted set的用途:
可以用作实时排名,例如微博用户的排名
还有TOPN问题等
http://wangyuanzju.blog.163.com/blog/static/1302920099311165490/
redis源码分析资料
四 8th
最近闲来无事,看看redis源码,看看redis为何如此高效~
下面是redis代码分析的资料,记录下:
比较全面但不太详细的分析:Redis: under the hood
简单的读和写的完整处理过程:More Redis internals: Tracing a GET & SET (同时也是一个挺好的GDB调试研究源码的实例教程)
关于虚拟内存:Virtual memory
其它资料:http://redis.io/documentation
那就先从redis最原始的1.0版本开始看吧,这里需要说明下,一般学习开源软件代码,最初的版本代码量比较少,看起来不是很费劲,而且基本上能够体现软件的架构信息。
有关本站redis的内容请点击这里

sheepdog源码分析之关键模块介绍(一)
三 15th
1) Worker工作线程模块
该模块是作为sheepdog工作线程模块,存在多个工作线程,默认NR_WORKER_THREAD =64个工作线程;线程的入口函数为worker_routine,同时struct work_queue中pending_list是双向链表,worker_routine从该链表中读取任务,然后执行,接着将执行过的任务放到struct worker_info中finished_list双向链表,然后向main thread发送一个信号,接着调用bs_thread_request_done来执行finished_list中任务的done函数,该函数的作用是发送响应信息。涉及的文件主要是worker.c和Worker.h
struct work_queue {
int wq_state; // int nr_active; //当前活跃的任务数目 struct list_head pending_list;//待执行的任务列表 struct list_head blocked_list; //没有用处了 }; struct worker_info { struct list_head worker_info_siblings;//链表的连接器,目前只有一个worker_info int nr_threads; //线程个数 pthread_mutex_t finished_lock; // struct list_head finished_list; /* wokers sleep on this and signaled by tgtd */ pthread_cond_t pending_cond; /* locked by tgtd and workers */ pthread_mutex_t pending_lock; /* protected by pending_lock */ struct work_queue q; pthread_mutex_t startup_lock; pthread_t worker_thread[0]; //工作线程的数据结构 }; |
这里需要特殊说明的是,有关任务Worker的属性WORK_SIMPLE和WORK_ORDERED,及有关block相关的函数,在0.2版本中应该是没有用处的,当时我也迷惑一阵。
Sheepdog存在三类的工作任务:
- Request: 所有来自客户端或者其他sheep的请求
- Recovery_work: 数据恢复任务
- Delete_work: 删除vdi的任务
- Cpg_event_work: 该任务作为cpg有关集群管理的任务,例如节点加入和send_message消息发送等,sheep保证当前系统只运行一个cpg_event_work任务,从sys->cpg_event_siblings中是未执行的任务。
sheepdog源码分析之关键数据结构介绍
三 15th
关键数据结构的说明
1.
struct sd_req {
uint8_t proto_ver; uint8_t opcode; //操作类型 uint16_t flags;// uint32_t epoch; uint32_t id; uint32_t data_length; uint32_t opcode_specific[8]; }; |
struct sd_rsp {
uint8_t proto_ver; uint8_t opcode; uint16_t flags; uint32_t epoch; uint32_t id; uint32_t data_length; uint32_t result; uint32_t opcode_specific[7]; }; |
这两个数据结构应该是作为抽象类,可以看出sizeof(struct sd_req) == sizeof(struct sd_rsp),这个是设计者故意为之,因为在发送请求和接收响应时,客户端是使用同一片内存区域; |
2.
struct sd_obj_req {
uint8_t proto_ver; uint8_t opcode; uint16_t flags; uint32_t epoch; uint32_t id; uint32_t data_length; uint64_t oid;//object id uint64_t cow_oid; uint32_t copies;//副本个数 uint32_t tgt_epoch; uint64_t offset; }; |
struct sd_obj_rsp {
uint8_t proto_ver; uint8_t opcode; uint16_t flags; uint32_t epoch; uint32_t id; uint32_t data_length; uint32_t result; uint32_t copies; uint32_t pad[6]; }; |
对object进行请求及响应,这里需要说明的一点:object在Sheepdog中作为数据存储单元,分为data_object 和vdi_object,分别存储数据和vdi的元数据,即后面提到的sheepdog_inode的内容,分片大小为4M。不知作者为何分这么小的分片? |
struct sd_vdi_req { uint8_t proto_ver; uint8_t opcode; uint16_t flags; uint32_t epoch; uint32_t id; uint32_t data_length; uint64_t vdi_size; //vdi的大小 uint32_t base_vdi_id; uint32_t copies; uint32_t snapid; uint32_t pad[3]; }; |
struct sd_vdi_rsp { uint8_t proto_ver; uint8_t opcode; uint16_t flags; uint32_t epoch; uint32_t id; uint32_t data_length; uint32_t result; uint32_t rsvd; uint32_t vdi_id; uint32_t pad[5]; }; |
对vdi进行有关操作的请求和响应 |
sheepdog源码学习二之代码目录结构介绍
三 9th
目录结构
include/
- config.h: 定义公共的宏
- bitops.h: 有关的位操作,主要是针对oid的使用情况
- util.h: 公用操作的实现
- list.h: 双向链表的实现,主要是参考linux内核代码的实现
- event.h: epoll异步事件模型
- logger.h: 日志操作
- net.h: socket网络IO
- sheepdog_proto.h: sheepdog中用到的操作类型及数据结构的定义:
- sheep.h: Sheep本身需要的数据结构和操作类型,与sheedog_proto.h为何分开定义暂不清楚
lib/
- logger.c: 有关日志文件的操作的实现
- net.c: 有关socket网络IO的实现
- event.c: 事件模型的有关实现
sheep/
- sheep_priv.h: 定义相关数据结构和声明相关函数
- work.h: 定义工作队列对外提供的数据结构和API
- work.c: 实现工作线程
- sdnet.c: 对网络IO的进一步封装,包括回调函数的定义
- group.c: 利用corosync对组进行管理
- store.c: sheepdog有关数据存储、epoch和日志的操作
- vdi.c: sheepdog中vdi的相关操作
- sheep.c: sheep的main函数入口
collie/
- treeview.h: vdi tree的有关操作
- treeview.c: vdi tree的实现
- collie.c: 对sheep进行管理实现

sheepdog源码学习笔记一
三 4th
最近这两天一直在看sheepdog的源码,有关sheepdog的用法,请参考我的另一篇博客:KVM分布式共享存储解决方案-sheepdog 总的来说,sheepdog的代码量不是很大,在一万行左右,比起其他的分布式文件系统如kfs,ceph等还是比较轻量级的,而且定位也是针对qemu/kvm等volume的解决方案.
sheepdog原理介绍
1. sheepdog是作为虚拟机kvm的volume使用的,是非普通的文件系统,这点和Amazon的EBS(Elastic Block Store)比较类似
2. sheepdog是一种对称(symmetric)的结构,各个节点的地位相同,没有中心节点,没有meta-server,使用Corosync 对物理节点进行管理
3. sheepdog中的对象存储分为两类,其一是One reader One Writer 其二是No writer multiple reader 而且对象是4M大小分片的,使用“一致性哈希”算法来确定对象存储位置,多副本存储
sheepdog的代码结构
./collie/treeview.c ./collie/collie.c ./sheep/vdi.c ./sheep/store.c ./sheep/sdnet.c ./sheep/work.c ./sheep/sheep.c ./sheep/group.c ./lib/logger.c ./lib/event.c ./lib/net.c
sheep目录下是有关sheepdog的大部分逻辑的处理,部署在各个节点上
collie目录是作为管理管理sheep的代码
lib目录下是关于网络、日志和事件等处理模型
…..
今天暂时写到这里……待续
近期评论