程序框架的最佳实践【翻译】

原文作者Chris Nokleberg and Brad Hawkes来自Google,Java框架开发者 原标题:程序框架最佳实践——虽然很强大,但并不适合所有人 共享代码库鼓励代码复用,实现不同团队技术的一致性并改进产品效率和质量。开发者需要选择合适的库,研究如何正确配置,最终把所有的库组装在一起。程序框架可以通过对库的默认安装和配置,来简化开发流程,提供更好的一致性,当然也损失了一些库的便利性。 框架不仅是一堆库的集合,还控制了整个程序的生命周期。确定的框架行为可以为开发开拓空间——例如,不用为每个程序应用都深入审查安全和隐私相关的代码。框架提供了跨团队和跨语言的功能一致性,同时也是更高级的自动化和智能系统的基础。 这篇文章先从框架的核心方面综述开始,然后深入到框架的优势、妥协以及我们推荐实现的最为重要的框架功能。最后,这篇文章展示了一个Google的实际框架应用案例:如何开发一个微服务平台,使得Google可以打破单一代码库的限制,以及框架如何使这一切成为可能。 什么是框架 框架和共享代码库在很多方面都类似。在Google,有两个技术原理用于区分框架和库:依赖反转和可扩展性。虽然看起来比较容易,但本文所讨论的框架很多优势,原则上都是从这两个原理衍生出来的。 IOC(依赖反转) 当从头开始开发一个程序的时候,工程师来决定程序的流程——这通常称为普通控制流。在一个基于框架的程序中,则是由框架来控制流程以及调用用户的代码——这叫做反转控制流。反转控制流有时也被引用为好莱坞原则:“别给我们打电话,我们会给你打电话”。框架控制流很好地定义了不同程序之间的标准。理想情况下,程序只需要实现它们特有的逻辑,而由框架来解决所有其他构建一个微服务所需要的各种细节。 可扩展性 扩展性是区分库和框架的第二个重要特点,它和依赖反转互相配合。因为框架的控制流是由框架负责的,唯一的改变框架运行方式的方法只能通过它暴露出来的扩展点。例如,一个服务端框架可能有一个扩展点是允许一个应用程序在每个请求来的时候运行一些代码。扩展点的模式也意味着框架的其他不可扩展性部分很固定,应用程序无法改变。 框架的好处 框架除了提供共享代码库所能提供的功能之外,还有很多好处,它们对不同的角色在不同方面都有益处。 对开发者 开发者这个角色最终决定是否使用一个可用的框架,也是最显然从框架中获益的角色。大部分的开发者的好处在于提升生产力,简便高效以及可应用最佳实践。开发者可以写很少的代码,利用内置的框架功能。由于框架处理了各种样板代码,因此他们所写的代码可以大幅简化。框架提供了合理的默认配置,消除了无意义而且浪费时间的决策判断,从而提供了充足的最佳实践。 对产品团队 除了为开发者提供生产力以外,框架也为产品团队解放了团队浪费在重复建设基础设施的资源。产品团队因此可以更关注于使他们产品与众不同的功能开发了。 框架可以让产品团队的开发与底层基础设施的变更隔离开,这也能让他们从中受益。虽然并不是普遍适用,但框架提供了额外的抽象,这意味着有些基础设施的迁移可以被当做实现细节,完全由框架维护者全权处理。 Google产品的发布需要很多团队的确认。例如,一个发布协调工程师负责审查产品安全性和有效性,同时有一个信息安全工程师检查程序应用的场景安全漏洞防范设计。当负责审查的团队熟悉框架并可以信任框架的功能保证时,框架就可以帮助简化审查流程。产品发布以后,标准化流程可以让系统更加便于管理。 对公司 从公司层面来说,常用的框架可以减少开发者上手启动一个新应用的时间,从而提升开发者的灵活性。如果一个公司有一个足够大的程序员社群,投入资源在高质量的文档和培训程序员将变得非常有价值。这也有助于吸引社群贡献文档和代码。一个被广泛应用的框架意味着,对框架很小的改进投入可以换来巨大的收益影响。 在过去一段时间,收敛框架架构可以使针对全局性的变更有广泛的应用范围。例如,如果你依赖一个统一的微服务/RPC框架,而且带宽比CPU更贵,那么框架可以基于成本权衡来优化默认的压缩参数。 框架的权衡 虽然框架有上述的多种好处,但也面临着各种权衡。 死板的框架能够掩盖创新 框架常常决定支持哪种技术方案。由于支持所有能想到的技术是不现实的,所以一个比较死板的框架也是有明显的好处的——那就是,它们更鼓励使用某种技术或者更偏好某种设计模式。 死板的框架可以极大简化一个开发者从无到有创建一个系统的工作量。当开发者有很多种方式来完成同一种任务时,他们很容易陷入是否会影响整个系统的细节决策中。对于这些开发者而言,接受一个框架所推荐的技术,可以让他们把重点放在构建他们系统的业务逻辑上。有一个普适并且一致的技术偏好对于整个公司而言更有利,虽然这个答案还不尽完美。 当然,你也必须处理程序和团队的长尾问题,有些产品需求或者团队喜好和现有的框架可能并不完全适配。框架的维护者被放在一个判断什么是最佳实践的位置上,也会需要确认一个不方便的使用案例是否“真实”,因为这个案例可能对每个用户来说都不方便。 另一个需要重点考虑的是,即使某些技术在今天看来的确是一个最佳实践,但技术也在不断快速地进化,对于框架而言也有一定的风险无法跟上技术创新的发展。采用不同的程序设计方案可能开发成本更高,因为开发者既需要学习框架实现细节,也需要框架维护者的协助。 普适性也会导致不必要的抽象 很多框架优势,例如通用的控制面板(后面解释),只有当大部分关键重要的应用都基于这个框架才有真正的意义。这样的一个框架必须足够普适来支持绝大多数用户的场景,这也意味着必须拥有丰富的请求生命周期,以及任何程序都需要的所有的扩展点。这些需求有必要在应用和底层库之间增加若干间接层,这些层也会增加学习成本以及CPU开销。对于应用开发者而言,软件栈中的更多层也会导致调试更复杂。 另一个框架潜在的缺陷是,它们需要工程师额外学习。当新来的Google员工学习如何让一个“hello world”样例运行的时候,他们经常会被他们所需要学习的技术的数量所抓狂。一个功能完备的框架也会让这个情况更糟而不会更好。 Google已经开始尝试让每个框架的核心尽量简单符合预期,让其他功能都成为可选模块,从而来解决这些问题。Google也会尝试提供配套框架的工具,可以帮助了解框架内部结构来简化调试。最终,虽然框架有一些你必须学习的成本,但你需要确保任何一个给定的框架提供了足够的好处来弥补这个成本。不同的编程语言的框架也许有不同的权衡组合,对于开发者而言这也是一个新的决策点和成本/收益权衡场景。 重要的框架特性 如上所述,反转控制和扩展性是框架最为基础的两个特点。除了这些基础能力以外,框架还需要负责若干其他功能。 标准化程序生命周期 再次重申,反转控制意味着框架拥有并且使一个应用程序的整个生命周期标准化,但这样的结构带来什么样的好处呢?我们以避免级联故障为例来说明这个问题。 级联故障是一个典型的引起系统超载的原因,Google内部也很有很多。它可能发生在分布式系统的部分服务失败,增加了其他部分失败的可能。关于级联故障更多的原因,以及如何避免他们,参考SRE(Site Reliability Engineering (O’Reilly Media, 2016))中的定位级联故障这一章。 Google的服务框架有很多内置的避免级联故障的保护功能,两个最重要的原则是: 持续运行。如果一个服务能成功响应请求,那么就应该保持。如果它能处理一部分请求但不能处理其他部分请求,那么就必须继续运行,而且响应它能服务的请求。 快速启动。一个服务必须尽量快地启动。更快地启动意味着可以快速从崩溃中恢复。服务必须避免类似启动时顺序等待RPC访问外部系统返回这样的操作。 Google生产环境给每个服务配置了一个成为健康状态(可以响应请求)的时长。如果超时了,系统则认为一个无法恢复的故障发生了,则终止这个服务进程。 有一个常见的反模式,常发生在缺乏框架的场景中:一个库创建他们管理的RPC连接,并等待连接可用。当服务端代码随着时间推移不断膨胀,你能获得一个实际有几十个这样的有序依赖的库。这样的结果是,处理初始化代码有效展开的话看起来如图1所示: 在通常的情况下,这样的代码工作很好。但因为没有任何潜在问题的提示,这样的代码会有个特殊问题。这个问题只有当一个相关的后端服务慢了或者同时挂了才会显现出来——这时关键服务启动已经延迟了。如果服务启动足够慢,那它将会在有机会处理请求之前被杀死,这会导致一场级联故障。 一种可能的改进是先创建RPC stubs,如图2所示,然后并行等待它们初始化完毕。在这种情况下,你只需等待stub初始化时间最长的那个而不是初始化时间之和。 虽然处理的并不十分完美,但这个有限的重构也说明了你需要某种在库所创建的RPC stubs之间的协调机制——它们必须可以有等待stub以及库以外的某些资源的能力。在Google的案例中,这样的事情是由服务端框架负责的,同时它也有如下功能: 通过定期拉取可用性来并行等待所有stubs可用(<1秒)。一旦配置的超时到了,即使并不是所有后端服务都准备好,服务依然可以继续初始化。 去掉用于人工或者机器可读的调试日志,而是用集成标准化监控和报警来代替。 通过一个通用的机制来支持插拔不同的资源,而不仅是RPC stubs。技术上来说,仅有返回布尔值的函数(为了“我是否准备好”)以及对应的名字,是有打印日志的必要。这些插拔点常被那些处理资源的通用库(例如:文件API)所使用;程序开发者通常只需要用这个库,就能自动地拥有这些能力 提供一个中心化的方式配置特定的关键后端服务,可以改变他们启动或者运行时的行为。 对任何一个单独的库来说,这些功能可能(也正确地)被认为是多了,但实现这些功能,能够让你在一个集中的地方实现,并在所有用这个库的后端服务都能生效。这也是有意义的一件事情。就像共享库是一种在不同应用程序中分享代码的方式,在这个定义下,框架也是一种在不同库之间共享功能的方式。 因为有类似这些的功能,SRE们更愿意支持基于框架的服务。他们也经过鼓励他们对口的程序员选择基于框架的开发方案。框架提供了一个生产规范的基础水平。这个生产规范将一堆没有关联的库关联到一起时是非常难以实现的——但也不是不可能。 标准化的请求生命周期 虽然细节取决于应用程序的类型,但很多框架支持在总的程序生命周期以外的生命周期管理。对于Google的服务端框架而言,最为重要的任务单位就是请求。除了遵循类似依赖反转的模型以外,请求生命周期管理的目标是将请求的不同方面的职责划分成独立的可扩展的代码片段。这允许程序开发者只关注于开发让他们的应用程序独一无二的实际业务逻辑。 这里有一个这样的实际使用的框架例子,它的组件片段见图3: Processors——拦截请求和返回的包。常用于打印日志,但也有一些短路请求的功能(例如,强制在整个程序中不强制执行不变量) Action——程序业务逻辑,接受请求,返回一个对象,可能有一些副作用。 Exception handler——将一个未捕捉的异常转换为一个响应对象。 Response handler——序列化一个响应对象给客户端。 虽然程序能从框架的扩展点中收益,程序代码的绝大部分都是以响应的形式执行,包括程序特有的业务逻辑。...

