关于qing

渺渺何所似,天地一沙鸥

微软云存储架构(Azure Cloud Storage)

原文:Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency

 

IDEA

A cloud storage system that provides customers the ability to store seemingly limitless amounts of data with high availablity and strong consistency. 为用户提供高可用、高一致性并近乎无限空间的云存储。

 

System characteristics 系统特点:

  1. High availablity and strong consistency 高可用性和强一致性
  2. Global and scalable namespace/storage 全局可扩展的名字空间、存储
  3. Multiple data abstractions from a single stack 支持多种类型的数据
  4. Automatic load balancing 自动负载均衡
  5. Range Partition vs Hashing 使用动态区域划分,而没采用哈希
  6. Append-only system 存储系统只有append 操作。
  7. End-to-end checksum 端到端的校验和
  8. Separate log file per RangePartition 日志文件粒度为RangePartition

高可用通过多副本策略实现(默认三个),数据写入的原子性操作保证强一致性。Azure 支持blob(数据块)、Table(structured storage)和Queues(消息队列)三类数据。所有数据都是以添加的方式写入的。

继续阅读

Differentiated Storage Services(差异化存储服务)

原文地址

  • Main idea

文章提出一个分类结构减少计算机系统和存储系统的日益扩大的语义差距。(我的理解文章做的工作就是将文件分级,按等级进行缓存提高效率)

We propose an I/O classification architecture to close the widening semantic gap between computer systems and storage systems.

 

  • 实验用例(Workload)

Filesystem prototypes and a database proof-of-concept that classify all disk I/O—with very little modification to the filesystem, database, and operation system.

 

  • 存在问题(Problems)

Block-based storage interface makes it difficult for computer systems to optimize for increasingly complex storage storage system internals, and storage systems do not have the semantic information to optimize independently. 块设备较稳定,但是问题就是带来存储没有上层语义信息进行存储优化。

 

  • 现有的解决方法(existing solutions)
    1. obtain more knowledge of storage system internals and use this information to guide block allocation. 计算机系统获取更多存储系统信息
    2. discover more about on-disk data structures and optimize I/O accesses to these structures. 对磁盘上不同数据结构进行I/O 优化
    3. I/O interface can evolve and become more expressive; object-based storage(天啊,我想到了老板) and type-safe disks fall into this category 增强型I/O 接口

这些解决方法也对应的遇到问题:1.计算机很难稳定地获得存储系统的内部信息;2.增加了计算机系统复杂度;3.受到块设备的限制。

另外还提到的一个解决方法也是我在之前考虑过的:通过预测模型加上预取提高I/O 性能,但这样不仅预测模型很难获取,而且很可能适得其反。

 

  • 文中提出的解决方法(solution provided by the paper)

We modify the OS block layer so that every I/O request carries a classifier. In this way, a storage system can provide block-level differentiated services—and do so on a class-by-class basis.

 

  • OS/FS/APP requirements(操作系统、文件系统、应用需求)
    1. In UNIX and Windows, we add a classification field to the OS data structure for block I/O (the Linux “BIO” and the Windows “IRP”) and we copy this field into the actual I/O command (SCSI or ATA)before it is sent to the storage system.
    2. FS have a classification scheme fot its I/O and assigns a policy to each class.
    3. Differentiated Storage services is a stateless protocol  ……(有点不懂既然每次读写都带了classificator,和存储设备就应该没有关系了,难道是因为分类在实现上是写到了不同存储介质,期望以后block 位置都不改变了,而其他情况可能改变block 的分配?)
    4. 在读写的时候添加分类符:classificator
  • Classifications(分类)

Class ID 从1-18,0 分别对应的是Ext3 superblock,group descriptor,bitmap,inode,directoryentry,journal entry,File<=4KB,File<=16KB ……File>1GB,unclassified 19个类,对应的优先级是0,0,0,0,0,0,0,1到12(0 最高)。

 

  • Evaluation(实验评估)

Workload: fileserver(文件服务器)、e-mail server(邮件服务器)and PostgreSQL database

Method: in-house, file-based workload generator for file and e-mail server workloads. Record the number of files written/read per second. Compare the performance of three storage configurations: no SSD cache, an LRU cache, and an enhanced LRU cache(LRU-S) that uses selective allocation and selective eviction.

Result: LRU-S caches much more smile file and metadata, so all results accord with it.

 

