keys.go raw
1 package store
2
3 // Index key layout. Every key starts with a three-byte prefix followed by
4 // fixed-width fields, so a file can be binary-searched by CmpLen bytes and a
5 // range scan is a pair of key constructions.
6
7 type prefix [3]byte
8
9 var (
10 pEid = prefix{'e', 'i', 'd'} // id hash + serial
11 pFpc = prefix{'f', 'p', 'c'} // serial -> full id + pubkey hash + timestamp
12 pSei = prefix{'s', 'e', 'i'} // serial -> full event id
13 pCA = prefix{'c', '-', '-'} // created_at + serial
14 pExp = prefix{'e', 'x', 'p'} // expiration + serial
15 pKC = prefix{'k', 'c', '-'} // kind + created_at + serial
16 pPC = prefix{'p', 'c', '-'} // pubkey hash + created_at + serial
17 pKPC = prefix{'k', 'p', 'c'} // kind + pubkey hash + created_at + serial
18 pTC = prefix{'t', 'c', '-'} // tag letter + value hash + created_at + serial
19 pTKC = prefix{'t', 'k', 'c'} // kind + tag letter + value hash + created_at + serial
20 pTPC = prefix{'t', 'p', 'c'} // pubkey hash + tag letter + value hash + created_at + serial
21 pTKP = prefix{'t', 'k', 'p'} // kind + pubkey hash + tag letter + value hash + created_at + serial
22 pWrd = prefix{'w', 'r', 'd'} // word hash + serial
23 pRep = prefix{'r', 'e', 'p'} // kind + pubkey hash + d hash + created_at + serial
24 pDel = prefix{'d', 'e', 'l'} // full 32-byte event id
25
26 // Pubkey serials make the graph indexes fixed-width: a pubkey is resolved
27 // to its serial once and every edge then carries five bytes instead of 32.
28 pPks = prefix{'p', 'k', 's'} // pubkey hash + pubkey serial
29 pSpk = prefix{'s', 'p', 'k'} // pubkey serial -> full 32-byte pubkey
30
31 // Social graph indexes. The two index families are the forward and reverse
32 // direction of the same edge, so each traversal is one prefix scan.
33 pEpg = prefix{'e', 'p', 'g'} // event -> pubkey
34 pPeg = prefix{'p', 'e', 'g'} // pubkey -> event
35 pEeg = prefix{'e', 'e', 'g'} // event -> event (outbound e-tags)
36 pGee = prefix{'g', 'e', 'e'} // event -> event (inbound e-tags)
37 pPpg = prefix{'p', 'p', 'g'} // pubkey -> pubkey (outbound)
38 pGpp = prefix{'g', 'p', 'p'} // pubkey -> pubkey (inbound)
39 )
40
41 // Graph edge directions. These values are on-disk bytes and must not change.
42 const (
43 DirAuthor byte = 0 // event author edge
44 DirPTagOut byte = 1 // event references pubkey via p tag
45 DirPTagIn byte = 2 // pubkey is referenced by an event's p tag
46
47 DirETagOut byte = 0 // event references target event via e tag
48 DirETagIn byte = 1 // event is referenced by source event via e tag
49
50 DirPKOut byte = 0 // pubkey references another pubkey
51 DirPKIn byte = 1 // pubkey is referenced by another pubkey
52 )
53
54 // Record and comparison lengths.
55 const (
56 eidRecLen = 3 + HashLen + SerialLen
57 eidCmpLen = 3 + HashLen
58
59 fpcRecLen = 3 + SerialLen + 32 + HashLen + 8
60 fpcCmpLen = 3 + SerialLen
61
62 seiRecLen = 3 + SerialLen
63 seiCmpLen = 3 + SerialLen
64 seiValLen = 32
65
66 caRecLen = 3 + 8 + SerialLen
67 caCmpLen = caRecLen
68 expRecLen = caRecLen
69 expCmpLen = expRecLen
70
71 kcRecLen = 3 + 2 + 8 + SerialLen
72 kcCmpLen = kcRecLen
73
74 pcRecLen = 3 + HashLen + 8 + SerialLen
75 pcCmpLen = pcRecLen
76
77 kpcRecLen = 3 + 2 + HashLen + 8 + SerialLen
78 kpcCmpLen = kpcRecLen
79
80 tcRecLen = 3 + 1 + HashLen + 8 + SerialLen
81 tcCmpLen = tcRecLen
82
83 tkcRecLen = 3 + 2 + 1 + HashLen + 8 + SerialLen
84 tkcCmpLen = tkcRecLen
85
86 tpcRecLen = 3 + HashLen + 1 + HashLen + 8 + SerialLen
87 tpcCmpLen = tpcRecLen
88
89 tkpRecLen = 3 + 2 + HashLen + 1 + HashLen + 8 + SerialLen
90 tkpCmpLen = tkpRecLen
91
92 wrdRecLen = 3 + HashLen + SerialLen
93 wrdCmpLen = wrdRecLen
94
95 repRecLen = 3 + 2 + HashLen + HashLen + 8 + SerialLen
96 repCmpLen = repRecLen
97
98 delRecLen = 3 + 32
99 delCmpLen = delRecLen
100
101 pksRecLen = 3 + HashLen + SerialLen // 16
102 pksCmpLen = 3 + HashLen // 11
103
104 spkRecLen = 3 + SerialLen // 8: key
105 spkValLen = 32 // + pubkey
106 spkCmpLen = spkRecLen // 8
107
108 epgRecLen = 3 + SerialLen + SerialLen + 2 + 1 // 16
109 pegRecLen = epgRecLen
110 eegRecLen = epgRecLen
111 geeRecLen = epgRecLen
112
113 ppgRecLen = 3 + SerialLen + SerialLen + 2 + 1 + SerialLen // 21
114 gppRecLen = ppgRecLen
115 )
116
117 func newKey(p prefix, n int) []byte {
118 k := make([]byte, n)
119 copy(k, p[:])
120 return k
121 }
122
123 // prefixEnd returns the smallest key greater than every key starting with p.
124 func prefixEnd(p []byte) []byte {
125 out := make([]byte, len(p))
126 copy(out, p)
127 for i := len(out) - 1; i >= 0; i-- {
128 out[i]++
129 if out[i] != 0 {
130 return out[:i+1]
131 }
132 }
133 // Every byte was 0xff: there is no successor. Callers use end==nil to mean
134 // "to the end of the index".
135 return nil
136 }
137
138 func appendHash(dst []byte, h [HashLen]byte) []byte { return append(dst, h[:]...) }
139
140 func makeEid(idHash [HashLen]byte, ser uint64) []byte {
141 k := newKey(pEid, eidRecLen)
142 copy(k[3:], idHash[:])
143 PutSerial(k[3+HashLen:], ser)
144 return k
145 }
146
147 func makeEidPrefix(idHash [HashLen]byte) []byte {
148 k := make([]byte, eidCmpLen)
149 copy(k, pEid[:])
150 copy(k[3:], idHash[:])
151 return k
152 }
153
154 func makeSei(ser uint64) []byte {
155 k := newKey(pSei, seiRecLen)
156 PutSerial(k[3:], ser)
157 return k
158 }
159
160 func makeSeiRec(ser uint64, id []byte) []byte {
161 rec := make([]byte, seiRecLen+seiValLen)
162 copy(rec, pSei[:])
163 PutSerial(rec[3:], ser)
164 copy(rec[seiRecLen:], id[:32])
165 return rec
166 }
167
168 func makeFpc(ser uint64, id, pubHash []byte, ts int64) []byte {
169 k := newKey(pFpc, fpcRecLen)
170 PutSerial(k[3:], ser)
171 copy(k[3+SerialLen:], id[:32])
172 copy(k[3+SerialLen+32:], pubHash[:HashLen])
173 PutTimestamp(k[3+SerialLen+32+HashLen:], ts)
174 return k
175 }
176
177 func makeCA(p prefix, ts int64, ser uint64, n int) []byte {
178 k := newKey(p, n)
179 PutTimestamp(k[3:], ts)
180 PutSerial(k[3+8:], ser)
181 return k
182 }
183
184 func makeKC(kind int, ts int64, ser uint64) []byte {
185 k := newKey(pKC, kcRecLen)
186 PutKind(k[3:], kind)
187 PutTimestamp(k[5:], ts)
188 PutSerial(k[13:], ser)
189 return k
190 }
191
192 func makePC(pubHash [HashLen]byte, ts int64, ser uint64) []byte {
193 k := newKey(pPC, pcRecLen)
194 copy(k[3:], pubHash[:])
195 PutTimestamp(k[3+HashLen:], ts)
196 PutSerial(k[3+HashLen+8:], ser)
197 return k
198 }
199
200 func makeKPC(kind int, pubHash [HashLen]byte, ts int64, ser uint64) []byte {
201 k := newKey(pKPC, kpcRecLen)
202 PutKind(k[3:], kind)
203 copy(k[5:], pubHash[:])
204 PutTimestamp(k[5+HashLen:], ts)
205 PutSerial(k[5+HashLen+8:], ser)
206 return k
207 }
208
209 func makeTC(tag byte, valHash [HashLen]byte, ts int64, ser uint64) []byte {
210 k := newKey(pTC, tcRecLen)
211 k[3] = tag
212 copy(k[4:], valHash[:])
213 PutTimestamp(k[4+HashLen:], ts)
214 PutSerial(k[4+HashLen+8:], ser)
215 return k
216 }
217
218 func makeTKC(kind int, tag byte, valHash [HashLen]byte, ts int64, ser uint64) []byte {
219 k := newKey(pTKC, tkcRecLen)
220 PutKind(k[3:], kind)
221 k[5] = tag
222 copy(k[6:], valHash[:])
223 PutTimestamp(k[6+HashLen:], ts)
224 PutSerial(k[6+HashLen+8:], ser)
225 return k
226 }
227
228 func makeTPC(pubHash [HashLen]byte, tag byte, valHash [HashLen]byte, ts int64, ser uint64) []byte {
229 k := newKey(pTPC, tpcRecLen)
230 copy(k[3:], pubHash[:])
231 k[3+HashLen] = tag
232 copy(k[4+HashLen:], valHash[:])
233 PutTimestamp(k[4+HashLen+HashLen:], ts)
234 PutSerial(k[4+HashLen+HashLen+8:], ser)
235 return k
236 }
237
238 func makeTKP(kind int, pubHash [HashLen]byte, tag byte, valHash [HashLen]byte, ts int64, ser uint64) []byte {
239 k := newKey(pTKP, tkpRecLen)
240 PutKind(k[3:], kind)
241 copy(k[5:], pubHash[:])
242 k[5+HashLen] = tag
243 copy(k[6+HashLen:], valHash[:])
244 PutTimestamp(k[6+HashLen+HashLen:], ts)
245 PutSerial(k[6+HashLen+HashLen+8:], ser)
246 return k
247 }
248
249 func makeWrd(wordHash [HashLen]byte, ser uint64) []byte {
250 k := newKey(pWrd, wrdRecLen)
251 copy(k[3:], wordHash[:])
252 PutSerial(k[3+HashLen:], ser)
253 return k
254 }
255
256 func makeRep(kind int, pubHash, dHash [HashLen]byte, ts int64, ser uint64) []byte {
257 k := newKey(pRep, repRecLen)
258 PutKind(k[3:], kind)
259 copy(k[5:], pubHash[:])
260 copy(k[5+HashLen:], dHash[:])
261 PutTimestamp(k[5+2*HashLen:], ts)
262 PutSerial(k[5+2*HashLen+8:], ser)
263 return k
264 }
265
266 func makeRepPrefix(kind int, pubHash, dHash [HashLen]byte) []byte {
267 k := make([]byte, 5+2*HashLen)
268 copy(k, pRep[:])
269 PutKind(k[3:], kind)
270 copy(k[5:], pubHash[:])
271 copy(k[5+HashLen:], dHash[:])
272 return k
273 }
274
275 func makeDel(id []byte) []byte {
276 k := newKey(pDel, delRecLen)
277 copy(k[3:], id[:32])
278 return k
279 }
280
281 // --- pubkey serial keys ---
282
283 func makePks(h [HashLen]byte, ser uint64) []byte {
284 k := newKey(pPks, pksRecLen)
285 copy(k[3:], h[:])
286 PutSerial(k[3+HashLen:], ser)
287 return k
288 }
289
290 func makePksPrefix(h [HashLen]byte) []byte {
291 k := make([]byte, pksCmpLen)
292 copy(k, pPks[:])
293 copy(k[3:], h[:])
294 return k
295 }
296
297 func makeSpk(ser uint64) []byte {
298 k := newKey(pSpk, spkRecLen)
299 PutSerial(k[3:], ser)
300 return k
301 }
302
303 func makeSpkRec(ser uint64, pubkey []byte) []byte {
304 rec := make([]byte, spkRecLen+spkValLen)
305 copy(rec, pSpk[:])
306 PutSerial(rec[3:], ser)
307 copy(rec[spkRecLen:], pubkey[:32])
308 return rec
309 }
310
311 // --- graph index keys ---
312
313 // makeEpg: epg|event_serial|pubkey_serial|kind|direction.
314 func makeEpg(evSer, pkSer uint64, kind int, dir byte) []byte {
315 k := newKey(pEpg, epgRecLen)
316 PutSerial(k[3:], evSer)
317 PutSerial(k[8:], pkSer)
318 PutKind(k[13:], kind)
319 k[15] = dir
320 return k
321 }
322
323 // makePeg: peg|pubkey_serial|kind|direction|event_serial.
324 func makePeg(pkSer uint64, kind int, dir byte, evSer uint64) []byte {
325 k := newKey(pPeg, pegRecLen)
326 PutSerial(k[3:], pkSer)
327 PutKind(k[8:], kind)
328 k[10] = dir
329 PutSerial(k[11:], evSer)
330 return k
331 }
332
333 // makeEeg: eeg|source_serial|target_serial|kind|direction.
334 func makeEeg(srcSer, tgtSer uint64, kind int, dir byte) []byte {
335 k := newKey(pEeg, eegRecLen)
336 PutSerial(k[3:], srcSer)
337 PutSerial(k[8:], tgtSer)
338 PutKind(k[13:], kind)
339 k[15] = dir
340 return k
341 }
342
343 // makeGee: gee|target_serial|kind|direction|source_serial.
344 func makeGee(tgtSer uint64, kind int, dir byte, srcSer uint64) []byte {
345 k := newKey(pGee, geeRecLen)
346 PutSerial(k[3:], tgtSer)
347 PutKind(k[8:], kind)
348 k[10] = dir
349 PutSerial(k[11:], srcSer)
350 return k
351 }
352
353 // makePpg: ppg|source_pk|target_pk|kind|direction|event_serial.
354 func makePpg(srcPK, tgtPK uint64, kind int, dir byte, evSer uint64) []byte {
355 k := newKey(pPpg, ppgRecLen)
356 PutSerial(k[3:], srcPK)
357 PutSerial(k[8:], tgtPK)
358 PutKind(k[13:], kind)
359 k[15] = dir
360 PutSerial(k[16:], evSer)
361 return k
362 }
363
364 // makeGpp: gpp|target_pk|kind|direction|source_pk|event_serial.
365 func makeGpp(tgtPK uint64, kind int, dir byte, srcPK, evSer uint64) []byte {
366 k := newKey(pGpp, gppRecLen)
367 PutSerial(k[3:], tgtPK)
368 PutKind(k[8:], kind)
369 k[10] = dir
370 PutSerial(k[11:], srcPK)
371 PutSerial(k[16:], evSer)
372 return k
373 }
374
375 // graphPrefix returns the fixed-width prefix for a graph serial scan.
376 func graphPrefix(p prefix, ser uint64) []byte {
377 k := newKey(p, 3+SerialLen)
378 PutSerial(k[3:], ser)
379 return k
380 }
381