-
Notifications
You must be signed in to change notification settings - Fork 0
/
memtable.go
140 lines (113 loc) · 2.67 KB
/
memtable.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
package memtable
import (
"github.com/cespare/xxhash"
"github.com/coocood/freecache"
"math/bits"
"time"
)
// Memtable ...
type Memtable struct {
leases []leaseList
mask uint32
cache *freecache.Cache
}
// New ...
func New(memsize int, options ...Option) *Memtable {
opts := computeOptions(options...)
leases := make([]leaseList, opts.numBuckets)
for i := range leases {
leases[i].init(opts.entryListSize, opts.leaseTimeout)
}
return &Memtable{
leases: leases,
cache: freecache.NewCache(memsize),
mask: opts.numBuckets - 1,
}
}
func hashFunc(data []byte) uint64 {
return xxhash.Sum64(data)
}
func getNow() uint32 {
return uint32(time.Now().Unix())
}
// GetStatus for cache Get
type GetStatus int
const (
// GetStatusFound for normal cache hit case
GetStatusFound GetStatus = iota
// GetStatusLeaseGranted when cache miss and lease is granted
GetStatusLeaseGranted
// GetStatusLeaseRejected when cache miss and lease is not granted
GetStatusLeaseRejected
)
// GetResult for result when calling Get
type GetResult struct {
Value []byte
LeaseID uint32
Status GetStatus
}
func computeHashKeyAndIndex(hash uint64, mask uint32) (uint32, uint32) {
return uint32(hash >> 32), uint32(hash) & mask
}
func (m *Memtable) getLeaseList(key []byte) (uint32, *leaseList) {
hash := hashFunc(key)
hashKey, index := computeHashKeyAndIndex(hash, m.mask)
return hashKey, &m.leases[index]
}
// Get value from the cache
func (m *Memtable) Get(key []byte) GetResult {
hashKey, l := m.getLeaseList(key)
l.mut.Lock()
defer l.mut.Unlock()
value, err := m.cache.Get(key)
if err == freecache.ErrNotFound {
leaseID, ok := l.getLease(hashKey, getNow())
if !ok {
return GetResult{
Status: GetStatusLeaseRejected,
}
}
return GetResult{
LeaseID: leaseID,
Status: GetStatusLeaseGranted,
}
}
return GetResult{
Value: value,
Status: GetStatusFound,
}
}
// Set value to the cache
func (m *Memtable) Set(key []byte, leaseID uint32, value []byte) (affected bool) {
hashKey, l := m.getLeaseList(key)
l.mut.Lock()
defer l.mut.Unlock()
deleted := l.deleteLease(hashKey, leaseID)
if !deleted {
return false
}
err := m.cache.Set(key, value, 0)
if err != nil {
return false
}
return true
}
// Invalidate an entry from the cache
func (m *Memtable) Invalidate(key []byte) (affected bool) {
hashKey, l := m.getLeaseList(key)
l.mut.Lock()
defer l.mut.Unlock()
l.forceDelete(hashKey)
return m.cache.Del(key)
}
// GetUnsafeInnerCache returns the freecache
func (m *Memtable) GetUnsafeInnerCache() *freecache.Cache {
return m.cache
}
func ceilPowerOfTwo(n uint32) uint32 {
if n == 0 {
return 1
}
shift := 32 - bits.LeadingZeros32(n-1)
return 1 << shift
}