Twitter Snowflake

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
简介:

这是一篇两年前 Twitter 开发团队写的文章,今天挖出来研究了一下。原文地址 http://engineering.twitter.com/2010/06/announcing-snowflake.html

Twitter 早期用 MySQL 存储数据,随着用户的增长,单一的 MySQL 实例没法承受海量的数据,开发团队就开始用 Cassandra 和 sharded MySQL 替代原有的系统。然而和 MySQL 不同的是,Cassandra 没有内置为每一条数据生成唯一 ID 的功能,因为在一个分布式环境下,很难有完美的 ID 生成方案。

对于 Twitter 而言,这样的 ID 生成方案要满足两个基本的要求,一是每秒能生成几十万条 ID 用于标识不同的 tweet;二是这些 ID 应该可以有个大致的顺序,也就是说发布时间相近的两条 tweet,它们的 ID 也应当相近,这样才能方便各种客户端对 tweet 进行排序。

第一个要求意味着 ID 生成要以一种非协作的(uncoordinated)的方式进行,例如不能有一个全局的原子变量。

第二个要求使得 tweet 按 ID 排序后满足 k-sorted 条件。如果序列 A 要满足 k-sorted,当且仅当对于任意的 p, q,如果 1 <= p <= q - k (1 <= p <= q <= n),则有 A[p] <= A[q]。换句话说,如果元素 p 排在 q 前面,且相差至少 k 个位置,那么 p 必然小于或等于 q。如果 tweet 序列满足这个条件,要获取第 r 条 tweet 之后的消息,只要从第 r - k 条开始查找即可。

Twitter 解决这两个问题的方案非常简单高效:每一个 ID 都是 64 位数字,由时间戳、节点号和序列编号组成。其中序列编号是每个节点本地生成的序号,而节点号则由 ZooKeeper 维护。

具体的参数可以在这个 IdWorker.scala 中看到。序列编号有 12 位,意味着每个节点在每毫秒可以产生 4096 个 ID。节点号在源码中被分成两部分,数据中心的 ID 和节点 ID,各自占 5 位。时间戳则是记录了从 1288834974657 (Thu, 04 Nov 2010 01:42:54 GMT) 这一时刻到当前时间所经过的毫秒数,占 41 位(还有一位是符号位,永远为 0)。

相关实践学习
基于CentOS快速搭建LAMP环境
本教程介绍如何搭建LAMP环境,其中LAMP分别代表Linux、Apache、MySQL和PHP。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
7月前
Twitter 应用的优缺点分析
Twitter 应用的优缺点分析
148 0
|
机器学习/深度学习 算法 搜索推荐
Twitter 算法开源究竟会是什么样的?
本文最初发布于 Travis Fischer 的个人博客。
341 0
Twitter 算法开源究竟会是什么样的?
|
搜索推荐 开发工具
完全基于开源软件构建的 Twitter
Twitter 宣布其整个系统基于开源软件系统构建,同时该公司也贡献很多开源的软件,并为这些开源软件专门制作一个汇集页面 http://twitter.github.io/
135 0
完全基于开源软件构建的 Twitter
|
算法 前端开发 JavaScript
分布式唯一ID系列(5)——Twitter的雪法算法Snowflake适合做分布式ID吗
写到这里,分布式Id算是写到最后一篇了,在这一篇里,我会讲到目前网上最适合分布式Id的方法,什么方法呢,请您往下看: 介绍Snowflake算法 SnowFlake算法是国际大公司Twitter的采用的一种生成分布式自增id的策略,这个算法产生的分布式id是足够我们我们中小公司在日常里面的使用了。
2423 0
|
分布式数据库 存储 关系型数据库
Google BigTable到底解决什么问题?
搞架构的人,Google的论文是必看的,但好像大家都不愿意去啃英文论文。故把自己的读书笔记,加入自己的思考,分享给大家。
4585 0
|
存储 NoSQL
为什么Twitter不使用Cassandra存储Tweets(译),互联网营销
原文地址:http://highscalability.com/blog/2010/7/11/so-why-is-twitter-really-not-using-cassandra-to-store-tweets.html   当前讨论的中心是Cassandra作为NoSQL的主要产品已经被剥去了华丽的衣裳。
1658 0
|
消息中间件 Java 开发工具