以技术为主
分布式数据存储
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目录下是关于网络、日志和事件等处理模型
…..
今天暂时写到这里……待续
KVM分布式共享存储解决方案-sheepdog
一 10th
介绍
今天在调研分布式文件系统时,非常偶然的机会看到sheepdog ,然后接着又看到KVM这个关键字,让我异常兴奋,这不是我一直在找的KVM镜像存储的分布式存储系统吗,原来KVM/Qemu最近已经开始对其进行了开发,并在Qemu 0.13.0版本后加入了与sheepdog的支持,太佩服国外的开源贡献者。
sheepdog(牧羊犬) 官方网站:http://www.osrg.net/sheepdog/
Sheepdog is a distributed storage system for KVM. It provides highly available block level storage volumes that can be attached to KVM virtual machines. Sheepdog scales to several hundreds nodes, and supports advanced volume management features such as snapshot, cloning, and thin provisioning.
安装步骤
1,环境准备
corosync-1.3.0.tar.gz sheepdog-0.2.0.tar.gz
2,安装corosync
corosync 是linux 集群管理的引擎,具体请参看官网
$ tar -xzvf corosync-1.3.0.tar.gz $ cd corosync-1.3.0 $ ./autogen.sh $ ./configure $ sudo make install
3,qemu 0.13的安装 (略)
4,sheepdog安装
$ tar -xzvf sheepdog-0.2.0.tar.gz $ cd sheepdog-0.2.0 $ ./autogen.sh $ ./configure $ sudo make install
这时可能会出现linux/signalfd.h 这个文件找不到,以及后续会出现signalfd undefined reference 的错误,我的系统是CentOS ,出现了这种错误,出现这种情况的话,我简单的解决方法是对signalfd进行模拟,这点我参考了qemu的有关实现,
具体是在sheep/work.c中加入以下代码:
代码太长,我贴到最后了,请参看附件
5,sheepdog的具体使用
1> 配置/etc/corosync/corosync.conf
mv /etc/corosync/corosync.conf.example /etc/corosync/corosync.conf
同时修改,bindnetaddr字段为自己的ip地址,mcastaddr(怎么修改暂时不清楚,应该是广播的地址,保持默认值即可)
2> 启动corosync
# corosync {注:需要是root账户}
3> 如果是ext3文件系统,需要加入user_xattr
mount -o remount,user_xattr /
4> 启动Sheep
# sheep ~/store_dir <span style="color: #ff6600;">#不能是相对路径,相对路径会出错</span>
# collie cluster format --copies=35> 查看状态
# collie node list
# collie cluster info
# colli vdi list6> 创建镜像
# qemu-img create sheepdog:Alice 256G
# qemu-img convert ~/amd64.raw sheepdog:Bob不过我在Convert时一直提示不成功,error while writing
查找原因:通过查看sheep.log日志文件,可以发现时由于Too Many open files 错误提示,原来是打开太多文件所造成的,因为sheepdog对文件进行4M进行分片的,这样会导致大量的文件打开,而一般的系统进程最多的文件数是1024 所以就这个错误!
解决方法:ulimit -n 4096 {或者更大的值} 这样修改只是在目前会话中有效,需要长久生效,请参看这篇文章
总结
sheepdog作为一个新的项目,感觉还是挺不错的,刚好弥补了开源虚拟化中有关镜像存储的问题,为后续的虚拟机迁移做准备,目前sheepdog暂时还未支持migrate ,不过看它的TODO LIST 下一步已经开始做了,系统能够尽快做出来,下一步主要是看下它的源码,因为很多地方会出现诡异的错误的,还需要解决呀!
KVM虚拟机在物理机间的迁移方法
一 5th
有关虚拟机间的动态迁移,我在虚拟机迁移技术漫谈 对它进行大概的介绍,现在结合今天我自身的实践,来具体解释下迁移的步骤;
1,环境准备
1) 共享存储-NFS: 理论上来说,需要迁移的虚拟机可以不适用共享存储,但是如果不用共享存储的话,在迁移的过程中就需要对镜像进行大量的拷贝,这个是非常耗时的,而且在大量的集群的情况下,基本上镜像都是存放在分布式的共享存储中,一是方便管理,一是为虚拟机的动态迁移做准备,有关NFS的使用和挂载,请参看我的另外一篇文章
CentOS配置NFS服务器的方法
2) 支持kvm迁移的qemu-kvm 和 kvm模块:我用的是最新的qemu-kvm-0.13.0.tar.gz ,而kvm模块,由于我的系统的内核版本过低,用的kvm-88中的kvm-intel.ko kvm.ko模块
2,启动kvm虚拟机
在下面的介绍中使用 源虚拟机是待迁移的虚拟机,目的虚拟机是迁移后的虚拟机
源主机的启动命令如下:
./qemu-system-x86_64 -m 512 -hda /home/yangguang/nfs_mnt/images/debian_lenny_i386_small.qcow2 -net tap -net nic,model=rtl8139 -vnc :1 -monitor stdio
#解释说明:
1, /home/yangguang/nfs_mnt: 代表NFS挂载的目录
2, -monitor stdio 将控制台定向的标准输入输出(这个是虚拟机迁移必须的,因为后续需要在命令行中进行操作)目的虚拟机的启动命令:
./qemu-system-x86_64 -m 512 -hda /home/yangguang/nfs_mnt/images/debian_lenny_i386_small.qcow2 -net tap -net nic,model=rtl8139 -vnc :1 -monitor stdio -incoming tcp:0:8888
#解释说明
1, 启动命令参数必须和源虚拟机的启动参数是一样的,包括网卡类型等
2, -incoming tcp:0:8888 这个是在端口8888接收迁移命令和数据这时在命令行中输入
info status
源虚拟机显示的状态是running
目的虚拟机的显示的状态时paused
更多 >
KFS[CloudStore] 使用fuse挂载方法【原创】
九 15th
1, 下载fuse-2.8.4.tar.gz
2, tar -xzvf fuse-2.8.4.tar.gz
3, ./configure && make && make install
注:需要root权限
4, echo “/usr/local/lib” >> /etc/ld.so.conf
/sbin/ldconfig
5, /sbin/modprobe fuse
如果出现fuse module not found的话,请使用fuse2.7.*版本,因为Fuse网页上提供下载的版本2.8以前的源码中包含kernel模块部分
,2.8及2.8以后的版本不包含kernel模块源码
6, 修改kfs-0.5中CMakeLists.txt中的
SET(Fuse_LIBRARY_DIR “/usr/local/lib”)
SET(Fuse_INCLUDE_DIR “/usr/local/include”)
7, 重新编译kfs-0.5 会在bin目录下生成kfs_fuse二进制文件
8, 启动kfs
9, 编写kfs.prp
metaServer.name=10.60.1.125
metaServer.port=20000
注:kfs.prp这个配置的路径是在kfs_fuse_main.cc中写的,
注意启动时kfs.prp与kfs_fuse是在同一个目录下
10, ./kfs_fuse /tmp/kfs-fuse -f -o allow_other 启动 #-o allow_other 运行其他用户访问
cd /tmp/kfs-fuse 就可以看到当前kfs下的所有数据了
11. fuse的一些参数:
- 其中,影响比较大的参数有
- -s 禁用多线程
- -o allow_other 允许其它用户访问
- -o allow_root 允许root用户访问
- -o nonempty 允许挂载在非空目录上
- -o auto_cache 开启基于修改时间的cache
- -o kernel_cache 开启内核cache
注:kfs-0.5版本中存在bug以及可优化的地方
1, 在fuse_read 和fuse_write 中调用Seek, 判断返回值status应该是大于等于0 而不是等于0
因为status 的值应该是seek后的文件偏移
2, 可以优化的地方,在每次fuse_read 和 fuse_write 时,都会进行open 和close 操作,这样会导致效率上的问题,加入读取很大的数据,导致进行多次open 和 close操作。
优化方法:使用client->Fileno(path) 来获得已经打开的fd ,如果fd不存在的话,再进行Open 操作,在函数结束时不进行
Close 操作,而是将close操作放到fuse_flush函数中(新增的函数),具体作用请参考fuse手册
结束


近期评论