December 5, 2022 · Skyan

Memory Models读后感

读了Russ Cox关于Memory Models的三篇综述文章: Hardware Memory Models Programming Language Memory Models Updating the Go Memory Model 读完之后终于搞明白Memory Models的大体脉络。 首先在一个单核单线程的程序中,是没有内存模型问题的。随着多核多线程的引入,程序开始实现并行化提升性能,同时编译器、操作系统以及硬件针对并行化做了大量的优化,这就出现了很多新的并发数据访问问题,就需要设计规范的内存模型来解决。 内存模型分为硬件内存模型和编程语言内存模型两个层面。 其中硬件内存模型分为以Intel CPU为代表的x86-TSO模型和以ARM/POWER为代表的Relaxed Memory Model模型。前者模型中,多核对写入主存的数据提供全局序,后者模型中,多核之间不存在全局序的概念。为了协调不同硬件,又有DRF-SC(Data-Race-Free Sequential Consistency)模型,该模型是一种能让大部分硬件都能接受实现的顺序内存访问模型,这样DRF-SC可以作为硬件内存模型的统一标准。 编程语言内存模型的定义分为两个流派: 以Java,Javascript为代表的happen-before流派。特点是通过happen-before语义来定义语言的哪些方面如何实现数据的同步。该流派规范定义最早,也最为经典。Java9以后增加了弱同步,类似C++的弱同步(acquire/release)。 以C/C++,Rust,Swift等为代表的强-弱-无顺序流派。特点是分为三类同步语义,强代表前后顺序一致,和Java的happen before语义一致。弱代表在部分协调条件下的一致。无代表没有同步。 按照作者的介绍,这两个流派的内存模型都存在缺陷。Java的内存模型定义并不严格,还是有非因果、非一致的情况发生。C++的内存模型有很多未定义的情况,尤其是弱同步和无同步语义其实存在很多坑,甚至在不同硬件下运行结果可能还不一致。 Go语言采取中间流派,即只通过happen-before来定义同步语义,只支持顺序一致,不支持弱同步,不支持无同步,严格定义,同时约束编译器的优化,保证最终结果可预测,即使有未定义的情况发生,也能约束结果在有限的范围内。 最终结论是,截止目前2022年,内存模型还处于不断探索和研究的方向,Go的这个尝试也是建立在无数前人理论的基础之上,未来有待更加规范定义的模型出现。

