有關 COW (CopyOnWrite) 的一切

語言: CN / TW / HK

概念

寫入時複製(英語:Copy-on-write,簡稱COW)是一種計算機 [程式設計]領域的優化策略。其核心思想是,如果有多個呼叫者(callers)同時請求相同資源(如記憶體或磁碟上的資料儲存),他們會共同獲取相同的指標指向相同的資源,直到某個呼叫者試圖修改資源的內容時,系統才會真正複製一份專用副本(private copy)給該呼叫者,而其他呼叫者所見到的最初的資源仍然保持不變。這過程對其他的呼叫者都是 [透明]的。此作法主要的優點是如果呼叫者沒有修改該資源,就不會有副本(private copy) 被建立,因此多個呼叫者只是讀取操作時可以共享同一份資源。

COW 已有很多應用,比如在。Linux 等的檔案管理系統也使用了寫時複製策略。

應用

Linux fork()

當通過 fork() 來建立一個子程序時,作業系統需要將父程序虛擬記憶體空間中的大部分內容全部複製到子程序中(主要是資料段、堆、棧;程式碼段共享)。這個操作不僅非常耗時,而且會浪費大量實體記憶體。特別是如果程式在程序複製後立刻使用 exec 載入新程式,那麼負面效應會更嚴重,相當於之前進行的複製操作是完全多餘的。

因此引入了寫時複製技術。核心不會複製程序的整個地址空間,而是隻複製其頁表,fork 之後的父子程序的地址空間指向同樣的實體記憶體頁。

但是不同程序的記憶體空間應當是私有的。假如所有程序都只讀取其記憶體頁,那麼就可以繼續共享實體記憶體中的同一個副本;然而只要有一個程序試圖寫入共享區域的某個頁面,那麼就會為這個程序建立該頁面的一個新副本。

如果是 fork()+exec() 的話,子程序被建立後就立即執行一個 executable,父程序記憶體中的資料對子程序而言沒有意義——即父程序的頁根本不會被子程序寫入。在這種情況下可以完全避免複製,而是直接為子程序分配地址空間,如下圖所示。

寫時複製技術將記憶體頁的複製延遲到第一次寫入時,更重要的是,在很多情況下不需要複製。這節省了大量時間,充分使用了稀有的實體記憶體。

虛擬記憶體管理中的寫時複製

虛擬記憶體管理中,一般把共享訪問的頁面標記為只讀,當一個 task 試圖向記憶體中寫入資料時,記憶體管理單元(MMU)丟擲一個異常,核心處理該異常時為該 task 分配一份實體記憶體並複製資料到此記憶體,重新向 MMU 發出執行該 task 的寫操作

這裡順便了解一下 Linux 的記憶體管理

Linux 記憶體管理

為了充分利用和管理系統記憶體資源,Linux 採用虛擬記憶體管理技術,在現代計算機系統中對實體記憶體做了一層抽象。

它為每一個程序都提供一塊連續的私有地址空間,在 32 位模式下,每一塊虛擬地址空間大小為 4GB。

Linux 採用虛擬記憶體管理技術,利用虛擬記憶體技術讓每個程序都有4GB 互不干涉的虛擬地址空間。

程序初始化分配和操作的都是基於這個「虛擬地址」,只有當程序需要實際訪問記憶體資源的時候才會建立虛擬地址和實體地址的對映,調入實體記憶體頁。

這個原理其實和現在的某某網盤一樣。假如你的網盤空間是1TB,真以為就一口氣給了你這麼大空間嗎?都是在你往裡面放東西的時候才給你分配空間,你放多少就分多少實際空間給你,但你看起來就像擁有1TB空間一樣。

