![场景
? 假定场景为一IM系统，数据存储包括
– 1. 用户表(user)
? {id, nickname, avatar, mood}
– 2. 用户消息资料(vcard)
? {id, nickname, gender, age, location…}
– 好友表(roster)
? {[id, subtype, nickname, avatar,
remark],[id2,…],…}](https://image.slidesharecdn.com/keyvaluestore-090809211516-phpapp02-110731043213-phpapp01/85/Key-value-4-320.jpg)
分布式碍别测-惫补濒耻别漫谈
- 1. 分布式 Key Value Store 漫谈 V1.0 广州技术沙龙(09/08/08) Tim Yang http://timyang.net/
- 2. Agenda ? Key value store 漫谈 – MySQL / Sharding / K/V store – K/V store性能比较 ? Dynamo 原理及借鉴思想 – Consistent hashing – Quorum (NRW) – Vector clock – Virtual node ? 其他话题
- 3. 说明 ? 不复述众所周知的资料 –不是Key value store知识大全 ? 详解值得讲解或有实践体会的观点
- 4. 场景 ? 假定场景为一IM系统，数据存储包括 – 1. 用户表(user) ? {id, nickname, avatar, mood} – 2. 用户消息资料(vcard) ? {id, nickname, gender, age, location…} – 好友表(roster) ? {[id, subtype, nickname, avatar, remark],[id2,…],…}
- 5. 单库单表时代 ? 最初解决方案 –单库单表, MySQL ? 随着用户增长，将会出现的问题 –查询压力过大 ? 通常的解决方案 –MySQL replication及主从分离
- 6. 单库单表时代 ? 用户数会继续增大，超出单表写的负 载 ? Web 2.0, UGC, UCD的趋势，写请求 增大，接近读请求 – 比如读feed, 会有 “like” 等交互需要写 ? 单表数据库出现瓶颈，读写效率过低
- 7. 分库分表时代 ? 将用户按ID(或其他 字段)分片到不同数 据库 ? 通常按取模算法 hash() mod n ? 解决了读写压力问 题
- 9. ? 架构及程序人员的精力消耗在 切分上 ? 每一个新的项目都是重复劳动
- 11. ? 有办法避免吗？
- 12. Sharding framework ? 框架，如hivedb –隔离分库的逻辑 –期望对程序透明，和单库方式编程 ? 没有非常成功的框架 –数据存储已经类似key/value –期望用SQL方式来用，架构矛盾
- 13. ? 框架之路也失败了，为什么？
- 15. Key value时代 ? 我们需要的是一个分布式，自扩展 的storage ? Web应用数据都非常适合 key/value形式 –User, vcard, roster 数据 ? {user_id: user_data}
- 16. 百家争鸣 ? Berkeley DB(C), MemcacheDB(C) ? Bigtable, Hbase(Java), Hypertable(C++, baidu) ? Cassandra(Java) ? CouchDB(Erlang) ? Dynamo(Java), Kai/Dynomite/E2dynamo(Erlang) ? MongDB ? PNUTS ? Redis(C) ? Tokyo Cabinet(C)/Tokyo Tyrant/LightCloud ? Voldemort(Java)
- 17. 问题 ? Range select： –比如需删除1年未登录的用户 ? 遍历 –比如需要重建索引 ? Search –广州，18-20
- 18. ? 没有通用解决方法，依赖外部 ? Search –Lucene –Sphinx
- 19. 非分布式key/value store ? 通过client hash来实现切分 ? 通过replication来实现backup, load balance ? 原理上和MySQL切分并无区别， 为什么要用？ –读写性能 –简洁性 (schema free)
- 20. Key store vs. MySQL ? 性能 – Key store读写速度几乎相同 O(1) ? O(1) vs. O(logN) – 读写性能都比MySQL快一个数量级以上 ? 使用方式区别 – MySQL: Relational Object – Key store: Serialize De-serialize
- 21. 非分布式k/v缺少 ? 自扩展能力，需要关心数据维护 – 比如大规模MCDB部署需专人维护 ? Availability, “always on” ? Response time, latency – No SLA(Service Level Agreement) ? Decentralize – Master/slave mode
- 22. 产物 ? Berkeley db及其上层产物, 如 memcachedb ? Tokyo cabinet/Tyrant及上层产物，如 LightCloud ? Redis及上层产物 ? MySQL, 也有用MySQL来做，如 friendfeed
- 23. 分布式K/V store ? Dynamo (Amazon) ? Cassandra (facebook) ? Voldemort (LinkedIn) ? PNUTS (Yahoo) ? Bigtable (Google) ? HyperTable(Baidu) (* 粗体为开源产物)
- 24. Benchmark ? Key value store – Berkeley db - memcachedb – Tokyo cabinet - Tyrant – Redis ? 测试环境 – XEON 2*4Core/8G RAM/SCSI – 1 Gigabit Ethernet
- 25. Benchmark ? Server使用同一服务器、同一硬盘 ? Client为局域网另外一台,16线程 ? 都是用默认配置，未做优化 – Memcached 1.2.8 – bdb-4.7.25.tar.gz – memcachedb-1.2.1(参数 -m 3072 –N –b xxx) – tokyocabinet-1.4.9, tokyotyrant-1.1.9.tar.gz – redis-0.900_2.tar.gz (client: jredis)
- 26. ? 三大高手 –Tokyo cabinet –Redis –Berkeley DB ? 究竟鹿死谁手？
- 27. 100 bytes, 5M rows request per second 900 00 800 00 700 00 600 00 500 00 400 00 Wie rt 300 00 Ra ed 200 00 100 00 0 Mmahd Mmahd ecce ecceb Tko oy Rds ei Cbnt aie
- 28. Requests per second, 16 threads Store Write Read Memcached 55,989 50,974 Memcachedb (bdb) 8,264 35,260 Tokyo 11,480 46,238 Cabinet/Tyrant Redis 85,765 71,708
- 29. 20k data, 500k rows request per second 16000 14000 12000 10000 8000 Write Read 6000 4000 2000 0 Memcachedb Tokyo Cabinet Redis
- 30. Requests per second, 16 threads Store Write Read Memcachedb 357 15,318 Tokyo Cabinet 2,080 7,900 Redis 1,874 5,641
- 31. ? 到此，我们已经了解了 –繁琐的切分 –Key value store的优势 –Key value store的性能区别 ? 可以成为一个合格的架构师了吗 ? 还缺什么
- 32. 新需求 ? 如何设计一个分布式的有状 态的服务系统？ –如IM Server, game server –用户分布在不同的服务器上， 但彼此交互 ? 前面学的“架构”毫无帮助
- 33. 分布式设计思想红宝书 – Dynamo: Amazon's Highly Available Key-value Store – Bigtable: A Distributed Storage System for Structured Data
- 34. CAP理论 ? 分布式领域CAP理论， Consistency(一致性), Availability(可用性), Partition tolerance(分布) 三部分在系统 实现只可同时满足二点，没法 三者兼顾。 ? 架构设计师不要精力浪费在如 何设计能满足三者的完美分布 式系统，而是应该进行取舍
- 35. Dynamo 思想 ? The A.P. in CAP – 牺牲部分consistency – “Strong consistency reduce availability” – Availability: 规定时间响应(e.g. < 30ms) ? Always writable – E.g. shopping cart ? Decentralize
- 36. 1. Consistent Hashing ? 传统的应用 – 如memcached, hash() mod n – Linear hashing ? 问题 – 增删节点，节点失败引起所有数据重新 分配 ? Consistent hash如何解决这个问题？
- 37. 1. Consistent Hashing * Image source: http://alpha.mixi.co.jp/blog/?p=158
- 38. 如何确保always writable ? 传统思路 – 双写？ – 如何处理版本冲突，不一致？
- 39. 2. Quorum NRW ? NRW – N: # of replicas – R: min # of successful reads – W: min # of successful write ? 只需 W + R > N
- 40. 场景 ? 典型实现：N=3, R=2, W = 2 ? 几种特殊情况 ? W = 1, R = N, 场景？ ? R = 1, W = N , 场景？ ? W = Q, R = Q where Q = N / 2 + 1
- 41. ? 如果N中的1台发生故障，Dynamo立 即写入到preference list中下一台，确 保永远可写入 ? 问题：版本不一致 ? 通常解决方案：timestamp，缺点？ – Shopping cart
- 42. 3. Vector clock ? Vector clock – 一个记录(node, counter)的列表 – 用来记录版本历史 * Image source: http://www.slideshare.net/takemaru/kai-an-open-source-implementation-of-amazons-dynamo-472179
- 43. Reconciliation, Merge version ? 如何处理(A:3,B:2,C1)？ – Business logic specific reconciliation – Timestamp – High performance read engine ? R = 1, W = N ? 越变越长？Threshold=10
- 44. 如果节点临时故障 ? 典型方案：Heart-beat, ping ? Ping如何处理无中心，多节点？ ? 如何保证SLA? –300ms没响应则认为对方失败 ? 更好的方案？
- 45. gossip
- 46. gossip * Image source: http://www.slideshare.net/Eweaver/cassandra-presentation-at-nosql
- 48. 由于存在故障因素 如何检查数据的一致性 ? Merkle tree
- 49. 4. Virtual Node ? Consistent hashing, 每个节点选一个落 点，缺点？
- 50. 增删节点怎么办 ? 传统分片的解决方法：手工迁移数据 ? Dynamo: replication on vnode
- 51. IDC failure ? Preference list ? N nodes must in different data center
- 52. 程序如何组织上述一切 ? Node has 3 main component – Request coordination – Membership – Failure detection
- 53. Client driven vs. server driven ? Coordinator – Choose N nodes by using consistent hashing – Forwards a request to N nodes – Waits responses for R or W nodes, or timeout – Check replica version if get – Send a response to client
- 54. Dynamo impl. ? Kai, in Erlang ? E2-dynamo, in Erlang ? Sina DynamoD, in C –N=3 – Merkle tree based on commit log – Virtual node mapping saved in db – Storage based on memcachedb
- 55. ? 已经学习了4种分布式设计思想 –Consistent hashing –Quorum –Vector clock –Virtual node
- 56. ? 只是分布式理论冰山一角 ? 但已经够我们使用在很多场合 ? 实战一下？
- 57. 分布式Socket Server 可借鉴的思想 ? 节点资源分布 ? 假定5个节点采用取模分布, hash() mod n ? 某台发生故障，传统解决解决方法 – 马上找一个替换机启动 – 将配置文件节点数改成4，重启 – 都需影响服务30分钟以上
- 58. 应用更多分布式设计 ? 1. consistent hashing ? 2. 临时故障？Gossip ? 3. 临时故障时候负载不够均匀？vnode
- 59. Hinted handoff ? 失败的节点又回来了，怎么办？ ? Node 2 back, but user still on Node1 ? Node 1 transfer handoff user session to Node2
- 60. 其他话题？
- 61. Bigtable
- 62. Bigtable ? 相比Dynamo, Bigtable是贵族式的 –GFS vs. bdb/mysql –Chubby vs. consistent hashing ? Dynamo更具有普遍借鉴价值
- 63. PNUTS
- 64. PNUTS
- 65. 进阶指南-了解源码 ? 如果关注上层分布式策略，可看 – Cassandra (= Dynamo + Bigtable) ? 关注底层key/value storage，可看 – Berkeley db – Tokyo cabinet
- 66. Language ? 实现分布式系统的合适语言？ ? Java, Erlang, C/C++ – Java, 实现复杂上层模型的最佳语言 – Erlang, 实现高并发模型的最佳语言 – C++, 实现关注底层高性能key value存储。
- 67. Q&A Thanks you! ? Tim Yang: http://timyang.net/ ? Twitter: xmpp