October 9, 2022 · Skyan

2022 KDD论文阅读:Intelligent Request Strategy Design in Recommender System

阿里巴巴2022年KDD上发表一篇论文,介绍“瀑布流”推荐产品如何智能地选定请求时机的问题。这篇论文之前作为淘宝端智能的一项成果在知乎发布过,详见这篇文章。今年算是正式在KDD发表论文了。 阅读过程中我也一直将论文的方法和我们所做的类似的项目做对比,结论是思路是一致的,并不落后,但这篇论文的手段更加丰富,资源投入也更多,值得我们参考和学习。 背景 论文一开始先介绍什么事“瀑布流”推荐,这对于国内的移动用户而言司空见惯,就是无限下拉无限刷新推荐结果的产品交互形式,国内一般也叫feed信息流。所以需要解决的一个问题是分页请求时机的问题,就是确定在什么时机向后端发送新的推荐请求。一般是每浏览n个item后(也叫一刷)发起后端推荐请求。如果n变小,请求的频度增加,则后端服务请求的压力增加,而且很多用户本来也没有购买或者点击意愿,新增的推荐请求返回的结果也没有转换为最终的业务收益,最终白白浪费了算力。相反,如果n变大,请求的频度减少,则用户反馈延迟较长,用户实时的意愿(例如点击,购买转化等行为)没能及时反馈到后端,导致下一刷展现的还是之前缓存的推荐结果,体验较差而且不能提升产品收益。作者以淘宝App首页推荐为例,统计了每一刷的推荐结果CTR的变化情况,如下图所示: 可以明显看出每一刷头几条结果都是点击率很高,但后续衰减也是非常明显的。而且每次一刷更新点击率都有一次迅速提升,原因是新的一刷捕捉到了用户最新的兴趣点,但之后又回归到衰减。 问题和解决方案 因此,如何确定什么时机发起下次刷新是这篇论文需要解决的问题,作者给该解决方案定义了一个名词:IRSD(Intelligent Request Strategy Design),还大言不惭的说据他们所知,这是第一个在瀑布流推荐产品中研究IRSD的论文。 作者提出该问题主要有如下几点挑战: 捕捉用户兴趣点动态变化是一个难点,因为用户兴趣点是隐式变化的 不能同时观测到用户增加或者不增加下一刷请求,本质上这是一个反事实现象,所以uplift预估存在巨大的挑战。 这一点非常赞同,和我们遇到的难题类似, 不同策略其实无法在一个用户中同时存在,这也是反事实模型需要解决的问题 如何平衡新增下一刷请求的收益和带来的额外资源消耗非常有挑战性,尤其是用户数一直在动态变化 这一点和我们遇到的问题类似,如何保持QPS在系统可承载的范围内,同时拿到额外的业务收益,这也是效果-算力之间平衡的难题 为了解决以上调整,他们提出了一种新的范式,即基于Uplift算法的端智能请求框架(Uplift-based On-edge Smart Request Framework (AdaRequest))。该框架部署在端上,这样可以更极致实时地收集和分析用户行为。该框架由如下几部分组成:用户行为理解模型(CUBE),反事实请求奖励估计(CREST),动态请求规划(DRP)。其中: CUBE挖掘用户稀疏的实时行为序列,长期行为序列,以及购买交互序列。通过比较用户实时意图和历史兴趣,CUBE可以评估出用户兴趣点是否有变化 CREST目标是对treatment和control组的用户分别建模,通过因果推断(causal inference)预估出增益(uplift)。 DRP动态选择新增请求的比例,用来选取最大化的请求奖励和资源消耗之比,在有限的资源约束前提下最大化请求奖励。 最终这套AdaRequest在手机淘宝的猜你喜欢页面(也就是首页推荐)落地,和固定增加请求比例对比,有GMV提升3%的额外收益。 总的来说,论文定义并调研了瀑布流推荐场景下的IRSD问题,同时提出了AdaRequest范式解决IRSD问题。同时通过在线和离线实验量化证明了AdaRequest的有效性。 问题定义 接下来论文介绍了实现的方法。首先定义问题,从形式上IRSD问题定义如下: 其中S函数代表用户的正向反馈,F函数代表决策结果(1代表请求,0代表不请求),\(c_i^X\)代表第i个上下文环境,\(u_i^X\)代表第i个用户,\(b_i^u\)代表第i个用户的历史行为,\(X_i\)代表第i刷。R代表新增请求的资源消耗函数。因此第一个公式代表在各种上下文环境、用户、历史行为、刷次中获取的总收益大小。第二个公式代表总资源消耗约束在theta阈值以内。优化目标是找到最优的算法F,使得在满足资源消耗约束条件下,最大化业务收益。 AdaRequest框架 接下来终于一窥AdaRequest方案的整体框架,如下图所示: 虽然CUBE,CREST,DRP三大组件看起来很高级的样子,其实核心在左边的流程图中: 首先在端上实时采集用户行为,第二步CUBE将用户行为转变为用户意图变化情况,转化方式实现采用了一个神经网络来解决,产出用户浏览历史匹配度,用户当前session点击历史匹配度,用户长期点击历史匹配度,以及候选推荐item的embedding向量。第三步CREST将第二步的输出作为输入,再加上用户以及上下文特征向量,可以预估出新增请求的奖励uplift,最终交给DRP来决策是否发起新增请求。 DRP将动态选择一部分高性价比的时机发起新的请求。如果决策新增一次推荐请求,端则向后端发起请求,上传用户实时行为,后端则重新分析用户意图,返回更新的推荐item,更好地匹配用户最新的兴趣点。 因此,该论文所采用的特征体系有: 用户特征F(user) 候选item特征F(cands) 用户细粒度的历史行为特征: 用户的浏览历史F(exp) 用户当前session的点击行为F(sclk) 用户长期点击行为F(clk) 粗粒度的当前session的上下文特征F(context) 在这个特征组中,F(sclk)和F(clk)分别代表了用户实时和长期的兴趣点。F(exp)代表了上次请求曝光后用户不喜欢的item,原因是负向反馈也是一种有价值的信号。F(context)代表用户在当前session中的推荐满意程度,例如浏览的深度。论文还很贴心的把所有特征列表附在论文附录。 CUBE CUBE组件的目标是从用户实时行为中找出用户意图是否发生变化。由于推荐候选item是由后端服务根据用户历史兴趣推荐选择的,CUBE将结合用户行为,将用户刚刚交互过的item和推荐候选的item进行匹配。如果这两者不是非常匹配,意味着当前候选item并不满足用户当前意图,进一步则意味着用户意图发生了变化,因此此时如果新增一次推荐请求,能收获显著的购买uplift。 具体来说,CUBE将F(exp), F(sclk), F(clk)和F(cands)作为输入,针对特征特点做细粒度的建模。具体来说,F(sclk)特征分为用户行为序列F(sclk_beh)和item序列特征F(sclk_item),分别通过两个GRU encoder输出向量并拼接在一起。F(exp)和F(clk)类似处理,而F(cands)采用一个GRU encoding编码,并通过mean-pooling操作做fusion融合。 最终,整个模型采用attention作为将候选item和用户以及交互行为序列匹配的算子。F(cand_emb)作为attention的query输入,用于匹配候选item是否满足用户实时意图。以F(sclk)为例,第i个item是否匹配用户意图的attention评分函数如下公式所示: 可见alpha_i即当前item的匹配率在所有匹配率中的softmax归一化值。输出向量M(sclk)定义如下: 可见M(sclk)即每个item的F(sclk_embs)的加权和,代表了当前候选item是否匹配用户实时意图的程度。 上述的Match函数代表匹配分,代表推荐候选集和用户实时交互的item序列之间的相似程度,即attetion匹配函数。论文实际采用的是内积函数作为匹配函数的实现。M(exp)和M(clk)也是类似方法产出,结果的分布代表了候选item是否匹配用户不喜欢的item以及用户长期感兴趣的item。 CREST CREST模块用于预估新增一个额外的推荐请求带来的uplift收益。由于用户无法同时存在有和没有新增推荐请求的状态,因此无法反事实地观察到收益uplift的真实值groundtruth。 为了解决这个问题,作者采用两个独立的预估网络,Control Net用于预估如果没有额外的请求,购买率是多少。以及Uplift Net,用于预估如果有额外的请求,额外的增益uplift是多少。Control Net和Uplift Net加一起,可以预估出如果有额外的请求,那么购买率是多少。 为了训练这两个预估网络,论文将实验用户随机分为两组用于数据收集:control组没有额外请求,而treatment组随机发起额外请求。Control Net用control组的数据训练,而Uplift Net用control组以及treatment组的数据训练。 预估的时候,只有Uplift Net需要运行,来预估出请求reward,作为决策此次额外请求是否需要触发的基础依据。 用因果推断causality的语言来描述,CREST就是用于对新增额外请求实现CATE,描述如下: Y(0)代表没有新增请求,Y(1)代表有新增请求,CATE代表对于一个新增请求所获得的uplift值。...