程序(執行的程式)佔用的使用者空間按照 訪問屬性一致的地址空間存放在一起 的原則,劃分成 5個不同的記憶體區域。訪問屬性指的是“可讀、可寫、可執行等。

  • 程式碼段

    程式碼段是用來存放可執行檔案的操作指令,可執行程式在記憶體中的映象。程式碼段需要防止在執行時被非法修改,所以只准許讀取操作,它是不可寫的。 - 資料段

    資料段用來存放可執行檔案中已初始化全域性變數,換句話說就是存放程式靜態分配的變數和全域性變數。 - BSS 段

    BSS段包含了程式中未初始化的全域性變數,在記憶體中 bss 段全部置零。 - 堆 heap

    堆是用於存放程序執行中被動態分配的記憶體段,它的大小並不固定,可動態擴張或縮減。當程序呼叫 malloc 等函式分配記憶體時,新分配的記憶體就被動態新增到堆上(堆被擴張);當利用 free 等函式釋放記憶體時,被釋放的記憶體從堆中被剔除(堆被縮減) - 棧 stack

    棧是使用者存放程式臨時建立的區域性變數,也就是函式中定義的變數(但不包括 static 宣告的變數,static 意味著在資料段中存放變數)。除此以外,在函式被呼叫時,其引數也會被壓入發起呼叫的程序棧中,並且待到呼叫結束後,函式的返回值也會被存放回棧中。由於棧的先進先出特點,所以棧特別方便用來儲存/恢復呼叫現場。從這個意義上講,我們可以把堆疊看成一個寄存、交換臨時資料的記憶體區。

可以在 linux 下用size 命令檢視編譯後程序的各個記憶體區域大小:

```Bash

size /usr/local/sbin/sshd

text data bss dec hex filename 1924532 12412 426896 2363840 2411c0 /usr/local/sbin/sshd ```

核心地址空間劃分

x86 32 位系統裡,Linux 核心地址空間是指虛擬地址從 0xC0000000 開始到 0xFFFFFFFF 為止的高階記憶體地址空間,總計 1G 的容量, 包括了核心映象、物理頁面表、驅動程式等執行在核心空間

直接對映區

直接對映區 Direct Memory Region:從核心空間起始地址開始,最大896M的核心空間地址區間,為直接記憶體對映區。

直接對映區的 896MB 的「線性地址」直接與「實體地址」的前896MB進行對映,也就是說線性地址和分配的實體地址都是連續的。核心地址空間的線性地址0xC0000001所對應的實體地址為0x00000001,它們之間相差一個偏移量PAGE_OFFSET = 0xC0000000

該區域的線性地址和實體地址存線上性轉換關係「線性地址 = PAGE_OFFSET + 實體地址」也可以用 virt_to_phys()函式將核心虛擬空間中的線性地址轉化為實體地址。

高階記憶體線性地址空間

核心空間線性地址從 896M 到 1G 的區間,容量 128MB 的地址區間是高階記憶體線性地址空間,為什麼叫高階記憶體線性地址空間?下面給你解釋一下:

前面已經說過,核心空間的總大小 1GB,從核心空間起始地址開始的 896MB 的線性地址可以直接對映到實體地址大小為 896MB 的地址區間。

退一萬步,即使核心空間的 1GB 線性地址都對映到實體地址,那也最多隻能定址 1GB 大小的實體記憶體地址範圍。

核心空間拿出了最後的 128M 地址區間,劃分成下面三個高階記憶體對映區,以達到對整個實體地址範圍的定址。而在 64 位的系統上就不存在這樣的問題了,因為可用的線性地址空間遠大於可安裝的記憶體。

動態記憶體對映區

vmalloc Region 該區域由核心函式vmalloc來分配,特點是:線性空間連續,但是對應的實體地址空間不一定連續。vmalloc 分配的線性地址所對應的物理頁可能處於低端記憶體,也可能處於高階記憶體。

永久記憶體對映區

Persistent Kernel Mapping Region 該區域可訪問高階記憶體。訪問方法是使用 alloc_page (_GFP_HIGHMEM) 分配高階記憶體頁或者使用kmap函式將分配到的高階記憶體對映到該區域。

固定對映區

Fixing kernel Mapping Region 該區域和 4G 的頂端只有 4k 的隔離帶,其每個地址項都服務於特定的用途,如 ACPI_BASE 等。

使用者空間記憶體資料結構

虛擬地址的好處

  • 避免使用者直接訪問實體記憶體地址,防止一些破壞性操作,保護作業系統
  • 每個程序都被分配了 4GB 的虛擬記憶體,使用者程式可使用比實際實體記憶體更大的地址空間

