Galxe - 二面 - 杭州 面經(jīng) 已oc
（一個(gè)小時(shí)二十分鐘）
1. 介紹一下最近三個(gè)月做的事情。
2. 對(duì)于 rocksdb 了解嗎？（參與的開(kāi)源項(xiàng)目中用到了）
3. 講講在這個(gè)項(xiàng)目中的用法。（對(duì)實(shí)現(xiàn)不太了解，從設(shè)計(jì)相關(guān)的角度講了一下）
4. 假設(shè)你有一個(gè)集群，有一批大量的 kv（key 很大(無(wú)規(guī)律)，value很?。┬枰獙懭耄阆胂脒@里對(duì)讀/寫分別怎么優(yōu)化？（大概從集群結(jié)構(gòu)，然后梳理到單節(jié)點(diǎn)，之后討論讀寫優(yōu)化，講異步寫的時(shí)候提到了 WAL）
5. 項(xiàng)目中 WAL 怎么用的？（拉了一個(gè)具體的實(shí)現(xiàn)場(chǎng)景出來(lái)講，ZSet SkipList優(yōu)化實(shí)現(xiàn)相關(guān)，講了流程）
6. 集群分片這里怎么實(shí)現(xiàn)？（上一輪面試和另一個(gè)面試官聊過(guò)，大概講了一下）
7. 我看你這里有做集群的擴(kuò)縮容，講講怎么做的。（本節(jié)點(diǎn)存一份連接信息，新增Voter，然后廣播出去）
8. 我看你這里有一些內(nèi)存泄漏的排查經(jīng)驗(yàn)，可以講講平時(shí)怎么排查嗎？（還是拉了一件具體做過(guò)的事情講了整個(gè)排查到確認(rèn)問(wèn)題的過(guò)程）
9. 我看你這里Golang比較熟悉，做個(gè)題吧。（并發(fā)安全的LRUCache）
遇到兩次了，貼個(gè)代碼
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() {
// 創(chuàng)建一個(gè)容量為 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，此時(shí)容量超出，應(yīng)當(dāng)淘汰最久未使用的元素 (k2 或 k1)
c.Put("k3", "v3")
// 檢查 k2 是否被淘汰
if val, ok := c.Get("k2"); ok {
fmt.Println("Get k2:", val)
} else {
fmt.Println("k2 不存在，已經(jīng)被淘汰")
}
// 繼續(xù)查看 k3
if val, ok := c.Get("k3"); ok {
fmt.Println("Get k3:", val) // 期望輸出 "v3"
} else {
fmt.Println("k3 不存在")
}
}
10. 繼續(xù)做題。（假設(shè)在區(qū)塊鏈中每次交易是一個(gè)最小事務(wù)，我現(xiàn)在需要保證并發(fā)進(jìn)行的結(jié)果和串行的結(jié)果是一致的，怎么實(shí)現(xiàn)）
結(jié)構(gòu)定義：
type Transaction struct {
ID string
WriteSet map[string]string // 準(zhǔn)備寫入的 key->newValue
}
測(cè)試數(shù)據(jù)：
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",
},
},
}
大致意思就是現(xiàn)在串行的結(jié)果是 A = 200, B = 200, C = 300
需要修改為并發(fā)，并且并發(fā)執(zhí)行的結(jié)果要和串行的一致。
思路：注意到 ID 的性質(zhì)，可以根據(jù) ID 確認(rèn)哪個(gè)值更新，考慮類似多版本的思想，將 ID 作為結(jié)果的版本，并發(fā)執(zhí)行時(shí)保存所有的版本，最終結(jié)果即每個(gè)key最新版本的值。
維護(hù)版本使用大根堆即可。如下：
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. 這里如果我每個(gè)交易都需要一個(gè)前提條件的完成后才能進(jìn)行，怎么辦，講講思路。（引入拓?fù)?，維護(hù)拓?fù)湫再|(zhì)的前提下維護(hù)堆性質(zhì)）
---
結(jié)束。
有些問(wèn)題忘了（
---
2.24 update: oc
#面經(jīng)#
查看22道真題和解析
好未來(lái)開(kāi)獎(jiǎng)13人在聊