文章提出了减少存储系统和计算机系统语义差距的一个方法,即在读写时添加标识符,对操作的文件根据其属性进行分级,提高系统性能,但缺点也是显而易见的,需要对从应用程序,操作系统,存储系统甚至存储设备进行修改,虽然文章强调对每个部分的修改都是很少的;其次测试中选了了10GB SSD 进行缓存,更多容量的缓存得出怎么的结果并没有给出,能不能适用于现在的缓存还很难说,对于像momentus MX 这样的混合硬盘可能比较合适;最后不管怎么说,文章给块设备(或者说文件)添加了一个属性,不也就是对象的思想么?既然块设备转变为面向对象的存储有难度,可以像本文所提到的做一个简单的对象存储,这或许是个好的思路。

Scalable Consistency in Scatter

原文地址

  • idea:可扩展、一致性的分布式key-value 存储(evaluation of Scatter, a scalable and consistent distributed key-value storage system)
  • key insight:基于DHT 的一致性组
  • DHT 功能简介:传统DHT 中,应用数据和节点ID 都哈希为键值key,数值保存在先于或紧接着键值key 的那个节点
  • 为什么会发生一致性问题:1.Assignment violation 节点加入或者离开时对keyID 范围的声明的重叠。2.节点加入和离开对临近指针的影响。

Scatter Design

goal:一致性,可扩展性,自适应性

方法:用组来代替单个节点,RSM 基于paxos 一致性算法,组内使用一致性协议维持内部一致性,但是如静态指定组会存在一些问题:

  1. 当大量nodes 离开或者加入会使得该组失效
  2. 健壮性、可扩展性问题
  3. 当组内节点增多,一致性算法性能下降
  4. 热点问题

因此Scatter 允许多组操作:

  1. split       组一分为二
  2. merge   两临近组合二为一
  3. migrate 将组员从一组移动到另一组
  4. repartition 临近两组交换键值空间

强一致性在拓扑结构不是原子变化的情况下是很难保证的,因此文章引出“自创”的nested consensus 老保证原子性,但实际上nested consensus 就是组内的paxos 算法保证强一致性,组间两阶段提交保证弱一致性。

接着文章从发起方coordinator group,参与方participant group 解释了nested consensus 过程,实际上就是两阶段提交,文章也指出这样的交互过程需要大量的广播和消息,可以作为future work 进行改进。

整个Scatter 系统对外提供存储服务,每个组中会利用paxos 算法选举出一个master,组间交互只通过master,而具体数据时存在组内所有成员,存储对应数据的称为primary。文章谈到了所做的一些性能优化,lease,diskless paxos(信息不用存盘)、relaxed reads 等。

最后进行了测试并与openDHT 比较了consistency。

 

个人体会:

文章主要是提出了可扩展和一致性的key-value 存储系统,最大的创新在于把传统DHT 中单个节点的方法改成了一个组,节点的加入和退出就限制在了组内,对外这个组的状态和功能还是不变的。为了满足可扩展性,组可以进行分裂合并操作,通过形式上说明和实验组操作的OPs/sec、延时说明这个方法是可行、高效的。一致性是通过paxos 算法和两阶段提交实现,也不能说有新意。文章通过与openDHT 的比较,说明Scatter 不损失性能和可用性的情况下,一致性上比openDHT要好。但我有个小问题,组操作如果是手动的话就谈不上adaptive 了,如果是自动的话,这种组操作在节点加入和离开的时候频不频繁,虽然文章也给出了组操作的thoughput 和latency ,但我觉得这个应该同时进行读写操作才能说明问题,如果在现实情况中组操作严重干扰了用户的正常读写的话,试验中的高性能和可用性就不好说了。

人人网关系爬虫

想写个爬人人网关系的一个小爬虫,能够从我的账户开始,爬我的朋友的朋友的朋友……。当遇到朋友隐私设置为不可读时,希望后期能够通过遍历所有其他人的朋友反推出该人的朋友,这就就需要把人人网绝大部分人的关系爬出来。单线程实测了一下,大概每小时能爬一万个用户,流量在200kb左右,速度明显不够,后面希望多线程能给力些,并且有问题再爬到7 万用户的时候出现了死循环,问题还没找出来。

考虑到后面优化的几点

多线程

效率(换语言?)

爬id 和id 差重应该分开处理

程序说明:getone() 从todolist 中获取一个未爬过的用户,savenews() 将爬出来的用户id 保存并去重。每一千个用户保存一个文件,保存形式为:该用户ID@用户好友1ID 用户好友2ID ……