系統處理流程

系統將虛擬記憶體分割成一塊塊固定大小的虛擬頁(Virtual Page),同樣的,實體記憶體也會被分割成物理頁(Physical Page),當程序訪問記憶體時,CPU 通過記憶體管理單元(MMU)根據頁表(Page Table)將虛擬地址翻譯成實體地址,最終取到記憶體資料。這樣在每個程序內部都像是獨享整個主存。

當 CPU 拿到一個虛擬地址希望訪存的時候,將其分為虛擬頁框號和便宜兩個部分,先拿著虛擬頁框號查 TLB,TLB 命中就直接將物理頁框號和偏移拼接起來得到實體地址。在拿著實體地址進行訪存。訪存的時候也是先看快取彙總是否有,沒有的話再訪問下一級儲存器。如果 TLB 沒有命中的話,就利用CR3暫存器(儲存當前程序的一級頁表基址)逐級地查頁表。

當初始化一個程序的時候,Linux 系統通過將虛擬地址空間和一個磁碟上的物件相關聯來初始化這個程序的虛擬地址空間,這個過程稱之為記憶體對映。

可執行檔案儲存在磁碟中,其中有虛擬記憶體中的各個段的資料,比如程式碼段,資料段等。比如程式碼段,它在程式執行的過程中應該是不變的,而且在記憶體中的樣子和在磁碟中是一樣的,

所以是如何載入到記憶體中的呢。

