譯者 | 李睿

審校 | 重樓

本文對(duì)垃圾回收進(jìn)行介紹，其中包括垃圾回收算法的概述，以及垃圾回收是如何在一些流行的編程語言(包括Java和Python)中實(shí)現(xiàn)的。在討論這個(gè)問題之前，首先考慮垃圾回收機(jī)制的優(yōu)點(diǎn)和缺點(diǎn)。為什么它是內(nèi)存分配錯(cuò)誤的常見解決方案？以下從不使用垃圾回收的C和C++等語言中內(nèi)存管理的風(fēng)險(xiǎn)開始。

C/ C ++中內(nèi)存管理的風(fēng)險(xiǎn)

內(nèi)存分配問題只是C/C++常見問題的一個(gè)子集，這些問題會(huì)導(dǎo)致潛在的錯(cuò)誤和漏洞，但它們是一個(gè)很大的子集，很難追蹤和修復(fù)。內(nèi)存分配錯(cuò)誤包括以下場景：

• 未能釋放已分配的內(nèi)存，最終可能會(huì)耗盡系統(tǒng)中的所有內(nèi)存，不僅會(huì)使程序崩潰，還會(huì)使計(jì)算機(jī)崩潰。
• 在釋放內(nèi)存之后，嘗試通過指針讀取或?qū)懭刖彌_區(qū)，可能會(huì)產(chǎn)生隨機(jī)結(jié)果（也稱為懸空指針）。
• 雙重釋放內(nèi)存塊，這可能會(huì)導(dǎo)致內(nèi)存管理器崩潰，最終導(dǎo)致程序甚至整個(gè)系統(tǒng)崩潰。

其他常見的C/C++漏洞包括緩沖區(qū)溢出和字符串操作，它們可以用數(shù)據(jù)覆蓋代碼?！坝腥ぁ钡牟糠质蔷W(wǎng)絡(luò)攻擊者對(duì)數(shù)據(jù)進(jìn)行處理，使其成為惡意可執(zhí)行代碼，然后設(shè)法運(yùn)行代碼。

很多人說這種情況不會(huì)再發(fā)生了，因?yàn)樵诒Ｗo(hù)模式系統(tǒng)中有單獨(dú)的代碼和數(shù)據(jù)段。不幸的是，這種情況仍然會(huì)發(fā)生。例如，一個(gè)程序在字符串中構(gòu)造SQL語句，然后將其發(fā)送到數(shù)據(jù)庫執(zhí)行，這通常會(huì)創(chuàng)建SQL注入漏洞。當(dāng)然，在避免SQL注入漏洞方面有一些良好的記錄的最佳實(shí)踐，但是在數(shù)據(jù)庫客戶端中不斷出現(xiàn)這類錯(cuò)誤，表明不是每一位程序員都會(huì)遵循最佳實(shí)踐。

垃圾回收：具有缺陷的糾正方法

使用垃圾回收可以完全消除主要的內(nèi)存分配和回收問題，但這是有代價(jià)的。最大的問題是垃圾回收器的開銷；當(dāng)垃圾回收器運(yùn)行時(shí)出現(xiàn)不可預(yù)測的暫停；并且當(dāng)服務(wù)器進(jìn)程停止時(shí)增加了延遲。后一個(gè)問題經(jīng)常出現(xiàn)在基于Java的服務(wù)器程序中。

垃圾回收的開銷可能很大，涉及內(nèi)存和性能之間的權(quán)衡。開發(fā)人員Matthew Hertz和Emery D.Berger在2005年發(fā)表的一篇論文指出：“具有五倍內(nèi)存的蘋果風(fēng)格的分代回收器具有非復(fù)制的成熟空間，與基于訪問的顯式內(nèi)存管理的性能相匹配。而如果只有三倍的內(nèi)存，回收器的運(yùn)行速度比顯式內(nèi)存管理平均慢17%。然而，如果只有兩倍的內(nèi)存，垃圾回收的性能降低了近70%。當(dāng)物理內(nèi)存不足時(shí)，分頁導(dǎo)致垃圾回收的運(yùn)行速度比顯式內(nèi)存管理慢一個(gè)數(shù)量級(jí)?！?/span>

蘋果風(fēng)格的分代回收器是保守的垃圾回收器，更具攻擊性的垃圾回收器有時(shí)可以用更少的內(nèi)存表現(xiàn)得更好。

停滯和延遲意味著基于垃圾回收的語言對(duì)于需要最小化延遲的實(shí)時(shí)程序和高吞吐量服務(wù)器來說可能不是最優(yōu)的。例如，在實(shí)時(shí)Lisp和實(shí)時(shí)Java方面已經(jīng)有了一些嘗試，所有這些嘗試都修改或消除了垃圾回收器。

最近，一些Java和Scala服務(wù)器采用非垃圾回收的編程語言進(jìn)行了重寫，例如Scylla（用C++重寫Cassandra）和Redpanda（用C++替換Kafka插件）。在“Scylla”和“Redpanda”中，與最初的服務(wù)器相比，已經(jīng)顯著減少了延遲。對(duì)于相同的負(fù)載，兩者都需要更小的集群。

垃圾回收算法

垃圾回收有幾十種算法，以下來看看一些最重要的算法及其顯著特征。

引用計(jì)數(shù)

在引用計(jì)數(shù)中，程序?qū)?duì)資源的引用、指針或句柄的數(shù)量存儲(chǔ)為分配資源的一部分，并在添加或刪除引用時(shí)增加或減少計(jì)數(shù)。當(dāng)引用計(jì)數(shù)為零時(shí)，資源可以被釋放。內(nèi)存垃圾回收只是引用計(jì)數(shù)的應(yīng)用之一；它也用于系統(tǒng)對(duì)象、Windows COM對(duì)象和文件系統(tǒng)塊或文件的釋放控制。

引用計(jì)數(shù)有兩個(gè)主要的缺點(diǎn)：過于頻繁的更新和循環(huán)引用。控制更新頻率的一種方法是允許編譯器對(duì)相關(guān)對(duì)象進(jìn)行批處理。處理循環(huán)引用的一種方法是不定期運(yùn)行跟蹤垃圾以刪除不可訪問的循環(huán)，循環(huán)引用使計(jì)數(shù)不會(huì)達(dá)到零。

跟蹤垃圾回收

跟蹤垃圾回收是引用計(jì)數(shù)的主要替代方案，包括以下所有算法以及更多的算法。通常跟蹤垃圾回收的思想是，跟蹤過程從一些根對(duì)象(如當(dāng)前局部變量、全局變量和當(dāng)前函數(shù)參數(shù))開始，并根據(jù)引用確定哪些對(duì)象是可訪問的，然后對(duì)所有無法訪問的對(duì)象進(jìn)行垃圾回收。跟蹤垃圾回收是如此普遍，有時(shí)簡單地稱之為垃圾回收。

標(biāo)記和掃描

1960年發(fā)布的“na?ve”標(biāo)記和掃描算法可以追溯到John McCarthy開發(fā)的Lisp編程語言，它的工作原理是首先凍結(jié)系統(tǒng)，然后將從根集中可訪問的所有對(duì)象標(biāo)記為“正在使用”。第三步是清除所有內(nèi)存并釋放未標(biāo)記為“正在使用”的任何塊。最后，清除所有剩余內(nèi)存塊中的“正在使用”位，為下一次回收做準(zhǔn)備，并允許系統(tǒng)繼續(xù)執(zhí)行。顯然，這對(duì)于實(shí)時(shí)系統(tǒng)是不合適的。

標(biāo)記和掃描的一種變體使用了三種“顏色”的內(nèi)存塊：白色塊是不可訪問的，如果算法結(jié)束時(shí)它們?nèi)匀辉诎咨现?，則將釋放它們；黑色塊可以從根訪問，并且沒有對(duì)白色集合中的對(duì)象的外向引用；灰色塊可以從根訪問，但還需要掃描對(duì)“白色”對(duì)象的引用。在算法完成后，灰色塊全部進(jìn)入黑色集合。通常情況下，初始標(biāo)記將根引用的所有塊放入灰色集合中，將所有其他塊放入白色集合中。

三色標(biāo)記算法分為三步：

（1）從灰色集合中選擇一個(gè)對(duì)象，并將其移動(dòng)到黑色集合中。

（2）將其引用的每個(gè)白色對(duì)象移動(dòng)到灰色集合。這確保了該對(duì)象及其引用的任何對(duì)象都不能被垃圾回收。

（3）重復(fù)最后兩個(gè)步驟，直到灰色集合為空。

