`
yjl49
  • 浏览: 113221 次
社区版块
存档分类
最新评论

Instagram 的ID生成策略[翻译]

阅读更多

项目中遇到一个ID生成策略的需求:需要在系统中为每个用户分配一个ID用作以后的用户标示。这个需求应该是非常普遍的,对于使用人数较少的系统而言不会 是一个问题,不过对于向用户众多的互联网系统来讲这不是一个简单的问题。下面是翻译的最近最火爆的Instagram应用开发者的一篇文章,看看他们一个 十几个人的公司是怎么解决这个问题的:

 

以下为简单翻译(不清楚的地方请参照原文):

                                                     Instagram 的分片和IDs

       每秒接收25副图片、90次"like"分享,Instagram存储了大量的数据。为了确保所有重要的数据都存入到了内存并且尽快地对于用户可用,我们将数据进行了分片---换句话说就是将数据存到很多小分片上,每个分片都持有数据的一部分。

       我们使用Django 和PostgreSQL 作为后台的数据库系统。在决定对数据进行分片后我们遇到的第一个问题就是是否仍旧将PostgreSQL作为我们主要的数据存储系统,还是换个其他的。我 们评估了一些不同的NoSQL解决方案,但最终决定:最符合我们需求的是将数据分片到由多个PostgreSQL组成的服务器组上。

       在将数据写入到PostgreSQL服务器组之前,我们必须先解决如何为数据库中每一份数据指定相应的唯一标示(例如每一副发布在我们系统上的图片)。典 型的解决方案在单个数据库中还行得通---直接使用数据库的自增来分配唯一标示;但要将数据同时插入到多个数据库时这种方案就不行了。这篇文章接下来的内 容就指明了我们是如何对付这个问题的。

       在开始之前我们列出了几个系统中必须的几个功能:

       1.生成的ID必须可以按时间排序(这样一来,一组图片可以不用再查找其他相关信息就能排序)

       2.ID最好是64bit的(为了索引更小且方便存储在像Redis这样的系统中)

       3.新系统造成的不确定性(or改动)越小越好---我们之所以能用这么少的工程师搞定Instagram,很大的原因就在于选择简单、易懂、可靠的解决方案。

       现存的解决方案

       对于ID生成问题现在已经有很多现存的方案,以下为几个我们可以考虑的:

 

       在web应用(web application)中生成ID

       这种方式将ID生成的问题全部交给你的应用程序,而不是数据库来解决。

       例如:MongoDB 的ObjectID 一共有12bytes长,并且将编码后的时间戳作为首要的组件。另一个常用的就是UUID。

       优点:

             1.每个应用程序线程都独立地生成ID,减少了故障和不一致。

             2.如果你使用时间戳作为ID的首要组件,ID就是可以按时间排序的。

       缺点:

             1.为了保证唯一性的可靠,一般需要更多的存储空间(96bit或更多)。

             2.有些UUID完全是随机的,不能自然排序。

 

      使用专门的服务生成ID

      例如:Twitter的 Snowflake---一个使用Apache ZooKeeper来整合所有节点然后生成64bit唯一ID的简洁的服务。

      优点:

            1.Snowflake生成的ID只有64位,只有UUID的一半大小。

            2.可以使用时间戳作为首要组件,可排序。

            3.分布式的系统,某个节点down掉也没事。

      缺点:

            1.会给整体架构引入额外的复杂性,和一些不确定内容(ZooKeeper, Snowflake servers)

 

      数据库"票务"服务器

      使用数据库的自增功能来保证唯一性。Flickr 使用了这种方法---但使用了两台数据库服务器(一台生成奇数,一台生成偶数)来防止单点当机。

      优点:

            1.数据库非常熟悉,有很多可预见的因素。

      缺点:

            1.会最终成为一个写瓶颈(根据Flickr的报告,即使在大规模并发的情况下这也不会成为一个问题)

            2.对于管理员而言额外多了一对机器。

            3.如果使用单个数据库则容易出现单点故障,使用多个则无法保证可以按时间排序。

 

      以上几种方法中Twitter的离我们想要的最为接近,但是运行一个专门的ID服务所造成的额外复杂性却是一个负面因素。

     替代地,我们选择了一个概念上与之相似的方法,并将它整合到了PostgreSQL中。

 

     我们的解决方案

     我们的分片系统由上千个逻辑分片组成,而这些逻辑分片在代码中与非常少的物理分片进行了映射。使用这种方法我们可以从很少的数据库服务器开始,最终转到更 多的服务器:只需要将一些逻辑片从一台服务器移到另一台,中间不需要重新打包任何数据。为了易于编码和管理我们使用Postgres的schema功能来 实现。

Schemas(不是SQL 中的表的schema) 是逻辑上的一组功能。每个Postgres 数据库可以拥有多个schema,每个schema中可以有一到多个表;表名在schema内是唯一的,在DB中可以不唯一;默认的,数据库将所有的信息 都放在一个叫"public"的schema中。

     在我们的系统中每个逻辑分片都是一个schema,每个被分片的表都存在于每个schema中。我们使用PL/PGSQL(Postgres内置的编程语言)和Postgers自身的自增函数,为每个分片中的每张表都赋予了生成ID功能。

     每个ID由以下部分组成:

     1.41bits 存储毫秒格式的时间。

     2.13bits 表示逻辑分片ID。

     3.10bits 存储自增序列值对1024取模后的结果,这意味着每个分片每秒可以产生1024个ID。

 

     下面进行一个测试:假设现在是2011-09-09 下午05:00,我们的业务从2011-01-01开始运行。从开始到现在已经运行了1387263000毫秒,开始构造我们的ID,我们使用左移位的方式填充左面的41位:

      id = 1387263000 << (64-41)

     接着,我们获取即将插入的这份数据所在的分片ID,假设我们按用户ID来进行分片,系统中一共有2000个逻辑分片;如果我们的用户ID是31341,那么我们的分片ID就是31341 % 2000 -> 1341 。我们使用这个值来填充接下来的13位:

    id |= 1341 << (64-41-13)

     最后我们使用任意生成的自增序列值(单个schema单张表内唯一)来填充其余的位数。假设我们要插入的那张表已经生成了5000个ID了,下一个值就是5001,我们对其使用1024取模(这样生成的数据就是10bits了),然后加上去:

     id |= (5001 % 1024)

    现在我们已经获取到了想要的ID,接下来可以使用return关键字作为insert过程的一部分返回给应用程序了。

    下面是以上整个过程的PL/PGSQL代码实现(例如:在schema实例5中):

CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$
DECLARE
    our_epoch bigint := 1314220021721;
    seq_id bigint;
    now_millis bigint;
    shard_id int := 5;
BEGIN
    SELECT nextval('insta5.table_id_seq') %% 1024 INTO seq_id;

    SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;
    result := (now_millis - our_epoch) << 23;
    result := result | (shard_id << 10);
    result := result | (seq_id);
END;
$$ LANGUAGE PLPGSQL;

 下面是创建数据库表:

 

CREATE TABLE insta5.our_table (
    "id" bigint NOT NULL DEFAULT insta5.next_id(),
    ...rest of table schema...
)

 

就这样了!主键在我们的应用里面是唯一的(作为捎带的私货,为了易于映射含有分片ID)。我们已经将这个方法应用到了产品中,目前看来效果挺令人满意。有兴趣帮助我们解决这些问题?我们的联系方式
      Mike Krieger, co-founder

 

分享到:
评论

相关推荐

    instagram-fonts-generator-script-download:instagram字体生成器源代码,instagram字体生成器html代码,instagram字体生成器javascript代码,instagram字体生成器代码,instagram字体生成器,时尚的文本生成器源,时尚的文本生成器javascript代码请参见此处的演示clcik >>>>>>>>> >>>>>>-html source download

    instagram的字体生成器脚本下载 instagram字体生成器源代码,instagram字体生成器html代码,instagram字体生成器javascript代码,instagram字体生成器代码,instagram字体生成器,时尚的文本生成器源,时尚的文本...

    新媒体Instagram营销策略及发展模式分析.ppt

    Instagram的发展模式主要基于社交媒体的互动性和用户生成内容。它不仅提供了用户分享生活的平台,还通过滤镜和设计元素吸引用户创造独特的内容。这种内容驱动的社区为品牌和商家提供了营销机会,他们可以通过赞助...

    前端开源库-passport-instagram

    前端开源库-passport-instagramPassport Instagram,用于Passport的Instagram身份验证策略。

    ios_Instagram客户端

    在iOS开发领域,Instagram客户端的高仿项目是一个热门的学习主题,尤其对于初学者而言,它提供了深入了解移动应用设计和实现的宝贵机会。本教程将围绕iOS平台上的Instagram客户端仿制展开,通过学习,开发者可以提升...

    类似instagram图片分享社区数据库设计

    综上所述,设计一个类似Instagram的图片分享社区数据库是一项涉及多方面技术和策略的任务,从基础架构到性能优化,再到用户体验,每个环节都需要精心设计和实施。通过“camera-jiegou.sql”和“camera-all.sql”这两...

    Instagram图片索引InstaIndex.zip

    InstaIndex 可以直观地索引你在 Instagram 的图片。InstaIndex 是一个简单的...创一个 Instagram 应用,生成一个 auth token在 http://www.clarifai.com/api 创建一个 Algolia 应用和索引 标签:InstaIndex

    Instagram-Helper,.zip

    为了开始使用`Instagram-Helper`,开发者需要配置他们的Instagram开发者账户,创建一个应用并获取相应的客户端ID和秘密。然后,他们需要按照项目文档的指示在AndroidManifest.xml中配置必要的权限,并在代码中初始化...

    instagram.apk

    instagram软件 apk

    Instagram图片下载 V1.0 绿色版

    Instagram图片下载V1.0绿色版是一款专为Instagram平台设计的工具,旨在帮助用户方便地获取Instagram上的图片资源。在互联网日益发达的今天,社交媒体平台如Instagram成为了分享和浏览图片的重要场所,但平台通常对...

    instagram克隆-源码

    13. **性能优化**:为了提高用户体验,项目可能实施了各种性能优化策略,如懒加载图片、代码分割、CDN内容分发网络等。 14. **错误跟踪**:通过引入如Sentry或LogRocket等工具,开发者可以追踪并解决线上应用出现的...

    Python爬虫爬取 Instagram 博主照片视频-Instagram_crawler.zip

    总的来说,Instagram_crawler项目涵盖了Python网络爬虫开发中的多个重要方面,包括HTTP请求、HTML解析、模拟用户交互、数据存储以及合规爬取策略。通过学习和实践这个项目,开发者可以提升自己的Web抓取技能,更好地...

    Laravel开发-laravel-instagram-api

    请注意,你需要替换上述代码中的四个占位符为实际的Instagram API凭据,包括Client ID、Client Secret、Access Token和Access Token Secret。 为了方便在控制器或其他地方使用,我们还需要在`...

    instagram-user-id:获取instagram中任何用户的用户ID

    instagram的用户ID 获取instagram中任何用户的用户ID用法 python main.py $USERNAME要求 pip install -r requirements.txtsudo apt-get install nodejs npmcd web-version && npm install && nodejs server.js示例-...

    2019年Instagram调查报告(英文)-Instagram

    2019年Instagram调查报告(英文)-Instagram,2019年Instagram调查报告(英文)-Instagram

    549654407452296Instagram.apk

    549654407452296Instagram.apk

    Instagram 6.12.2

    作者 Instagram 大小 10.29MB 描述 Instagram,iPhone上最著名的照片抓拍、编辑工具之一。它与众不同,为用户创建了一个完整的社交网络。现在它终于抵达了安卓平台,让所有安卓手机用户也能体验这款软件带来的...

    instagram mac版

    Instagram Mac版是一款专为苹果Mac用户设计的应用程序,允许用户在桌面环境中享受Instagram的功能。这款应用将社交媒体体验扩展到了电脑平台,让用户可以更方便地浏览、编辑和分享照片与视频,同时保持与移动设备上...

    Laravel开发-instagram

    1. **设置OAuth授权**:Instagram API采用OAuth 2.0进行身份验证,因此你需要在Instagram开发者平台上注册一个应用,并获取Client ID和Client Secret。这些信息将用于引导用户授权你的应用访问他们的Instagram账户。...

    Scaling-Instagram.pdf

    ### 分布式系统下的Instagram扩展策略 #### 一、引言与背景介绍 在《Scaling Instagram》这份由Mike Krieger(Instagram联合创始人)于2012年AirBnB技术讲座上分享的演讲中,他详细介绍了Instagram是如何从一个...

Global site tag (gtag.js) - Google Analytics