August 30, 2022 · Skyan

并行编程之内存管理(总结)

这篇总结并行编程的三种常见的内存管理方法,三种方法如下: Reference Counting:并行编程之内存管理(一) Hazard Pointer:并行编程之内存管理(二) RCU:并行编程之内存管理(三) 三种方法各有利弊,优缺点对比如下: 引用计数(Reference Counting) Hazard Pointer RCU 读性能 低,不可扩展 高,可扩展 高,可扩展 可保护的对象数量 可扩展 不可扩展 可扩展 保护周期 支持长周期 支持长周期 用户必须限制保护周期长度 遍历是否需要重试 如果和删除冲突需要重试 如果和删除冲突需要重试 不需要 存在性保证 复杂 保证 保证 读竞争 高 无 无 对象遍历开销 CAS原子操作,内存屏障,cache missing 内存屏障 无 读遍历机制 无锁 无锁 有限制的无等待(wait free) 读引用获取 可能失败 可能失败 不会失败 内存开销 有限 有限 无限 内存回收机制 无锁 无锁 阻塞 自动回收 是 部分 部分 已经有很多C++项目,包括开源和大厂内部项目,都开始采用Hazard Pointer和RCU来实现并发数据结构,而且C++标准委员会也已经在讨论将这两个组件加入到C++26标准中。 时代在变,并行编程技术也在突飞猛进。多线程多核(multi-core)技术,甚至甚多核(many-core)技术都在飞速发展,加上各种并行编程范式的应用,可以预见到在一段时期内,并行编程将面临百花齐放,技术爆发的局面。