源码:

   1: #!/usr/bin/env python

   2: #encoding=utf-8

   3:  

   4: import urllib, urllib2, cookielib, re, sys

   5:  

   6: class  Renren(object):

   7:  

   8:     def __init__(self,email,password):

   9:         self.email=email

  10:         self.password=password

  11:         self.origURL='http://www.renren.com/Home.do'

  12:         self.domain='renren.com'

  13:         # 如果有本地cookie,登录时无需验证。

  14:         self.cj = cookielib.LWPCookieJar()

  15:         try:

  16:             self.cj.revert('renren,cookie')

  17:         except:

  18:             None

  19:         self.opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(self.cj))

  20:         urllib2.install_opener(self.opener)

  21:  

  22:     def login(self):

  23:         params = {'email':self.email,'password':self.password,'origURL':self.origURL,'domain':self.domain}

  24:         req = urllib2.Request(

  25:             'http://www.renren.com/PLogin.do',

  26:             urllib.urlencode(params)      

  27:         )

  28:         r = self.opener.open(req)

  29:  

  30:     def friends(self):

  31:         #好友目录地址

  32:         req='http://friend.renren.com/myfriendlistx.do'

  33:         print "Get my friends"

  34:         r=self.opener.open(req)

  35:         data=r.read()

  36:         f=re.findall('"id":(\d{6,15}),',data)

  37:         print "friends list"

  38:         print f,len(f)

  39:         #todo

  40:         self.todolist=f

  41:         self.donelist=[]

  42:         #write data

  43:         fdata=open('data0.txt','w')

  44:         for item in f:

  45:             fdata.write(item+' ')

  46:         fdata.close()

  47:         sernum=0

  48:         while True:

  49:             temp1w={}

  50:             sernum=sernum+1

  51:             print "data"+str(sernum)

  52:             count=1000

  53:             while count>0:

  54:                 count=count-1

  55:                 rrid=self.getone()        #从todo 里面取一个数据

  56:                 print count,rrid

  57:                 f=self.getfriends(rrid)

  58:                 self.savenews(f)    #保存该组数据到todo

  59:                 templst=''

  60:                 for eachid in f:

  61:                     templst=eachid+' '+templst

  62:                 temp1w[rrid]=templst

  63:             #将count 个结果写到文件

  64:             filename="data_"+str(sernum)+".txt"

  65:             fp=open(filename,'w')

  66:             for each in temp1w:

  67:                 fp.write(each+'@'+temp1w[each])

  68:                 fp.write('\n')

  69:     def getfriends(self,rrid):

  70:         friends=[]

  71:         count=0

  72:         while True:

  73:             req="http://friend.renren.com/GetFriendList.do?curpage="+str(count)+'&id='+rrid

  74:             print 'Get',req

  75:             r=self.opener.open(req)

  76:             data=r.read()

  77:             f=re.findall('profile.do\?id=(\d{7,15})"><img',data)

  78:             friends=friends+f

  79:             count=count+1

  80:             if f==[]:

  81:                 exit()

  82:         return friends

  83:     

  84:     def getone(self):

  85:         if self.todolist==[]:

  86:             print "Empty todo list"

  87:         popup=self.todolist[1]        #选择第一个id

  88:         self.donelist.append(popup)    #加入到done 列表

  89:         del self.todolist[1]        #在todo 中删除

  90:         return popup                #返回

  91:         

  92:     def savenews(self,newlist):

  93:         for item in newlist:                    #删除出现在了done 列表中的id

  94:             if item in self.donelist:

  95:                 newlist.remove(item)

  96:         self.todolist=self.todolist+newlist        #添加到todo 列表中

  97:         self.todolist=list(set(self.todolist))    #去掉重复元素

  98:  

  99:  

 100:  

 101: if __name__ == "__main__":

 102:     semail='[email protected]'

 103:     spassword='xxxxxxxxxx'

 104:     a=Renren(semail,spassword)

 105:     print "your account and password are %s %s" % (semail, spassword)

 106:     a.login()

 107:     a.friends()

听李德仁院士报告

昨晚和shenli 在八号楼听李院士的报告,显然主题是科协设置的,讲如何百优之类的。李院士讲了显然不可能人人百优,全国这么多高校,这么多专业,和每个专业众多的博士。学生只要用心学习,在某一方面有所贡献,就应该算是人才了。

第一点讲了最近升空的资源三号卫星,谈了卫星的性能以及他所带的团队是如何完成这个工程的,接着是敦煌数字化一些工作。就从他所谈到的工作和他的学生所做的工作来看,其实出几个百优都很正常的,很多都是独创性的工作,而且工作做得也非常具体,还有一点也非常重要的是贴合了国家的需要。