Linux 將記憶體的不同區域對映成下面兩種磁碟檔案中的一種:

  1. Linux 檔案系統的常規檔案。比如可執行檔案。檔案的某一部分被劃分為頁大小的快,每一塊包含一個虛擬地址頁的初始內容。當某一塊不足一頁的時候,用零進行填充。但是作業系統並不會在一開始就將所有的內容真的放到記憶體中,而是 CPU 第一次訪問發生了缺頁的時候,才由缺頁中斷將這一頁調入實體記憶體。(當程序在申請的記憶體的時候,linux 核心其實只分配一塊虛擬記憶體地址,並沒有分配實際的實體記憶體,相當於作業系統只給程序這一塊地址的使用權。只有當程式真正使用這塊記憶體時,會產生一個缺頁異常,這時核心去真正為程序分配物理頁,並建立對應的頁表,從而將虛擬記憶體和實體記憶體建立一個對映關係,這樣可以做到充分利用到實體記憶體。
  2. 匿名檔案。虛擬記憶體的一片區域也可以對映到由核心建立的一個匿名檔案,如堆疊部分和未初始化的全域性變數,在可實行檔案中並沒有實體,這些會對映到匿名檔案。當 CPU 訪問這些區域的時候,核心找到一個物理頁,將它清空,然後更新程序的頁表。這個過程沒有發生磁碟到主存中間的資料互動。但是需要注意,在C++堆申請的記憶體不一定都是 0,因為C++內部實現了堆記憶體管理,可能申請的記憶體並不是作業系統新分配的,而是之前分配了返回了,但是被C++記憶體管理部分保留了,這次申請又直接返回給了使用者。

在上面兩種情況下,虛擬頁被初始化之後,它會在交換空間和主存中進行換入換出。交換空間的大小限制了當前正在執行的程序的虛擬頁的最大數量。交換空間的大小可以在按照作業系統的時候進行設定。

記憶體對映與程序間共享物件 (CopyOnWrite)

不同的程序可以共享物件。比如程式碼段是隻讀的,運行同一個可執行檔案的程序可以共享虛擬記憶體的程式碼段,這樣可以節省實體記憶體。還有程序間通訊的共享記憶體機制。這些都可以在虛擬記憶體對映這個層次來實現。可以將不同程序的虛擬頁對映到同一個物理頁框,從而實現不同程序之間的記憶體共享。 同時為了節省實體記憶體,可以使用copy-on-write技術,來實現程序私有的地址空間共享。初始時刻讓多個程序共享一個實體記憶體頁,然後當有某一個程序對這個頁進行寫的時候,出發copy-on-write機制,將這個物理頁進行復制,這樣就實現了私有化。

Buddy(夥伴)分配演算法

Linux 核心引入了夥伴系統演算法(Buddy system),什麼意思呢?就是把相同大小的頁框塊用連結串列串起來,頁框塊就像手拉手的好夥伴,也是這個演算法名字的由來。

具體的,所有的空閒頁框分組為 11 個塊連結串列,每個塊連結串列分別包含大小為 1,2,4,8,16,32,64,128,256,512 和 1024 個連續頁框的頁框塊。最大可以申請 1024 個連續頁框,對應 4MB 大小的連續記憶體。

因為任何正整數都可以由 2^n 的和組成,所以總能找到合適大小的記憶體塊分配出去,減少了外部碎片產生 。

slab 分配器

看到這裡你可能會想,有了夥伴系統這下總可以管理好實體記憶體了吧?不,還不夠,否則就沒有 slab 分配器什麼事了。

那什麼是 slab 分配器呢?

一般來說,核心物件的生命週期是這樣的:分配記憶體-初始化-釋放記憶體,核心中有大量的小物件,比如檔案描述結構物件、任務描述結構物件,如果按照夥伴系統按頁分配和釋放記憶體,對小物件頻繁的執行「分配記憶體-初始化-釋放記憶體」會非常消耗效能。

夥伴系統分配出去的記憶體還是以頁框為單位,而對於核心的很多場景都是分配小片記憶體,遠用不到一頁記憶體大小的空間。slab分配器,「通過將記憶體按使用物件不同再劃分成不同大小的空間」,應用於核心物件的快取。

夥伴系統和 slab 不是二選一的關係,slab 記憶體分配器是對夥伴分配演算法的補充。

mmap

mmap 是 POSIX 規範介面中用來處理記憶體對映的一個系統呼叫,它本身的使用場景非常多:

  • 可以用來申請大塊記憶體
  • 可以用來申請共享記憶體
  • 也可以將檔案或裝置直接對映到記憶體中

程序可以像訪問普通記憶體一樣訪問被對映的檔案,在實際開發過程使用場景非常多

在 LINUX 中我們可以使用 mmap 用來在程序虛擬記憶體地址空間中分配地址空間,建立和實體記憶體的對映關係。

mmap 是將一個檔案直接對映到程序的地址空間,程序可以像操作記憶體一樣去讀寫磁碟上的檔案內容,而不需要再呼叫 read/write 等系統呼叫。

C int main(int argc, char **argv) { char *filename = "/tmp/foo.data"; struct stat stat; int fd = open(filename, O_RDWR, 0); fstat(fd, &stat); void *bufp = mmap(NULL, stat.st_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0); memcpy(bufp, "Linuxdd", 7); munmap(bufp, stat.st_size); close(fd); return 0; }

在 mmap 之後,並沒有在將檔案內容載入到物理頁上,只上在虛擬記憶體中分配了地址空間。當程序在訪問這段地址時,通過查詢頁表,發現虛擬記憶體對應的頁沒有在實體記憶體中快取,則產生"缺頁",由核心的缺頁異常處理程式處理,將檔案對應內容,以頁為單位 (4096) 載入到實體記憶體,注意是隻載入缺頁,但也會受作業系統一些排程策略影響,載入的比所需的多。

所處空間

一個程序的虛擬空間有多個部分組成,mmap 的檔案所處的記憶體空間在記憶體對映段中。

mmap 和 read/write 的區別

read 的系統呼叫的流程大概如下圖所示:

a) 使用者程序發起 read 操作;
b) 核心會做一些基本的 page cache 判斷,從磁碟中讀取資料到 kernel buffer 中;
c) 然後核心將 buffer 的資料再拷貝至使用者態的 user buffer;
d) 喚醒使用者程序繼續執行;

而 mmap 的流程如下圖所示

核心直接將記憶體暴露給使用者態,使用者態對記憶體的修改也直接反映到核心態,少了一次的核心態至使用者態的記憶體拷貝,速度上會有一定的提升