June 14, 2022 · Skyan

并行编程之内存管理(三)

RCU(Read-Copy-Update) 前述的几种内存管理方式只能同时管理一个内存对象,而RCU是一种同时管理多个对象的并发读写的方法。它实际上是提供了一种受保护的内存区域,通过RCU方法,将对象关联到受保护内存区域后,可以保证读操作完成以后才会回收对象,而且读操作开销极其低(5ns左右),适合多个对象的批量保护,以及读多写少的场景。自从2002年RCU功能引入Linux内核以后,在内核中使用次数突飞猛进,如下图所示: 在内核中RCU API被广泛应用于网络,内存管理,文件系统等内核组件中。除了内核,RCU也有开源的user space RCU库,被广泛应用于QEMU模拟器,DPDK,Go语言的垃圾回收等项目中。 那么RCU到底是什么神秘的方法呢?其实原理正如其名:Read-Copy-Update。当需要修改对象的时候,先拷贝这个对象,修改产生新版本对下,然后变更新版本对象,等待老版本对象的reader完成读操作,再销毁老版本对象。可以明显看出,这个思想和Copy-On-Write思想一脉相承,和MVCC的思想更是极其类似。在生产环境中,按照类似原理实现的支持并行变更的数据结构也屡见不鲜,例如索引领域的hashmap,B+树等数据结构都可以按照类似思想实现并发读写。因此,思想并不新,但如果要正确实现,有三个原则需要保证,有很多细节需要处理,这也是RCU比较神秘之处。 RCU正确实现的三个原则是:宽限期保证(grace-period guarantee),发布-订阅保证(publish-subscribe)和内存顺序保证(memory-order guarantee)。解释如下: 宽限期保证 允许所有的更新操作等待之前存在的读操作完成。之前存在的读操作其实就是还在访问修改前的内存对象的reader,因此如果不等待这些reader就销毁老版本的对象,则会导致并发错误。在一个链表的场景中,先删除一个节点的链接,然后通过宽限期保证等待所有该节点的访问结束之后,就可以安全销毁这个节点。 相关的RCU接口有rcu_read_lock,rcu_read_unlock, synchronize_rcu,其中rcu_read_lock,rcu_read_unlock用于读操作,标记当前线程正在读该内存区域,rcu_read_lock,rcu_read_unlock之间访问的所有内存对象被称为读端临界区(read-side critical section)。synchronize_rcu接口用于执行宽限期保证,等待所有还在读老版本数据的线程完成。 发布-订阅保证 该保证是说所有reader读取一个新版本对象的时候,可以保证该对象已经初始化好了。这里reader就是所谓的订阅者,RCU通过rcu_assign_pointer接口实现发布操作,RCU的这个保证可以保证订阅者看到的一定是发布者发布时刻的对象,不存在乱序等因素的干扰。实现上,发布方可以通过std::memory_order_release操作来更新对象,而读方可以通过std::memory_order_consume来读取对象,这样就可以避免乱序读取的情况发生。 内存顺序保证 该保证是宽限期保证的自然延续。读端临界区之间保护的内存对象和synchronize_rcu调用之间,存在一个严格保证的内存顺序关系。 下面几个例子说明该顺序的含义,其中X和Y的初始值都为0: 类别 图示 描述 情况1 如果按照绿色箭头的顺序执行,RCU可以保证读端临界区之后,即rcu_read_unlock发生之后才发生synchronize_rcu,这样如果r2==1,那么可以保证r1==0 情况2 如果CPU 0在读端临界区间运行时发生synchronize_rcu调用,RCU可以保证synchronize_rcu之前发生的事件一定在读端临界区中生效。在这个例子中,如果r2==1,那RCU一定保证r1==1 情况3 如果两个读端临界区并行执行,RCU是无法保证两者之间的内存顺序的。在这个例子中,CPU0和CPU2的读端临界区中对象的读取顺序是无法保证的,因此如果按照绿色箭头执行,r1==0,r3==0,是无法保证X=1和r2=X之间不乱序的 情况4 如果RCU的读端临界区和宽限期保证synchronize_rcu调用重叠,如果按照绿色箭头执行顺序,RCU可以保证读端临界区先于synchronize_rcu执行之前,即r1==1,r2==0 那么,如何实现RCU的呢?实际上,一个最简单的实现方式只需要10行代码,如下所示: static void rcu_read_lock(void) { spin_lock(&rcu_gp_lock); } static void rcu_read_unlock(void) { spin_unlock(&rcu_gp_lock); } void synchronize_rcu(void) { spin_lock(&rcu_gp_lock); spin_unlock(&rcu_gp_lock); } 可以看出rcu_read_lock和rcu_read_unlock通过一把锁来保证和synchronize_rcu之间严格的顺序关系,同时synchronize_rcu必须等待rcu_read_unlock执行完成之后才能执行。当然,这种naive的实现性能最低,而且不支持并发读,在生产环境中完全不可用。 有几种可以考虑的改进思路: 通过引用计数的方式来实现并发读; 通过TLS的方式减少读之间的竞争; 通过多版本的方式来减少锁竞争。 这样一个优化的实现如下所示: DEFINE_SPINLOCK(rcu_gp_lock); // 全局spin lock,用于保证并发只有一个写线程 DEFINE_PER_THREAD(int [2], rcu_refcnt); // 每个线程缓存一个引用计数 long rcu_idx; // 全局多版本号 DEFINE_PER_THREAD(int, rcu_nesting); // 每个线程缓存一个内嵌计数,用于支持读端临界区的重复进入 DEFINE_PER_THREAD(int, rcu_read_idx); // 每个线程缓存一个版本号 // 进入读端临界区 static void rcu_read_lock(void) { int i; int n; n = __get_thread_var(rcu_nesting); if (n == 0) { // 第一次进入的时候更新引用计数 i = atomic_read(&rcu_idx); // 获取可用的全局版本号 __get_thread_var(rcu_read_idx) = i; // 在对应版本计数 __get_thread_var(rcu_refcnt)[i]++; } __get_thread_var(rcu_nesting) = n + 1; // TLS内嵌计数++ smp_mb(); } // 退出读端临界区 static void rcu_read_unlock(void) { int i; int n; smp_mb(); n = __get_thread_var(rcu_nesting); if (n == 1) {// 最后一次退出的时候更新引用计数 i = __get_thread_var(rcu_read_idx); // 获取可用的全局版本号 __get_thread_var(rcu_refcnt)[i]--; // 在对应版本更新计数 } __get_thread_var(rcu_nesting) = n - 1; // TLS内嵌计数-- } // 反转全局版本号,保证所有读线程完成 static void flip_counter_and_wait(int i) { int t; atomic_set(&rcu_idx, !...

