Algorithm
func maximalSquare(matrix [][]byte) (result int) {
m := len(matrix)
n := len(matrix[0])
results := make([][]int, m)
maxSize := 0
for i := 0; i < m; i++ {
results[i] = make([]int, n)
for j := 0; j < n; j++ {
if matrix[i][j] == '1' {
results[i][j] = 1
var temp int
if i == 0 || j == 0 {
temp = 1
} else {
temp = min(min(results[i-1][j-1], results[i][j-1]), results[i-1][j]) + 1
}
results[i][j] = temp
if temp > maxSize {
maxSize = temp
}
} else {
results[i][j] = 0
}
}
}
result = maxSize * maxSize
return
}
func min(x, y int) int {
if x <= y {
return x
}
return y
}
Review
NA
TIP
這周在工作過程接觸到公司redis的熱承載功能，這里記錄下小渊。
應(yīng)用場景
業(yè)務(wù)上如果有熱點key的問題薄坏，可以通過開始熱承載來解決。比如現(xiàn)在有個功能是通過直播間ID獲取當前直播間正在售賣的商品列表，對應(yīng)到代碼層面的設(shè)計就是key是room_id辩诞，value是product_id list癣蟋。這種設(shè)計會導致頭部主播開播過程如果看播的觀眾特別多，會有大量的請求（10萬qps以上）去同一個redis分片讀取同一個room_id key進而導致這個redis分片負載較高影響業(yè)務(wù)初斑，這就是一個典型的業(yè)務(wù)熱點場景。
原理
目前公司內(nèi)部redis實現(xiàn)架構(gòu)是redis client -> redis proxy -> redis server膨处，而熱承載開啟之后會在client和proxy上維護一個localcache见秤，如果請求命中了localcache就直接返回對應(yīng)的值，從而減少redis server的壓力真椿。當然這里只是大體設(shè)計秦叛，具體的技術(shù)細節(jié)不能透漏太多。
優(yōu)點
業(yè)務(wù)遇到熱點場景不需要自己在業(yè)務(wù)端實現(xiàn)一套localcache了瀑粥，直接開啟熱承載就可以了挣跋。
缺點
- 有緩存必然就涉及到一致性問題，不可避免狞换。
- 不能定制化localcache避咆，只能單純地使用原始的kv值舟肉。
Share
學習“redis設(shè)計與實現(xiàn)”
壓縮列表
Ziplist 是由一系列特殊編碼的內(nèi)存塊構(gòu)成的列表，一個 ziplist 可以包含多個節(jié)點（entry）查库，每個節(jié)點可以保存一個長度受限的字符數(shù)組（不以 \0 結(jié)尾的 char 數(shù)組）或者整數(shù)路媚。
ziplist 的構(gòu)成
節(jié)點的構(gòu)成
pre_entry_length
pre_entry_length 記錄了前一個節(jié)點的長度，通過這個值樊销，可以進行指針計算整慎，從而跳轉(zhuǎn)到上一個節(jié)點。
encoding 和 length
encoding 域的長度為兩個 bit 围苫，它的值可以是 00 裤园、01 、10 和 11：
? 00 剂府、01 和 10 表示 content 部分保存著字符數(shù)組拧揽。
? 11 表示 content 部分保存著整數(shù)。
content
content 部分保存著節(jié)點的內(nèi)容腺占，它的類型和長度由 encoding 和 length 決定
將節(jié)點添加到末端
將新節(jié)點添加到 ziplist 的末端需要執(zhí)行以下三個步驟：
- 記錄到達 ziplist 末端所需的偏移量（因為之后的內(nèi)存重分配可能會改變 ziplist 的地址淤袜，因此記錄偏移量而不是保存指針）
- 根據(jù)新節(jié)點要保存的值，計算出編碼這個值所需的空間大小衰伯，以及編碼它前一個節(jié)點的長度所需的空間大小铡羡，然后對 ziplist 進行內(nèi)存重分配。
- 設(shè)置新節(jié)點的各項屬性：pre_entry_length 意鲸、encoding 烦周、length 和 content 。
- 更新 ziplist 的各項屬性临扮，比如記錄空間占用的 zlbytes 论矾，到達表尾節(jié)點的偏移量 zltail教翩，以及記錄節(jié)點數(shù)量的 zllen 杆勇。
將節(jié)點添加到某個/某些節(jié)點的前面
- 記錄到達 ziplist 末端所需的偏移量（因為之后的內(nèi)存重分配可能會改變 ziplist 的地址，因此記錄偏移量而不是保存指針）
- 根據(jù)新節(jié)點要保存的值饱亿，計算出編碼這個值所需的空間大小蚜退，以及編碼它前一個節(jié)點的長度所需的空間大小，然后對 ziplist 進行內(nèi)存重分配彪笼。
- 設(shè)置新節(jié)點的各項屬性：pre_entry_length 钻注、encoding 、length 和 content 配猫。
- 更新 ziplist 的各項屬性幅恋，比如記錄空間占用的 zlbytes ，到達表尾節(jié)點的偏移量 zltail泵肄，以及記錄節(jié)點數(shù)量的 zllen 捆交。
- 將 new 節(jié)點的長度編碼進 next 節(jié)點的 pre_entry_length 域里淑翼。這里會出現(xiàn)三種可能：
- next 的 pre_entry_length 域的長度正好能夠編碼 new 的長度（都是 1 字節(jié)或者都是 5字節(jié)）
- next 的 pre_entry_length 只有 1 字節(jié)長，但編碼 new 的長度需要 5 字節(jié)
- next 的 pre_entry_length 有 5 字節(jié)長品追，但編碼 new 的長度只需要 1 字節(jié)
對于情況 1 和 3 玄括，程序直接更新 next 的 pre_entry_length 域。
如果是第二種情況肉瓦，那么程序必須對 ziplist 進行內(nèi)存重分配遭京，從而擴展 next 的空間。然而泞莉，因為 next 的空間長度改變了哪雕，所以程序又必須檢查 next 的后繼節(jié)點——next+1 ，看它的pre_entry_length 能否編碼 next 的新長度戒财，如果不能的話热监，程序又需要繼續(xù)對 next+1 進行擴容。程序必須沿著路徑一個個檢查后續(xù)的節(jié)點是否滿足新長度的編碼要求饮寞，直到遇到一個能滿足要求的節(jié)點（如果有一個能滿足孝扛，那么這個節(jié)點之后的其他節(jié)點也滿足），或者到達 ziplist 的末端 zlend 為止幽崩，這種檢查操作的復雜度為O(N2) 苦始。
刪除節(jié)點
- 定位目標節(jié)點，并計算節(jié)點的空間長度 target-size
- 進行內(nèi)存移位慌申，覆蓋 target 原本的數(shù)據(jù)陌选，然后通過內(nèi)存重分配，收縮多余空間
- 檢查 next 蹄溉、next+1 等后續(xù)節(jié)點能否滿足新前驅(qū)節(jié)點的編碼咨油。和添加操作一樣，刪除操作也可能會引起連鎖更新柒爵。
遍歷
可以對 ziplist 進行從前向后的遍歷役电，或者從后先前的遍歷。
當進行從前向后的遍歷時棉胀，程序從指向節(jié)點 e1 的指針 p 開始法瑟，計算節(jié)點 e1 的長度（e1-size），然后將 p 加上 e1-size 唁奢，就將指針后移到了下一個節(jié)點 e2 霎挟。
當進行從后往前遍歷的時候，程序從指向節(jié)點 eN 的指針 p 出發(fā)麻掸，取出 eN 的 pre_entry_length值酥夭，然后用 p 減去 pre_entry_length ，這就將指針移動到了前一個節(jié)點 eN-1。
