一个速度快内存占用小的一致性哈希算法

一致性哈希最早由 MIT的 Karger 提出,在发表于1997年的论文 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, Karger et al 和合作者们提出了一致性哈希的概念(consistent hash),用来解决分布式Cache的问题。这篇论文中提出在动态变化的Cache环境中,哈希算法应该满足的4个适应条件::Balance(均衡)、Monotonicity(单调性)、Spread(分散性)、Load(负载)。

在分布式缓存系统中使用一致性哈希算法时,某个节点的添加和移除不会重新分配全部的缓存,而只会影响小部分的缓存系统,如果均衡性做的好的话,当添加一个节点时,会均匀地从其它节点移一部分缓存到新的节点上;当删除一个节点的时候,这个节点上的缓存会均匀地分配到其它活着的节点上。

一致性哈希缓存还被扩展到分布式存储系统上。数据被分成一组Shard,每个Shard由一个节点管理,当需要扩容时,我们可以添加新的节点,然后将其它Shard的一部分数据移动到这个节点上。比如我们有10个Shard的分布式存储系统,当前存储了120个数据,每个Shard存储了12个数据。当扩容成12个Shard时,我们从每个Shard上拿走2个数据,存入到新的两个Shard上,这样每个Shard都存储了10个数据,而整个过程中我们只移动了20/120=1/6的数据。

Karger 一致性哈希算法将每个节点(bucket)关联一个圆环上的一些随机点,对于一个键值,将其映射到圆环中的一个点上,然后按照顺时针方向找到第一个关联bucket的点,将值放入到这个bucke中。因此你需要存储一组bucket和它们的关联点,当bucket以及每个bucket的关联点很多的时候,你就需要多一点的内存来记录它。这个你经常在网上看到的介绍一致性哈希的算法(有些文章将节点均匀地分布在环上,比如节点1节点2节点3节点4节点1节点2节点3节点4……, 这是不对的,在这种情况下节点2挂掉后它上面的缓存全部转移给节点3了)。

其它的一致性算法还有Rendezvous hashing, 计算一个key应该放入到哪个bucket时,它使用哈希函数h(key,bucket)计算每个候选bucket的值,然后返回值最大的bucket。buckets比较多的时候耗时也较长,有人也提出了一些改进的方法,比如将bucket组织成tree的结构,但是在reblance的时候花费时间又长了。