第二点是他对研究生和老师的要求。要求学生能够“读书”、“思考”、“创新”、“实践”,谈到学习,李院士讲到了他那时候学习条件没有这么好,也没有互联网带来的方便,自己基本上就是在图书馆里看书,做的笔记当时就有二十本了。而且现在学术界浮躁的风气非常严重,很多都没有认证读书,觉得到时候能到网上copy 就可以了。缜密思考能够指导人走向正确的方向,节约人的时间,如果一开始就选择了错误的模型,再怎么编程、调bug 也是浪费时间;批判性的思考能够给人以灵感和创新。创新是你所做的工作最好没有人做,如果去“啃”别人已经啃烂了的骨头,很难有什么肉的。实践就不说了,没有实践,之前的都是枉然。

第二点的第二部分是对老师提了几点要求:首先是要对自己的学生好,对一个学生好对他的将来影响非常大,老师的一点点鼓励会是学生的持久动力,并举了李院士本科时期得到王副校长肯定和帮助的例子,而他自己给他的研究生的补贴也是非常非常丰厚的。第二点是要大胆将自己的学生推到学术的前沿,老师可能在某些方面的细节没有学生清楚,但应该能够把握学科的前沿,并将学生指导到前沿进行研究,而不要拿一些别人已经做烂的东西来给学生做,更不能拿学生作为自己的劳动力(这个似乎在报告最开始就谈到了),这样才能够让自己的学生好毕业。第三点是要让每个学生能够发挥自己特长,不要强行改变学生喜好,对于毕业有困难的也要给其分配一个稍微适合他的工作让其毕业(中国毕竟现在还没有淘汰制)。最后一点是要向学生学习。

写一个分布式存储系统有多简单? (How easy to write a Distributed Storage System ?)

用python 写了个用户态分布式存储系统(且这么称吧),实现文件存储。(今天在google 上看到两个人和我干了同样工作,PyGfs 使用了pyro 库封装了一些远程调用,后者则是模拟实现了GFS 功能,两份代码都不长。)

自己的分布式文件系统总体分为Client 端和DataServer 端,没有NameServer 是因为通过文件名hash 得到对应的DS 服务器。存储的粒度为文件,提供write 和fetch,写文件和获取文件功能,读写过程:通过对路径+文件名进行hash,用机器数量为模数,得到目的主机编号和地址,数据通过socket 传过去,DS 的机器数在部署时可配置,写在配置文件。

TODO:文件分片,NS 实现(只保存目录树)

配置文件为ip , port 格式:

 1: 127.0.0.1,10001
 2: 127.0.0.1,10002
 3: 127.0.0.1,10003

 

DataServer 端:

 1: #!/usr/bin/env python
 2: #encoding=utf-8
 3: import os,sys
 4: import socket
 5:
 6: class DataServer:
 7:     port=10000
 8:     def __init__(self):
 9:         pass
 10:     def run(self):
 11:         dsoc=socket.socket(socket.AF_INET,socket.SOCK_STREAM)
 12:         dsoc.bind(('localhost',self.port))
 13:         print "listening at",self.port
 14:         while True:
 15:             dsoc.listen(1)
 16:             conn,addr=dsoc.accept()
 17:             print "connected",addr
 18:             databuf=conn.recv(13)
 19:             print "received",databuf
 20:             if databuf.startswith('WRITFILE'):
 21:                 print "OPS == write file"
 22:                 dlist=databuf.split(',')
 23:                 fnamelen=int(dlist[1])
 24:                 conn.send('OK')
 25:                 print "filenamelen is",fnamelen
 26:                 filename=conn.recv(fnamelen)
 27:                 filename=filename[filename.rindex('\\')+1:]
 28:                 print "file is",filename
 29:                 fp=open(filename,'wb')
 30:                 while True:
 31:                     data=conn.recv(1024)
 32:                     if not data:break
 33:                     fp.write(data)
 34:                 fp.flush()
 35:                 fp.close()
 36:                 print "finished!",filename
 37:             if databuf.startswith('FETCFILE'):
 38:                 print "OPS == fetch file"
 39:                 dlist=databuf.split(',')
 40:                 fnamelen=int(dlist[1])
 41:                 conn.send('OK')
 42:                 print "filenamelen is",fnamelen
 43:                 filename=conn.recv(fnamelen)
 44:                 filename=filename[filename.rindex('\\')+1:]
 45:                 print "file is",filename
 46:                 fp=open(filename,'rb')
 47:                 while True:
 48:                     data=fp.read(4096)
 49:                     if not data:
 50:                         break
 51:                     while len(data)>0:
 52:                         sent=conn.send(data)
 53:                         data=data[sent:]
 54:                 print "Fished to send ",filename
 55:             conn.close()
 56:
 57:     def setPort(self,port):
 58:         self.port=int(port)
 59:
 60: if __name__=="__main__":
 61:     ds=DataServer()
 62:     ds.setPort(sys.argv[1])
 63:     ds.run()

 

