Line data Source code
1 : #ifndef HEADER_fd_src_disco_store_fd_shredb_h
2 : #define HEADER_fd_src_disco_store_fd_shredb_h
3 :
4 : #include "../../ballet/shred/fd_shred.h"
5 :
6 : /* An on-disk shred store for serving repair requests.
7 :
8 : Unlike fd_store, fd_shredb stores individual raw shreds keyed
9 : by (slot, shred_index) and is optimized for random lookups.
10 :
11 : To speedup the HighestShred query, we have two hashmaps.
12 : - A per-slot map, which tracks what the highest known index for a slot is.
13 : - A per-shred map, keyed by (slot, shred_index) and
14 : contains the ring buffer position for a shred.
15 :
16 : The ring buffer is file-backend, and maps to a fixed-size circular array
17 : of shred entries. FIFO evicition by advancing the write head allows us
18 : to retain only the newest entries.
19 :
20 : NOTE: For now, this design does not have any WAL or crash recovery.
21 :
22 : NOTE: In the current design, the Rserve tile subscribes to the
23 : shred_out link for getting the shreds, but we may have the shred tile
24 : write directly into the store in the future. */
25 :
26 :
27 : FD_FN_CONST static inline ulong
28 3120981 : fd_shredb_key_pack( ulong slot, uint shred_idx ) {
29 3120981 : return (slot << 16) | (ulong)(ushort)shred_idx;
30 3120981 : }
31 :
32 : FD_FN_CONST static inline ulong
33 483864 : fd_shredb_key_slot( ulong key ) {
34 483864 : return fd_ulong_extract( key, 16, 63 );
35 483864 : }
36 :
37 : FD_FN_CONST static inline uint
38 483867 : fd_shredb_key_shred_idx( ulong key ) {
39 483867 : return (uint)fd_ulong_extract( key, 0, 15 );
40 483867 : }
41 :
42 : /* per-shred entry, (slot, shred_index) -> ring_idx */
43 : struct fd_shredb_shred_entry {
44 : ulong key;
45 : ulong ring_idx;
46 : };
47 : typedef struct fd_shredb_shred_entry fd_shredb_shred_entry_t;
48 :
49 : #define MAP_NAME fd_shredb_shred_map
50 6665571 : #define MAP_T fd_shredb_shred_entry_t
51 36444027 : #define MAP_KEY_T ulong
52 30727272 : #define MAP_KEY_NULL ULONG_MAX
53 36444027 : #define MAP_KEY_INVAL(k) ((k)==ULONG_MAX)
54 25180875 : #define MAP_KEY_EQUAL(k0,k1) ((k0)==(k1))
55 14384118 : #define MAP_KEY_HASH(k,seed) ((uint)fd_ulong_hash( (k) ^ (seed) ))
56 : #define MAP_MEMOIZE 0
57 : #define MAP_KEY_EQUAL_IS_SLOW 0
58 : #include "../../util/tmpl/fd_map_dynamic.c"
59 :
60 : /* per-slot entry, slot -> (highest_shred_idx, cnt) */
61 : struct fd_shredb_slot_entry {
62 : ulong key;
63 : uint highest_shred_idx; /* highest shred_idx we have for this slot */
64 : ulong cnt; /* number of shreds we have for this slot */
65 : };
66 : typedef struct fd_shredb_slot_entry fd_shredb_slot_entry_t;
67 :
68 : #define MAP_NAME fd_shredb_slot_map
69 3730668 : #define MAP_T fd_shredb_slot_entry_t
70 14930151 : #define MAP_KEY_T ulong
71 958230 : #define MAP_KEY_NULL ULONG_MAX
72 14930151 : #define MAP_KEY_INVAL(k) ((k)==ULONG_MAX)
73 14582982 : #define MAP_KEY_EQUAL(k0,k1) ((k0)==(k1))
74 3966786 : #define MAP_KEY_HASH(k,seed) ((uint)fd_ulong_hash( (k) ^ (seed) ))
75 : #define MAP_MEMOIZE 0
76 : #define MAP_KEY_EQUAL_IS_SLOW 0
77 : #include "../../util/tmpl/fd_map_dynamic.c"
78 :
79 : /* On-disk ring buffer entry. */
80 : struct __attribute__((aligned(64))) fd_shredb_entry {
81 : ulong key; /* for reverse lookups on eviction */
82 : ushort shred_sz; /* actual shred byte count */
83 : uchar occupied; /* 1 if this slot holds valid data */
84 : uchar shred[FD_SHRED_MAX_SZ];
85 : };
86 : typedef struct fd_shredb_entry fd_shredb_entry_t;
87 :
88 : struct fd_shredb {
89 : ulong max_shreds; /* ring buffer capacity */
90 : ulong write_head; /* next ring position to write */
91 : ulong cnt; /* current number of entries */
92 : void * mapped;
93 : ulong mapped_sz; /* the size of `mapped` in bytes */
94 : int fd; /* file descriptor for the backing file */
95 : ulong file_shreds; /* current file capacity in shred entries */
96 : fd_shredb_shred_entry_t * shred_map;
97 : fd_shredb_slot_entry_t * slot_map;
98 : };
99 : typedef struct fd_shredb fd_shredb_t;
100 :
101 : FD_PROTOTYPES_BEGIN
102 :
103 : FD_FN_CONST static inline ulong
104 288 : fd_shredb_align( void ) {
105 : return alignof(fd_shredb_t);
106 288 : }
107 :
108 : FD_FN_CONST ulong
109 : fd_shredb_footprint( ulong max_size_gib );
110 :
111 : void *
112 : fd_shredb_new( void * shmem,
113 : ulong max_size_gib,
114 : char const * file_path,
115 : ulong seed );
116 :
117 : fd_shredb_t *
118 : fd_shredb_join( void * shstore );
119 :
120 : void *
121 : fd_shredb_leave( fd_shredb_t const * store );
122 :
123 : void *
124 : fd_shredb_delete( void * shstore );
125 :
126 : /* Insert a complete shred into the store. shred_sz is the result of
127 : fd_shred_sz( shred ). Derives (slot, shred_idx) from the header. */
128 : void
129 : fd_shredb_insert( fd_shredb_t * store,
130 : fd_shred_t const * shred,
131 : ulong shred_sz );
132 :
133 : /* Given a (slot, shred_index), returns the corresponding entry.
134 : If no entry was found, returns -1, otherwise returns the amount
135 : of bytes written to out. */
136 : int
137 : fd_shredb_query( fd_shredb_t * store,
138 : ulong slot,
139 : uint shred_idx,
140 : uchar out[ FD_SHRED_MAX_SZ ] );
141 :
142 : /* Given a (slot, min_shred_idx), returns the highest shred the store
143 : knows of for that slot.
144 :
145 : If the store has no shreds for the given slot, or does not have a shred
146 : with a high enough index, returns -1, otherwise returns the amount of
147 : bytes written to out. */
148 : int
149 : fd_shredb_query_highest( fd_shredb_t * store,
150 : ulong slot,
151 : uint min_shred_idx,
152 : uchar out[ FD_SHRED_MAX_SZ ] );
153 :
154 : FD_PROTOTYPES_END
155 :
156 : #endif /* HEADER_fd_src_disco_store_fd_shredb_h */
|