mmap 的優點有很多,相比傳統的 read/write 等 I/O 方式,直接將虛擬地址的區域對映到檔案,沒有任何資料拷貝的操作,當發現有缺頁時,通過對映關係將磁碟的資料載入到記憶體,使用者態程式直接可見,提高了檔案讀取的效率。對索引資料這種大檔案的讀取、cache、換頁等操作直接交由作業系統去排程,間接減少了使用者程式的複雜度,並提高了執行效率。

優缺點

優點如下:

  1. 對檔案的讀取操作跨過了頁快取,減少了資料的拷貝次數,用記憶體讀寫取代 I/O 讀寫,提高了檔案讀取效率。
  2. 實現了使用者空間和核心空間的高效互動方式。兩空間的各自修改操作可以直接反映在對映的區域內,從而被對方空間及時捕捉。
  3. 提供程序間共享記憶體及相互通訊的方式。不管是父子程序還是無親緣關係的程序,都可以將自身使用者空間對映到同一個檔案或匿名對映到同一片區域。從而通過各自對對映區域的改動,達到程序間通訊和程序間共享的目的。同時,如果程序 A 和程序 B 都映射了區域 C,當 A 第一次讀取 C 時通過缺頁從磁碟複製檔案頁到記憶體中;但當 B 再讀 C 的相同頁面時,雖然也會產生缺頁異常,但是不再需要從磁碟中複製檔案過來,而可直接使用已經儲存在記憶體中的檔案資料。
  4. 可用於實現高效的大規模資料傳輸。記憶體空間不足,是制約大資料操作的一個方面,解決方案往往是藉助硬碟空間協助操作,補充記憶體的不足。但是進一步會造成大量的檔案 I/O 操作,極大影響效率。這個問題可以通過 mmap 對映很好的解決。換句話說,但凡是需要用磁碟空間代替記憶體的時候,mmap 都可以發揮其功效。

缺點如下:

  1. 檔案如果很小,是小於 4096 位元組的,比如 10 位元組,由於記憶體的最小粒度是頁,而程序虛擬地址空間和記憶體的對映也是以頁為單位。雖然被對映的檔案只有 10 位元組,但是對應到程序虛擬地址區域的大小需要滿足整頁大小,因此 mmap 函式執行後,實際對映到虛擬記憶體區域的是 4096 個位元組,11~4096 的位元組部分用零填充。因此如果連續 mmap 小檔案,會浪費記憶體空間。
  2. 對變長檔案不適合,檔案無法完成拓展,因為 mmap 到記憶體的時候,你所能夠操作的範圍就確定了。
  3. 如果更新檔案的操作很多,會觸發大量的髒頁回寫及由此引發的隨機 IO 上。所以在隨機寫很多的情況下,mmap 方式在效率上不一定會比帶緩衝區的一般寫快

Linux 等的檔案管理系統使用了寫時複製策略

ZFSBTRFS 兩種寫時複製檔案系統,寫時複製檔案系統採用了日誌式技術。

ZFS

ZFS 檔案系統的英文名稱為 Zettabyte File System, 也叫動態檔案系統(Dynamic File System), 是第一個 128 位檔案系統。最初是由 Sun 公司為 Solaris 10 作業系統開發的檔案系統。作為 OpenSolaris 開源計劃的一部分,ZFS 於 2005 年 11 月釋出,被 Sun 稱為是終極檔案系統,經歷了 10 年的活躍開發。而最新的開發將全面開放,並重新命名為 OpenZFS

利用寫時拷貝使 ZFS 的快照和事物功能的實現變得更簡單和自然,快照功能更靈活。缺點是,COW 使碎片化問題更加嚴重,對於順序寫生成的大檔案,如果以後隨機的對其中的一部分進行了更改,那麼這個檔案在硬碟上的實體地址就變得不再連續,未來的順序讀會變得效能比較差。

BTRFS

BTRFS(通常念成 Butter FS),由 Oracle 於 2007 年宣佈並進行中的 COW(copy-on-write 式)檔案系統。目標是取代 Linux ext3 檔案系統,改善 ext3 的限制,特別是單一檔案大小的限制,總檔案系統大小限制以及加入檔案校驗和特性。加入 ext3/4 未支援的一些功能,例如可寫的磁碟快照 (snapshots),以及支援遞迴的快照 (snapshots of snapshots),內建磁碟陣列(RAID)支援,支援子卷 (Subvolumes) 的概念,允許線上調整檔案系統大小。