June 8, 2022 · Skyan

并行编程之内存管理(二)

Hazard Pointer Hazard Pointer的思想和引用计数恰好相反。不在数据内部存储一份引用计数,而是从外部来管理对象。流程如下:首先为每个需要管理的对象标记一个指针,放到一个全局或者per-thread的list中。在这个list中的标记指针就叫做hazard pointer。需要销毁对象的时候将hazard pointer放到一个待回收list,根据一些策略来决定是否正式销毁对象。销毁待回收的对象的方式还有主动和异步的接口,主动的方式是直接调用接口回收销毁。异步是通过异步线程定期销毁。销毁回收对象的时候,首先查看下hazard pointer list中有没有指向这个对象指针,有就不回收,没有就可以安全回收。其实本质上通过统计指向这个对象的hazard pointer数量来作为“引用计数”。将复杂性放到回收阶段,这也是为什么hazard pointer适合读多写少的场景的原因。 实现Hazard Pointer的主要复杂度在于管理正确处理被保护的hazard pointer和待回收的hazard pointer之间的关系。对于C++来说,可以通过构造/析构函数(RAII)来自动实现加入/退出hazard pointer的保护。整个流程可以见如下示意图所示: 从上图可以看出,销毁hazard pointer所管理的对象是通过延迟销毁来解决。通过对比被销毁的hazard pointer地址和当前正在被保护的hazard pointer地址,从而避免销毁掉正在使用中的指针对象,从而实现保护的目的。 作为样例,我们首先实现一个全局的hazard pointer基类,所有需要拥有hazard pointer保护功能的类都需要继承这个基类。 // 该类实现基本的hazard pointer回收方法 class HazPtrObj { using ReclaimFnPtr = void (*)(HazPtrObj*); template <typename T> friend class HazPtrObjBase; friend class HazPtrDomain; // 对象回收函数 ReclaimFnPtr reclaim_; // 下一个待回收对象。本质上是通过这个指针,将所有待回收对象连成一个链表 HazPtrObj* next_; // 将自身加入到待回收对象list中,依赖全局对象domain,domain统一管理所有已保护和待回收的hazard pointer list void push_obj(HazPtrDomain& domain) { hazptr_domain_push_retired(this, this, domain); } // 对象回收函数 ReclaimFnPtr reclaim() noexcept { return reclaim_; } // 原始指针 const void* raw_ptr() const { return this; } public: HazPtrObj() noexcept : next_(this) {} HazPtrObj(const HazPtrObj& o) noexcept : next_(this){} HazPtrObj(HazPtrObj&& o) noexcept : next_(this) {} /** Copy operator */ HazPtrObj& operator=(const HazPtrObj&) noexcept { return *this; } /** Move operator */ HazPtrObj& operator=(HazPtrObj&&) noexcept { return *this; } HazPtrObj* next() const noexcept { return next_; } void set_next(HazPtrObj* obj) noexcept { next_ = obj; } }; // hazard pointer基类,所有需要保护的类都继承该类 template <typename T> class HazPtrObjBase: public HazPtrObj { // 默认的对象回收函数 void delete_obj(T* p) { delete p; } public: // 将this放到待回收list中,准备被回收 void retire(HazPtrDomain& domain = default_hazptr_domain()) { assert(next_ == this); this->reclaim_ = [](HazPtrObj* p) { auto hobp = static_cast<HazPtrObjBase*>(p); auto obj = static_cast<T*>(hobp); hobp->delete_obj(obj); }; this->push_obj(domain); } }; 实现代码也比较直观,通过继承HazPtrObjBase类,任意一个对象都可以拥有一个retire方法,这个方法可以认为和delete等同用于销毁对象,但并不是立即回收,而是通过hazard pointer的延迟回收。 接下来需要实现一个保护HazPtrObjBase的对象,如下样例代码所示:...

June 8, 2022 · Skyan

并行编程之内存管理(一)

