抖音缓存的数据是啥(抖音缓存的数据在哪里)

本文选自“字节跳动基础架构实践”系列文章。

“字节跳动基础架构实践”系列文章是由字节跳动基础架构部门各技术团队及专家倾力打造的技术干货内容，和大家分享团队在基础架构发展和演进过程中的实践经验与教训，与各位技术同学一起交流成长。

2019 年，Gartner 将图列为 2019 年十大数据和分析趋势之一，字节跳动在面对把海量内容推荐给海量用户的业务挑战中，也大量采用图技术。本文将对字节跳动自研的分布式图数据库和图计算专用引擎做深度解析和分享，展示新技术是如何解决业务问题，影响几亿互联网用户的产品体验。

1. 图状结构数据广泛存在

字节跳动的所有产品的大部分业务数据，几乎都可以归入到以下三种：

用户信息、用户和用户的关系（关注、好友等）；内容（视频、文章、广告等）；用户和内容的联系（点赞、评论、转发、点击广告等）。

这三种数据关联在一起，形成图状（Graph）结构数据。

为了满足 social graph 的在线增删改查场景，字节跳动自研了分布式图存储系统——ByteGraph。针对上述图状结构数据，ByteGraph 支持有向属性图数据模型，支持 Gremlin 查询语言，支持灵活丰富的写入和查询接口，读写吞吐可扩展到千万 QPS，延迟毫秒级。目前，ByteGraph 支持了头条、抖音、 TikTok、西瓜、火山等几乎字节跳动全部产品线，遍布全球机房。在这篇文章中，将从适用场景、内部架构、关键问题分析几个方面作深入介绍。

ByteGraph 主要用于在线 OLTP 场景，而在离线场景下，图数据的分析和计算需求也逐渐显现。 2019 年年初，Gartner 数据与分析峰会上将图列为 2019 年十大数据和分析趋势之一，预计全球图分析应用将以每年 100% 的速度迅猛增长，2020 年将达到 80 亿美元。因此，我们团队同时也开启了在离线图计算场景的支持和实践。

下面会从图数据库和图计算两个部分，分别来介绍字节跳动在这方面的一些工作。

2. 自研图数据库（ByteGraph）介绍

从数据模型角度看，图数据库内部数据是有向属性图，其基本元素是 Graph 中的点（Vertex）、边（Edge）以及其上附着的属性；作为一个工具，图数据对外提供的接口都是围绕这些元素展开。

图数据库本质也是一个存储系统，它和常见的 KV 存储系统、MySQL 存储系统的相比主要区别在于目标数据的逻辑关系不同和访问模式不同，对于数据内在关系是图模型以及在图上游走类和模式匹配类的查询，比如社交关系查询，图数据库会有更大的性能优势和更加简洁高效的接口。

2.1 为什么不选择开源图数据库

图数据库在 90 年代出现，直到最近几年在数据爆炸的大趋势下快速发展，百花齐放；但目前比较成熟的大部分都是面对传统行业较小的数据集和较低的访问吞吐场景，比如开源的 Neo4j 是单机架构；因此，在互联网场景下，通常都是基于已有的基础设施定制系统：比如 Facebook 基于 MySQL 系统封装了 Social Graph 系统 TAO，几乎承载了 Facebook 所有数据逻辑；Linkedln 在 KV 之上构建了 Social Graph 服务；微博是基于 Redis 构建了粉丝和关注关系。

字节跳动的 Graph 在线存储场景， 其需求也是有自身特点的，可以总结为：

海量数据存储：百亿点、万亿边的数据规模；并且图符合幂律分布，比如少量大 V 粉丝达到几千万；海量吞吐：最大集群 QPS 达到数千万；低延迟：要求访问延迟 pct99 需要限制在毫秒级；读多写少：读流量是写流量的接近百倍之多；轻量查询多，重量查询少：90%查询是图上二度以内查询；容灾架构演进：要能支持字节跳动城域网、广域网、洲际网络之间主备容灾、异地多活等不同容灾部署方案。

事实上，我们调研过了很多业界系统， 这个主题可以再单独分享一篇文章。但是，面对字节跳动世界级的海量数据和海量并发请求，用万亿级分布式存储、千万高并发、低延迟、稳定可控这三个条件一起去筛选，业界在线上被验证稳定可信赖的开源图存储系统基本没有满足的了；另外，对于一个承载公司核心数据的重要的基础设施，是值得长期投入并且深度掌控的。

因此，我们在 18 年 8 月份，开始从第一行代码开始踏上图数据库的漫漫征程，从解决一个最核心的抖音社交关系问题入手，逐渐演变为支持有向属性图数据模型、支持写入原子性、部分 Gremlin 图查询语言的通用图数据库系统，在公司所有产品体系落地，我们称之为 ByteGraph。下面，会从数据模型、系统架构等几个部分，由浅入深和大家分享我们的工作。