Client 端:

 1: #!/usr/bin/env python
 2: #encoding=utf-8
 3: import os
 4: import socket
 5: import hashlib
 6:
 7: class Configuration:
 8:     count=0
 9:     clist=[]
 10:     def __init__(self):
 11:         self.readPath("machineconf.txt")
 12:     def readPath(self,pStr):
 13:         self.pathStr=pStr
 14:         fp=open(self.pathStr,'r')
 15:         while True:
 16:             line=fp.readline()
 17:             if not line:
 18:                 break
 19:             line=line.rstrip()
 20:             self.clist.append(line)
 21:             self.count=self.count+1
 22:     def getCount(self):
 23:         return self.count
 24:     def getList(self):
 25:         return self.clist
 26:
 27: class Client:
 28:     maList=[]
 29:     macNum=0
 30:     def __init__(self):
 31:         conf=Configuration()
 32:         self.maList=conf.getList()
 33:         self.macNum=conf.getCount()
 34:     def write(self,src):
 35:         srcHash=self.hash(src)
 36:         print "File is",src
 37:         locatedNum=srcHash%self.macNum
 38:         print "Location machine number is",locatedNum
 39:         IPort=self.maList[locatedNum].split(',')
 40:         toIp=IPort[0]
 41:         toPort=IPort[1]
 42:         print "Send to",toIp,toPort
 43:         self.send(src,toIp,toPort)
 44:     def hash(self,src):
 45:         md5=hashlib.md5()
 46:         md5.update(src)
 47:         return int(md5.hexdigest()[-4:],16)
 48:     def send(self,src,ip,port):
 49:         clsoc=socket.socket(socket.AF_INET,socket.SOCK_STREAM)
 50:         clsoc.connect((ip,int(port)))
 51:         fp=open(src,'rb')
 52:         formStr="WRITFILE,%04d"%len(src)
 53:         print "formStr",formStr,len(formStr)
 54:         clsoc.send(formStr)
 55:         resdata=clsoc.recv(1024)
 56:         if resdata.startswith('OK'):
 57:             print "OK"
 58:         print "sending....",src
 59:         clsoc.send(src)
 60:         print "sending data...."
 61:         while True:
 62:             data=fp.read(4096)
 63:             if not data:
 64:                 break
 65:             while len(data)>0:
 66:                 sent=clsoc.send(data)
 67:                 data=data[sent:]
 68:         print "Fished to send ",src
 69:         fp.close()
 70:     def fetch(self,src):
 71:         srcHash=self.hash(src)
 72:         locatedNum=srcHash%self.macNum
 73:         IPort=self.maList[locatedNum].split(',')
 74:         toIp=IPort[0]
 75:         toPort=IPort[1]
 76:         print "fetch from",toIp,toPort
 77:         self.get(src,toIp,toPort)
 78:     def get(self,src,ip,port):
 79:         clsoc=socket.socket(socket.AF_INET,socket.SOCK_STREAM)
 80:         clsoc.connect((ip,int(port)))
 81:         formStr="FETCFILE,%04d"%len(src)
 82:         print "formStr",formStr
 83:         clsoc.send(formStr)
 84:         resdata=clsoc.recv(1024)
 85:         if resdata.startswith('OK'):
 86:             print "OK"
 87:         print "sending....",src
 88:         clsoc.send(src)
 89:         print "fetching data...."
 90:         ffile=src[src.rindex('\\')+1:]
 91:         fp=open(ffile,'wb')
 92:         while True:
 93:             data=clsoc.recv(1024)
 94:             if not data:break
 95:             fp.write(data)
 96:             print "fetching",data[-8:]
 97:         fp.flush()
 98:         fp.close()
 99:         print "finished!",src
 100: if __name__=="__main__":
 101:     mac=Client()
 102:     src="e:\\pics\\tumblr_m0pvvmcIv41r9mp65o1_500.gif"
 103:     mac.write(src)
 104:     mac.fetch(src)