nosql 数据库笔记
I/O的五分钟法则
在 1987 年，
Jim Gray与 Gianfranco Putzolu 发表了这个"五分钟法则"的观点，简而言之，如果一条记录频繁被访问，就应该放到内存里，否则的话就应该待在硬盘上按需要再访问。这个临界点就是五分钟。 看上去像一条经验性的法则，实际上五分钟的评估标准是根据投入成本判断的，根据当时的硬件发展水准，在内存中保持 1KB 的数据成本相当于硬盘中存据 400 秒的开销(接近五分钟)。这个法则在 1997 年左右的时候进行过一次回顾，证实了五分钟法则依然有效（硬盘、内存实际上没有质的飞跃)，而这次的回顾则是针对 SSD 这个"新的旧硬件"可能带来的影响。
随着闪存时代的来临，五分钟法则一分为二：是把 SSD 当成较慢的内存（extended buffer pool ）使用还是当成较快的硬盘（extended disk）使用。小内存页在内存和闪存之间的移动对比大内存页在闪存和磁盘之间的移动。在这个法则首次提出的 20 年之后，在闪存时代，5 分钟法则依然有效，只不过适合更大的内存页(适合 64KB 的页，这个页大小的变化恰恰体现了计算机硬件工艺的发展，以及带宽、延时)。
不要删除数据Oren Eini（又名Ayende Rahien）建议开发者尽量避免数据库的软删除操作，读者可能因此认为硬删除是合理的选择。作为对Ayende文章的回应，Udi Dahan强烈建议完全避免数据删除。 所谓软删除主张在表中增加一个IsDeleted列以保持数据完整。如果某一行设置了IsDeleted标志列，那么这一行就被认为是已删除的。Ayende觉得这种方法“简单、容易理解、容易实现、容易沟通”，但“往往是错的”。
为了代替IsDeleted标志，Dahan建议用一个代表相关数据状态的字段：有效、停用、取消、弃置等等。用户可以借助这样一个状态字段回顾过去的数据，作为决策的依据。
删除数据除了破坏数据一致性，还有其它负面的后果。Dahan建议把所有数据都留在数据库里：“别删除。就是别 删除。” 手段篇一致性哈希
要求分布式架构的发展说起。
第一阶段
考虑到单服务器不能承载，因此使用了分布式架构，最初的算法为 hash() mod n,hash()通常取用户ID，n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发生故障时，系统无法自动恢复。
优点：发生单点故障时负载会均衡分散到其他所有节点，程序实现也比较优雅。 算法的选择
不同的哈希算法可以导致数据分布的不同位置，如果十分均匀，那么一次MapReduce就涉及节点较多，但热点均匀，方便管理。反之，热点不均，会大致机器效率发挥不完全。
Paxospaxos是一种处理一致性的手段，可以理解为事务吧。其他的手段不要Google GFS使用的Chubby的Lock service。我不大喜欢那种重型的设计就不费笔墨了。 背景
当规模越来越大的时候。
一、Master/slave 这个是多机房数据访问最常用的方案，一般的需求用此方案即可。因此大家也经常提到“premature optimization is the root of all evil”。 优点：利用mysql replication即可实现，成熟稳定。 缺点：写操作存在单点故障，master坏掉之后slave不能写。另外slave的延迟也是个困扰人的小问题。 二、Multi-master Multi-master指一个系统存在多个master,每个master都具有read-write能力，需根据时间戳或业务逻辑合并版本。比如分布式版本管理系统git可以理解成multi-master模式。具备最终一致性。多版本数据修改可以借鉴Dynamo的vector clock等方法。 优点：解决了单点故障。 缺点：不易实现一致性，合并版本的逻辑复杂。 三、Two-phase commit(2PC) Two-phase commit是一个比较简单的一致性算法。由于一致性算法通常用神话(如Paxos的The Part-Time Parliament论文)来比喻容易理解，下面也举个类似神话的例子。 某班要组织一个同学聚会，前提条件是所有参与者同意则活动举行，任意一人拒绝则活动取消。用2PC算法来执行过程如下 Phase 1 Prepare: 组织者(coordinator)打电话给所有参与者(participant) ，同时告知参与者列表。 Proposal: 提出周六2pm-5pm举办活动。 Vote: participant需vote结果给coordinator：accept or reject。 Block: 如果accept,participant锁住周六2pm-5pm的时间，不再接受其他请求。 Phase 2 Commit: 如果所有参与者都同意，组织者coodinator通知所有参与者commit,否则通知abort，participant解除锁定。 Failure 典型失败情况分析 Participant failure: 任一参与者无响应，coordinator直接执行abort Coordinator failure: Takeover: 如果participant一段时间没收到cooridnator确认(commit/abort)，则认为coordinator不在了。这时候可自动成为Coordinator备份(watchdog) Query: watchdog根据phase 1接收的participant列表发起query Vote: 所有participant回复vote结果给watchdog,accept or reject Commit: 如果所有都同意，则commit,否则abort。 优点：实现简单。 缺点：所有参与者需要阻塞(block)，throughput低；无容错机制，一节点失败则整个事务失败。 四、Three-phase commit (3PC) Three-phase commit是一个2PC的改进版。2PC有一些很明显的缺点，比如在coordinator做出commit决策并开始发送commit之后，某个participant突然crash，这时候没法abort transaction,这时候集群内实际上就存在不一致的情况，crash恢复后的节点跟其他节点数据是不同的。因此3PC将2PC的commit的过程1分为2,分成preCommit及commit,如图。 (图片来源：http://en.wikipedia.org/wiki/File:Three-phase_commit_diagram.png) 从图来看，cohorts(participant)收到preCommit之后，如果没收到commit,默认也执行commit,即图上的timeout cause commit。 如果coodinator发送了一半preCommit crash,watchdog接管之后通过query,如果有任一节点收到commit,或者全部节点收到preCommit,则可继续commit,否则abort。 优点：允许发生单点故障后继续达成一致。 缺点：网络分离问题，比如preCommit消息发送后突然两个机房断开，这时候coodinator所在机房会abort,另外剩余replicas机房会commit。 Google Chubby的作者Mike Burrows说过， “there is only one consensus protocol,and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即“世上只有一种一致性算法，那就是Paxos”，所有其他一致性算法都是Paxos算法的不完整版。相比2PC/3PC,Paxos算法的改进 P1a. 每次Paxos实例执行都分配一个编号，编号需要递增，每个replica不接受比当前最大编号小的提案 P2. 一旦一个 value v 被replica通过，那么之后任何再批准的 value 必须是 v，即没有拜占庭将军(Byzantine)问题。拿上面请客的比喻来说，就是一个参与者一旦accept周六2pm-5pm的proposal,就不能改变主意。以后不管谁来问都是accept这个value。 一个proposal只需要多数派同意即可通过。因此比2PC/3PC更灵活，在一个2f+1个节点的集群中，允许有f个节点不可用。 另外Paxos还有很多约束的细节，特别是Google的chubby从工程实现的角度将Paxos的细节补充得非常完整。比如如何避免Byzantine问题，由于节点的持久存储可能会发生故障，Byzantine问题会导致Paxos算法P2约束失效。 DHTDistributed hash table Map Reduce ExecutionMap Reduce已经烂大街了，不过还是要提一下。参见：http://zh.wikipedia.org/wiki/MapReduce Handling Deletes
但我们执行删除操作的时候必须非常谨慎，以防丢失掉相应的版本信息。
通常我们给一个Object标注上"已删除"的标签。在足够的时间之后，我们在确保版本一致的情况下可以将它彻底删除。回收他的空间。 列存描述数据库以行、列的二维表的形式存储数据，但是却以一维字符串的方式存储，例如以下的一个表：
这个表存储在电脑的内存(RAM)和存储(硬盘)中。虽然内存和硬盘在机制上不同，电脑的操作系统是以同样的方式存储的。数据库必须把这个二维表存储在一系列一维的“字节”中，又操作系统写到内存或硬盘中。 行式数据库把一行中的数据值串在一起存储起来，然后再存储下一行的数据，以此类推。1,Smith,Joe,40000;2,Jones,Mary,50000;3,Johnson,Cathy,44000; 列式数据库把一列中的数据值串在一起存储起来，然后再存储下一列的数据，以此类推。1,2,3;Smith,Johnson;Joe,Cathy;40000,50000,44000; 特点
亚数据库我发明的新概念，就是称不上数据库但有一些数据库的特征。可以指缓存。MemCachedMemcached是danga.com（运营LiveJournal的技术团队）开发的一套分布式内存对象缓存系统，用于在动态系统中减少数据库 负载，提升性能。特点
Memcached处理的原子是每一个（key，value）对（以下简称kv对），key会通过一个hash算法转化成hash-key，便于查找、对比以及做到尽可能的散列。同时，memcached用的是一个二级散列，通过一张大hash表来维护。 Memcached有两个核心组件组成：服务端（ms）和客户端（mc），在一个memcached的查询中，mc先通过计算key的hash值来 确定kv对所处在的ms位置。当ms确定后，客户端就会发送一个查询请求给对应的ms，让它来查找确切的数据。因为这之间没有交互以及多播协议，所以 memcached交互带给网络的影响是最小化的。 内存分配默认情况下，ms是用一个内置的叫“块分配器”的组件来分配内存的。舍弃c++标准的malloc/free的内存分配，而采用块分配器的主要目的 是为了避免内存碎片，否则操作系统要花费更多时间来查找这些逻辑上连续的内存块（实际上是断开的）。用了块分配器，ms会轮流的对内存进行大块的分配，并 不断重用。当然由于块的大小各不相同，当数据大小和块大小不太相符的情况下，还是有可能导致内存的浪费。 同时，ms对key和data都有相应的限制，key的长度不能超过250字节，data也不能超过块大小的限制 --- 1MB。 缓存策略当ms的hash表满了之后，新的插入数据会替代老的数据，更新的策略是LRU（最近最少使用），以及每个kv对的有效时限。Kv对存储有效时限是在mc端由app设置并作为参数传给ms的。 同时ms采用是偷懒替代法，ms不会开额外的进程来实时监测过时的kv对并删除，而是当且仅当，新来一个插入的数据，而此时又没有多余的空间放了，才会进行清除动作。 缓存数据库查询现在memcached最流行的一种使用方式是缓存数据库查询，下面举一个简单例子说明： App需要得到userid=xxx的用户信息，对应的查询语句类似： “SELECT * FROM users WHERE userid = xxx” App先去问cache，有没有“user:userid”（key定义可预先定义约束好）的数据，如果有，返回数据；如果没有，App会从数据库中读取数据，并调用cache的add函数，把数据加入cache中。 当取的数据需要更新，app会调用cache的update函数，来保持数据库与cache的数据同步。 从上面的例子我们也可以发现，一旦数据库的数据发现变化，我们一定要及时更新cache中的数据，来保证app读到的是同步的正确数据。当然我们可 以通过定时器方式记录下cache中数据的失效时间，时间一过就会激发事件对cache进行更新，但这之间总会有时间上的延迟，导致app可能从 cache读到脏数据，这也被称为狗洞问题。（以后我会专门描述研究这个问题） 数据冗余与故障预防从设计角度上，memcached是没有数据冗余环节的，它本身就是一个大规模的高性能cache层，加入数据冗余所能带来的只有设计的复杂性和提高系统的开支。 当一个ms上丢失了数据之后，app还是可以从数据库中取得数据。不过更谨慎的做法是在某些ms不能正常工作时，提供额外的ms来支持cache，这样就不会因为app从cache中取不到数据而一下子给数据库带来过大的负载。 同时为了减少某台ms故障所带来的影响，可以使用“热备份”方案，就是用一台新的ms来取代有问题的ms，当然新的ms还是要用原来ms的IP地址，大不了数据重新装载一遍。 另外一种方式，就是提高你ms的节点数，然后mc会实时侦查每个节点的状态，如果发现某个节点长时间没有响应，就会从mc的可用server列表里 删除，并对server节点进行重新hash定位。当然这样也会造成的问题是，原本key存储在B上，变成存储在C上了。所以此方案本身也有其弱点，最好 能和“热备份”方案结合使用，就可以使故障造成的影响最小化。 Memcached客户端（mc）Memcached客户端有各种语言的版本供大家使用，包括java，c，php，.net等等，具体可参见memcached api page[2]。 缓存式的Web应用程序架构有了缓存的支持，我们可以在传统的app层和db层之间加入cache层，每个app服务器都可以绑定一个mc，每次数据的读取都可以从ms中取得，如果 没有，再从db层读取。而当数据要进行更新时，除了要发送update的sql给db层，同时也要将更新的数据发给mc，让mc去更新ms中的数据。 性能测试Memcached 写速度平均速度: 16222 次/秒 最大速度 18799 次/秒 Memcached 读速度 平均速度: 20971 次/秒 最大速度 22497 次/秒 Memcachedb 写速度 平均速度: 8958 次/秒 最大速度 10480 次/秒 Memcachedb 读速度 平均速度: 6871 次/秒 最大速度 12542 次/秒 dbcached● dbcached 是一款基于 Memcached 和 NMDB 的分布式 key-value 数据库内存缓存系统。 ● dbcached = Memcached + 持久化存储管理器 + NMDB 客户端接口 ● Memcached 是一款高性能的，分布式的内存对象缓存系统，用于在动态应用中减少数据库负载，提升访问速度。 ● NMDB 是一款多协议网络数据库(dbm类)管理器，它由内存缓存和磁盘存储两部分构成，使用 QDBM 或 Berkeley DB 作为后端数据库。 ● QDBM 是一个管理数据库的例程库，它参照 GDBM 为了下述三点而被开发：更高的处理速度，更小的数据库文件大小，和更简单的API。QDBM 读写速度比 Berkeley DB 要快，详细速度比较见《 Report of Benchmark Test》。 Memcached 和 dbcached 在功能上一样吗?● 兼容：Memcached 能做的，dbcached 都能做。除此之外，dbcached 还将“Memcached、持久化存储管理器、NMDB 客户端接口”在一个程序中结合起来，对任何原有 Memcached 客户端来讲，dbcached 仍旧是个 Memcached 内存对象缓存系统，但是，它的数据可以持久存储到本机或其它服务器上的 QDBM 或 Berkeley DB 数据库中。 列存系列Hadoop之Hbase耶鲁大学之HadoopDBGreenPlumFaceBook之CassandraCassandra: API:manyThrift?languages,Protocol: ?,Query Method:MapReduce,Replicaton:,Written in:Java,Concurrency:eventually consistent,Misc: like "Big-Table on Amazon Dynamo alike",initiated by Facebook,Slides?,Clients? Cassandra是facebook开源出来的一个版本，可以认为是BigTable的一个开源版本，目前twitter和digg.com在使用。 Cassandra特点
Cassandra的主要特点就是它不是一个数据库，而是由一堆数据库节点共同构成的一个分布式网络服务，对Cassandra的一个写操作，会 被复制到其他节点上去，对Cassandra的读操作，也会被路由到某个节点上面去读取。对于一个Cassandra群集来说，扩展性能是比较简单的事 情，只管在群集里面添加节点就可以了。我看到有文章说Facebook的Cassandra群集有超过100台服务器构成的数据库群集。 Cassandra也支持比较丰富的数据结构和功能强大的查询语言，和MongoDB比较类似，查询功能比MongoDB稍弱一些，twitter的平台架构部门领导Evan Weaver写了一篇文章介绍Cassandra： http://blog.evanweaver.com/articles/2009/07/06/up-and-running-with-cassandra/，有非常详细的介绍。 Cassandra以单个节点来衡量，其节点的并发读写性能不是特别好，有文章说评测下来Cassandra每秒大约不到1万次读写请求，我也看 到一些对这个问题进行质疑的评论，但是评价Cassandra单个节点的性能是没有意义的，真实的分布式数据库访问系统必然是n多个节点构成的系统，其并 发性能取决于整个系统的节点数量，路由效率，而不仅仅是单节点的并发负载能力。 KeyspaceCassandra中的最大组织单元，里面包含了一系列Column family，Keyspace一般是应用程序的名称。你可以把它理解为Oracle里面的一个schema，包含了一系列的对象。Column family（CF）CF是某个特定Key的数据集合，每个CF物理上被存放在单独的文件中。从概念上看，CF有点象数据库中的Table.Key数据必须通过Key来访问，Cassandra允许范围查询，例如：start => '10050',:finish => '10070'Column在Cassandra中字段是最小的数据单元，column和value构成一个对，比如：name:“jacky”，column是name，value是jacky，每个column:value后都有一个时间戳：timestamp。和数据库不同的是，Cassandra的一行中可以有任意多个column，而且每行的column可以是不同的。从数据库设计的角度，你可以理解 为表上有两个字段，第一个是Key，第二个是长文本类型，用来存放很多的column。这也是为什么说Cassandra具备非常灵活schema的原 因。 Super columnSuper column是一种特殊的column，里面可以存放任意多个普通的column。而且一个CF中同样可以有任意多个Super column，一个CF只能定义使用Column或者Super column，不能混用。下面是Super column的一个例子，homeAddress这个Super column有三个字段：分别是street，city和zip： homeAddress: {street: "binjiang road",city: "hangzhou",zip: "310052",}Sorting不同于数据库可以通过Order by定义排序规则，Cassandra取出的数据顺序是总是一定的，数据保存时已经按照定义的规则存放，所以取出来的顺序已经确定了，这是一个巨大的性能优势。有意思的是，Cassandra按照column name而不是column value来进行排序，它 定义了以下几种选项：BytesType,UTF8Type,LexicalUUIDType,TimeUUIDType,AsciiType,和LongType，用来定义如何按照column name来排序。实际上，就是把column name识别成为不同的类型，以此来达到灵活排序的目的。UTF8Type是把column name转换为UTF8编码来进行排序，LongType转换成为64位long型，TimeUUIDType是按照基于时间的UUID来排序。例如：Column name按照LongType排序： {name: 3,value: "jacky"}, {name: 123,value: "hellodba"}, {name: 976,value: "Cassandra"}, {name: 832416,value: "bigtable"} Column name按照UTF8Type排序： {name: 123, {name: 3,value: "bigtable"} {name: 976,value: "Cassandra"} 下面我们看twitter的Schema： <Keyspace Name="Twitter"> <ColumnFamily CompareWith="UTF8Type" Name="Statuses" /> <ColumnFamily CompareWith="UTF8Type" Name="StatusAudits" /> <ColumnFamily CompareWith="UTF8Type" Name="StatusRelationships" CompareSubcolumnsWith="TimeUUIDType" ColumnType="Super" /> <ColumnFamily CompareWith="UTF8Type" Name="Users" /> <ColumnFamily CompareWith="UTF8Type" Name="UserRelationships" CompareSubcolumnsWith="TimeUUIDType" ColumnType="Super" /> </Keyspace> 我们看到一个叫Twitter的keyspace，包含若干个CF，其中StatusRelationships和 UserRelationships被定义为包含Super column的CF，CompareWith定义了column的排序规则，CompareSubcolumnsWith定义了subcolumn的排序 规则，这里使用了两种：TimeUUIDType和UTF8Type。我们没有看到任何有关column的定义，这意味着column是可以灵活变更的。 为了方便大家理解，我会尝试着用关系型数据库的建模方法去描述Twitter的Schema，但千万不要误认为这就是Cassandra的数据模型，对于Cassandra来说，每一行的colunn都可以是任意的，而不是象数据库一样需要在建表时就创建好。 Users CF记录用户的信息，Statuses CF记录tweets的内容，StatusRelationships CF记录用户看到的tweets，UserRelationships CF记录用户看到的followers。我们注意到排序方式是TimeUUIDType，这个类型是按照时间进行排序的UUID字段，column name是用UUID函数产生（这个函数返回了一个UUID，这个UUID反映了当前的时间，可以根据这个UUID来排序，有点类似于timestamp 一样），所以得到结果是按照时间来排序的。使用过twitter的人都知道，你总是可以看到自己最新的tweets或者最新的friends. 存储Cassandra是基于列存储的(Bigtable也是一样)，这个和基于列的数据库是一个道理。
我对Cassandra数据模型的理解： 1.column name存放真正的值，而value是空。因为Cassandra是按照column name排序，而且是按列存储的，所以往往利用column name存放真正的值，而value部分则是空。例如：“jacky”:“null”，“fenng”:”null” 2.Super column可以看作是一个索引，有点象关系型数据库中的外键，利用super column可以实现快速定位，因为它可以返回一堆column，而且是排好序的。 3.排序在定义时就确定了，取出的数据肯定是按照确定的顺序排列的，这是一个巨大的性能优势。 4. 非常灵活的schema，column可以灵活定义。实际上，colume name在很多情况下，就是value（是不是有点绕）。 5.每个column后面的timestamp，我并没有找到明确的说明，我猜测可能是数据多版本，或者是底层清理数据时需要的信息。 最后说说架构，我认为架构的核心就是有所取舍，不管是CAP还是BASE，讲的都是这个原则。架构之美在于没有任何一种架构可以完美的解决各种问题，数据库和NoSQL都有其应用场景，我们要做的就是为自己找到合适的架构。
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |