ACM通信
实践
GitHub上的静态分析
图片来源:Andrij Borys Associates;Git-SCM.com
GitHub是一个建立在Git版本控制系统之上的代码托管网站，托管着超过6500万开发人员上传的数亿代码库。GitHub的语义代码团队构建并运行一套技术，支持github.com上的符号代码导航。符号代码导航让开发人员在源代码中点击一个命名标识符来导航到该实体的定义，反之亦然:给定一个标识符，他们可以列出该标识符在项目中的所有用途。
该系统由云对象存储服务支持，从一个tb分片关系数据库迁移而来，每分钟处理超过40000个请求，包括读写操作。静态分析阶段本身构建在一个名为Tree-sitter的开源解析工具包上，实现了一些著名的计算机科学研究，并与github.com基础设施集成，以便从源代码中提取名称绑定信息。
该系统支持9种流行的编程语言，覆盖600万个存储库。将即使是最微不足道的程序分析扩展到这个级别也需要大量的工程工作，这里详述了这一点，希望它能够为那些将静态分析扩展到大型且快速变化的代码库提供有用的指导。
动机:从森林中寻找(解析)树
导航代码是阅读、编写和理解程序的基本部分。Unix工具，例如grep (1)允许开发人员搜索文本模式，但程序员的需求范围更大:他们最感兴趣的是程序的各个部分是如何连接在一起的——给定一个函数，在哪里调用它，在哪里定义它?对这些查询的快速和高质量的回答使程序员能够建立程序结构的心理模型;这反过来又允许进行有效的修改或排除故障。像grep这样仅限于文本匹配且不了解程序结构的工具通常提供的信息太少或太多。
流畅的代码导航也是研究bug的宝贵工具。错误报告系统中的堆栈跟踪开始尝试理解导致错误的程序的状态;象征性地导航代码可以减轻理解上下文中代码的负担。因此，大多数集成开发环境(ide)都广泛支持代码导航和其他静态分析，从而减轻用户的负担。
语义代码团队想把这种ide风格的符号代码导航带到github.com上。该团队的灵感来自于单一用途的网站，例如source.dot.net， Mozilla和Chromium代码搜索，提供全面的浏览器内代码导航。问题是如何大规模地做到这一点:GitHub为超过6500万的开发者提供服务，为370种编程语言的2亿多个存储库做出贡献。仅在过去的12个月里，github.com上就有22亿的捐款。这需要大量的代码和更改。
哲学:树或不树
语义代码团队实现代码导航的方法围绕以下核心思想。
- 零配置。终端用户不需要做任何设置或配置来利用代码导航，除了将代码推送到GitHub。没有设置、定制或可选择的特性—如果支持存储库的语言，它就应该可以工作。这对于这个特定的用例来说是至关重要的，因为如果你在GitHub上用支持的语言查看源代码文件，期望代码导航应该只是工作。如果每个开源项目都必须做一点额外的工作来配置它的repo或建立一个构建来发布这些信息，那么在GitHub上浏览代码的体验将会因项目的不同而发生巨大的变化，并且推送和能够使用代码导航之间的时间可能取决于缓慢而复杂的构建过程。
仅仅要求开发者克隆并运行他们自己的IDE是不够的(或者等待浏览器内的IDE，如GitHub Codespaces加载);开发人员希望能够快速阅读和浏览代码没有必须下载该代码及其相关工具。要让这个特性扩展并服务于所有GitHub，它必须在任何地方和每个项目中都可用。这样做的目的是让开发人员专注于他们的程序和他们试图解决的问题，而不是配置GitHub来正确地与他们的项目一起工作，或者说服其他项目所有者进行正确的设置。
- Incrementality。对于推送到存储库的每个更改，后端处理应该只对更改的文件进行处理。这与建立持续集成工作流不同，在持续集成工作流中，用户可能特别想要一个可重复构建的新环境。它还暗示，在按秒而不是分钟的顺序推送之后，搜索结果将会更快地显示出来。等待整个构建周期来显示代码导航数据对于期望的用户体验来说是行不通的;开发人员希望导航特性能够跟上他们的变化。
- 语言不可知论。不管分析的语言是什么，都应该运行和操作相同的后端处理代码。因此，团队决定不运行特定于语言的工具，例如针对c#的Roslyn项目或针对Python的Jedi项目，因为这将需要针对每种语言(有时针对每种语言的每个版本)操作不同的技术栈。
尽管这意味着语言语法可能接受给定语言的超集，但这种哲学可以更快地扩展和交付结果。该基础设施可以运行单个代码栈，不需要管理多个容器和相关的资源成本，不存在启动工具的冷启动时间，也不需要尝试检测项目的结构、配置或目标语言版本。
这也意味着分析的主要方面可以在一个地方实现，提供诸如机器可读语法和树查询语言之类的抽象。在一种编程语言能够在其他技术栈中启用之前，只有某些特定的东西必须被开发出来。
- 进步的忠诚。结果足够好难道就不该等那一天到来吗完美的。该系统的设计是为了随着时间的推移，它产生的结果可以得到完善和改进。该团队并没有试图为所有GitHub上的所有语言构建并展示一个完美的系统，而是选择了渐进式的改进:逐个添加语言，并通过进一步的技术投资来改善导航结果。
- 人类的合作。伟大的软件工具可以增强和补充人类的能力。在这种情况下，GitHub的语义代码团队想要促进阅读、编写和理解软件的过程，并且以这样一种方式，开发人员可以用他们最关心的语言为工具做出贡献。系统应该在最大程度上避免软件开发的封闭花园模型，因为语言社区经常准备并愿意修复与他们选择的语言有关的错误和疏忽。
方法:标记ast
GitHub代码导航特性是建立在静态分析基础上的标记分析。标签分析查看函数、变量和数据类型的定义和用法，将它们整理成适合查看给定实体的定义的格式，并全面查询代码库以确定使用该实体的所有地方。
这个分析是由一个名为ctags，由Ken Arnold开发，并于1979年作为BSD Unix 3.0的一部分发布。顾名思义，ctags只支持C语言编程;尽管如此，它还是立即获得了成功，并最终被纳入到单一Unix规范中。进一步的后裔ctags增加了对更多编程语言的支持，现在绝大多数文本编辑器和ide都提供了支持ctags集成。虽然标签分析是微不足道的，与静态程序分析的艺术状态相关，但在GitHub的规模和GitHub的分布式架构中实现这样的分析却不是。
Tree-sitter。任何类型的静态分析的第一步都是将文本源代码解析为机器可读的数据结构。这是通过使用解析器生成器工具和增量解析库生成具体的语法树来实现的。
Tree-sitter允许为编程语言指定语法，然后生成解析器，这是一个无依赖的C程序。给定一个解析器和一些源代码，系统生成该源代码的语法树。标记代码的行为需要遍历树并执行筛选映射操作。使用类似于s表达式的DSL(特定于领域的语言)，tree -sitter提供树查询，允许指定在语法树中匹配哪些节点(例如，表示函数名称的标识符)。tree -sitter生态系统中的工具允许快速迭代语法开发和树匹配，使得快速支持新语言语法或识别用于代码导航的新结构成为可能。
“树坐者”理论借鉴了几个学术研究领域，但最突出的是广义LR (GLR)解析。GLR算法是众所周知的LR(从左到右派生)解析算法的扩展，它可以处理现代编程语言中常见的歧义或不确定语法。现实世界的语言使用许多不同的解析算法:Python使用LL(1)算法，Ruby使用LALR, GCC (GNU Compiler Collection)项目使用定制的递归下降解析器。GLR算法由Bernard Lang于1974年提出，1984年由Masaru Tomita实现，具有足够的灵活性来解析所有这些语言;依赖于像LR(1)这样不那么复杂的算法会有太多的限制，因为这样的解析器仅限于在输入中查找一个标记(请参阅侧栏了解更多信息)。
标签树。下一个挑战是对解析树进行一些基本分析。首先，团队决定仅根据已知语法结构的标识符提供简单的名称绑定信息。这最初是作为一个原型设计的，但它运行得非常好，在开始进一步改进的时候就发布了。
基本的想法是:
- 解析源文件。
- 遍历解析树，捕捉特定语法结构(如函数定义)的标识符。
- 保留这些标记的数据库表，以及它们在原始源代码中出现的行/col等信息，以及标识符是某个东西的定义还是引用(例如，函数调用将是引用)。
事实证明，对于许多语言来说，这个名称绑定信息本身就提供了一种引人注目的产品体验。它并不完美，但相对于完全没有任何信息的情况，这是一个很大的改进，因此该团队使用这个原型来充实生产规模的系统，同时研究如何提高结果的精度。
要遍历解析树，使用tree -sitter对查询的支持就足够了。通过使用s表达式语法指定包含有用标识符信息的语法节点类型的结构，遍历解析树只能生成指定的节点。所示图1，给定在Ruby中标识方法定义的用例，将解析一小段定义添加方法的Ruby代码。
图1。一个解析和标记Ruby代码的示例。
图2。索引器序列。
在更复杂的情况下，tree -sitter树查询可以在查询操作期间维护自定义状态。这对于Ruby这样的语言非常重要，因为它在变量和不带参数调用的函数之间没有语法上的区别。为了产生有用的结果，必须记录给定Ruby作用域中任何局部变量的名称，这可以消除语法上的歧义。
实现:体系结构
GitHub的代码导航管道是建立在开源软件和标准之上的:
- Apache卡夫卡。用于处理高吞吐量数据流(如提交到存储库)的平台。流中的单个数据是消息。
- Git。分布式版本控制系统。程序员将更改上传到GitHub上的代码库中。每个更改都会影响存储库中的一个或多个文件(称为blob)。对一个或多个blobs进行更改的单位称为提交，而上载一个或多个提交的行为称为推(push)。一旦提交被推送，其他程序员就可以看到并将这些提交合并到他们计算机上的存储库副本中。程序员可以通过针对一个分支(一个命名的提交集合)上传他们的代码，而不影响其他人。Git项目从一个单独的分支开始，通常称为“main”，然后通过直接推提交或通过检查和集成其他人的更改(拉请求)来更改它。Git存储库中的实体根据SHA-1哈希算法被赋予一个唯一的标签。
- Kubernetes。Kubernetes是一个用于部署和操作应用程序服务的编排系统，它提供了pods(独立的计算单元)，可以在上面部署一个或多个给定应用程序的副本。
- 语义。一个来自GitHub的开源程序分析工具。
- Tree-sitter。这个解析工具包构建在GLR算法之上，生成能高效解析源代码的代码:解析行为将人类可读的源代码文本表示转换成树状数据结构，通常称为语法树，适合机器使用和分析。
- 可鄙的人。Twirp是一个RPC(远程过程调用)标准，它定义了系统中实体可以通信的方式。
该系统由部署在Kubernetes上的三个独立服务组成，它们与github.com上的Ruby on Rails应用程序(由于其规模和复杂性，被亲切地称为“巨石”)集成在一起索引器使用Kafka消息进行git推送，并编排解析、标记和将结果保存到一个提交SHA的特定存储库的过程;的薄铁片是一种服务，它接受原始源代码内容，解析并标记这些代码，并返回结果;的查询服务提供了一个Twirp RPC接口到符号数据库，允许github.com的前端查找定义和引用。
图2显示各种索引器序列组件之间的关系。
图2。索引器序列。
索引。开发人员通过推送Git或通过网站界面编辑文件的方式将代码上传到GitHub。当收到一个新的推送时，GitHub服务器会发送一个消息给Kafka，描述关于这个推送的元数据(项目位置，变更作者，目标分支)。该系统运行一个Kubernetes pods池，分布在多个集群和物理数据中心，侦听这些消息。由于消息是根据存储库的惟一标识符跨pods池分布的，因此给定的pod通常会反复使用相同存储库的消息，从而允许在索引管道中进行有效的本地缓存。
当消息被使用时，索引器进程将它们聚合起来，确保在一个时间窗口内推送到相同存储库的消息被作为一个请求处理。它随后过滤掉无效消息;由于规模的原因，push只被索引到默认分支;它们必须只涉及系统支持的编程语言。然后,它油门索引的速度，这样初始索引就可以在后续的推送被处理之前完全完成。Kafka记录给定的消息何时被传递去处理，同时处理的上限放置反压力在卡夫卡。这意味着在容量超载的情况下，索引器将不会尝试使用太多消息，从而在系统中提供弹性和弹性。
在处理推送时，索引器将存储库浅克隆到临时目录。聚合阶段意味着单个下载可以在未来的索引中重用。
索引涉及到确定在分析变更时库中的哪些git blob没有被索引。blob的OID(对象标识符)是其内容的SHA-1哈希值;这个标识符可以很容易地用于跟踪需要处理的文件。没有更改的blob在提交之间共享，不需要额外的工作，但会记录特定提交中可达的路径集和blob。
对于确实需要解析和标记的blob，索引器调用在另一组pods上运行的单独服务。这种分离的原因是，并不是每个推送都代表相同数量的解析工作。需要处理的文件可能在1到2万个之间。索引器的工作负载主要是I/ o绑定的:等待套接字(对于Kafka，数据存储，repo克隆)和对文件系统的读写。然而，解析主要是计算绑定的，因此拥有一个独立的pod池(请求在其中进行负载平衡)意味着资源可以适当地伸缩，并且系统不会遇到使用单个索引器pod的情况热这是处理大型或活动存储库的结果。
该系统每天部署数十次，它通过停止任何新的Kafka消息的消耗，允许飞行索引在30秒的窗口内完成处理，并中止和重新排队任何不能在该窗口内完成的索引，优雅地处理这些部署。由于对每个git blob的处理都是递增的，因此获取该消息的新pod必须只解析和标记那些在初始运行期间没有完成的blob。
查询。当标签结果被完全处理后，它们被存储在一个数据库中，连同足够的信息来服务于未来的查询:对于提交Y的存储库X喷火定义?该系统提供了几个Twirp RPC(远程过程调用)端点，允许github.com前端用户界面根据用户的交互和上下文查找定义和引用。在过去，团队选择的数据库是一个大型MySQL实例，通过Vitess(一种MySQL分片技术)跨多台机器进行分区。在撰写本文时，标记数据存储在Microsoft Azure Blob Storage中，这是一个支持上传文件的云存储系统。
图3显示各种查询序列组件之间的关系。
图3。查询序列。
操作的旅程
该系统的第一个原型使用ctags命令行工具的直接调用ctags将产生的标记转储到与已标记存储库相关联的Git存储中，并且在每次推入该存储库时都尝试这样做。这对于演示版本来说很棒，但却不适合大规模运行:Git存储服务器的CPU资源非常昂贵;多个推到多个裁判使管理标签文件具有挑战性;在这些服务器上处理查找请求并不理想。Ctags不具备利用Git数据结构所需的API，并且不容易使用命令行程序，使其操作可以由Web服务提供。
输入Tree-sitter。当语义代码团队接手项目时，下一个迭代使用Tree-sitter而不是ctags但是大部分的索引逻辑还是在github.com的Ruby on Rails应用程序中实现的。在推送时排队，用Ruby编写的索引作业用于通过内部RPC获取Git内容，检测源文件的语言，过滤不相关的内容(例如，二进制文件，不支持的语言的代码)，调用服务进行解析/标记，并保存结果标记。一个专用的MySQL数据库用于存储和检索标记数据，查询路径实际上是从Rails控制器直接到这个数据库的。
这解决了一组特定的问题，并证明了Tree-sitter解析器和初始名称绑定分析可以将解析/标记作为一种服务提供，便于语法迭代和解析计算工作负载的横向扩展。最重要的是，这个原型让领导层相信，这是一组值得构建的功能，它以一种有意义的方式增强了GitHub的体验。它还表明我们有一个扩展计划，支持GitHub上的所有存储库，并支持新语言。
从巨石中出来。下一个迭代离开了github。com Ruby on Rails应用程序，有以下几个原因:
- GitHub中的工作架构不太有弹性，并且有“尝试一次，尽最大努力”的语义，这导致了不可靠性。此外，这些操作还会导致worker与GitHub上正在处理的无数后台任务(如webhooks、发送电子邮件和更新pull request)共享大量的资源争用。
- 随着添加了更多的存储库、用户和语言，标记数据库的增长削弱了扩展的能力。这很快成为GitHub上最大的MySQL实例之一。
从工程组织的角度来看，在主要的Ruby on Rails应用程序代码库中工作是缓慢的，并伴随着许多限制。如今，GitHub主要部署管道的许多部分都已经简化了，但在那个时候，部署一个pull请求可能需要一天以上的时间。为了应对这些挑战，我们增设了以下服务:
- 解析/标记服务的重写，使用GitHub的开源语义语言工具包。
- indexer服务使用来自Kafka的推送信息，克隆和解析存储库，并将结果插入到专用的MySQL数据库中。
- 执行数据库查找并将结果返回给Ruby on Rails应用程序的查询服务。
这些模式在相当长的一段时间内很好地为系统服务，允许快速增长，发布了几种用于代码导航特性的新语言，并简化了开发和部署。
扩展MySQL。下一次迭代需要将数据库从单个MySQL实例迁移到一个由分区MySQL实例组成的水平分布式集群，由开源项目Vitess提供支持。迁移到Vitess带来了工程上的复杂性:团队需要编写新的模式，选择新的分片策略，并在这个集群中部署主MySQL和从MySQL实例。在此期间，团队从基于语义的标记服务迁移到完全使用(新开发的)Tree-sitter查询操作的服务。尽管Semantic执行得很好，但使用Tree-sitter查询语言允许更快的迭代，并避免了程序分析框架的操作开销。
移动到斑点存储。最近的一次迭代，以及在撰写本文时部署到github.com的一次迭代，导致了数据库格式的巨大变化。虽然vitss分片的MySQL数据库在理论上为水平扩展提供了重要的跑道(只需要添加更多的分片)，但一些新的约束也变得很明显:
- 钱。使用Vitess集群，在技术上对MySQL的水平扩展没有限制，但足够强大的硬件需要大量的前期和维护成本。虽然这些成本受到了仅对存储库的主分支进行索引的限制，但对所有GitHub上所有代码的所有分支进行解析的成本的预测是令人望而却步的。
- 并不是MySQL的所有特性都可以使用，特别是SQL的容量受到Vitess的限制，从而无法正确地对数据库进行分片。
- 对数据库的写操作的数量超过了MySQL:为了保持MySQL和Vitess的平稳运行，流量必须通过一个节流服务，这导致了索引器性能的显著瓶颈。对MySQL的写入是基于复制延迟进行节流的。当延迟(将主节点的写操作应用到副本的时间间隔)超过某个阈值时，索引器将退回插入操作。通常这些都是由不健康的硬件、配置差异或数据模式引起的临时问题(例如，开发人员在周一早上和假期后的1月份特别忙)。
虽然这种迁移主要与成本结构有关，但数据存储的变化也带来了一些有趣的性能好处。尽管在体系结构上，系统中的所有东西都保持不变:只是把写着“MySQL”的盒子换成写着“Azure”的盒子——这至少是当时的想法。
从工程组织的角度来看，在主要的Ruby on Rails应用程序代码库中工作是缓慢的，并伴随着许多限制。
在实践中，这涉及重大工作。团队不仅要同时维护旧的MySQL和新的Azure系统，而且还要为标签数据设计一个与Azure兼容的模式，该模式将允许存储库的增量索引和标签的查询，其性能与基于MySQL的系统大致相同。这意味着优化空间、时间和成本。(存储需要花钱，但每个操作也需要花钱:例如，读操作比写操作花费更少，而写操作比列表查询操作花费更少。)
数据存储设计。团队最终得到的存储结构如下，以类似文件系统的形式表示。整个路径结构包括一个前缀，以允许对数据存储进行主要的结构和格式更改。然后，每个存储库的数据都以其id为前缀(参见图4）.
图4。数据存储文件系统布局。
这个数据库内文件层次结构提供了对提供有用的代码导航信息所需的所有不同数据的访问。在建立索引期间，将适当的文件上载到blob存储中，用于分析中的回购。在查询时，存储库、提交SHA和符号名称提供了足够的信息来获取适当的文件并计算结果。所有文件都是不可变的。
符号名称由哈希前缀文件(图5)包含提交文件中共享存储为TSV的两个字符SHA1哈希前缀的所有符号名。这个前缀允许基于这个两个字符的前缀进行过滤，从而加速数据库查询。这是在进行符号查找以获得定义(D)或引用(R)符号的blob sha列表时读取的第一个文件。
图5。符号名称由哈希前缀。
提交文件的索引blobs (图6)表示一个提交已经建立了索引，并保存了提交中所有blob sha的映射，以及这些blob的路径。读取这个文件，并将blob sha与上一步的那些相交，给出一个要在后面的步骤中获取的blob列表。
图6。为提交创建索引团。
该文件包含一个头和两个TSV内容部分。报头给出每个部分开始的字节偏移量(从文件开始算起)。每个部分包含一行用于索引的每个路径。第一部分包含\ t字段，并按路径排序。这允许对特定路径进行二进制搜索，以在提交中找到它的blob SHA。第二部分中的行包含一个字段，它是第1部分中某一行的偏移量(从文件开始算起)。的部分图6按blob SHA排序，并允许对一组blob SHA进行二进制搜索，以找到它们在提交中出现的路径。
一个特定的git blob (图7)是符号查找的最后一步，提供返回到前端的信息。在此步骤中，许多定义查找都会导致读取单个文件。因为引用可以分布在多个文件中，所以读取是并行进行的，并且有一个上限。
图7。blob的所有定义和引用。
首先存储定义，以便在到达第一个引用时尽早返回查找操作。注意，由于这是blob内容的SHA1散列，一旦blob被解析，它就不需要再次解析，并且可以在任何包含该blob的提交之间共享。
其他文件用于快速判断某个分支或标记是否已被索引。refs /(头|标签)/ . tsv包含已建立索引的分支尖端的单个提交SHA。DEFAULT.tsv包含一个提交SHA和裁判默认分支的。
系统的每次迭代，甚至数据存储的每次迁移都是在完全的生产负载下进行的，对最终用户的影响最小甚至没有影响。blob存储更改显著节省了成本，增加了索引吞吐量，并略微减少了查询请求时间。
结论
生成的代码导航系统每分钟处理和索引超过1000次推送，并每分钟生成超过200万个新的标识符名称。p99 (99th百分位;也就是说，对于存储库的第一次索引，最慢的1%索引所花费的时间大约为60秒(50th百分位数约为1.1秒)。增量索引的p99为~10秒(p50为~1.3秒)。该系统每分钟处理3万个符号查找请求，p99请求次数大约为90毫秒。它支持9种语言:c#、CodeQL、Go、Java、JavaScript、PHP、Python、Ruby和TypeScript，以及许多其他正在开发的语法。
然而，我们了解到，规模——包括大量的用户、存储库、HTTP请求以及托管在github上的庞大代码库——是关于采用、用户行为、增量改进和实用的。特别是静态分析很难衡量人类行为;我们经常认为复杂的分析工具是用来发现代码中潜在的问题模式，然后试图说服人们来修复它们。我们的方法采取了不同的策略:使用基本的分析技术，快速地将增强我们理解程序的能力的信息放在每个阅读GitHub上代码的人面前，无需配置，并且在代码更改后几乎立即可用。其结果是在GitHub上阅读、导航、分享和理解代码的愉快体验。
数字图书馆是由计算机协会出版的。版权所有©2022 ACM股份有限公司
没有发现记录