搜索
分布式KeyValueStore漫谈V1.0广州技术沙龙(09/08/08)TimYang•Keyvaluestore漫谈–MySQL/Sharding/K/Vstore–K/Vstore性能比较•Dynamo原理及借鉴思想–Consistenthashing–Quorum(NRW)–Vectorclock–Virtualnode•其他话题说明•不复述众所周知的资料–不是Keyvaluestore知识大全•详解值得讲解或有实践体会的观点场景•假定场景为一IM系统，数据存储包括–1.用户表(user)•{id,nickname,avatar,mood}–2.用户消息资料(vcard)•{id,nickname,gender,age,location…}–好友表(roster)•{[id,subtype,nickname,avatar,remark],[id2,…],…}单库单表时代•最初解决方案–单库单表,MySQL•随着用户增长，将会出现的问题–查询压力过大•通常的解决方案–MySQLreplication及主从分离单库单表时代•用户数会继续增大，超出单表写的负载•Web2.0,UGC,UCD的趋势，写请求增大，接近读请求–比如读feed,会有“like”等交互需要写•单表数据库出现瓶颈，读写效率过低分库分表时代•将用户按ID(或其他字段)分片到不同数据库•通常按取模算法hash()modn•解决了读写压力问题但是，Shard≠架构设计•架构及程序人员的精力消耗在切分上•每一个新的项目都是重复劳动不眠夜-resharding通知：我们需要21:00-7:00停机维护•有办法避免吗？Shardingframework•框架，如hivedb–隔离分库的逻辑–期望对程序透明，和单库方式编程•没有非常成功的框架–数据存储已经类似key/value–期望用SQL方式来用，架构矛盾•框架之路也失败了，为什么？分库分表过时了•无需继续深入了解那些切分的奇巧淫技•nosql!Keyvalue时代•我们需要的是一个分布式，自扩展的storage•Web应用数据都非常适合key/value形式–User,vcard,roster数据•{user_id:user_data}百家争鸣•BerkeleyDB(C),MemcacheDB(C)•Bigtable,Hbase(Java),Hypertable(C++,baidu)•Cassandra(Java)•CouchDB(Erlang)•Dynamo(Java),Kai/Dynomite/E2dynamo(Erlang)•MongDB•PNUTS•Redis(C)•TokyoCabinet(C)/TokyoTyrant/LightCloud•Voldemort(Java)问题•Rangeselect：–比如需删除1年未登录的用户•遍历–比如需要重建索引•Search–广州，18-20•没有通用解决方法，依赖外部•Search–Lucene–Sphinx非分布式key/valuestore•通过clienthash来实现切分•通过replication来实现backup,loadbalance•原理上和MySQL切分并无区别，为什么要用？–读写性能–简洁性(schemafree)Keystorevs.MySQL•性能–Keystore读写速度几乎相同O(1)•O(1)vs.O(logN)–读写性能都比MySQL快一个数量级以上•使用方式区别–MySQL:RelationalObject–Keystore:SerializeDe-serialize非分布式k/v缺少•自扩展能力，需要关心数据维护–比如大规模MCDB部署需专人维护•Availability,“alwayson”•Responsetime,latency–NoSLA(ServiceLevelAgreement)•Decentralize–Master/slavemode产品•Berkeleydb及其上层产品,如memcachedb•Tokyocabinet/Tyrant及上层产品，如LightCloud•Redis及上层产品•MySQL,也有用MySQL来做，如friendfeed分布式K/Vstore•Dynamo(Amazon)•Cassandra(facebook)•Voldemort(LinkedIn)•PNUTS(Yahoo)•Bigtable(Google)•HyperTable(Baidu)(*粗体为开源产品)Benchmark•Keyvaluestore–Berkeleydb-memcachedb–Tokyocabinet-Tyrant–Redis•测试环境–XEON2*4Core/8GRAM/SCSI–1GigabitEthernetBenchmark•Server使用同一服务器、同一硬盘•Client为局域网另外一台,16线程•都是用默认配置，未做优化–Memcached1.2.8–bdb-4.7.25.tar.gz–memcachedb-1.2.1(参数-m3072–N–bxxx)–tokyocabinet-1.4.9,tokyotyrant-1.1.9.tar.gz–redis-0.900_2.tar.gz(client:jredis)•三大高手–Tokyocabinet–Redis–BerkeleyDB•究竟鹿死谁手？100bytes,5Mrowsrequestpersecond0100002000030000400005000060000700008000090000MemcachedMemcachedbTokyoCabinetRedisWriteReadRequestspersecond,16threads71,70885,765Redis46,23811,480TokyoCabinet/Tyrant35,2608,264Memcachedb(bdb)50,97455,989MemcachedReadWriteStore20kdata,500krowsrequestpersecond0200040006000800010000120001400016000MemcachedbTokyoCabinetRedisWriteReadRequestspersecond,16threads5,6411,874Redis7,9002,080TokyoCabinet15,318357MemcachedbReadWriteStore•到此，我们已经了解了–繁琐的切分–Keyvaluestore的优势–Keyvaluestore的性能区别•可以成为一个合格的架构师了吗•还缺什么新需求•如何设计一个分布式的有状态的服务系统？–如IMServer,gameserver–用户分布在不同的服务器上，但彼此交互•前面学的“架构”毫无帮助分布式设计思想红宝书–Dynamo:Amazon'sHighlyAvailableKey-valueStore–Bigtable:ADistributedStorageSystemforStructuredDataCAP理论•分布式领域CAP理论，Consistency(一致性),Availability(可用性),Partitiontolerance(分布)三部分在系统实现只可同时满足二点，没法三者兼顾。•架构设计师不要精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍Dynamo思想•TheA.P.inCAP–牺牲部分consistency–“Strongconsistencyreduceavailability”–Availability:规定时间响应(e.g.30ms)•Alwayswritable–E.g.shoppingcart•Decentralize1.ConsistentHashing•传统的应用–如memcached,hash()modn–Linearhashing•问题–增删节点，节点失败引起所有数据重新分配•Consistenthash如何解决这个问题？1.ConsistentHashing*Imagesource:=158如何确保alwayswritable•传统思路–双写？–如何处理版本冲突，不一致？2.QuorumNRW•NRW–N:#ofreplicas–R:min#ofsuccessfulreads–W:min#ofsuccessfulwrite•只需W+RN场景•典型实现：N=3,R=2,W=2•几种特殊情况•W=1,R=N,场景？•R=1,W=N,场景？•W=Q,R=QwhereQ=N/2+1•如果N中的1台发生故障，Dynamo立即写入到preferencelist中下一台，确保永远可写入•问题：版本不一致•通常解决方案：timestamp，缺点？–Shoppingcart3.Vectorclock•Vectorclock–一个记录(node,counter)的列表–用来记录版本历史*Imagesource:•如何处理(A:3,B:2,C1)？–Businesslogicspecificreconciliation–Timestamp–Highperformancereadengine•R=1,W=N•越变越长？Threshold=10如果节点临时故障•典型方案：Heart-beat,ping•Ping如何处理无中心，多节点？•如何保证SLA?–300ms没响应则认为对方失败•更好的方案？gossipgossip*Imagesource:临时故障时写入的数据怎么办•Hintedhandoff由于存在故障因素如何检查数据的一致性•Merkletree4.VirtualNode•Consistenthashing,每个节点选一个落点，缺点？增删节点怎么办•传统分片的解决方法：手工迁移数据•Dynamo:replicationonvnodeIDCfailure•Preferencelist•Nnodesmustindifferentdatacenter程序如何组织上述一切•Nodehas3maincomponent–Requestcoordination–Membership–FailuredetectionClientdrivenvs.serverdriven•Coordinator–ChooseNnodesbyusingconsistenthashing–ForwardsarequesttoNnodes–WaitsresponsesforRorWnodes,ortimeout–Checkreplicaversionifget–SendaresponsetoclientDynamoimpl.•Kai,inErlang•E2-dynamo,inErlang•SinaDynamoD,inC–N=3–Merkletreebasedoncommitlog–Virtualnodemappingsavedindb–Storagebasedonmemcachedb•已经学习了4种分布式设计思想–Consistenthashing–Quorum–Vectorclock–Virtualnode•只是分布式理论冰山一角•但已经够我们使用在很多场合•实战一下？分布式SocketServer可借鉴的思想•节点资源分布•假定5个节点采用取模分布,hash()modn•某台发生故障，传统解决