- 浏览: 310040 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
xugangwen:
你好 你知道b+树在初始化的时候加载策略么?不会全部加载,一般 ...
Berkeley DB Java Edition存储文件格式概述 -
zxjlwt:
欢迎交流http://surenpi.com
Eclipse插件开发打包为Update Site -
xuehaiwuyaya:
专门注册了个账号来顶楼主
eclipse中plugin与feature的区别 -
chenliaoliu:
上面写错了,提示是:There are no categori ...
Eclipse插件开发打包为Update Site -
chenliaoliu:
楼主你好,我按照你的方法来做,却提示there is no s ...
Eclipse插件开发打包为Update Site
Key-value存储简介
具备高可靠性及可扩展性的海量数据存储对互联网公司来说是一个巨大的挑战,传统的数据库往往很难满足该需求,并且很多时候对于特定的系统绝大部分的检索都是基于主键的的查询,在这种情况下使用关系型数据库将使得效率低下,并且扩展也将成为未来很大的难题。在这样的情况下,使用Key-value存储将会是一个很好的选择。
它被广泛应用于缓存,搜索引擎等等领域。
根据以上的描述,一个好的key-value存储需要满足哪些条件呢?
l Availability可用性
l Scalability可扩展性
l Failover故障恢复
l Performance高性能
简单来说,就是数据不能丢失,服务不能中断,能对故障进行感知并能自动恢复,读写性能极高。
文件存储
这一部分比较大,以后会另开主题写
单文件还是多文件
不少nosql的产品采用的是单文件存储的,数据量大以后肯定会遇到性能瓶颈,这一点无需多说,我想强调的是,采用多文件存储数据优点还是非常多的,不过也需要注意,操作系统对于能够打开的文件数目是由限制的,貌似Linux好像是1024(待确认),
Only Append
为了支持更快的写操作,数据文件的写操作只支持append,这个就不多说了,相信大部分的海量存储设计都是这样的。因此,更新操作等价于写操作,不过在写的时候第一步判断写到树的哪个位置时肯定会定位到树已有的节点上,这样可以使得这次写失效或者直接覆盖。
这样存在一个问题,就是对于失效的数据(比如更新过的数据)如何处理,比较好的办法是启动独立线程定时或手动进行清理,请注意,这是一个非常巨大的过程,它将耗光你的CPU和I/O,因为要进行频繁计算和数据迁移。
数据结构
B Tree家族这一数据结构被广泛的运用于数据库索引,如Mssql的B+tree,oracle的B-tree,熟悉索引的朋友一定很清楚,这种数据结构非常适合作为我们的Key-value存储的数据结构.关于B+tree,可以参见下图:它是一个多路搜索树, 数据存储在叶子节点上,非叶子节点作为叶子节点的索引,加速数据的查找,而叶子节点是一个有序的链表,每次搜索都会到达叶子节点才会结束,插入新数据可能会引起节点的分裂。
在本篇文章中,你需要知道,上层的节点成为IN(Internal Node),它持有其他节点的引用,叶子节点的上层是(Bottom Internal Node),而叶子节点则是存储数据的节点。
图片来自:http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx
这部分是纯粹的数据结构,就不多说了,如果想深入了解的话可以看看这篇论文《The Ubiquitous B-Tree》
设计要点
Partition
因为系统要具备高扩展性,因此,增加删除机器是频繁的操作,如何将数据均匀分散到集群中呢?比较常用的办法是hash取模的办法,但是这样一来,增加机器的瞬间,按照之前的hash取模方式,数据无法读取,这意味着需要对数据进行迁移,等待机器预热,这是很不好的办法。
目前比较公认的解决办法就是一致性哈希(consistent hashing)
首先按照机器的hash进行顺时针分布,如图,目前有5台机器,如果有一个读写请求,那么hash该key值得的一个hash值,定位到环上,如果没有定位到具体的机器,那么按照顺时针查找,找到的第一个机器就是目标节点。
如果需要新增机器,增加过程为,首先hash新机器得到其位置,加入新机器F,这时访问策略不变,那么按照之前的策略,如果hash到C-F之间的数据就无法找到了,但是这样一来影响就局限于C-F之间,不象之前需要整体迁移了。
最后,为了降低增加机器所带来的影响,我们可以为其增加虚拟节点(virtual nodes)。这样的话服务器在环上的分布就比较均匀,这样多个虚拟节点将对应一个我们的物理节点,增加机器所受到的影响也会变得最小。
Replication
为了达到高可用性和数据不丢失,我们需要通过复制将数据备份到多台机器,replication的实现机制一般是通过Master与replica之间的TCP/IP连接,然后根据相应的一致性策略将数据分发到replica上,这里的一致性策略主要包括两项:
1. replica能够延迟master的时间,这个的意思就是说,在这个时间内更新的数据,replica可能是看不到的。例如你设置的一致性时间是3s,那么在某个特定的时刻,replica上的数据实际上可能是master3s以前的snapshot。
2. master事务提交返回之前是否需要得到replica的确认。为了尽量保证数据不丢失,master需要得到一定数量的replica确认数据更新成功之后才能提交事务。
关于数据可靠性和性能之间,是需要进行折衷的,很显然,越是高的数据保障,那么性能肯定会受到影响。在这样的情况下,需要对上层的应用进行分析,看是否允许丢失一部分数据。
另外,还有一个问题就是,数据的同步是采用master分发还是replica定时请求的问题,两者各有优缺点,前者会在replica较多的情况下遇到瓶颈,而后者可能会有一些延迟。多级同步的方式能在一定程度上解决这个问题,即master向某些机器同步,而这些机器向其他机器同步。
当然,master管理写请求而replica管理读请求,至于如何决定读写请求的分发,我们可以使用monitor节点,由它来作为读写的入口, 如下图,然后Monitor管理集群的状态和生命周期,例如Master fail后,monitor将收到事件,它将发起一次选举选出新的Master,一般的选举算法就是在集群中寻找最后一次更新的节点,因为往往它的数据是最新。还有就是在有新的机器加入集群的情况下,Monitor会告诉新机器集群内的master是谁,replica机器才能与master取得连接同步数据。
<!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Visio.Drawing.11" ShapeID="_x0000_i1025" DrawAspect="Content" ObjectID="_1344072934"> </o:OLEObject> </xml><![endif]-->
使用Monitor的Master-replica集群
当然,自从有了ZooKeeper,这种监控和协同的脏活累活就可以都交给它了,利用ZooKeeper管理集群内节点的健康状况具备很大的便利,毕竟,上面这个办法的架构存在单点问题,最后肯定Monitor会拖集群的后腿。所以用ZooKeeper管理集群并且针对不同的事件作出响应。下面是一个示意图:
<!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Visio.Drawing.11" ShapeID="_x0000_i1026" DrawAspect="Content" ObjectID="_1344072935"> </o:OLEObject> </xml><![endif]-->
用ZooKeeper管理集群
最后,关于事务提交时的处理策略也值得注意,你需要为master和replica都指定.一般情况下,我们需要在减少频繁的I/O操作和数据保障性方面进行折衷,以下提交策略可选:
1. 在事务提交时将数据由内存刷到硬盘,这样数据具有最高的保障,但是你需要等待昂贵的I/O操作。
2. 在事务提交时将数据刷到操作系统buffer中,然后由操作系统自己决定何时刷到硬盘。这样可以在虚拟机挂了的情况下保证数据不丢失,但是不能hardware failture
3. 在事务提交时数据仍然维持在内存中,而在存储系统比较闲的时候进行持久到硬盘的操作,或在内存不够用的情况下进行写磁盘操作。
Get和Put操作
这两个动作是key-value存储系统最核心的两个操作,因此在设计上需要做更多的考虑。
下面是一种写操作的过程:
1. 执行tree搜索以定位插入数据所在的位置
2. 锁定该位置的父节点
3. 创建新的叶子节点
4. 将叶子节点写入。这个写操作发生在内存中,并且返回一个number它决定了叶子节点写到硬盘的位置
5. 修改父节点指向该叶子节点的引用。该父节点既持有指向内存的叶子节点的引用又持有磁盘的位置的number。
6. 标记该父节点为dirty(意味着内存中的版本没有出现在磁盘中)
7. 解锁该父节点
请注意,很明显,这个写操作完全发生在内存中,那么何时将数据同步到磁盘呢?这就是后面要讲的checkpoint。通过它定时的将内存中的脏数据写到硬盘。
读操作就简单很多了,搜索tree,定位到叶子节点,取出数据就行了,当然还有一些包括为缓存服务的操作就不细讲了(比如,为每个节点计数,每次对该节点的访问都使得其+1,这样在缓存evict的时候就很有用了)
上面所说的写操作在内存中并不会影响到读操作,因为,为了加快读操作,我们会在启动时预加载硬盘数据文件的内容到内存,由于只有叶子节点存储数据,因此我们需要根据加载的叶子节点还原整棵B+tree,毫无疑问这是一个耗时的操作,但是却是值得的。
数据模型
这块比较大,这里只重点讲一下以什么数据结构存取的问题。
首先需要解决的是,存储对象的问题,很显然,我们都有存取对象的需求,那么如何将对象转换为我们的底层存储格式呢?一般的办法有序列化,Json,XML之类,下面依次讲一下优缺点:
1. 序列化。可能是比较简单易实现的办法,但是空间占用过大
2. Json和XML都差不多,存储格式比较可读一点,解析和转换比较方便,不过对于数据量大的情况还是不推荐。
3. 字符串或者字节数组。我们按照一定的约定将对象拼成字符串,或者一次将对象的属性写入到字节数组,读取时按照相同的顺序解析即可,比较好的办法是定义一个接口,然后由客户端去实现对象字符串之间转换顺序的方法。这个比较推荐。
还有一些序列化的工具值得推荐,比如hadoop下的avro。
Checkpoint
和普通的关系型数据库一样,key-value也可以有自己的checkpoint,一般情况,checkpoint是为了减少数据恢复所需要的时间.在检查点到来时,按照之前的设计,它会将所有的dirty Internal Node写入log,这样会存在一个问题,大多数情况下,checkpoint会把整棵树写到log,解决问题的办法是我们采用增量的办法进行log,例如,如果有a和b加入到某个父节点。那么此时如果进行checkpoint时我们需要首先写一个完整的IN引用,并且记录对其进行的操作,add a,add b,这些操作记录在一个list中,当list变得过大以后我们又重新写一个完整的IN节点。
过期数据清理
这一部分只针对按照顺序写并且仅append的情况,为了减少I/O操作,无效数据仅仅被标记为delete且删除内存中对应的树的叶节点而不进行物理的删除,那么长期下去,失效数据会很多,这时候需要进行清理,一般的策略就是,当失效数据在文件中所占比例达到一定程度以后,执行清除操作。
1. 首先根据预先存储的记录信息判断哪些文件需要进行清理操作。
2. 扫描文件,找到仍然active的数据,拷贝到新的文件,扫描完成后删除此文件。
请注意,在写操作密集的情况下,这会造成竞争,因此尽量在访问量少的情况下执行此操作。
另外,可以使用多线程来进行清理操作。当然还有很多策略可以在清理的时候使用,比如,缓存一个叶子节点的父节点,在锁住该父节点执行迁移操作的时候可以顺便扫描该父节点下的其他叶子节点。
Need More?
复杂查询
人的欲望是无止境的…….除了基于主键的检索你可能还需要基于某个属性的检索,最好还能在多个属性上查询完了以后来个取交集,这个时候怎么办呢?
首先,我们有一个基于主键的key-value数据库,key存储的主键,而value存储的对象(物理存储为byte数组),那么假如我们想对对象的某个属性如name进行查询的话,那么我们可以再建一个数据库,key是待查询的字段,value是主键数据库的id。
Primary Database
Key(ID) |
Value(Object) |
1 |
Byte[] |
2 |
Byte[] |
Secondary Database
Foreign Key(Name) |
Value(ID) |
dahuang |
2 |
tugou |
1 |
这样一来按照name查询只需要查询一次secondary database取出主键id,再查一查primary database即可,这有点像正排索引和倒排索引的概率,如果对于多个字段的组合查询,只需要对其进行一次join即可,在join的时候可以先对待join的结果按照结果集大小进行排序,这样可以省下不少时间消耗。
虽然key-value存储按照上面的描述也可以支持多条件查询,但是不建议这样做,一是建立索引(二级数据库)需要额外的空间,二是这样需要多次查询影响性能,不管怎么样适度的折衷吧。
最后不得不提一下,由于B+tree的数据结构,它很好地支持范围查询(查询可以不下到叶子节点)可以极大的弥补搜索引擎中倒排索引进行范围查询需要全部扫描的缺陷。这也是其应用场景之一。
总结
Key-value在海量数据存储中占据很重要的地位,对于它的深入研究能带给我们很多启发,而它在某些局部问题上所表现的优秀的能力也值得我们关注。本文大致总结了一下目前所了解的一些问题,没有提到的东西还有很多(文件系统设计,事务,缓存等等),接下来如果有空会对文件系统设计进行详细讲解。
声明
首先,本文只是代表本人的一些浅见,不代表任何官方意见。其次,由于作者水平的原因,肯定会出现错误,欢迎指正(最好站内,给我留一点脸面-_-)
参考文献:
Dynamo: Amazon’s Highly Available Key-value Store
http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx (BTree,B-Tree,B+Tree,B*Tree都是什么)
评论
这一点能详细分享吗
这篇文章是否有点价值:
http://space.itpub.net/?uid-9842-action-viewspace-itemid-324586
tks,关于数据库级别的优化请多多分享
楼主的综合能力远在我之上,真的非常钦佩,目标也很远大,加油呀,给你鼓掌。
关于数据库内部的数据结构和一些算法,ali有好多高手,比如biti_rainy。
俗话说三人行必有我师呀,不知道有没有搞类似“同行评审”的活动。
有空可以组织一下,呵呵
这一点能详细分享吗
这篇文章是否有点价值:
http://space.itpub.net/?uid-9842-action-viewspace-itemid-324586
tks,关于数据库级别的优化请多多分享
楼主的综合能力远在我之上,真的非常钦佩,目标也很远大,加油呀,给你鼓掌。
关于数据库内部的数据结构和一些算法,ali有好多高手,比如biti_rainy。
俗话说三人行必有我师呀,不知道有没有搞类似“同行评审”的活动。
这一点能详细分享吗
这篇文章是否有点价值:
http://space.itpub.net/?uid-9842-action-viewspace-itemid-324586
tks,关于数据库级别的优化请多多分享
这一点能详细分享吗
这篇文章是否有点价值:
http://space.itpub.net/?uid-9842-action-viewspace-itemid-324586
这一点能详细分享吗
可修改系统内核参数
或者在系统启动脚本中加入这么一句:
ulimit -n 65535
仅对当前进程生效
每个文件、每个网络连接,都占用文件句柄
tks
发表评论
-
海量数据存储之动态Schema的传说
2011-04-26 13:06 11567简介 众所周知,对于海量数据的schema修改是一个极其昂贵 ... -
海量数据存储之存储设计(二)
2011-03-13 17:58 6569本节重点讲述数据的Durability(可靠性),纵然CAP理 ... -
海量数据存储之存储设计(一)
2011-03-06 13:51 11142相关文章推荐: 海量数据存储之Key-Value存 ... -
海量数据存储之新存储设备性能优化
2011-01-04 19:50 6806本文主要讲述NoSQL在Flash设备上的可以选择的其中一种优 ... -
Berkeley DB Java Edition存储文件格式概述
2010-12-13 17:21 8692Bdb je的底层存储格式是Log-Structured ... -
HBase存储文件格式概述
2010-11-29 19:36 12856概述 HBase是基于Bigtable ... -
主流数据库的分页sql
2009-05-06 11:00 1303------------------------------- ... -
JDBC事务
2009-05-06 11:02 3049作者:Jack Shirazi 开发通过ACID测试的 ... -
数据库设计之反规范化
2009-06-21 21:11 3065原文出处: http://www.aiview.com/ ... -
使用Oracle instant sqlplus连接远程数据库
2009-07-28 21:57 1969网上说的很复杂,其实根本不用那么复杂。 你只要在cmd下面敲 ... -
JDBC调用oracle存储过程
2009-07-29 09:52 1645好久不用java调用存储过程的系统了,今天被别人给问住了。。。 ... -
数据库联合查询的思考
2009-08-10 11:21 2552转自:巴士飞扬-技术BLOG : http://www.bus ...
相关推荐
如果使用key-value中的value来存储list(比如:list打包成json放入value中),其操作性能是非常低效的。 理想的Key-list通常需要如下特点: 1.list是海量的、且操作性能高效 2.list是有序的、且可动态调整顺序 ...
2.1 基于 Key-Value 存储的 NoSQL 数据库 基于 Key-Value 存储的 NoSQL 数据库主要是基于键值对来存储,利⽤哈希表来维护 Key 值与具体 Value 之间的映射关系,⽤户可以通 过 Key ⽅便的对数据进⾏定位。 Value 是...
1.1 Redis是一个key-value存储系统,支持多种存储结构,如String,Hash,list,zset等; 1.2 Redis采用内存中数据集的形式,因此读写性能优异; 1.3 Redis支持数据持久化,支持AOF和RDB两种持久化方式; 1.4 Redis类似...
#资源达人分享计划#
毫秒服务引擎集RPC、名字发现服务、负载均衡、业务监控、灰度发布、容量管理、日志管理、key-value存储于一体。 毫秒服务引擎的创作冲动和构建经验,来自QQ后台团队超过10年的运营思考。它是一整套解决方案,...
本文提出了一种通过引入内存数据库层,建立两层多分区分布式数据库架构。...NoSQL、Key-Value引擎如BigTable、Cassendra等在很多大型网站被采用,很好的解决了海量数据存储和访问问题。而对于电子商务类
海量数据的高效率存储与访问 高可扩展性和高可用性 1.2 产品分类 分类 代表产品 典型应用场景 数据模型 优点 缺点 键值(key-value) Tokyo Cabinet/Tyrant, Redis, Voldemort, Oracle BDB 内容缓存,主要用于处理...
这里的key-value存储不像memcached那样在内存中保存数据,而是把数据保存在硬盘上。与memcached在内存中处理数据比起来,由于必然要发生对硬盘的IO操作,所以性能上还是有差距的。但数据不会丢失是它最大的优势。 ...
是以key-value形式存储,和传统的关系型数据库不一样,不一定遵循传统数据库的一些基本要求。 优点: 对数据高并发读写 对海量数据的高效率存储和访问 对数据的可扩展性和高可用行 缺点: redis(ACID)处理...
数据存储技术相关)+ Mapreduce(数据处理),Hadoop的数据来源可以是任何形式,在处理半结构化和非结构化数据上与关系型数据库相比有更好的性能,具有更灵活的处理能力,不管任何数据形式最终会转化为key/value,...
举个例⼦,Redis是⼀个性能⾮常⾼的 内存Key-Value NoSQL,它⽀持List和Set、SortedSet等简单集合,如果你的数据分析需求简单地通过排序,链表就可以解决,同时总的数 据量不⼤于内存(准确地说是内存加上虚拟内存再...
目前对于互联网公司不使用Redis的很少,Redis不仅仅可以作为key-value缓存,而且提供了丰 富的数据结果如set、list、map等,可以实现很多复杂的功能;但是Redis本身主要用作内存缓存,不适合做持久化存储,因此目前...
:Bigtable 作为Google 云计算的一项关键技术,在需要海量的存储要求的Google 地图、Google Earth、Gmail、Youtube...了云计算环境下Key/value 存储系统的发展趋势,并从理论上得出Bigtable 系统的高可用性和高可靠性。
【什么是Bit-map】 所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 如果说了这么多还没明白什么是Bit-map,那么...
Bigtable是一个管理结构化数据的分布式存储系统,它被设计用来处理海量数据:分布在数千台通用服务器上的PB级的数据。Google的很多项目将数据存储在Bigtable中,包括Web索引、Google Earth、Google Finance。这些...
Redis 开源的⽀持⽹络,基于内存可持久化⽇志,key-value数据库,可⽤于 数据库 缓存 消息中间件 Neo4j 开源⾼性能的NoSQL图形数据库 7 数据处理 MapReduce 分布式离线的计算框架 批处理 ⽇渐被spark和flink取代 ...
作为常用的NoSQL存储系统之一,KV存储系统受到了开发者的关注。但常见的KV存储系统并不具备自动容灾和在线扩容功能,这给系统运营造成了不少麻烦。本文提出了一种构建高可用和自动弹性伸缩的KV存储系统的方法。与...
⼤数据技术涵盖了从数据的海量存储、处理到应⽤多⽅⾯的技术,包括海量分布式⽂件系统、并⾏计算框架、NoSQL数 据库、实时流数据处理以及智能分析技术如模式识别、⾃然语⾔理解、应⽤知识库等等。 ⼤数据和云计算...