记录学习过程中的点点滴滴
分布式数据存储
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临时性不可用.
libmecached的版本是0.53
刚开始以为是网络间隔性异常导致，但是在排查无果的情况，只能深入看下libmemcached的源代码，发现了其内部实现的
retry_timeout的机制：
- 当某个时刻，某台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目录下是关于网络、日志和事件等处理模型
…..
今天暂时写到这里……待续
近期评论