前言 随着现代处理器的发展和多核多CPU体系结构的大面积应用,C和C++编程面临着更加复杂和陡峭的学习曲线。特别是基于多线程带来的并行编程,带来了很多内存并行访问的问题。这需要非常专业的知识,深入了解CPU指令集,内存访问,CPU Cache等体系结构的底层知识,才能正确写好高性能和安全的并行程序。最近十多年,学术和工业界在并行编程方面进行了非常多创新的探索和研究,总结出一套优秀的编程实践和并行内存管理组件,并在Linux内核和大型开源软件中广泛应用。这里选取和内存对象管理有关的三个编程组件进行介绍,分别是引用计数Reference Counting,Hazard Pointer和RCU,都属于延迟处理类型的组件。本文目的一是为了个人学习的总结,另外也是给更多感兴趣的同学以启发。 引用计数 引用计数的思想很简单,通过原子变量来追踪对象的引用数量,来防止错误地销毁对象。这种思想最早可以追溯到20世纪40年代:当时工人们如果要修理危险的大型机械,他们会在进入机器之前,在机器开关上面挂一把锁,防止他在里面的时候被其他人误开机器。这也说明了引用计数的作用:通过计数来管理对象的生命周期。 以shared pointer为例,参考gcc shared_ptr实现,做了一些简化,样例代码如下: // 计数管理类 template <typename T> class RefCount { public: RefCount(T *p = nullptr) : ptr_(p), cnt_(1) {} ~RefCount() { // 如果计数为0,销毁自己 if (Release()) { delete this; } } RefCount(const RefCount<T> &rc) = delete; void operator=(const RefCount<T> &rc) = delete; // 原子++ void AddRef() { ++cnt_; } // 原子--,如果计数为0,销毁保存的对象 bool Release() { if (cnt_.fetch_sub(1, std::memory_order_acq_rel) == 1) { delete ptr_; return true; } return false; } // 返回管理的指针 T *Get() const noexcept { return ptr_; } private: T *ptr_; // 管理的对象指针 std::atomic_int32_t cnt_; // 原子计数 }; // 包装为智能指针 template <typename T> class SharedPtr { public: SharedPtr() noexcept : rc_(nullptr) {} SharedPtr(T *p) : rc_(nullptr) { rc_ = new RefCount(p); } // 创建引用计数对象 SharedPtr(const SharedPtr<T> &sp) : rc_(sp....

June 6, 2022 · Skyan

CATE效应入门(系列之四)

背景 随着互联网的逐步普及和兴起,在线A/B实验获得了越来越广泛地应用。无论是营销策略,交互样式,机器学习模型,搜索算法都依赖在线A/B实验来进行试错和迭代。 实际上,A/B实验的思想最早起源于R.A.Fisher在20世纪20年代进行的针对农业的田间实验(Field Experimentation),之后经过近一个世纪现代统计学的蓬勃发展,逐步成熟应用到各行各业。 在最近50年,随着科技的进步,人类可获取数据量呈现指数级增长,统计学从此有了更多的研究空间,并进入了一个飞速发展的阶段,诞生了因果推断1等更深刻的思想。A/B实验不再仅限于分析平均实验效应(ATE, Average Treatment Effect),还进入到了有条件的平均实验效应(CATE, Conditional Average Treatment Effect),进一步深入挖掘数据内部的规律。 通俗来说,ATE只是对比不同实验版本之间指标的差异,而CATE对比的是不同维度条件下不同实验版本之间指标的差异。而这个思想以及相关的方法,能够进一步挖掘产品,模型,算法,策略的潜力,实现“物以类聚人以群分”的个性化方案,同时也能够更深入的理解实验背后的因果关系。 ATE和CATE 在介绍CATE的具体算法之前,我们先理解ATE的理论基础。这里我们采用Neyman-Rubin的潜在产出模型(potential outcome framework)的理论框架来描述ATE的基本原理。 设Wi表示个体i进入实验组与否,在实验组中取1,对照组取0 (多实验版本的可以做相应的推广);Yi 表示个体 i 的结果变量,就是我们所观察的实验指标。另外记 \({Y_i(1),Y_i(0)}\) 表示个体 i 接受处理或者对照的潜在结果 (potential outcome),那么 \( Y_i(1)−Y_i(0) \)表示个体 i 在实验组中的个体因果作用。不幸的是,每个个体要么接受处理,要么接受对照\({Y_i(1),Y_i(0)}\) 中必然缺失一半,个体的因果作用是不可识别的。观测的结果是: $$Y_i=W_iY_i(1)+(1–W_i)Y_i(0)$$ 但是,在 W 做随机化的前提下,我们可以识别总体的平均因果作用 (Average Treatment Effect; ATE): $$ATE = E\{Y_i(1) – Y_i(0)\}$$ 这是因为实验组是随机抽样,个体进入实验组与否和Y是独立不相关,即Wi和Yi正交,如下面推导所示: $$ ATE = E\{Y_i(1)\} -E\{Y_i(0)\} \\ = E\{Y_i(1) \mid W_i =1\} -E\{Y_i(0)\mid W_i=0\} \\ = E\{Y_i \mid W_i =1\} – E\{Y_i \mid W_i=0\} $$ 所以ATE是可以通过随机化,从由观测的数据估计出来。...

March 30, 2022 · Skyan

数据可视化指南(系列之三)

