Slim
Slim 是一组非常节省空间的数据类型，带有相应的序列化 API 以将它们保存在磁盘上或传输。
why slim
随着互联网上的数据呈指数级增长，内存和磁盘之间的容量差距变得更大。
大多数时候，数据本身不需要加载到昂贵的主内存中。
只有更重要的信息 WHERE-A-DATA-IS 才值得在主内存中占有一席之地。
这就是slim所做的，在主内存中保留尽可能少的信息，作为大量外部数据的最小化索引。
特征：
最小化：每个密钥 11 位（远小于 64 位指针！！）。
稳定：内存消耗在各种场景下都是稳定的。 最坏情况紧密地收敛于平均消费。 参见基准。
Loooong 密钥：您可以拥有非常长的密钥（16K 字节），而不会浪费任何内存（和金钱）。 不要浪费你的生命写另一个前缀压缩:)。 （aws-s3 将密钥长度限制为 1024 字节）。 内存消耗仅与密钥数量有关，与密钥长度无关。
有序：像 btree 一样，键被存储。 范围扫描将在 0.6.0 中准备就绪。
快速：每个 Get() 约 150 ns。 get 的时间复杂度为 O(log(n) + k)； n：键数； k：密钥长度。
准备好传输：一个 proto.Marshal() 是序列化、传输或持久化磁盘等所需的全部。
内存开销
随机字符串，固定长度，默认模式，如果可能的话不存储标签：
位/键：一个键平均消耗的内存或磁盘空间（以位为单位）。 当 key-length(k) 变大时它不会改变！
100 万个 var-length 字符串，10 到 20 字节的不同模式 SlimTrie：
概要
索引键，按键获取
[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
63package index_test
import (
"fmt"
"strings"
"github.com/openacid/slim/index"
)
type Data string
func (d Data) Read(offset int64, key string) (string, bool) {
kv := strings.Split(string(d)[offset:], ",")[0:2]
if kv[0] == key {
return kv[1], true
}
return "", false
}
func Example() {
// Accelerate external data accessing (in memory or on disk) by indexing
// them with a SlimTrie:
// `data` is a sample of some unindexed data. In our example it is a comma
// separated key value series.
//
// In order to let SlimTrie be able to read data, `data` should have
// a `Read` method:
// Read(offset int64, key string) (string, bool)
data := Data("Aaron,1,Agatha,1,Al,2,Albert,3,Alexander,5,Alison,8")
// keyOffsets is a prebuilt index that stores key and its offset in data accordingly.
keyOffsets := []index.OffsetIndexItem{
{Key: "Aaron", Offset: 0},
{Key: "Agatha", Offset: 8},
{Key: "Al", Offset: 17},
{Key: "Albert", Offset: 22},
{Key: "Alexander", Offset: 31},
{Key: "Alison", Offset: 43},
}
// `SlimIndex` is simply a container of SlimTrie and its data.
st, err := index.NewSlimIndex(keyOffsets, data)
if err != nil {
fmt.Println(err)
}
// Lookup
v, found := st.Get("Alison")
fmt.Printf("key: %q\n found: %t\n value: %q\n", "Alison", found, v)
v, found = st.Get("foo")
fmt.Printf("key: %q\n found: %t\n value: %q\n", "foo", found, v)
// Output:
// key: "Alison"
// found: true
// value: "8"
// key: "foo"
// found: false
// value: ""
}
索引键范围，按键获取
为每 4 个（或更多，如您所愿）键创建一个索引项。
如果外部数据中有大量的键，让几个相邻的键共享一个索引项可以减少很多内存成本。
例如在 4TB 磁盘上索引数十亿个 4KB 对象（因为一个磁盘 IO 读取 4KB 或读取 1MB 的成本为 20ms）。
[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
78package index_test
import (
"fmt"
"strings"
"github.com/openacid/slim/index"
)
type RangeData string
func (d RangeData) Read(offset int64, key string) (string, bool) {
for i := 0; i < 4; i++ {
if int(offset) >= len(d) {
break
}
kv := strings.Split(string(d)[offset:], ",")[0:2]
if kv[0] == key {
return kv[1], true
}
offset += int64(len(kv[0]) + len(kv[1]) + 2)
}
return "", false
}
func Example_indexRanges() {
// Index ranges instead of keys:
// In this example at most 4 keys shares one index item.
data := RangeData("Aaron,1,Agatha,1,Al,2,Albert,3,Alexander,5,Alison,8")
// keyOffsets is a prebuilt index that stores range start, range end and its offset.
keyOffsets := []index.OffsetIndexItem{
// Aaron +--> 0
// Agatha |
// Al |
// Albert |
// Alexander +--> 31
// Alison |
{Key: "Aaron", Offset: 0},
{Key: "Agatha", Offset: 0},
{Key: "Al", Offset: 0},
{Key: "Albert", Offset: 0},
{Key: "Alexander", Offset: 31},
{Key: "Alison", Offset: 31},
}
st, err := index.NewSlimIndex(keyOffsets, data)
if err != nil {
panic(err)
}
v, found := st.RangeGet("Aaron")
fmt.Printf("key: %q\n found: %t\n value: %q\n", "Aaron", found, v)
v, found = st.RangeGet("Al")
fmt.Printf("key: %q\n found: %t\n value: %q\n", "Al", found, v)
v, found = st.RangeGet("foo")
fmt.Printf("key: %q\n found: %t\n value: %q\n", "foo", found, v)
// Output:
// key: "Aaron"
// found: true
// value: "1"
// key: "Al"
// found: true
// value: "2"
// key: "foo"
// found: false
// value: ""
}
Scan
[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
80package trie
import (
"fmt"
"github.com/openacid/slim/encode"
)
func ExampleSlimTrie_ScanFrom() {
var keys = []string{
"",
"`",
"a",
"ab",
"abc",
"abca",
"abcd",
"abcd1",
"abce",
"be",
"c",
"cde0",
"d",
}
values := makeI32s(len(keys))
codec := encode.I32{}
st, _ := NewSlimTrie(codec, keys, values, Opt{
Complete: Bool(true),
})
// untilD stops when encountering "d".
untilD := func(k, v []byte) bool {
if string(k) == "d" {
return false
}
_, i32 := codec.Decode(v)
fmt.Println(string(k), i32)
return true
}
fmt.Println("scan (ab, +∞):")
st.ScanFrom("ab", false, true, untilD)
fmt.Println()
fmt.Println("scan [be, +∞):")
st.ScanFrom("be", true, true, untilD)
fmt.Println()
fmt.Println("scan (ab, be):")
st.ScanFromTo(
"ab", false,
"be", false,
true, untilD)
// Output:
//
// scan (ab, +∞):
// abc 4
// abca 5
// abcd 6
// abcd1 7
// abce 8
// be 9
// c 10
// cde0 11
//
// scan [be, +∞):
// be 9
// c 10
// cde0 11
//
// scan (ab, be):
// abc 4
// abca 5
// abcd 6
// abcd1 7
// abce 8
}
参考资料
https://github.com/openacid/slim
