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的热承载功能，这里记录下。
应用场景
业务上如果有热点key的问题，可以通过开始热承载来解决。比如现在有个功能是通过直播间ID获取当前直播间正在售卖的商品列表，对应到代码层面的设计就是key是room_id，value是product_id list。这种设计会导致头部主播开播过程如果看播的观众特别多，会有大量的请求（10万qps以上）去同一个redis分片读取同一个room_id key进而导致这个redis分片负载较高影响业务，这就是一个典型的业务热点场景。
原理
目前公司内部redis实现架构是redis client -> redis proxy -> redis server，而热承载开启之后会在client和proxy上维护一个localcache，如果请求命中了localcache就直接返回对应的值，从而减少redis server的压力。当然这里只是大体设计，具体的技术细节不能透漏太多。
优点
业务遇到热点场景不需要自己在业务端实现一套localcache了，直接开启热承载就可以了。
缺点
- 有缓存必然就涉及到一致性问题，不可避免。
- 不能定制化localcache，只能单纯地使用原始的kv值。
Share
学习“redis设计与实现”
压缩列表
Ziplist 是由一系列特殊编码的内存块构成的列表，一个 ziplist 可以包含多个节点（entry），每个节点可以保存一个长度受限的字符数组（不以 \0 结尾的 char 数组）或者整数。
ziplist 的构成
节点的构成
pre_entry_length
pre_entry_length 记录了前一个节点的长度，通过这个值，可以进行指针计算，从而跳转到上一个节点。
encoding 和 length
encoding 域的长度为两个 bit ，它的值可以是 00 、01 、10 和 11：
• 00 、01 和 10 表示 content 部分保存着字符数组。
• 11 表示 content 部分保存着整数。
content
content 部分保存着节点的内容，它的类型和长度由 encoding 和 length 决定
将节点添加到末端
将新节点添加到 ziplist 的末端需要执行以下三个步骤：
- 记录到达 ziplist 末端所需的偏移量（因为之后的内存重分配可能会改变 ziplist 的地址，因此记录偏移量而不是保存指针）
- 根据新节点要保存的值，计算出编码这个值所需的空间大小，以及编码它前一个节点的长度所需的空间大小，然后对 ziplist 进行内存重分配。
- 设置新节点的各项属性：pre_entry_length 、encoding 、length 和 content 。
- 更新 ziplist 的各项属性，比如记录空间占用的 zlbytes ，到达表尾节点的偏移量 zltail，以及记录节点数量的 zllen 。
将节点添加到某个/某些节点的前面
- 记录到达 ziplist 末端所需的偏移量（因为之后的内存重分配可能会改变 ziplist 的地址，因此记录偏移量而不是保存指针）
- 根据新节点要保存的值，计算出编码这个值所需的空间大小，以及编码它前一个节点的长度所需的空间大小，然后对 ziplist 进行内存重分配。
- 设置新节点的各项属性：pre_entry_length 、encoding 、length 和 content 。
- 更新 ziplist 的各项属性，比如记录空间占用的 zlbytes ，到达表尾节点的偏移量 zltail，以及记录节点数量的 zllen 。
- 将 new 节点的长度编码进 next 节点的 pre_entry_length 域里。这里会出现三种可能：
- next 的 pre_entry_length 域的长度正好能够编码 new 的长度（都是 1 字节或者都是 5字节）
- next 的 pre_entry_length 只有 1 字节长，但编码 new 的长度需要 5 字节
- next 的 pre_entry_length 有 5 字节长，但编码 new 的长度只需要 1 字节
对于情况 1 和 3 ，程序直接更新 next 的 pre_entry_length 域。
如果是第二种情况，那么程序必须对 ziplist 进行内存重分配，从而扩展 next 的空间。然而，因为 next 的空间长度改变了，所以程序又必须检查 next 的后继节点——next+1 ，看它的pre_entry_length 能否编码 next 的新长度，如果不能的话，程序又需要继续对 next+1 进行扩容。程序必须沿着路径一个个检查后续的节点是否满足新长度的编码要求，直到遇到一个能满足要求的节点（如果有一个能满足，那么这个节点之后的其他节点也满足），或者到达 ziplist 的末端 zlend 为止，这种检查操作的复杂度为O(N2) 。
删除节点
- 定位目标节点，并计算节点的空间长度 target-size
- 进行内存移位，覆盖 target 原本的数据，然后通过内存重分配，收缩多余空间
- 检查 next 、next+1 等后续节点能否满足新前驱节点的编码。和添加操作一样，删除操作也可能会引起连锁更新。
遍历
可以对 ziplist 进行从前向后的遍历，或者从后先前的遍历。
当进行从前向后的遍历时，程序从指向节点 e1 的指针 p 开始，计算节点 e1 的长度（e1-size），然后将 p 加上 e1-size ，就将指针后移到了下一个节点 e2 。
当进行从后往前遍历的时候，程序从指向节点 eN 的指针 p 出发，取出 eN 的 pre_entry_length值，然后用 p 减去 pre_entry_length ，这就将指针移动到了前一个节点 eN-1。