可视化 作为数据分析的一个重头戏,数据可视化被称为数据分析的半壁江山一点不为过,当然另外半壁就是统计学。 数据可视化将枯燥的并不直观的一维统计数字,直接通过二维甚至三维图形的方式展现给人们。图像的信息含量远大于数字,使得人们可以直接发现数据的趋势,找到异常点,甚至洞察更深层次的规律。 数据可视化并不是简单的用Excel画个线图或者柱状图就可以搞定,事实上,数据可视化属于一门严格的统计学方向「探索性数据分析」,这是由美国著名统计学家John. W. Tukey于1977年首创,借助图形对数据进行探索性分析的方法。美国统计学家Wilkinson于2005年给出了一个很好的数据可视化框架,它直接导致了R包ggplot2的发明,并影响了世界上最好的数据可视化软件之一Tableau。所有这一切历史其实想说明,数据的可视化并不是想当然地画图,而是需要对所要解决的问题和适合表达的图形有非常明确的认识和理解,才能真正发挥数据可视化的潜力,开发出统计图形的价值。 用于数据可视化的图形的种类其实有多种多样,我们需要首先了解每种分类,以及适合的分析场景。如下表所示: 变量(度量)个数 分析目标 图形名称 图形样例 使用场景 一个 不同类别下数据展示 条形图 在各类别之间比较数据,一个坐标轴是维度,另一个坐标轴是度量。表示在维度的不同维度值下,度量的大小情况。 条形图还可以叠加更多维度拆解,例如在每个类别下继续按照另一个维度类型拆解,查看更细粒度的指标情况 一个 数据的统计分布 直方图 展示连续数据分布最常用的工具,它本质上是对密度函数的一种估计。通过将连续度量的值分组为数据桶,来观察数据的分布规律 一个 数据分位点分布 箱线图 主要是从四分位数的角度出发 描述数据的分布,它通过最大值,上四分位数,中位数,下四分位数和最小值五处位置来获取一维数据的分布概况。通过每一段数据占据的长度,我们可以大致推断出数据的集中或离散趋势(长度越短,说明数据在该区间上越密集,反之则稀疏)。 一个 数据在不同类别下的占比 饼图 每一个扇形的角度与相应数据的数值大小成比例,但实际上通过饼图来查看不同类别占比的差别并不是很直观,有时还不如条形图直观 一个 数据在不同地理位置之间的分布 地图 展示和地理位置有关的数据分布关系时,最合适的工具 一个 数据随着时间的趋势变化 折线图 将视图中的各个数据点连接起来。折线图为直观显示一系列值提供了一种简单方法,适合显示数据随时间变化的趋势,或者预测未来的值。 一个 数据随着时间的趋势变化以及按维度拆解 面积图 和折线图类似,只是将折现下方的区域按照不同类别维度填色,展示各类别随时间变化的趋势 二个 两个变量之间的相关关系 散点图 散点图通常用来展示两个变量之间的关系,这种关系可能是线性或非线性的。图中每一个点的横纵坐标都分别对应两个变量各自的观测值,因此散点所反映出来的趋势也就是两个变量之间的关系。 二个 两个变量之间的相关关系 热图 热图用矩阵表示两个变量之间的相关关系,同时将单元格数值用颜色表达,如颜色深表示数值大。跟进一步,热图还可以表达聚类关系,即在颜色图的边界区域加上聚类的谱系图,这样可以同时观测数值分布和聚类的结果 二个 两个变量之间的相关关系 密度图 在散点图的基础上,通过颜色进一步突出相关关系,以及热点区域 三个 三个变量之间的关系 三维透视图 通过三维透视的形式,将三个变量变成三个维度,直接展示三者之间的关联。但三维图容易受到视角变化的影响,因此需要不断调整视角观测到真实的规律 三个 三个变量之间的关系 等高线图 将三维透视图的等高线展示在二维图像上,这样视角更广,不用担心视角的问题 多个(>=3) 三个甚至更多变量之间的关系 散点图矩阵 散点图的高维扩展,只是将多个变量的两两散点图以矩阵的形式排列起来,就构成了所谓的散点图矩阵。它从一定程度上克服了在平面上展示高维数据的困难,对于查看变量之间的两两关系非常有用。 在正式画图之前,我们还需要区分度量(变量)和维度的概念,这为我们能画出正确的图形奠定基础。 度量:也叫变量,是指我们需要分析,观察的对象。例如:展现次数,点击次数,点击率,时间,这些都是度量,都是我们需要观察的变量。变量可以是离散的,例如次数,个数,也可以是连续的,例如点击率,出价,时间等。度量可以是累加型的,例如点击次数,交易总量,也可以是非累加型的,例如去重用户数,点击率等。 维度:是指在变量值可以进一步拆解的类别。例如用户类型,设备型号,地域等,这些都是维度。维度是用来拆解度量的,一般是离散值。度量在维度的不同维度值下按照不同的聚合逻辑进行聚合。例如点击次数是相加,去重用户数是去重计数。 下面我们以常用的直方图和散点图为例,介绍统计意义的数据可视化是如何应用的。下面可视化软件用的Tableau,大家也可以用python的matplotlib库或者R语言的ggplot2库编程实现,MS Excel不推荐使用,主要是Excel对于复杂的图形难以满足要求。...

March 10, 2022 · Skyan

Numpy & Pandas入门(系列之二)

背景和环境搭建 Numpy和Pandas是目前最为流行的数据分析工具之二,基于Python语言开发。Numpy偏向数值计算,Pandas偏向数据分析,底层也是基于Numpy数据结构。两者结合可以完成一系列令人眼花缭乱的数据分析任务,并在机器学习,统计分析,因果推断等领域得到广泛应用。 作为入门,首先需要搭建开发环境。这里建议直接采用miniconda+VS Code的方式搭建,简单高效,步骤如下: 打开miniconda,找到适合自己操作系统的安装包,安装miniconda 国内环境推荐使用清华的conda和pip镜像,参考pypi镜像 和anaconda镜像 打开命令行,运行conda install pandas numpy 打开vscode官网,安装VS Code 打开VS Code,安装Python,Jupyter插件 在VS Code打开Command Palette (⇧⌘P) ,运行Jupyter: Create New Jupyter Notebook 命令 然后就能看到一个Jupyter Notebook,选择Python环境为刚才安装minicoda所在的位置 一个基本Python环境已经搭建好了, 之后就可以愉快的开发了,注意保存代码 在开发之前,需要先学习下narray,Series和Dataframe这几个基本的数据结构,搞懂这几个数据结构以及对应的计算模式,开发代码就会更加高效和方便。 所有的运算就基于这三个数据结构来做运算,计算过程类似矩阵或者集合的运算。编程的范式和传统的过程式编程有区别,不再是线性的执行顺序,而是集合和集合之间的关系运算。 例如,我们经常写foreach循环遍历数组中每一个元素进行运算,但用numpy就不需要,因为它直接提供了各种数组间运算的函数。再比如我们想将数据按照维度的聚合计算,对于pandas而言直接调用groupby函数即可。 下面分别介绍这三种基础数据结构。 narray narray是numpy的基础数据结构,它本质上是有一个多维数组,1维的就是一个数组array或者向量vector,2维是一个矩阵matrix,3维甚至更高维就是一个张量tensor。所以这个“n”代表维度,narray全称也就是“N-dimensional array”。 一个narray如下所示,一个维度称为一个axis。下面这个narray有两个axes,第一个axis长度为2,第二个axis长度为3。 >>> import numpy as np >>> a = np.array([[1, 2, 3, 4], [5, 6, 7, 8]]) >>> a [[1, 2, 3, 4], [5, 6, 7, 8]] 需要时刻记住,narray对应的是一个多维数组,如下图所示: numpy提供了一系列方便创建narray的函数,如下所示: >>> np.zeros(2) array([0., 0.]) # 0数组 >>> np....

February 20, 2022 · Skyan