• Feeds

  • Archive for the ‘架构’ Category


    微博分布式存储作业实现方法

    可能通过「高可用架构」听说过在微博的系统中,单张 MySQL 在线业务表 60 亿条数据的场景。很多关注互联网架构的工程师也非常关注如何如何设计类似系统。下面是一道微博新兵训练营的分布式存储课堂练习,要设计合格才能上岗。

    关注为什么超长列表数据的翻页技术实现复杂的读者请直接参看文末链接。

    feeds2

    考虑到网上有很多架构师也在讨论,补充题目一些说明如下。

    1、访问场景

    由于上面题目的应用场景,用户一般情况下,主要查看用户查看自己收到的最新的微博,以及某个特定用户 profile 的所有微博。

    • 收到的微博,考虑微博以拉为主的模式,则需要访问关注用户最近 n 条最新的微博。
    • 用户 profile,需要访问用户历史上所有发表的微博,而且支持分页查看,可以直接跳转到某一页或者某个时间段,因此需要适当考虑分页的效率(可参考扩展阅读)。

    访问特征

    • 从上面描述以及社交网络的用户访问特点来看,用户大部分情况( > 90% )是访问最近 7 天的数据。

    不需要考虑的点

    • 此题主要是存储层的设计,因此不需要考虑缓存如何设计。
    • 由于微博是异步写入的,在某种程度可以起到错峰作用,所以作业暂时不需要考虑写入的峰值。
    • 不需要考虑 id 如何产生,假定已经有发号服务。
    • 不需要考虑用户收到的微博怎么聚合,那个是更上层服务层的职责。

    2、设计需要考虑的点

    Scale-out 扩展性

    • 将数据拆分到多个独立的单元存储
    • 可以在适当时机进一步拆分,拆分时候需要继续提供在线访问
    • 存储在廉价硬件上,考虑到数据规模比较大,需要适当考虑方案的整体成本,因此不要假定默认全部使用 SSD 存储。

    Cost 成本

    • 不同访问级别的数据存储在不同访问速度(成本)的硬件上。

    High availability 高可用,以及 Reliability 可靠性 – 复制

    在当前场景下,主要通过 MySQL replication 来解决可用性、以及分担读的请求。

    3、Sharding 策略

    Shard 常用策略

    range based:根据用户 uid 来分布,相邻 uid 的数据保存在一起。
    hash based:根据某个 hash 函数,将一个用户 uid 的数据保存在指定的分片。

    Re-Sharding 拆分设计
    当数据持续增长,原先存储的数据(或者访问量)超过当前节点的容量上限,则需要对节点进行进一步拆分。

    feeds3

    如何确定shard数量

    db buffer > hot data

    容量规划

    • 预规划: 容纳未来一段时间的数据
    • 2 的指数倍: shard 数量变更简单

    Tradeoff

    • 分片多:影响 IO 效率;
    • 分片少:扩容频繁、复杂

    4、部分投稿案例

    案例一:使用 user id range 作为分片

    case1

    案例二:使用user id hash作为分片

    case2

     

    方案三 (via 张亮)
    历史数据:
    1. 每半年根据日期分库,如:2015.01-2015.06为一个库。每天增加1亿数据,半年180亿,约为0.72T数据,可以保留在1T的磁盘中。
    2. 根据 uid 取模分库(表),便于查询和分散数据。

    当前 n 日数据:
    1. 暂定n为10,存储10亿数据。
    2. 根据uid + 权重的hash算法分库。权重可以根据每个uid的微博id数量,粉丝数等指标离线计算。

    hash算法需保证:
    1. 同一uid需落在一个库。
    2. 权重接近的用户尽量均匀的落在不同库。
    3. 为了应对突然发生的事件导致访问量激增,需要考虑2级甚至3级分片,而不宜直接做re-sharding导致数据迁移。多级分片可考虑读取一个标记,放在zk中。根据标记确定分片的hash算法加入小时等维度。

    查询索引:
    1. 增加发帖索引字段,记录每个用户的每个帖子的索引。
    2. 增加发帖总数统计表,以用户为维度,每个用户发一次贴则发帖总数++。
    3. 增加二级索引表,记录每个用户,每次分片库的发帖索引。如:uid 1的用户,在2015年第一帖是该用户发帖的总数的第10贴,2015年最后一贴是该用户发帖总数的第50贴。
    4. 分页查询使用二级索引表,先查到该查哪个真实库(可能是多个),再到真实库中获取数据。

    总结:
    1. 通过灵活的运用时间维度分片,免去因uid分片数量不足导致的大规模迁移,使用外部flag灵活的控制分片策略。而且用时间维度分片更易做到冷热分离。
    分片逻辑可以灵活到,zk中记录时间段,某个时间段内,按月分,某个时间段,按年分,之类。
    2. 通过离线计算权重的方式均匀分散数据访问。权重周期性调整,对于调整权重的用户,需要重点考虑当前n日数据的数据迁移方案。但由于调整权重的用户属于少量,所以迁移应该数据变动较小。历史数据不需权重概念,无需数据迁移。
    3. 查询使用二级索引。使用修改btree结构去掉二级索引能有效减少数据量,但实现难度较大,可以在之后的局部优化中实现,对总体数据库结构影响不大。
    4. 将前n日数据和当天数据整合在一起,之前对微博的场景理解不深,以为有首屏显示这样的概念。

     

    5、扩展阅读

    关于分页:
    为什么超长列表数据的翻页技术实现复杂
    为什么超长列表数据的翻页技术实现复杂(二)

    Pinterest的Feed架构与算法

    Pinterest首页的Feed消息流,最早是按照用户的关注对象的Pin(类似微博)聚合后按时间进行排序(自然序,类似朋友圈),后来版本的feed系统放弃了自然序,而是根据一定规则及算法来设计,内部称之为Smart feed,其算法及架构根据其公开资料整理如下,值得业界做信息流产品的技术架构师参考。

    Pinterest每个用户的首页feed都是个性化内容。Pinterest系统大约1/3流量都指向feed页面,因此它是整个系统最关键的页面之一。当工程师开发新版Smart Feed时,如何达到99.99%可用性也是衡量项目是否成功的指标之一。

    Pinterest smart feed的主要算法及规则如下

    • 不同来发表来源的Pin按照不同的频次聚合。
    • 将Pin按照算法及权重有选择的去除(或延迟加载),质量较低的发表来源不必每次显示全部,系统可以有选择的决定哪些立即出现,哪些延迟显示。Pin的质量都是从当前接收用户的角度来衡量。
    • Pin排序的逻辑是最好的优先,而不是最新的优先。一些发表来源的Pin可能最新的优先,但另外一些发表来源的可能新的Pin优先级低。

    Pinterest Feed如图所示主要由以下几部分构成,最左边是数据来源,最右边是用户看到的Pinterest瀑布流。中间的三个服务介绍如下。
    pinterest-1

    Feed worker

    Feed worker职责:接收新的pin并根据接收的用户的不同赋予pin权重并保存。同一个Pin,不同的接收用户有不同的权重打分。
    新的pin主要有三个来源:关注用户,相关内容,关注关系的感兴趣内容。Worker会给每个来源的pin打分之后插入到一个pool里面,每个Pool是针对单个用户的优先队列(Priority Queue,即优先级高的内容先出)。
    由于Feed Worker按照接收用户的维度存储,因此所有的pin进入worker时候已经按照关注关系进行分发(即行内通常说的Feed推模式)。

    Feed content generator

    Feed content generator负责返回用户上次访问后新的pin。Content Generator可以返回前n条或者全部新的pin,用户获取过(即浏览过)的pin会从pool中删除。Content Generator可以将多个发表源的pin按照一定规则重新排列,但是不能改变原来的Priority Queue返回的优先顺序。即队列中高优先级的会被优先取出。

    Smart feed service

    物化视图用于保存用户上次feed列表的快照。此服务不需要对feed的重新排序,它将上次返回给用户的pin按照当时的顺序完整保存,由于它属于用户已阅读过的历史列表,读写较少,因此它可以提供更好的可用性。另外由于可以限制历史列表的长度,存储空间可控,因此可以更低成本来增加从库来提高访问的可用性。

    Feed依赖content generator来提供新的Pin,如果content generator不可用,服务可以优雅的降级,用户仍然可以获取历史的列表,返回物化存储的结果。

    Pinterest通过以上3个不同的服务,实现了对feed返回内容灵活的控制,每个服务都有自己明确的职责,达到了每个用户都具备个性化返回内容的目标。

    Feed存储

    Pinterest的feed存储需要解决以下几个需求:

    • 写入新发表的feed,由于Pinterest采用的是推模式,这个场景需要面临需要高的写入QPS,但用户能容忍一定的写入延迟。
    • 获取首页的物化feed列表,相对与写入的QPS要小很多,但是用户对请求的延迟容忍度低。
    • 删除feed。

    可以采用简单的设计方法,比如将所有的feed写入到一个存储,可以简单实现访问、更新及删除功能。在Pinterest当前的访问规模有上百T的数据以及每秒百万访问操作。经过综合评估,选择使用HBase来实现了上述需求,Pinterest业务场景需要提供非常高的读写及更新操作,HBase同时提供较高的读写及更新访问性能。

    用户发表一个新的Pin时,将Pin分发给他所有的粉丝,他的粉丝可能被shard到所有的HBase region上,因此一个分发操作可能要访问到多个region,并锁定每个region的WAL日志,然后进行更新再解锁。每次的write/delete/update操作锁定WAL非常低效,而且很快成为系统的瓶颈。更好的方法是将HBase的操作批量进行,并且可以加大HBase的吞吐能力,但另外一方面增加了访问的时延latency,如果是面向用户请求的操作,访问时延增大是不能接受的。

    为了满足不同的需求,Pinterest设计使用了双HBase集群的方法,将数据在不同的阶段写入到不同的HBase集群的方法,请参考图示。
    pinterest-3
    Zen是一个在HBase基础上提供图(Graph)存储的服务。
    SmartFeed Worker将用户发表的内容分发后通过Zen保存在HBase中,异步处理任务通过PinLater服务来调用。
    SmartFeed ContentGenerator负责返回最新的Pin,并进行评分及排序。
    当用户刷新请求自己首页的feed时,SmartFeed服务从Content Generator和物化存储的HBase归并数据返回给用户,如果生成服务请求超时,则系统仍然可以返回物化存储的数据给用户。在后台,SmartFeed将物化存储的数据从左边的存储删除。
    在实际的场景中,物化存储HBase的数据远远要比发表池的数据要少,这样请求的速度会非常快。

    Feed的高可用

    使用上述设计后,系统的可用性相当于物化存储HBase的可用性。HBase集群目前存在GC卡顿的风险,还有单点故障region迁移等问题,因此使用单一的HBase集群,可用性很难保证99.99%以上。

    为了解决这个问题,在另外一个EC2可用区启用一个备用集群,任何写入到主集群的数据将会在数百毫秒内同步到另外一个集群上。当主集群不可用时,可以从备用集群返回用户请求的数据。通过上述设计,整个系统的可用性达到99.99%以上(不包括写)。

    pinterest-2

    参考资料

    http://pingineering.tumblr.com/post/105293275179/building-a-scalable-and-available-home-feed
    https://engineering.pinterest.com/blog/building-scalable-and-available-home-feed

    《火星救援》中你应该知道的5个高可用系统故障恢复原则

    《火星救援》是最近一部受到广泛关注的片子,讲述在一次人类登陆火星的任务中,宇航员马克·沃特尼经历了一场恶劣的风暴后,与他的机组成员失联,所有人都认为他在这次任务中丧生。然而,马克却幸运地活了下来,然而他发现自己孤单地置身于异星球。面对贫乏的生命补给,马克必须用他的聪明才智和顽强的精神存活下来,并如何寻求求救的故事。

    大部分互联网系统也面临各种临时突发的故障,技术负责人及相关工程师需要及时响应故障,采取合适的手段来解决问题。因此火星救援中体现的很多原则,做法和高可用系统故障恢复是同理。

    1、故障信息的透明性原则

    martian-1
    在火星救援中,当NASA发现马克还生存时候,NASA第一时间再次举行了新闻发布会,向媒体及公众进行了交代,包括后续大部分事件如文本聊天,也是通过媒体现场直播,这是信息透明的原则。但是里面只有一点,NASA将相关信息给宇宙飞船的成员隐瞒了很长一段时间,这个是信息不透明带来后果的案例,后面面对公众时也出现了尴尬、被动包括可能需要承担职责的局面。

    互联网系统在故障发生时候,技术人员第一时间发现了故障,如果不能马上排除,则需要考虑是否将问题上报、以及将信息公示给所有用户。

    给公司上级上报故障在某种程度会对技术团队留下负面印象,给外界用户公示故障会给产品带来负面的印象及不信任。因此保证信息透明需要有一定勇气。但反过来思考,故障已经成为事实,也已经对用户使用系统造成影响,隐瞒问题会带来更多及更大的问题。技术负责人主动承认问题发生,及时通报问题以便各部门采取合适的应对及支援手段,以便能合理利用更多的资源来更早的解决问题。及时公示问题给用户(比如通过官方微博及官方网站),以便争取用户的理解及支持。

    从长远来看,所有故障都不是某个人及所在小组的责任,管理层很少会出现迁怒于人的可能,而更多的是去改进体系上及管理上的问题。因此公开故障可以帮助公司及团队更好的、更透明的去认识问题,帮助技术团队做出改进,以便将来从体系上规避类似问题。

    2、故障突发性对应的解决时限性原则

    martian-2
    火星救援中几个时间点都非常急迫。马克在火星的食品非常有限,并且可能会随时遇到不可预料的情况。尤其是当栖息舱爆炸后,全部种植的马铃薯死亡,且无法再次种植。瓦特尼只能倚靠之前收成的马铃薯生存下去,当时能让他再多活200个火星日。但是发射宇宙飞船登陆火星是一件非常庞大的系统工程,需要做好长时间的准备及周密的测试,并且存在欲速不达的可能。因此火星项目负责人需要在有限的时间内做出最佳可行的方案选择。

    故障选择也大多处于类似被动的局面,当故障发生时候,用户访问系统受到影响,需要在尽可能短的时间内恢复服务。但由于时间紧迫,负责人可能没有足够的时间来分析故障的根本原因,只能根据现象及已有经验迅速做出判断。而且根据故障问题的不同,一些恢复手段如数据重建可能需要较长的时间,一些方案可能会超过用户容忍的极限,因此需要技术负责人在短时间内做出快速解决故障的选择。

    3、故障中解决方案的技术决定性原则

    martian-3
    火星救援中,有几个场景体现了技术的决定作用。一个是中国的太阳神助推器,将宇宙飞船赫耳墨斯号推向火星,一个是航天动力学家里奇·布内尔的航行方案,可以看到,临时的技术方法在救援中起了决定作用。

    故障恢复时候也有这样的情况,大家围着主要负责人旁边一筹莫展时候,突然角落里不起眼的程序员说找出了解决方法,然后非常及时的解决了问题。故障时候仅能看到现象,很多时候还没来得及分析出根本的原因,因此技术负责人也很难当机立断提出非常确认的方案来解决问题。熟悉体系的程序员这时候可以发挥自身的能动性,小范围的去推测、尝试及验证,有有很大的机会更快的解决问题。一些故障拖很长时间,有一定程度是团队成员没有有效手段,另外一个原因也许是团队成员群体思维,全部按照主流的思想或者负责人的思路去应对及处理,如果主流方法不是合适解法,有可能会将故障时间拉长。

    还有一些公司将线上系统当成黑盒,工程师只需要将自己模块合并进去,无需关注线上运行状况。这种情况一旦出了可用性问题,大部分工程师是一筹莫展的,只能依靠少数几个精英来解决问题,通常不利于问题的迅速解决。

    4、充分利用系统预留扩展能力的原则

    martian-4
    马克与地球取得联系,是依靠1996年发射的火星探路者号(Pathfinder),并且依靠其预留的通讯接口,让实时文本聊天成为可能。火星救援最后的决定作用是预留的MAV,通过下次任务战神四号预留的MAV上升载具起飞到太空轨道,然后对接上宇宙飞船赫耳墨斯号返回地球。这让马克在食品用完之前返回地球成为了可能。

    我们在开发高可用系统时,大部分服务模块的代码都留了一个开关,可以在适当时候开启或者关闭一段代码。虽然在99.9%的场景下这个开关不起作用,但在灾难事故发生时候,可能一个小小的开关犹如发生故障时玻璃窗旁边的救生锤,可以决定整个事故的走向。

    5、简单粗暴处理原则

    火星救援最后的MAV起飞时候,由于上升高度不能到达赫耳墨斯号对接,因此简单粗暴的将所有没用的东西去除。看起来可能在电影里面才会出现,但如果真的碰到类似情况,可能也没有更好的处理方法。

    在处理故障过程当中,很多时候也需要打破常规,用一些简单粗暴的方法,这些方法可能临时会造成一些用户访问的问题,甚至会引起部分数据的不一致,但是如果能让整体迅速恢复,这些简单粗暴的方法是值得鼓励和尝试的。关键技术负责人需要知道有合适的善后技术方案来恢复这些用户的数据。

    马克·瓦特尼回到地球,许多天后的一天清晨,坐在公园长椅喝咖啡,原来我们写代码普通一天也是火星人羡慕的幸福生活。

    本文中文翻译参考《火星救援》译林出版社中文版。

    123...Last