首届云原生编程挑战赛正在报名中，初赛共有三个赛道，题目如下：
赛道一：实现一个分布式统计和过滤的链路追踪
赛道二：实现规模化容器静态布局和动态迁移
赛道三：服务网格控制面分治体系构建
立即报名（报名时间即日起至07/01）：https://tianchi.aliyun.com/specials/promotion/cloudnative#problem-definition
本文主要针对赛道一题目做出剖析，帮助选手更高效的解题。
背景
为了应对各种复杂的业务，系统架构也从单机大型软件演化成微服务架构。微服务构建在不同的软件集上，这些软件模块可能是由不同团队开发的，可能使用不同的编程语言来实现，还可能发布在多台服务器上。因此，如果一个服务出现问题，可能导致几十个服务都出现异常。
分布式追踪系统用来记录请求范围内的信息，用户在页面的一次点击发送请求，这个请求的所有处理过程，比如经过多少个服务，在哪些机器上执行，每个服务的耗时和异常情况。可参考链路追踪的概念
采集链路数据过程中，采集的数据越多，消耗的成本就越多。为了降低成本，目前普遍的做法是对数据进行采样。请求是否采样都是从头节点决定并通过跟踪上下文透传到所有节点(head-based sampling)。
目前业界普遍的采样都是按照这个方式，比如固定比例采样(Probabilistic Sampling)，蓄水池采样(Rate Limiting Sampling)，混合采样(Adaptive Sample)。这样的采样可以保证整个调用链的完整性。但是这样采样也带来两个问题：
1、有些异常和慢请求因为采样的原因没有被采集到，而这些链路数据对业务很重要。
2、99% 的请求都是正常的，而这些数据对问题排查并不重要，也就是说大量的成本花在并不重要的数据上。
本题目是另外一种采样方式(tail-based Sampling)，只要请求的链路追踪数据中任何节点出现重要数据特征（错慢请求），这个请求的所有链路数据都采集（由分布式微服务的各个节点上产生），这种采样方式在一些场景特别有效，比如错慢全采，大客户全采。目前开源的链路追踪产品都没有实现完整的 tail-based Sampling ，主要的挑战是：任何节点出现符合采样条件的链路数据，那就需要把这个请求的所有链路数据采集。即使这些链路数据在这个链路节点之前或者之后产生，即使这些链路数据在分布式系统的成百上千台机器上。
一 赛题
首届云原生编程挑战赛1：实现一个分布式统计和过滤的链路追踪链接
用户需要实现两个程序，一个是数量流（橙色标记）的处理程序，该程序拉取数据后进行处理，一个是后端程序（蓝色标记），和客户端数据流处理程序（橙色标记）通信，将最终数据结果在后端引擎上聚合。
架构示例图
赛题可以理解为很多组数据（trace）分布在两台机器上，任何一条数据（span）符合采集条件（ http.status_code 不为 200，或者 error 等于1），需要将这组数据（trace）从两台机器上采集下来，在后端程序上聚合汇总。
数据聚合过程如下图
数据处理示例图
二 赛题分析
赛题数据处理很简单，就是一个 map-reduce 处理。在实际场景中，无法将所有数据都上报进行实时计算（全量上报的数据量非常大），需要在客户端完成筛选，在服务端进行聚合。
最大程度利用三台分布式机器的资源
最简单的解决方案是，在一台机器上读取多个数据流数据存放到一个文件中。跳过数据同步的过程，直接对这个文件做数据聚合。这样处理会带来两个问题：
1、只利用单台机器的资源，无法充分利用另外两台机器的资源。
2、存放到文件中，涉及到读写硬盘，相比内存处理会慢一些。
为了最大限度的利用三台机器的资源，需要三者之间良好的协同。我们可以分析链路追踪的场景，需要采集的数据占总数据的比例比较低。那可以在数据处理层做第一次过滤，过滤后三台机器只需要基于需要采集的数据进行通信。
数据处理端的数据缓存、同步
每个节点都只有部分数据，需要将数据进行缓存，再将符合条件的数据在服务端聚合。
数据处理示例图中，数据流 1 缓存了 traceId:1,traceId:2,traceId:3. 检测发现 traceId ：2 符合采集条件。数据流 2 也缓存了 traceId:1,traceId:2,traceId:3，检测发现traceId：3 符合采集条件. 那最终只需要聚合 traceId:2,traceId:3 的数据。traceId：1 的数据不做任何处理。
在评测环境，数据流 1 和数据流 2 都大于 4G 的数据， 而处理数据流的机器内存都只有 4G ，无法在内存中做全量缓存。那选手需要思考做流式缓存处理。在链路追踪的真实场景中，会有时间窗口方式来处理，一般请求不会超过 3 分钟，各个数据流节点同步时间窗口内的数据。同步数据，那就需要保持各个接口数据的同步。而各个节点的数据处理有快有慢，同步的话，可能会 block 数据处理，对性能有影响。通用的解决方式是多个线程来处理，数据处理和数据同步分别两个线程。，数据处理和线程拉取数据并处理，数据同步是对历史数据做同步，例如数据处理示例图中，在数据处理线程处理traceId：3 时， 数据同步线程可以上报 traceId：2 的数据。
服务端的数据缓存，同步和聚合
服务端收集到这个节点的数据后，需要检查各个节点数据是否齐全，如果齐全的话，那需要收集各个节点的数据，如果不齐全的话，那就需要继续等待，甚至阻塞数据上报，直到数据齐全或者超时。比如说，采集某一段数据或者某一个时间窗口的数据时， 节点 1 的数据上报了，节点 2 数据未上报，那需要继续等待节点2的数据。由于并发执行的缘故，节点1的数据在持续上报，而节点 2 数据迟迟未上报，那就需要考虑超时，缓存清除，数据同步。
数据聚合时，题目对真实场景做了简化。在真实场景中，需要同一个请求的所有数据（同一个 traceId 下的所有 span ）构建调用关系的一颗树。
实际场景中的链路详情展示（阿里云链路追踪产品）
简化后，选手只需要根据数据的 startTime 做升序排序，生成 checkSum（Md5）值,保证数据完整性的同时降低业务逻辑的强耦合。具体的 Md5 计算可参考 Demo 。
其他的优化点
1、rpc 建立长连接。
2、Demo 程序采用的 http 方式，本地在服务端程序除了开放了8002端口，还开放了8003，8004端口。选手可以利用这些端口开启长连接通信，比如dubbo，grpc，加快处理过程，提高性能。
3、多线程拉取。
4、为了充分利用数据处理程序的机器资源，可以通过Rang方式多线程去拉取数据。
例如curl -H 'Range: bytes=200-2000' "http://localhost:8081/trace1.data"
三 赛题评测
评测环境由 1 台 2 核 4G 的评测机，2 台 2 核 4G 的数据流处理机器和 1 台 1 核 2G 的后端服务组成。数据流处理机器和后端服务机器都会在docker内运行（docker 容器会限制 CPU 和内存大小）。
1、用户提交编译好的docker image（不限定开发语言，分布式程序建议用go和java）。
2、通过kubernetes的部署docker 容器。
3、评测机器调用数据流处理机器和后端服务机器，检查应用是否启动。
4、评测机器发送评测数据的位置发给数据流处理机器和后端服务机器，并开始计时。
5、评测机器收到上报的接口，并进行分值计算。
6、评测程序的跑分方式：将选手生成的结果同已知结果进行对比，计算 F1 Score；同时记录整个跑分从开始到输出结果的时间 time，最后的比赛得分: F1/time。即 F1 值越大越好，耗时越小越好。
四 总结
本文结合首届云原生挑战赛的赛题背景、题目场景、题目分析和评测环境与过程的角度，介绍了分布式链路跟踪系统的tail-based sampling的基本设计思路，希望对即将参加比赛的同学们能有所帮助，也欢迎更多的技术同学报名参加我们的挑战赛，分享你在编程方面的思考和实践。
五 更多
2、链路追踪的demo（需要开通链路追踪服务，开通后不上报数据，不收取任何费用）
