【學到一個新名詞】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.