写一个分布式存储系统有多简单? (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)

HOW TO PRESENT A PAPER

Leslie Lamport

4 August 1979

原址

1.  WHAT TO SAY(说什么

    – Don’t give your paper; the audience can’t take it.  If someone
      can understand in thirty minutes what it took you weeks to
      develop, then you’re in the wrong business.

不要和别人谈论你的论文,别人不可能在短时间内理解的。如果别人能在三十分钟内理解你花了几个星期才写出的成果,那只能说明你的成果并不是很有价值。

另外分析一个句子If someone can understand in thirty minutes what it took you weeks to develop, then you’re in the wrong business.,这是一个同位语从句,what 是understand 的宾语,同时也是后面的句子的同位语。

    – Do advertise your paper.  The purpose of an automobile ad is
      to get potential customers to the showroom, not to give technical
      specifications.  The purpose of your talk is to get people who
      might be interested in your work to read the paper, not to save
      them the trouble of reading it.

要为你的文章打广告,汽车广告的目的是将潜在的客户吸引到它的showroom,而不是给出技术细节。你演讲的目的是使得可能对你论文感兴趣的文章的人去阅读你的文章,而不是节省他们阅读文章的困难。

    – Giving a good presentation is an art, requiring both practice
      and talent.  No rules can turn you into an artist, but the
      following suggestions might be helpful.

        1.  Describe simple examples rather than general results. 
            Try to make the examples much too simple — you will not
            succeed.

        2.  Don’t use formalism.  If your results cannot be described
            simply and informally, then there is no reason why anyone
            should be interested in them.

        3.  It is better to be inaccurate than incomprehensible.  The
            place for accuracy is in the paper.  (However, false
            advertising is unethical.)

2.  HOW TO SAY IT

    – Slides are effective.  Here are some suggestions for their proper
      use.
     
              1.  Don’t put too much on a slide — a picture of a thousand
            words is worthless.  For 8 x 11 slides, all letters should
            be at least 3/8 inch high, with plenty of blank space. 
            People in the back row have to read them too.

        2.  Slides should be neat and legible.  The listener isn’t
            your secretary; it’s not his job to decipher your
            handwriting.

        3.  A rapid sequence of slides has a hypnotic effect.  Unless
            you are a licensed hypnotist, don’t use more than one slide
            per minute.
           
        – Time your talk.  Running over your allotted time is a mark of
      incompetence, and displaying your incompetence is a poor way
      to get someone to read your paper.  Remember that talking to
      an audience takes longer than talking to a mirror.

3.  DA CAPO

    – You are now thinking:  “All those dull speakers I’ve listened
      to should use these rules, but I don’t need them because my talks
      are interesting.”  All those dull speakers are now thinking exactly the
      same thing.  Read the rules again with the proper humility.  They
      apply to everyone.

        “The only wisdom we can hope to acquire
        Is the wisdom of humility:  humility is endless.”

4.  CODA – For Session Chairmen

– Be utterly ruthless about enforcing time limits.  Warn the
      speaker when he has 10 minutes left and when he has 5 minutes
      left, and stop him in midsentence when his time is up. 
      The audience will be grateful.  (A loud alarm clock works quite
      well if you don’t turn it off until the speaker has finished
      talking.)
     
       – Protect the speaker and the audience from inappropriate
      questions.  Questions should be allowed during the talk only
      if the audience is small and the question is a simple request
      for clarification.  After the talk, you must be prepared
      to silence the following two kinds of questioner.

        1.  One who leads the speaker into a long discussion of an
            obscure detail which is of no interest to most of the audience.
           
               2.  One who monopolizes the time arguing with the speaker over
            unresolvable philosophical issues.

      Remember that silencing one person enables the rest of the
      audience to ask questions.

FAST10、FAST11和FAST12 字频统计

FAST10、FAST11和FAST12 字频统计

  • 操作系统
    1. linux      408
    2. nfs         231
    3. zfs          201
    4. lustre     134
    5. windows 128 (许多文章来自Microsoft 公司)
    6. MAC       8
  • 文件系统
    1. ext3        425
    2. ext2        264
    3. hdfs        87
    4. ntfs         27
  • 领域/方向
    1. file system 4964
    2. storage   3839 (从前两项就可以看出这会议是FAST 了)
    3. flash 1681 + SSD 1002 (2683) (这两年NAND flash 已经明显超过了disk 的关注)
    4. disk        2399 (2011 年有个专题就叫做:Disk is not dead)
    5. memory  1829
    6. cache     1516
    7. workload 1173
    8. metadata 954
    9. deduplication 737
    10. algorithm  373
  • 性能/对比
    1. write        2283 (在写性能方面做的工作比读更多,可见写性能更收到关注)
    2. read        1610
    3. size         1363(容量>价格>延时>吞吐量)
    4. throughput 598
    5. latency     744
    6. price         841

Python线程,网络

最近写了些测试程序,python 的一些网络和线程总结如下:

  • Server/Client
  1. 创建socket 对象
  2. 绑定socket 到指定地址
  3. socket 的listen 方法接受连接
  4. 处理
  5. socket.close 关闭连接
  • 创建监听服务器方法:

创建一个类继承BaseRequestHandler(import SocketServer)

class Myserver(SocketServer.BaseRequestHandler):

这个服务器将在收到一个连接后创建一个线程,线程code 在handle里

def handle(self):

  • 全局变量&类变量

能不用全局变量就不用全局变量是个好习惯

即使在handle 内定义了全局变量 global param 也只是局部变量,该变量在线程死亡后被清理

可以使用类变量达到全局变量的效果

Extracting Flexible, Replayable Models from Large Block Traces

原文

文章看了三天都没有看出所以然来。

今天重新看了yangsuli 博客,发现原来文章所谈的就是我读的那么回事。至于为什么我没有看出东西来,是因为我不知道这篇文章是要干嘛的,难道只是对trace进行了压缩么?

Main idea: take standard trace, then divide them into chunks, define feature function to turn traces into a muliti-demention diagrame, to trade accuracy for size reduction.

将标准的trace 按照时间点(文章谈到了在trace可能出现的误差点或不精确点chunk 作为分隔点)或者块大小分隔大小,然后根据特征(读、写、偏移)函数将traces 转化为多维度的图,然后通过重复数据删除和benchmark plugin对数据进行压缩,以减少精确度换取size 的缩小。

我的点点想法:

  1. 重复数据删除在算法优劣的评价下并没有一个数据集合,一方面是如果真的有这个数据集合也会是非常非常大的,它的存在价值不大;另一方面更需要一个精简的方法来衡量算法的优劣,这个方法甚至可以自己创造一个数据集合对重复数据删除算法进行评估。重复数据算法实际上就是压缩算法,比较压缩算法的优劣也没有固定的数据集合,但可以通过压缩率来衡量,有人要说压缩率对不同的数据集的压缩率也是不一样的,好在就在于压缩算法更容易用数学来进行考察。这样有一个方式就是通过比较重复数据删除和固定压缩算法的压缩比,但问题又来了还是需要数据集。而且数据集合取得不好的话,可能这两者之比相差非常大,比如讲一个word 文档复制后重命名,重复数据删除这两个文档几乎没有压缩,而压缩算法对这种情况却十分有利。
  2. chrome 客户端写一个插件可以保存指点图片/链接(右键该图片/链接)、保存指定文字(选中该文字)、保存页面(页面上右键)到远程服务器(可以考虑ustor 哦)。在本地桌面安装一个快捷方式可以随时查看以上保存的文件。有人要质疑这样做的好处了,本地不都是可以做这些的么?但没有感觉本地在保存图片和页面的步骤繁琐,还需选文件夹,chrome 还要卡卡的以下,能够让远程服务器(云端)做这样的事情,我们只是单击下邮件或者按下快捷键是多么惬意的事情啊?有一个小小的问题就是如何认证所在的用户并保存它的数据到他的远程文件夹(显然是要先注册的)。

SSD 综述

写在文章之前

从传统的观点来看,SSD 分为两大类:基于Flash 的SSD 和基于DRAM 的SSD ,DRAM 为易失性存储介质,所以需要外接电源;主流基于Flash 的SSD 又分为NOR Flash 的SSD 和NAND Flash 的SSD。

NOR Flash 和NAND Flash 的物理存储单元都是浮栅晶体管(floating-gate transistors),Intel 在1988 率先发明了NOR Flash,价格昂贵,数据线和地址线分开,所以芯片内cell 电路复杂(容量也没有做到很大);而东芝toshiba 在1989 年发明了NAND Flash,价格较便宜,将数据线和地址线合并,芯片电路得以简化。NOR Flash 最大的特点就是程序可以在Flash 中执行而不用读取到RAM 中,其读速度要比NAND Flash 快些,两者在写入前大都需要擦除,写入和擦除NAND Flash 比NOR Flash 快。接下我们谈到的都是NAND Flash SSD。

另外在看SSD 论文的时候会提到program 这个单词,指的是SSD 的写入,单指一个cell 写入0或者1 的这种情况,对应的单词是earse (擦除)。

SSD 的组成

SSD 物理上主要由控制器(controller)、缓存(DRAM)、总线(BUS) 和NAND Flash 芯片组成。

  • 控制器:和HDD 中控制器类似,负责和主机通信,进行读写控制。
  • 缓存:缓存从Flash 中读出的数据,另外FTL 的转换表也保存在这里。
  • 存储芯片:真正保存数据的地方,也是SSD 区别于HDD 的主要地方。
  • 总线和接口:包括数据线、控制线(channel 等)和传输接口(SATA,PCI-e,SAS 等)。

逻辑组成可以按照SSD 各部分的逻辑功能来划分:Host Interface 是主机接口、FTL 是逻辑地址到物理地址的转换层、RAM 用于缓存数据、Multiple Parallel Elements 持久化存储数据(为什么是Parallel 后面会讲到),结构如图:

picture_11

下面详细介绍下Flash 芯片的组成,我们将从小到大的顺序介绍:cell,page(页),block(块),plane(区域),chip。

  • cell:Flash 存储原理是浮栅场效应晶体管存储电子能力来保存数据的,SSD 0/1 位数据物理存储单元称为cell。根据cell 存储位数的不同可以分为SLC(single-level cell)、MLC(Multi-level cell)和TLC,SLC 在每个cell 中保存一位数据,MLC 在每个cell 中保存两位数据。NAND Cell2a
  • page:cells 组成page 页,每个page 有4KB-8KB 左右大小(会多出一些容量保存ECC 校验等信息)。Page也是Flash芯片读写I/O的最小单位,大容量的SSD 会采用更大的存储页,比如 256Gb 或者更大容量的存储页就是 8KiB 而非 128Gb(以及 64Gb、32Gb)的 4KiB。
  • block:pages 页组成block 块,每个块由128/256 个页组成,大小为512KB-1MB 左右。cell、page 和block 的关系见如下图。SSD 按块进行擦除。

9

  • plane:blocks 块组成plane 区域,每个区域有几千个块组成,大小达到GB。
  • die:planes 区域组成die ,die 也被称为LUN(逻辑单元)。下图是4 个planes 组成两个dies,两个dies组成一个chip。die_380_0

各种制程:1323315355_b3dbd0e5

256GB-世界最大单chip 容量

1323315362_ab477d79

  • chip:(也就是上图中手指上的东西),而我们平时看到的是封装好的package(感觉封装好了就是package,package 是里面可能有一个或者两个chip 被封装)。

ocz-vertex-3-pro-board-img1

多通道

我们已经知道了一块SSD 盘中会有多个Flash chips(每个chip 又包含两个dies,每个die 又有两个planes,每个plane 包含很多个blocks ……),每一个芯片的读速度可达40MB/S,写可达10MB/S,为了提高读写性能,SSD 实际上在内部对芯片做了一个RAID 0 ,也称为多通道技术。

前面谈到了die 也被称为LUN,这是因为die 是控制器(FBC=Flash Bus Controller)地址线寻址的最小单位,下图是一个四通道的例子,每个通道称为一个channel,一般包含了一个数据线和多个地址线。在一个channel 上的LUNs 之间串行的,但在不同channel 上的LUNs 之间并行的。

ONFI_multichannel

 

这就是之前为什么使用 Multiple Parallel Elements 描述Flash 存储体。

写放大(write amplification)

谈到写放大首先应该了解SSD 的写过程,写放大是因为每次重写都要擦除整块的数据再重新写入,如果这个块里面还有其他数据,还要涉及到数据的迁移。我们通过写放大率来衡量写放大:

写放大率=写入flash memory 的数据量/主机写入的数据量

垃圾回收和TRIM

垃圾回收和TRIM 是为了解决两个问题:

  1. Flash 长久使用后,可用空间碎片越来越多,影响I/O性能。
  2. 热点块I/O次数过大,影响SSD 寿命。

垃圾回收(Garbage collection)出现的原因是因为在一些块中,一些页保存着active 文件,而一些页被标记为“未使用”(SSD 中并不真正的删除文件),那么这些标记为“未使用”的页实际上被浪费了(garbage),因为这些页并不能被写入任何数据。可以想象SSD 在这样运行时间长了的情况下,垃圾空间越来越多,直至最后“没有空间”存储数据,一旦写入数据会出现大量的数据擦除和移动。

垃圾回收实际上是个进程,它会在负载轻的时候对这些有垃圾空间的块进行复制和擦除,整理出可用的空间给新写入的数据。

TRIM 是一个SATA 命令,它允许OS 通知SSD 哪些块不再被使用了,可以擦除了,使用这个命令可以动态的优化对SSD 的写操作,使得磁盘I/O 分散到整个SSD。window 7 和Linux 2.6.33 之后版本开始支持TRIM。

SSD 和HDD

SSD 和HDD 一个明显区别就是后者为机械设备,读写操作有机械的寻道延时和旋转延时(共计5-10 ms),因此IOPS 较低(<200),而SSD IOPS 能上万(随机访问时间<0.1ms),随机读写性能优于HDD,对应的延时也较小;现在SSD 的throughput 也要优于HDD ,数据传输率可以高达500MB/S,另外SSD 在功耗和抗震动也要胜HDD 一筹。但HDD 在容量、使用寿命(几乎无限)和价格上就要比SSD 更加有优势。

SSD 和存储卡(SD,microSD,CF 等)

wiki 中提到了一个有意思的话题:comparison of SSD with memory cards,SSD 和存储卡(其实还有我们使用的u 盘)在介质上使用的都是NAND Flash 芯片,但是它们都是为各自应用环境进行优化后的结果,各自考虑方面有能耗,性能,大小和可靠性。

SSD 存在是为了作为primary storage 设备,所以应该high throughput,low latency,能耗和大小就不太关注;而存储卡是为了能够方便的应用在数码产品上,必须足够的小,低能耗,而相应的速度就比SSD 要慢3X-4X,造成速度差异还是因为单通道和多通道。

Reference

  1. http://en.wikipedia.org/wiki/SSD(有问题找wiki 还是很方便的)
  2. http://www.qdpma.com/Storage/SSD.html
  3. http://baike.baidu.com/view/2741245.htm(NOR Flash 百科)
  4. http://pc.pcinlife.com/Storage/20111115/95.html#7(中文中算讲的很详细的啦)
  5. http://static.usenix.org/event/usenix09/tech/full_papers/rajimwale/rajimwale_html/
  6. http://pc.pcinlife.com/Storage/20111115/95.html#2_1(选购和测评信息)
  7. http://www.google.com/ncr
  8. http://wccftech.com/article/solid-state-drive-primer/(卡通版介绍,休闲娱乐专属)
  9. http://www.condusiv.com/blog/post/2010/12/31/Inside-SSDs.aspx(看着挺舒服的)
  10. http://www.blog.solidstatediskshop.com/2012/how-does-an-ssd-write/(SSD 写傻瓜教程)
  11. http://www.blog.solidstatediskshop.com/2012/how-does-an-ssd-write-part-2/(楼上续集)
  12. http://www.modoy.com.cn/2009/0716/5408.html(用SDHC 做RAID 0 蛋疼!)
  13. http://bbs.evolife.cn/thread-415-1-1.html(基础知识普及)
  14. http://www.youtube.com/watch?v=EhihfJHIu0I (不错的视频,需proxy)