當(dāng)灰色集合為空時(shí)，所有白色塊都可以釋放。三色標(biāo)記算法可以在程序運(yùn)行時(shí)在后臺(tái)執(zhí)行;開銷仍然存在，但它不會(huì)讓“整個(gè)世界停止”。

復(fù)制回收

復(fù)制回收(又名半空間垃圾回收)的思想是將內(nèi)存分為兩個(gè)大小相等的區(qū)域，分別稱為“從空間”和“到空間”。在空間中按順序分配內(nèi)存塊，直到空間填滿，然后執(zhí)行回收。這交換了區(qū)域的角色，并將活動(dòng)對(duì)象從“從空間”復(fù)制到“到空間”，在“到空間”的末尾留下一塊空閑空間(對(duì)應(yīng)于所有不可訪問對(duì)象使用的內(nèi)存)。

復(fù)制回收存在復(fù)雜性。最大的一個(gè)問題是，當(dāng)復(fù)制數(shù)據(jù)塊時(shí)，它們的地址會(huì)發(fā)生變化；一種解決方案是維護(hù)轉(zhuǎn)發(fā)地址表。另一個(gè)主要問題是，復(fù)制集合所需的內(nèi)存是標(biāo)記和掃描所需內(nèi)存的兩倍。如果大部分內(nèi)存是垃圾，復(fù)制回收比標(biāo)記和掃描要快，但如果大部分內(nèi)存可訪問，則復(fù)制回收較慢。

標(biāo)記和壓縮

標(biāo)記和壓縮回收的本質(zhì)是復(fù)制在單個(gè)內(nèi)存空間內(nèi)運(yùn)行的回收。標(biāo)記和壓縮回收器掃描所有可訪問的對(duì)象，并將它們壓縮在堆的底部，這使得堆的頂部可供使用。標(biāo)記和壓縮回收的最大缺點(diǎn)是比較耗時(shí)。

分代回收

分代回收根據(jù)對(duì)象的年齡(也就是代)將堆劃分為多個(gè)空間(通常是兩個(gè)或三個(gè))。一般來說，最近的對(duì)象比舊的對(duì)象更可能是垃圾，因此在大多數(shù)情況下掃描新對(duì)象以尋找垃圾，而不使用舊對(duì)象是有意義的。一些分代回收器在不同的代上使用不同的掃描頻率或回收算法。

哪些編程語言使用垃圾回收?

自從John McCarthy在1958年開發(fā)Lisp編程語言以來，Lisp就一直在用于垃圾回收。Java、Scala、Python和.Net/C#都是流行的垃圾回收語言。其他垃圾回收語言包括相對(duì)年輕的Go、Ruby、D、OCaml和Swift，以及較老的語言Eiffel、Haskell、ML、Modula-3、Perl、Prolog、Scheme和Smalltalk。

Java、Python和.Net/C#是一些比較流行的實(shí)現(xiàn)垃圾回收的編程語言。Java虛擬機(jī)(JVM)實(shí)際上提供了四種不同的垃圾回收器：串行、并行、并發(fā)標(biāo)記、掃描，以及第一個(gè)垃圾回收器G1GC。G1GC現(xiàn)在是Java中的默認(rèn)值，它是一個(gè)區(qū)域化和世代并行壓縮收集器，可實(shí)現(xiàn)軟實(shí)時(shí)目標(biāo)。

Python（特別是標(biāo)準(zhǔn)的CPython實(shí)現(xiàn)）將引用計(jì)數(shù)與僅專注于清理容器對(duì)象的三級(jí)代收集相結(jié)合。.NETCLR（公共語言運(yùn)行時(shí)）使用三級(jí)生成標(biāo)記和緊湊收集算法。CLR還將內(nèi)存對(duì)象分為兩個(gè)堆，一個(gè)用于大型對(duì)象（85000字節(jié)或更高），另一個(gè)用于小型對(duì)象；大型對(duì)象堆通常不會(huì)被壓縮，只是被標(biāo)記和掃描，但如果需要可以被壓縮。

結(jié)論

正如人們所看到的，處理垃圾回收的方法有很多，其中大多數(shù)都有自己的用途。更成熟的垃圾回收實(shí)現(xiàn)結(jié)合了多種算法，并且多年來進(jìn)行了大量調(diào)優(yōu)，以盡量減少延遲。

原文標(biāo)題：What is garbage collection? Automated memory management for your programs，作者：Martin Heller