【學到一個新名詞】String interning(字串駐留/字串內部化)

作者:張富春(ahfuzhang)，轉載時請註明作者和參照連結，謝謝！

• cnblogs部落格
• zhihu
• Github
• 公眾號:一本正經的瞎扯
  

在閱讀 VictoriaMetrics v1.95.1 的命令列手冊的時候，發現這樣一段：

  -internStringCacheExpireDuration duration
     The expiry duration for caches for interned strings. See https://en.wikipedia.org/wiki/String_interning . See also -internStringMaxLen and -internStringDisableCache (default 6m0s)

什麼是 String interning 呢？我通過了 wiki 連結學習了一下。
並且，我還找到了一個使用 String interning 技術的 golang 專案：https://github.com/josharian/intern . 作者還寫了 blog: Interning strings in Go 來進一步介紹細節。

String interning 可以翻譯為 字串駐留 或者 字串內部化。這個技巧用於節約頻繁出現的字串的空間佔用，還可以用於頻繁出現的字串的比較的加速。
它的處理思路如下：

1. 首先有一個全域性的執行緒安全的鍵值對的字串池；

類似於： map[string]string

然後把出現頻率超級高的字串儲存在其中。

2. 當出現新的字串的時候，要先去字串池中匹配。
   匹配到以後，程式就可以參照字串池中的物件，而把當前參照的物件釋放掉。
   當存在大量的這樣內容相同的字串的時候，這樣做無疑是可以節省空間的。
   在這樣的場景下，相當於時間換空間。

3. 當字串都來自字串池，且需要頻繁比較的時候，直接比較指標就可以確定是否是同一個字串，而無需逐個字元比較。
   在這樣的場景下，相當於空間換時間。

讓我們再看看那個簡單的 golang 實現的字串內部化的原始碼：
see: https://github.com/josharian/intern/blob/master/intern.go

package intern

import "sync"

var (
	pool sync.Pool = sync.Pool{   // 作者想用 sync.Pool 來解決不參照時候的釋放問題。但是並行環境下可能導致分配了多個鍵值對的字串池。
		New: func() interface{} {    // sync.Pool 能夠在並行環境下工作，不管怎麼說，並行情況下使用不會出錯。
			return make(map[string]string)
		},
	}
)

// String returns s, interned.
func String(s string) string {
	m := pool.Get().(map[string]string)
	c, ok := m[s]  // 這裡要經過  1.計算字串 hashcode; 2.hash 查詢; 3.字串內容比較。時間換空間的成本還是挺高的。
	if ok {
		pool.Put(m)
		return c  // 如果字串池中存在，就置換為字串池中的物件
	}
	m[s] = s  // 這裡不會發生並行問題
	pool.Put(m)
	return s
}

// Bytes returns b converted to a string, interned.
func Bytes(b []byte) string {
	m := pool.Get().(map[string]string)
	c, ok := m[string(b)]  // string(b) 這裡有個隱含的知識點：這種情況下編譯器不會分配新的字串物件。
	if ok {
		pool.Put(m)
		return c
	}
	s := string(b)
	m[s] = s
	pool.Put(m)
	return s
}

// todo: 這裡還缺乏一個內容：當字串都來自字串池的時候，可以提供按照指標比較的方法
// 類似於:
//  isSmae := &str1==&str2 || str1==str2

看完了原始碼，這個字串內部化似乎也沒有很複雜很高深。或許某個存在大量重複字串的場景中，我們很能用上這個技術。

最後，ChatGPT 還給了我一段 VictoriaMetrics 中使用 String interning 技術的講解：

// 以下內容由  ChatGPT 4.0 產生：
VictoriaMetrics採用了字串內部化技術來優化其時間序列資料庫的效能，尤其在處理度量指標的後設資料時。這些後設資料通常由標籤-值對組成，並且在VictoriaMetrics中以字串的形式表示。下面是VictoriaMetrics中字串內部化實現的詳細資訊：

1. 字串內部化的目的和效果：在VictoriaMetrics中，由於後設資料字串在實踐中變化不大，因此在資料收集過程中會產生大量重複。例如，`go_info` 度量指標的後設資料包含Go版本的標籤-值對。這些版本並不經常變化，但每次從應用程式中收集此度量時，都需要解析其後設資料並在記憶體中分配，直到它被垃圾回收。為了避免多次儲存相同的字串，VictoriaMetrics通過內部化每個獨特字串一次，並在需要時參照它，從而顯著節省記憶體​​​​。

2. 實現方法：在單執行緒應用中，字串內部化的一種簡單實現方式是使用Go的map型別。但在vmagent這樣的多執行緒應用中，這種方法由於多核系統上存取此對映時可能產生大量爭用，因此不太適合。為了在多執行緒環境下實現內部化，VictoriaMetrics使用了Go標準庫中的sync.Map，這是一個執行緒安全的實現​​。

3. sync.Map的優化用途：sync.Map特別適用於以下兩種情況：
  * 當一個給定的鍵只被寫入一次但多次使用時，即快取命中率高的情況。
  * 當多個goroutine為不同的鍵集合讀取、寫入和覆蓋條目時，即每個goroutine使用不同的鍵集​​。

4. 內部化的注意事項：
  * 記憶體增長問題：隨著時間的推移，map會逐漸增長，無限制的記憶體增長是危險的。為了防止map無限增長，需要定期旋轉map，通過刪除並重建它，或為鍵實現某種形式的生存時間（TTL）邏輯。
  * 引數檢查：intern函數在處理常規字串時表現良好，但除非鎖定介面，否則可能會有人嘗試傳遞可能破壞函數的內容。例如，在Go中，位元組切片是可變的，不適合作為對映中的鍵使用​​。

5. 內部化的通用建議：在實現字串內部化時，克隆傳遞給函數的字串是一個好主意。這可以幫助消除一些微妙的錯誤。VictoriaMetrics使用字串內部化來減少解析度量後設資料時的記憶體使用。這是一種對於讀取密集型工作負載效果最佳的強大技術，尤其適用於潛在字串變體較少的情況​​。

總的來說，VictoriaMetrics通過字串內部化有效地優化了記憶體使用和效能，特別是在處理大量重複且不經常變化的度量後設資料時。這一技術不僅提高了效能，還降低了對垃圾收集器的負擔，是處理大規模時間序列資料的有效方法。

Have fun.