2.2 ByteGraph 的数据模型和 API数据模型

就像我们在使用 SQL 数据库时，先要完成数据库 Schema 以及范式设计一样，ByteGraph 也需要用户完成类似的数据模型抽象，但图的数据抽象更加简单，基本上是把数据之间的关系“翻译”成有向属性图，我们称之为“构图”过程。

比如在前面提到的，如果想把用户关系存入 ByteGraph，第一步就是需要把用户抽象为点，第二步把"关注关系”、“好友关系”抽象为边就完全搞定了。下面，我们就从代码层面介绍下点边的数据类型。

点（Vertex）

点是图数据库的基本元素，通常反映的是静态信息。在 ByteGraph 中，点包含以下字段：

图划分

对于单机无法处理的超级大图，则需要将图数据划分成几个子图，采用分布式计算方式，因此，会涉及到图划分的问题，即如何将一整张图切割成子图，并分配给不同的机器进行分布式地计算。常见的图划分方式有切边法（Edge-Cut）和切点法（Vertex-Cut），其示意图如下所示：

切边法顾名思义，会从一条边中间切开，两边的节点会分布在不同的图分区，每个节点全局只会出现一次，但切边法可能会导致一条边在全局出现两次。如上左图所示，节点 A 与节点 B 之间有一条边，切边法会在 A 和 B 中间切开，A 属于图分区 1，B 属于图分区 2。

切点法则是将一个节点切开，该节点上不同的边会分布在不同的图分区，每条边全局只会出现一次，但切点法会导致一个节点在全局出现多次。如上图右图所示，节点 A 被切分为 3 份，其中边 AB 属于分区 2，边 AD 属于图分区 3。

图划分还会涉及到分图策略，比如切点法会有各种策略的切法：按边随机哈希、Edge1D、Edge2D 等等。有些策略是可全局并行执行分图的，速度快，但负载均衡和计算时的通信效率不理想；有些是需要串行执行的但负载均衡、通信效率会更好，各种策略需要根据不同的业务场景进行选择。

执行模型

执行模型解决的是不同的节点在迭代过程中，如何协调迭代进度的问题。图计算通常是全图多轮迭代的计算，比如 PageRank 算法，需要持续迭代直至全图所有节点收敛才会结束。

在图划分完成后，每个子图会被分配到对应的机器进行处理，由于不同机器间运算环境、计算负载的不同，不同机器的运算速度是不同的，导致图上不同节点间的迭代速度也是不同的。为了应对不同节点间迭代速度的不同，有同步计算、异步计算、以及半同步计算三种执行模型。

同步计算是全图所有节点完成一轮迭代之后，才开启下一轮迭代，因为通常每个节点都会依赖其他节点在上一轮迭代产生的结果，因此同步计算的结果是正确的。

异步计算则是每个节点不等待其他节点的迭代进度，在自己计算完一轮迭代后直接开启下一轮迭代，所以就会导致很多节点还没有完全拿到上一轮的结果就开始了下一轮计算。

半同步计算是两者的综合，其思想是允许一定的不同步，但当计算最快的节点与计算最慢的节点相差一定迭代轮数时，最快的节点会进行等待。 同步计算和异步计算的示意图如下图：

同步计算和异步计算各有优劣，其对比如下表所示，半同步是两者折中。多数图计算系统都采用了同步计算模型，虽然计算效率比异步计算弱一些，但它具有易于理解、计算稳定、结果准确、可解释性强等多个重要的优点。

通信模型

为了实现拓展性，图计算采用了不同的通信模型，大致可分为分布式共享内存、Push 以及 Pull。分布式共享内存将数据存储在共享内存中，通过直接操作共享内存完成信息交互；Push 模型是沿着出边方向主动推送消息；Pull 则是沿着入边方向主动收消息。三者优劣对比如下表格所示：

3.2 技术选型

由于字节跳动要处理的是世界级的超大规模图，同时还对计算任务运行时长有要求，因此主要考虑高性能、可拓展性强的图计算系统。工业界使用比较多的系统主要有以下几类：

Pregel & Giraph

Google 提出了 Pregel 来解决图算法在 MapReduce 上运行低效的问题，但没有开源。Facebook 根据 Pregel 的思路发展了开源系统 Giraph，但 Giraph 有两个问题：一是 Giraph 的社区不是很活跃；二是现实生活中的图都是符合幂律分布的图，即有一小部分点的边数非常多，这些点在 Pregel 的计算模式下很容易拖慢整个计算任务。

