一种适合分享的去中心化分布式海量存储分配和路由方法.doc

技术交底书腾讯案号交底书名称一种适合文件分享的去中心化分布式存储分配和路由方法发明人 zorroyliu, stephenzou 撰写人zorroyliu所在部门架构平台部相关产品微信C2C传图缩略语和关键术语定义接入节点: 无中心存储系统中负责处理上传下载请求，分配存储的功能性节点，数量不定，各节点身份对等。数据节点: 无中心存储系统中负责实际数据落地存储的节点，本文所提的为抽象的，可以自我管理自身数据的数据落地节点。数据KEY: 传统键值(Key-Value)存储系统中，用户在要求存储数据时需提供的数据标识，用于在存储系统中唯一识别被要求存储的数据，作为读取凭据。构造KEY: 本文所述系统中，通过数据KEY以及一些其他信息在接入节点上构造的数据标识，用于代替数据KEY作为用户对上传数据的读取凭据。1. 现有技术方案1.1. 概述在无中心分布式存储系统的设计中，面对大量的数据和节点，如何能够均衡地分配存储空间， 如何均衡存储节点的负载，如何快速地查询数据存储位置，是系统较为重要的指标，传统的无中心存储系统，很大一部分都存在存储不均匀的问题，而另一部分则存在存储均衡和查询效率这两个重要指标相互矛盾的问题。本文提出的存储和路由方法能够有效地规避这一问题。1.2. 传统无中心存储系统主要实现方案传统的无中心存储方案在分配存储空间和查找文件时较为常用的一致性哈希算法，即对数据的KEY进行一致性哈希后输出的值域在一个固定的环空间中(及最大哈希值紧邻最小哈希值)。对于数据节点而言，通过对各个节点随机赋予一定值，标定他在环状空间中的位置，来划分各节点负责存储的哈希值范围，通常每个节点负责他与他之前的节点区编号区域之间的存储。在分配存储空间和查询数据时，直接对数据KEY进行一致性哈希，通过哈希值来分配或者定位所需的存储。这种方案方便地实现了通过数据KEY存储路由，能够快速的查询和分配空间，但是由于存储空间分配直接与数据KEY相关，随机分配数据节点导致存储和数据节点负载不均衡。1.3. 传统方案的技术缺点存储分配依赖于KEY，不能各节点实际负载情况来分配，可能导致数据节点的负载和存储分配不均。2. 本发明技术方案的详细阐述（发明内容）我们的技术是定期地同步所有存储节点的负载情况，在上传时根据各数据节点实际负载和存储情况，来为数据分配存储节点，并以实际存储的数据节点路由信息，数据KEY，数据长度等等一些相关信息，主动构造一个新的全局唯一的结构化KEY，称为构造KEY，并将此KEY分配给用户的方式，来规避存储节点分配依赖数据KEY的问题，在下载时，用户提供构造KEY，任何一个接入节点可以将构造KEY按固定格式解出存储路由信息，并快速地定位数据所在位置，而无需进行过多地查询。相比传统实现方案，本方案规避了依赖KEY进行随机分配存储可能带来的负载不均情况，实现合理分配，快速访问。不仅如此，由于构造KEY以结构化方式构造，还可以向其中写入更多的上传数据相关信息，使客户端在不与系统通讯的情况下，就能够获取数据的一些基本信息。2.1. 处理流程1、 上传流程任意接入节点3)数据KEY+存储路由信息+数据信息2)数据KEY+数据1)数据KEY+数据存储节点集合4)构造KEY构造KEY编解码模块客户端存储节点管理模块存储节点图1 上传流程示意图如图1所示为本发明所述系统上传流程，详细描述如下:(1) 客户端开始请求上传数据，将数据与数据KEY发送至某一接入节点(2) 接入节点接收完毕收据后，不同于传统无中心存储系统必须依赖数据KEY进行一致性哈希算法来随机挑选存储节点，本方案可以由存储节点管理模块根据存储节点即时负载情况选择最优的存储节点，并成功写入数据。(3) 通过构造KEY编解码模块，将数据KEY，数据信息(如大小，CRC等)，存储路由信息以及上传时间，上传客户端标识等一些自定义信息填充构造KEY结构体后，编码为BASE64。(4) 接入节点将编码成功的构造KEY返回给客户端，客户端持有此构造KEY即可进行数据下载。2、下载流程5)数据任意接入节点4)数据3)目标存储节点地址2)路由信息1)构造KEY存储节点管理模块存储节点集合客户端 构造KEY编解码模块图2 下载流程示意图如图2 所示为本发明所述下载流程，详细描述如下:(1) 客户端开始请求下载数据，将构造KEY发送至某一接入节点(2) 接入节点接收到构造KEY，通过编解码模块验证与解码，提取出数据存储节点的路由信息，转至存储节点管理模块处理。(3) 存储节点管理模块通过路由信息，直接确定出存储节点具体位置，并向其请求数据。(4) 对应存储节点读取数据并返回给接入节点。(5) 接入节点将数据返回给客户端。2.2. 构造KEY构造KEY结构定义如下:unsigned magic;构造KEY标志;unsigned short version;构造KEY结构版本编号;unsigned timestamp;构造KEY对应数据上传时间戳;unsigned length;构造KEY对应数据长度;unsigned routing;路由信息unsigned crc32;CRC校验值unsigned keylength;数据KEY长度char realkey0;数据KEY该结构被填充后以二进制形式存在，通过BASE64编码转化为可见字符串返回给客户端。2.3. 本方案优势1、 通过主动分配结构化的KEY并将路由信息写入KEY的方式，规避了传统无中心存储系统必须依赖KEY来进行存储分配和路由的方式，从而避免因此导致的负载不均的问题2、 由于构造的KEY为结构化数据，可以向其中写入更多的上传数据相关信息，时KEY持有方在不与服务器通讯的情况下能取得对应文件的一些属性。3、 由于数据查询路由不再依赖数据KEY，因此可以允许重复的数据KEY存在，而不用担心冲突。3. 针对2中的技术方案，是否还有其他别的替代方案1、 二进制构造KEY还可以使用punycode,urlencode等其他二进制转可见字符的编码方式编码成可见字符分发给客户端，若对KEY形式不做要求，亦可直接以二进制形式直接作为KEY。2、 构造KEY中系统必须的信息为数据路由信息，除此之外，可以根据实际需求向构造KEY中写入任何数据，而不限于本文提及构造KEY结构所包含字段。3、 构造KEY中所存储的路