Java程序员熟悉的Memcached的客户端Spymemcached、Xmemcached以及Folsom都提供了Ketama算法。其实Ketama算法最早于2007年用c 实现(libketama),很多其它语言也实现了相同的算法,它是基于Karger 一致性哈希算法实现:

  • 建立一组服务器的列表 (如: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
  • 为每个服务器节点计算一二百个哈希值
  • 从概念上讲,这些数值被放入一个环上(continuum). (想象一个刻度为 0 到 2^32的时钟,这个时钟上就会散落着一些数字)
  • 每一个数字关联一个服务器,所以服务器出现在这个环上的一些点上,它们是哈希分布的
  • 为了找个一个Key应该放入哪个服务器,先哈希你的key,得到一个无符号整数, 沿着圆环找到和它相邻的最大的数,这个数对应的服务器就是被选择的服务器
  • 对于靠近 2^32的 key, 因为没有超过它的数字点,按照圆环的原理,选择圆环中的第一个服务器。

以上两种算法可以处理节点增加和移除的情况。对于分布式存储系统,当一个节点失效时,我们并不期望它被移除,而是使用备份节点替换它,或者将它恢复起来,因为我们不期望丢掉它上面的数据。对于这种情况(节点可以扩容,但是不会移除节点),Google的 John Lamping, Eric Veach提供一个高效的几乎不占用持久内存的算法: Jump Consistent Hash

阅读全文

[转]各大互联网公司架构演进之路汇总

原文地址:各大互联网公司架构演进之路汇总 by HollisChuang
请转载时务必保留文章的上述原始出处。

Web


支付宝和蚂蚁花呗的技术架构及实践
支付宝的高可用与容灾架构演进
聚划算架构演进和系统优化 (视频+PPT)
淘宝交易系统演进之路 (专访)
淘宝数据魔方技术架构解析
淘宝技术发展历程和架构经验分享(视频+PPT)(2.3日更新)
高德——快速转型时期的稳定性架构实践(视频+PPT)(2.3日更新)
秒杀系统架构分析与实战
腾讯社区搜索架构演进(视频+PPT)
京东峰值系统设计
京东咚咚架构演进
新浪微博平台架构
微博图床架构揭秘
微博推荐架构的演进
当当网系统分级与海量信息动态发布实践
当当网架构演进及规划实现(视频+PPT)
LinkedIn架构这十年
Facebook’s software architecture(英文)
从0到100——知乎架构变迁史
豆瓣的基础架构
搜狗搜索广告检索系统-弹性架构演进之路(视频+PPT)
小米网抢购系统开发实践
小米抢购限流峰值系统「大秒」架构解密
海尔电商峰值系统架构设计最佳实践
唯品会峰值系统架构演变
1号店电商峰值与流式计算
蘑菇街如何在双11中创造99.99%的可用性
麦包包峰值架构实践
苏宁易购:商品详情系统架构设计
携程的技术演进之路
篱笆网技术架构性能演进(视频+PPT)
从技术细节看美团的架构(1.26日更新)
美团云的网络架构演进之路(2.3日更新)
百度开放云大数据技术演进历程(视频+PPT)(2.3日更新)
途牛供应链系统的架构演进(视频+PPT)(2.3日更新)
Airbnb架构要点分享(2.3日更新)
12306核心模型设计思路和架构设计(2.20日更新)

无线


阿里无线技术架构演进
支付宝钱包客户端技术架构(2.3日更新)
手机淘宝构架演化实践
手淘技术架构演进细节
手机淘宝移动端接入网关基础架构演进之路
微信后台系统的演进之路
微信红包的架构设计简介
微信Android客户端架构演进之路
Android QQ音乐架构演进(视频+PPT)
快的打车架构实践
Uber 四年时间增长近 40 倍,背后架构揭秘
Uber容错设计与多机房容灾方案
大众点评移动应用的架构演进(视频+PPT)
饿了么移动APP的架构演进

其他


魅族实时消息推送架构
魅族云端同步的架构实践和协议细节



欢迎补充!~

Ignite vs Hazelcast

内存数据网格HazelcastIgnite是大家非常熟悉的两种分布式内存数据网格工具。

Hazelcast 是一款基于 Java的内存数据网格,它的名称和公司的名称相同。hazelcast支持分布式队列,集合,map,线程池,锁,支持事务处理,分布式的监听和事件,支持动态增加集群节点,动态备份数据,动态failover等。

关于Apache Ignite 的中文介绍可以参考李玉珏写的Apache Ignite(一):简介以及和Coherence、Gemfire、Redis等的比较等系列文章。Ignite来源于尼基塔·伊万诺夫于2007年创建的GridGain系统公司开发的GridGain软件,2015年1月,GridGain通过Apache 2.0许可进入Apache的孵化器进行孵化,很快就于8月25日毕业并且成为Apache的顶级项目,9月28日即发布了1.4.0版,2016年1月初发布了1.5.0版,迭代速度很快。

两个产品背后的公司Hazelcast和GridGain都有风投的背影。所以产品在开源免费的基础上还会提供商业版的支持。

我没有在实际产品中使用过这两款产品,仅仅关注过这一类的产品,所以并不完全了解它们的详细特性,但是最近的一些有趣的争论引起了我的兴趣,特地跟踪了多个帖子,弄清楚了争论的来龙去脉,特地整理了一下,也算作为我的性能系列的文章的一部分吧。

最近的事件是这两个产品背后的公司进行了激烈的性能之争。

起因是GridGain发布了一篇性能报告:GridGain vs. Hazelcast Benchmarks, 它比较了最新的GridGain Community Edition 1.5.0 和 最新的Hazelcast 3.6-EA2的性能,测试数据显示Ignite的性能要好于Hazelcast。相关的测试代码可以参照yardstick-ignite yardstick-hazelcast

进一步GridGain还到Hazelcast的用户讨论组中踢馆子,他们把测试结果和代码发布在Hazelcast的邮件列表中,请Hazelcast的人review和提意见。嚣张啊!
Hazelcast的CEO Luck把这个帖子从邮件列表中删除了,并说:

我们认为你在我的地盘上发布这样的性能数据是不合适的。 我们将删除这个帖子,请发布在你的地盘上。

当然,这也不是GridGain第一次踢馆子,在2015初Apache孵化器Ignite项目的导师Konstantin Boudnik就到Tachyon 的邮件列表中比较这两个项目的缓存特性差异,也被认为是营销惨遭删帖。

阅读全文

uriDB网站的可扩展的技术栈

背景

uriDB本身不生产干货,uriDB技术流网站只是大自然的搬运工。
Hacker News诞生依赖,已经有多个中文技术头条的网站了,比如开发者头条极客头条,为什么还要做这样一个雷同的头条网站呢?

有两个原因:
一是我想做一个分类头条的网站,按照技术领域对文章进行分类,这样只对前端感兴趣的同学可以只跟踪最新的前端文章。 同时uriDB只会筛选最新的技术干货,不会将问答,闲聊等技术层次低的文章收录。
二是这么多年来,我涉及的领域包括后台,大数据,前端和移动端的技术也是我感兴趣的领域。心中那份对技术的持久的热情,促使我将多年的技术积累以某种具体的形式呈现出来,籍此展示并能持久的进行技术架构的演化。

因此,uriDB技术流网站也就孵化出来了。虽然目前的访问量比较少,但是看的用户数和访问量在逐步的提升,也是一件令人欣慰的事。至少,这个网站收集的干货也为那些执着学习的同学带来些许的便利和技能提升。

与其说uriDB类似Hacker News网站, 还不说说它类似今日头条, 只不是今日头条上全是新闻类的内容,而uriDB上全是技术干货。今日头条会将目标网站上的内容抓去过来进行重新排版,更加适合阅读。我也抓去了目标文章的内容,却没有进行重新排版显示,主要是考虑到了版权的问题,还是老老实实的做Hacker News一样的转发。

这个网站是2015年国庆节期间开始启动的,也是作为我的side project在维护。我会时不时的将我的新的想法,技术灵感应用于这个网站上。

阅读全文

雪球在股市风暴下的高可用架构改造分享

本文根据唐福林老师在“高可用架构”微信群所做的《股市风暴下的雪球架构改造经验分享》整理而成,转发请注明来自微信公众号ArchNotes。

唐福林,雪球首席架构师,负责雪球业务快速增长应对及服务性能与稳定架构优化工作。毕业于北京师范大学,硕士学位。之前曾任微博平台资深架构师,微博技术委员会成员。长期关注并从事互联网服务后端性能及稳定性架构优化工作。

阅读全文

大型网站系统架构的演化

原文: 大型网站系统架构的演化, 作者:李平

一个成熟的大型网站(如淘宝、京东等)的系统架构并不是开始设计就具备完整的高性能、高可用、安全等特性,它总是随着用户量的增加,业务功能的扩展逐渐演变完善的,在这个过程中,开发模式、技术架构、设计思想也发生了很大的变化,就连技术人员也从几个人发展到一个部门甚至一条产品线。所以成熟的系统架构是随业务扩展而完善出来的,并不是一蹴而就;不同业务特征的系统,会有各自的侧重点,例如淘宝,要解决海量的商品信息的搜索、下单、支付,例如腾讯,要解决数亿的用户实时消息传输,百度它要处理海量的搜索请求,他们都有各自的业务特性,系统架构也有所不同。尽管如此我们也可以从这些不同的网站背景下,找出其中共用的技术,这些技术和手段可以广泛运行在大型网站系统的架构中,下面就通过介绍大型网站系统的演化过程,来认识这些技术和手段。

阅读全文

LinkedIn架构这十年

原文: A Brief History of Scaling LinkedIn

Josh Clemm是LinkedIn的高级工程经理,自2011年加入LinkedIn。他最近(2015/07/20)写了一篇文章,介绍了LinkedIn针对用户规模急速扩大带来的架构方面的变革。
文章有点像子柳写的淘宝技术这十年

2003年是LinkedIn元年,公司成立的目标是连接你的个人人脉以获得更好的的工作机会。上线第一周才有2700个会员注册,时光飞梭,LinkedIn的产品、会员数量、服务器负载都极大的增长了。
今天,LinkedIn全球用户已经超过3.5亿。我们每秒有数十万个页面被访问,移动端流量已占到50%以上 (mobile moment)。所有这些请求都从后台获取数据,而我们的后台系统可以处理每秒上百万次查询。

问题来了: 所有这些是怎么做到的呢?

阅读全文

架构学习资料整理(2013)

地瓜哥2013攒的架构资料:分享D瓜哥最近攒的资料(架构方面)

以前见过零零散散地介绍一些知名网站架构的分析文章。最近D瓜哥也想研究一下各大知名网站的架构。所以,就搜集了一下这方面资料。限于时间问题,这篇文章分享的文章并没有都看完,所以不保证所有文章的质量。另外,如果有朋友发现更好的文章,欢迎留言告知。再补充进来。

阅读全文

CQRS 和 Event sourcing

CQRS全称为Command Query Responsibility Segregation。 CQRS并不是一个完整的架构,而是一个小的模式。这个模式首先由Greg Young 和 Udi Dahan提出,Martin Flower有一篇文章专门介绍这个模式,微软也有一个专门教程介绍CQRS。
CQRS描述起来很简单,就是命令和查询职责分离。

阅读全文