GraphX

GraphX 是基于 Spark 构建的图计算系统，融合了很多 PowerGraph 的思想，并对 Spark 在运行图算法过程中的多余 Shuffle 进行了优化。GraphX 对比原生 Spark 在性能方面有很大优势，但 GraphX 非常费内存，Shuffle 效率也不是很高，导致运行时间也比较长。

Gemini

Gemini 是 16 年发表再在 OSDI 的一篇图计算系统论文，结合了多种图计算系统的优势，并且有开源实现，作为最快的图计算引擎之一，得到了业界的普遍认可。

正如《Scalability! But at what COST? 》一文指出，多数的图计算系统为了拓展性，忽视了单机的性能，加之分布式带来的巨大通信开销，导致多机环境下的计算性能有时甚至反而不如单机环境。针对这些问题，Gemini 的做了针对性优化设计，简单总结为：

图存储格式优化内存开销：采用 CSC 和 CSR 的方式存储图，并对 CSC/CSR 进一步建立索引降低内存占用；Hierarchical Chunk-Based Partitioning：通过在 Node、Numa、Socket 多个维度做区域感知的图切分，减少通信开销；自适应的 Push / Pull 计算：采用了双模式通信策略，能根据当前活跃节点的数量动态地切换到稠密或稀疏模式。

兼顾单机性能和扩展性，使得 Gemini 处于图计算性能最前沿，同时，Gemini 团队也成立了商业公司专注图数据的处理。

3.3 基于开源的实践

Tencent Plato 「链接」是基于 Gemini 思想的开源图计算系统，采用了 Gemini 的核心设计思路，但相比 Gemini 的开源版本有更加完善的工程实现，我们基于此，做了大量重构和二次开发，将其应用到生成环境中，这里分享下我们的实践。

更大数据规模的探索

开源实现中有个非常关键的假设：一张图中的点的数量不能超过 40 亿个；但字节跳动部分业务场景的数据规模远超出了这个数额。为了支持千亿万亿点的规模，我们将产生内存瓶颈的单机处理模块，重构为分布式实现。

点 ID 的编码

Gemini 的一个重要创新就是提出了基于 Chunk 的图分区方法。这种图分区方法需要将点 id 从 0 开始连续递增编码，但输入的图数据中，点 id 是随机生成的，因此需要对点 id 进行一次映射，保证其连续递增。具体实现方法是，在计算任务开始之前将原始的业务 id 转换为从零开始的递增 id，计算结束后再将 id 映射回去，如下图所示：

在开源实现中，是假设图中点的数量不可超过 40 亿，40 亿的 id 数据是可以存储在单机内存中，因此采用比较简单的实现方式：分布式计算集群中的每台机器冗余存储了所有点 id 的映射关系。然而，当点的数量从 40 亿到千亿级别，每台机器仅 id 映射表就需要数百 GB 的内存，单机存储方案就变得不再可行，因此需要将映射表分成 shard 分布式地存储，具体实现方式如下：

我们通过哈希将原始业务点 id 打散在不同的机器，并行地分配全局从 0 开始连续递增的 id。生成 id 映射关系后，每台机器都会存有 id 映射表的一部分。随后再将边数据分别按起点和终点哈希，发送到对应的机器进行编码，最终得到的数据即为可用于计算的数据。当计算运行结束后，需要数据需要映射回业务 id，其过程和上述也是类似的。

上面描述的仅仅是图编码部分，40 亿点的值域限制还广泛存在于构图和实际计算过程中，我们都对此做了重构。另外在我们的规模下，也碰到了一些任务负载不均，不够稳定，计算效率不高等问题，我们对此都做了部分优化和重构。

通过对开源实现的改造，字节跳动的图计算系统已经在线上支撑了多条产品线的计算任务，最大规模达到数万亿边、数千亿点的世界级超大图，这是业内罕见的。同时，面对不断增长的业务，并且我们还在持续扩大系统的边界，来应对更大规模的挑战。

自定义算法实现

在常见图计算算法之外，字节跳动多元的业务中，有大量的其他图算法需求以及现有算法的改造需求，比如需要实现更适合二分图的 LPA 算法，需要改造 PageRank 算法使之更容易收敛。

由于当前图计算系统暴露的 API 还没有非常好的封装，使得编写算法的用户会直接感知到底层的内部机制，比如不同的通信模式、图表示方式等，这固然方便了做图计算算法实现的调优，但也导致业务同学有一定成本；另外，因为涉及超大规模数据的高性能计算，一个细节（比如 hotpath 上的一个虚函数调用，一次线程同步）可能就对性能有至关重要的影响，需要业务同学对计算机体系结构有一定了解。基于上述两个原因，目前算法是图计算引擎同学和图计算用户一起开发，但长期来看，我们会封装常用计算算子并暴露 Python Binding ，或者引入 DSL 来降低业务的学习成本。