首先是擴充套件性 (scalability) 相關的特性,btrfs 最重要的設計目標是應對大型機器對檔案系統的擴充套件性要求。 ExtentB-Tree 和動態 inode 建立等特性保證了 btrfs 在大型機器上仍有卓越的表現,其整體效能而不會隨著系統容量的增加而降低。其次是資料一致性 (data integrity) 相關的特性。系統面臨不可預料的硬體故障,Btrfs 採用 COW 事務技術來保證檔案系統的一致性。 btrfs 還支援 checksum,避免了 silent corrupt 的出現。而傳統檔案系統則無法做到這一點。第三是和多裝置管理相關的特性。 Btrfs 支援建立快照 (snapshot),和克隆 (clone) 。 btrfs 還能夠方便的管理多個物理裝置,使得傳統的卷管理軟體變得多餘。最後是其他難以歸類的特性。這些特性都是比較先進的技術,能夠顯著提高檔案系統的時間/空間效能,包括延遲分配,小檔案的儲存優化,目錄索引等。

資料庫一般採用了寫時複製策略,為使用者提供一份 snapshot

MySQL MVCC

多版本併發控制(MVCC) 在一定程度上實現了讀寫併發,它只在 可重複讀(REPEATABLE READ)提交讀(READ COMMITTED) 兩個隔離級別下工作。其他兩個隔離級別都和 MVCC 不相容,因為 未提交讀(READ UNCOMMITTED),總是讀取最新的資料行,而不是符合當前事務版本的資料行。而 可序列化(SERIALIZABLE) 則會對所有讀取的行都加鎖。

行鎖,併發,事務回滾等多種特性都和 MVCC 相關。MVCC 實現的核心思路就是 Copy On Write

Java 中的寫時複製應用

j.u.c 包中支援寫時複製的執行緒安全的集合: CopyOnWriteArrayList、CopyOnWriteArraySet

與 fail-fast 的容器相比,fail-safe 的 COW 容器固然安全了很多,但是由於每次寫都要複製整個陣列,時間和空間的開銷都更高,因此只適合讀多寫少的情景。在寫入時,為了保證效率,也應儘量做批量插入或刪除,而不是單條操作。並且它的正本和副本有可能不同步,因此無法保證讀取的是最新資料,只能保證最終一致性。

Redis

Redis 在生成 RDB 快照檔案時不會終止對外服務

Redis 重啟後可以恢復資料。比如 RDB,是儲存某個瞬間 Redis 的資料庫快照。執行 bgsave 命令,Redis 就會儲存一個 dump.rdb 檔案,這個檔案記錄了這個瞬間整個資料庫的所有資料。Redis 厲害的地方就是,在儲存的同時,Redis 還能處理命令。那麼有一個很有趣的問題——Redis 是怎麼保證 dump.rdb 中資料的一致性的?Redis 一邊在修改資料庫,一邊在把資料庫儲存到檔案,就不擔心臟讀髒寫問題嗎?

Redis 有一個主程序,在寫資料,這時候有一個命令過來了,說要把資料持久化到磁碟。我們知道 redis 的 worker 是單執行緒的,如果要持久化這個行為也放在單執行緒裡,那麼如果需要持久化資料特別多,將會影響使用者的使用。所以單開(fork)一個程序(子程序)專門來做持久化的操作。

至於實現原理,是這樣的:fork() 之後,kernel 把父程序中所有的記憶體頁的許可權都設為 read-only,然後子程序的地址空間指向父程序。當父子程序都只讀記憶體時,相安無事。當其中某個程序寫記憶體時,CPU 硬體檢測到記憶體頁是 read-only 的,於是觸發頁異常中斷(page-fault),陷入 kernel 的一箇中斷例程。中斷例程中,kernel 就會把觸發的異常的頁複製一份,於是父子程序各自持有獨立的一份。

是父程序持有原品、子程序持有複製品,還是反之?

誰修改記憶體,誰就持有複製品

kernel 進行復制的單位是一個記憶體頁嗎?

copy 的大小是一個頁大小

參考