Galxe - 二面 - 杭州 面经 已oc
（一个小时二十分钟）
1. 介绍一下最近三个月做的事情。
2. 对于 rocksdb 了解吗？（参与的开源项目中用到了）
3. 讲讲在这个项目中的用法。（对实现不太了解，从设计相关的角度讲了一下）
4. 假设你有一个集群，有一批大量的 kv（key 很大(无规律)，value很小）需要写入，你想想这里对读/写分别怎么优化？（大概从集群结构，然后梳理到单节点，之后讨论读写优化，讲异步写的时候提到了 WAL）
5. 项目中 WAL 怎么用的？（拉了一个具体的实现场景出来讲，ZSet SkipList优化实现相关，讲了流程）
6. 集群分片这里怎么实现？（上一轮面试和另一个面试官聊过，大概讲了一下）
7. 我看你这里有做集群的扩缩容，讲讲怎么做的。（本节点存一份连接信息，新增Voter，然后广播出去）
8. 我看你这里有一些内存泄漏的排查经验，可以讲讲平时怎么排查吗？（还是拉了一件具体做过的事情讲了整个排查到确认问题的过程）
9. 我看你这里Golang比较熟悉，做个题吧。（并发安全的LRUCache）
遇到两次了，贴个代码
package main
import (
"fmt"
"sync"
"sync/atomic"
"unsafe"
)
type Node struct {
key string
val string
next *Node
prev *Node
}
type LRUCache struct {
capacity int
size atomic.Int64
cache sync.Map // key -> *Node
head *Node
tail *Node
}
func NewLRUCache(capacity int) *LRUCache {
lru := &LRUCache{
capacity: capacity,
head: &Node{},
tail: &Node{},
}
lru.head.next = lru.tail
lru.tail.prev = lru.head
return lru
}
func (c *LRUCache) Get(key string) (string, bool) {
if node, ok := c.cache.Load(key); ok {
c.moveToHead(node.(*Node))
return node.(*Node).val, true
}
return "", false
}
func (c *LRUCache) Put(key string, value string) {
if node, ok := c.cache.Load(key); ok {
node.(*Node).val = value
c.moveToHead(node.(*Node))
return
}
newNode := &Node{key: key, val: value}
c.cache.Store(key, newNode)
c.addToHead(newNode)
c.size.Add(1)
if c.size.Load() > int64(c.capacity) {
removed := c.removeTail()
c.cache.Delete(removed.key)
c.size.Add(-1)
}
}
func (c *LRUCache) addToHead(n *Node) {
atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&n.prev)), unsafe.Pointer(n.prev), unsafe.Pointer(c.head))
atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&n.next)), unsafe.Pointer(n.next), unsafe.Pointer(c.head.next))
atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&c.head.next.prev)), unsafe.Pointer(c.head.next.prev), unsafe.Pointer(n))
atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&c.head.next)), unsafe.Pointer(c.head.next), unsafe.Pointer(n))
}
func (c *LRUCache) moveToHead(n *Node) {
c.removeNode(n)
c.addToHead(n)
}
func (c *LRUCache) removeNode(n *Node) {
atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&n.prev.next)), unsafe.Pointer(n.prev.next), unsafe.Pointer(n.next))
atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&n.next.prev)), unsafe.Pointer(n.next.prev), unsafe.Pointer(n.prev))
}
func (c *LRUCache) removeTail() *Node {
tail := c.tail.prev
c.removeNode(tail)
return tail
}
func main() {
// 创建一个容量为 2 的 LRUCache
c := NewLRUCache(2)
// 放入 k1, k2
c.Put("k1", "v1")
c.Put("k2", "v2")
// 再次获取 k1
if val, ok := c.Get("k1"); ok {
fmt.Println("Get k1:", val) // 期望输出 "v1"
} else {
fmt.Println("k1 不存在")
}
// 插入 k3，此时容量超出，应当淘汰最久未使用的元素 (k2 或 k1)
c.Put("k3", "v3")
// 检查 k2 是否被淘汰
if val, ok := c.Get("k2"); ok {
fmt.Println("Get k2:", val)
} else {
fmt.Println("k2 不存在，已经被淘汰")
}
// 继续查看 k3
if val, ok := c.Get("k3"); ok {
fmt.Println("Get k3:", val) // 期望输出 "v3"
} else {
fmt.Println("k3 不存在")
}
}
10. 继续做题。（假设在区块链中每次交易是一个最小事务，我现在需要保证并发进行的结果和串行的结果是一致的，怎么实现）
结构定义：
type Transaction struct {
ID string
WriteSet map[string]string // 准备写入的 key->newValue
}
测试数据：
txs := []Transaction{
{
ID: "Tx1",
WriteSet: map[string]string{
"A": "100",
"B": "200",
},
},
{
ID: "Tx2",
WriteSet: map[string]string{
"C": "300",
"B": "200",
},
},
{
ID: "Tx3",
WriteSet: map[string]string{
"A": "200",
},
},
}
大致意思就是现在串行的结果是 A = 200, B = 200, C = 300
需要修改为并发，并且并发执行的结果要和串行的一致。
思路：注意到 ID 的性质，可以根据 ID 确认哪个值更新，考虑类似多版本的思想，将 ID 作为结果的版本，并发执行时保存所有的版本，最终结果即每个key最新版本的值。
维护版本使用大根堆即可。如下：
type TxPair struct {
ID string
Value string
}
type TxPairHeap []TxPair
func (h TxPairHeap) Len() int { return len(h) }
func (h TxPairHeap) Less(i, j int) bool { return h[i].ID > h[j].ID }
func (h TxPairHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *TxPairHeap) Push(x interface{}) {
*h = append(*h, x.(TxPair))
}
func (h *TxPairHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
剩下的 goroutine + WaitGroup，不断Push到堆就行
func main() {
txs := []Transaction{
{
ID: "Tx1",
WriteSet: map[string]string{
"A": "100",
"B": "200",
},
},
{
ID: "Tx2",
WriteSet: map[string]string{
"C": "300",
"B": "200",
},
},
{
ID: "Tx3",
WriteSet: map[string]string{
"A": "200",
},
},
}
res := make(map[string]*TxPairHeap)
var wg sync.WaitGroup
mu := &sync.Mutex{}
for _, tx := range txs {
wg.Add(1)
go func(t Transaction) {
defer wg.Done()
mu.Lock()
defer mu.Unlock()
txID := t.ID
for k, v := range t.WriteSet {
var pairHeap *TxPairHeap
if _, ok := res[k]; ok {
pairHeap = res[k]
} else {
pairHeap = &TxPairHeap{}
res[k] = pairHeap
heap.Init(pairHeap)
}
pairHeap.Push(TxPair{ID: txID, Value: v})
}
}(tx)
}
wg.Wait()
for k, hp := range res {
fmt.Println("Key = ", k, "Value = ", hp.Pop().(TxPair).Value)
}
}
11. 这里如果我每个交易都需要一个前提条件的完成后才能进行，怎么办，讲讲思路。（引入拓扑，维护拓扑性质的前提下维护堆性质）
---
结束。
有些问题忘了（
---
2.24 update: oc
#面经#
查看6道真题和解析