3.4 未来展望

面对字节跳动的超大规模图处理场景，我们在半年内快速开启了图计算方向。支持了搜索、风控等多个业务的大规模图计算需求，取得了不错的进展，但还有众多需要我们探索的问题：

从全内存计算到混合存储计算：为了支持更大规模的数据量，提供更加低成本的计算能力，我们将探索新型存储硬件，包括 AEP / NVMe 等内存或外存设备，扩大系统能力；动态图计算：目前的系统只支持静态图计算，即对完整图的全量数据进行计算。实际业务中的图每时每刻都是在变化的，因此使用现有系统必须在每次计算都提供整张图。而动态图计算能够比较好地处理增量的数据，无需对已经处理过的数据进行重复计算，因此我们将在一些场景探索动态图计算；异构计算：图计算系统属于计算密集型系统，在部分场景对计算性能有极高的要求。因此我们会尝试异构计算，包括使用 GPU / FPGA 等硬件对计算进行加速，以追求卓越的计算性能；图计算语言：业务直接接触底层计算引擎有很多弊端，比如业务逻辑与计算引擎强耦合，无法更灵活地对不同算法进行性能优化。而通过图计算语言对算法进行描述，再对其编译生成计算引擎的执行代码，可以将业务逻辑与计算引擎解耦，能更好地对不同算法进行自动地调优，将性能发挥到极致。4. 总结

随着字节跳动业务量级的飞速增长和业务需求的不断丰富，我们在短时间内构建了图存储系统和图计算系统，在实际生产系统中解决了大量的问题，但同时仍面临着巨大的技术挑战，我们将持续演进，打造业界顶尖的一栈式图解决方案。未来已来，空间广阔，希望更多有兴趣的同学加入进来，用有趣的分布式技术来影响几亿人的互联网生活。

5. 参考文献Bronson, Nathan, et al. "{TAO}: Facebook’s distributed data store for the social graph." Presented as part of the 2013 {USENIX} Annual Technical Conference ({USENIX}{ATC} 13). 2013.Malewicz, Grzegorz, et al. "Pregel: a system for large-scale graph processing." Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. 2010.Low, Yucheng, et al. "Distributed graphlab: A framework for machine learning in the cloud." arXiv preprint arXiv:1204.6078 (2012).Gonzalez, Joseph E., et al. "Powergraph: Distributed graph-parallel computation on natural graphs." Presented as part of the 10th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 12). 2012.Gonzalez, Joseph E., et al. "Graphx: Graph processing in a distributed dataflow framework." 11th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 14). 2014.Zhu, Xiaowei, et al. "Gemini: A computation-centric distributed graph processing system." 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 2016.Kyrola, Aapo, Guy Blelloch, and Carlos Guestrin. "Graphchi: Large-scale graph computation on just a {PC}." Presented as part of the 10th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 12). 2012.Roy, Amitabha, Ivo Mihailovic, and Willy Zwaenepoel. "X-stream: Edge-centric graph processing using streaming partitions." Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. 2013.Shun, Julian, and Guy E. Blelloch. "Ligra: a lightweight graph processing framework for shared memory." Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming. 2013.McSherry, Frank, Michael Isard, and Derek G. Murray. "Scalability! But at what {COST}?." 15th Workshop on Hot Topics in Operating Systems (HotOS {XV}). 2015.Aditya Auradkar, Chavdar Botev, Shirshanka Das. "Data Infrastructure at LinkedIn "2012 IEEE 28th International Conference on Data Engineering更多分享

字节跳动 EB 级 HDFS 实践

字节跳动如何优化万级节点 HDFS平台

字节跳动基础架构团队

字节跳动基础架构团队是支撑字节跳动旗下包括抖音、今日头条、西瓜视频、火山小视频在内的多款亿级规模用户产品平稳运行的重要团队，为字节跳动及旗下业务的快速稳定发展提供了保证和推动力。

公司内，基础架构团队主要负责字节跳动私有云建设，管理数以万计服务器规模的集群，负责数万台计算/存储混合部署和在线/离线混合部署，支持若干 EB 海量数据的稳定存储。

文化上，团队积极拥抱开源和创新的软硬件架构。我们长期招聘基础架构方向的同学，具体可参见 job.bytedance.com，感兴趣可以联系邮箱 arch-graph@bytedance.com 。

欢迎关注字节跳动技术团队

以上就是小编带来的抖音缓存的数据是啥的全部内容，希望能够帮助到大家，更多抖音操作运营内容，请关注金符游戏。