RSS / GO map -2

關於 Ameba 的 100 篇

GO map - 1

今天看了一下 RSS (Receive Side Scaling)

RSS是一種能在多CPU(多核) 上, 使用多隊列接收封包, 來高效分發的網卡驅動技術 

Ref: https://kknews.cc/zh-tw/tech/5394mp6.html

RSS中的過濾器是一個基於L3和L4層頭部的hash函數，

例如，基於IP位址和TCP埠的4元組的hash函數。

最常見的RSS硬體實現中，使用了128個間接表，其中每個表存儲一個隊列號(注，網卡的隊列數比較少，比如igb是8個，bnx2是5個)。針對某個包而言，使用這個包計算出的hash值（hash是Toeplitz算法）的低7位先確定間接表，再從間接表中的值獲取相應的隊列號。

簡單的說，Intel的千兆網卡硬體支持128個數據流的分類，這些數據流可以交給8個隊列來接收。 一些高級的網卡允許使用可編程的過濾器來控制包屬於哪個隊列。

像綁定TCP埠80的webserver，數據包能被指向某個隊列, 鎖定在某個 cpu 核心來執行. 

例如 Intel 82575 硬體邏輯圖

1. 用以計算 hash 值 的 參數: 

    可以參考 Microsoft 所列, 通常用 source 和 destination 的  IP address , port , protocol (e.g. TCP or UDP .. )

    https://docs.microsoft.com/en-us/windows-hardware/drivers/network/rss-hashing-types

2. 取 hash 值的 低幾位 作為 RETA (redirection table) 的 index

3. 根據 RETA 的儲存值 決定安排到哪個 CPU

 ===

想起要介紹一下 GO map 的 實作方式: 

https://github.com/golang/go/blob/master/src/runtime/map.go

GO 的 map 是一種 hash table, 在這個 淺談 GO 語言實現原理 的  3.2 hash table 中

有相關的介紹

Hash table 簡介  - 

    可以參考 Techbridge 的 這一篇 - 白話的 Hash Table 簡介

    和這篇 Javascript hash table

GO 利用一個 2^B 個數的 bucket array

一個 bucket 是一個 bmap , bucketCnt 是常數 8, 

結構圖類似如下. 

hash function : 按照 key 的類型採用相對應的  hash 算法, 

例如 字串 是使用  rabin-karp algorithm 所用的 hash function :

( from : http://wiki.csie.ncku.edu.tw/acm/course/String_Matching )

查找 index 的第一層函式 是 mapaccess1()

  1. 調用 key 類型所用的 hash function, 計算出 key 的 hash 值

  2. 依照 hash 值找出對應的 bucket index

  3,. 在 bucket 中找到和 key 值相符 (key1~key8) 的對應 value 值 (value1~value8)