uqa_graph/persistent_store/
identifiers.rs1use std::num::NonZeroU64;
10
11use uqa_storage::catalog::graph_identifiers::GraphIdentifierNamespace;
12use uqa_storage::mvcc::{IdentifierAllocator, IdentifierRequest};
13use uqa_storage::{GraphEntityFilter, GraphEntityKind};
14
15use crate::memory_store::{MAX_GRAPHID_LABEL_ID, MAX_GRAPHID_SEQUENCE as MAX_SEQUENCE};
16use crate::{
17 graphid_label_id, graphid_sequence, GraphLabelRegistry, GraphStoreError, GraphStoreResult,
18 LabelKind, GRAPHID_LABEL_SHIFT,
19};
20
21use super::{PersistentGraphStore, ID_PAGE_SIZE};
22
23pub struct GraphIdentifierScope<'a> {
25 allocator: &'a dyn IdentifierAllocator,
26 namespace: GraphIdentifierNamespace,
27}
28
29pub fn decode_identifier_generation(value: Option<&str>) -> GraphStoreResult<[u8; 16]> {
30 value.map_or(Ok([0; 16]), |value| {
31 serde_json::from_str(value)
32 .map_err(|error| GraphStoreError::CorruptGraph(error.to_string()))
33 })
34}
35
36impl<'a> GraphIdentifierScope<'a> {
37 pub(super) fn namespace(&self) -> GraphIdentifierNamespace {
38 self.namespace
39 }
40 pub fn catalog(allocator: &'a dyn IdentifierAllocator, generation: [u8; 16]) -> Self {
41 Self::new(allocator, None, generation)
42 }
43
44 pub fn standalone(
45 allocator: &'a dyn IdentifierAllocator,
46 scope: &str,
47 generation: [u8; 16],
48 ) -> Self {
49 Self::new(allocator, Some(scope), generation)
50 }
51
52 fn new(
53 allocator: &'a dyn IdentifierAllocator,
54 scope: Option<&str>,
55 generation: [u8; 16],
56 ) -> Self {
57 Self {
58 allocator,
59 namespace: GraphIdentifierNamespace::new(scope, generation),
60 }
61 }
62
63 fn legacy_graph_identity(&self, graph: &str) -> [u8; 16] {
64 self.namespace.legacy_graph_identity(graph)
65 }
66
67 fn watermark(&self, key: &[u8]) -> GraphStoreResult<Option<u64>> {
68 Ok(self.allocator.identifier_watermark(key)?)
69 }
70
71 fn observe(&self, key: &[u8], value: u64) -> GraphStoreResult<()> {
72 if self.watermark(key)?.is_none_or(|current| current < value) {
73 self.allocator
74 .allocate_identifiers(key, IdentifierRequest::Observe(value))?;
75 }
76 Ok(())
77 }
78
79 fn reserve(&self, key: &[u8], minimum: u64, maximum: u64) -> GraphStoreResult<u64> {
80 if minimum > maximum {
81 return Err(GraphStoreError::IdExhausted(
82 "graph identifier space is exhausted".into(),
83 ));
84 }
85 Ok(self
86 .allocator
87 .allocate_identifiers(
88 key,
89 IdentifierRequest::Reserve {
90 minimum,
91 maximum,
92 count: NonZeroU64::MIN,
93 },
94 )?
95 .watermark())
96 }
97
98 fn entity_key(&self, kind: GraphEntityKind, prefix: u32) -> [u8; 78] {
99 self.namespace.entity_key(kind, prefix)
100 }
101
102 fn hint_key(&self, kind: GraphEntityKind) -> [u8; 78] {
103 self.namespace.hint_key(kind)
104 }
105
106 fn sequence_key(&self, graph: [u8; 16], prefix: u32) -> [u8; 78] {
107 self.namespace.sequence_key(graph, prefix)
108 }
109
110 fn label_key(&self, graph: [u8; 16]) -> [u8; 78] {
111 self.namespace.label_key(graph)
112 }
113
114 pub(super) fn restore_registry(
115 &self,
116 graph: &str,
117 registry: &mut GraphLabelRegistry,
118 ) -> GraphStoreResult<()> {
119 if registry.allocation_id == [0; 16] {
120 registry.allocation_id = self.legacy_graph_identity(graph);
121 }
122 if let Some(last) = self.watermark(&self.label_key(registry.allocation_id))? {
123 let next = last
124 .checked_add(1)
125 .and_then(|value| u32::try_from(value).ok())
126 .ok_or_else(|| {
127 GraphStoreError::CorruptGraph("invalid label allocation watermark".into())
128 })?;
129 registry.next_label_id = registry.next_label_id.max(next);
130 }
131 for label in registry.labels() {
132 let key = self.sequence_key(registry.allocation_id, label.id);
133 if let Some(value) = self.watermark(&key)? {
134 registry
135 .sequences
136 .entry(label.id)
137 .and_modify(|old| *old = (*old).max(value))
138 .or_insert(value);
139 }
140 }
141 Ok(())
142 }
143}
144
145fn entity_kind(kind: LabelKind) -> GraphEntityKind {
146 match kind {
147 LabelKind::Vertex => GraphEntityKind::Vertex,
148 LabelKind::Edge => GraphEntityKind::Edge,
149 }
150}
151
152impl PersistentGraphStore {
153 fn prefix_floor(
155 &self,
156 identifiers: &GraphIdentifierScope<'_>,
157 kind: GraphEntityKind,
158 prefix: u32,
159 ) -> GraphStoreResult<u64> {
160 let observed = identifiers.watermark(&identifiers.entity_key(kind, prefix))?;
161 if identifiers
162 .watermark(&identifiers.namespace.entity_seed_key(kind, prefix))?
163 .is_some()
164 {
165 return Ok(observed.unwrap_or(0));
166 }
167 let mut floor = self
168 .storage
169 .counter(kind)?
170 .and_then(|next| next.checked_sub(1))
171 .filter(|id| graphid_label_id(*id) == prefix)
172 .map_or(0, graphid_sequence)
173 .max(observed.unwrap_or(0));
174 let mut after = (u64::from(prefix) << GRAPHID_LABEL_SHIFT).checked_sub(1);
175 'pages: loop {
176 let ids = self
177 .storage
178 .ids(GraphEntityFilter::new(kind, None), after, ID_PAGE_SIZE)?;
179 if ids.is_empty() {
180 break;
181 }
182 after = ids.last().copied();
183 for id in ids {
184 if graphid_label_id(id) != prefix {
185 break 'pages;
186 }
187 floor = floor.max(graphid_sequence(id));
188 }
189 }
190 for graph in self.storage.graph_names()? {
191 let registry = self.storage.registry(&graph)?;
192 for label in registry.labels() {
193 if label.id == prefix && entity_kind(label.kind) == kind {
194 floor = floor.max(label.last_sequence);
195 }
196 }
197 }
198 identifiers.observe(&identifiers.entity_key(kind, prefix), floor)?;
199 identifiers.observe(&identifiers.namespace.entity_seed_key(kind, prefix), 1)?;
200 Ok(floor)
201 }
202
203 pub(super) fn observe_durable_id(
204 &self,
205 identifiers: &GraphIdentifierScope<'_>,
206 kind: GraphEntityKind,
207 id: u64,
208 ) -> GraphStoreResult<()> {
209 let prefix = graphid_label_id(id);
210 let floor = self.prefix_floor(identifiers, kind, prefix)?;
211 identifiers.observe(
212 &identifiers.entity_key(kind, prefix),
213 floor.max(graphid_sequence(id)),
214 )?;
215 identifiers.observe(&identifiers.hint_key(kind), id)
216 }
217
218 pub(super) fn allocate_durable_counter(
219 &self,
220 identifiers: &GraphIdentifierScope<'_>,
221 kind: GraphEntityKind,
222 ) -> GraphStoreResult<u64> {
223 let mut minimum = self.next_counter(kind)?;
224 if let Some(last) = identifiers.watermark(&identifiers.hint_key(kind))? {
225 minimum =
226 minimum.max(last.checked_add(1).ok_or_else(|| {
227 GraphStoreError::IdExhausted("graph id counter overflow".into())
228 })?);
229 }
230 loop {
231 let prefix = graphid_label_id(minimum);
232 let floor = self.prefix_floor(identifiers, kind, prefix)?;
233 if floor > MAX_SEQUENCE {
234 return Err(GraphStoreError::CorruptGraph(
235 "invalid graph entity allocation watermark".into(),
236 ));
237 }
238 if floor == MAX_SEQUENCE {
239 minimum = (u64::from(prefix) + 1) << GRAPHID_LABEL_SHIFT;
240 if prefix == u32::from(u16::MAX) {
241 return Err(GraphStoreError::IdExhausted(
242 "graph id counter overflow".into(),
243 ));
244 }
245 continue;
246 }
247 let sequence = identifiers.reserve(
248 &identifiers.entity_key(kind, prefix),
249 graphid_sequence(minimum).max(floor + 1),
250 MAX_SEQUENCE,
251 )?;
252 let id = (u64::from(prefix) << GRAPHID_LABEL_SHIFT) | sequence;
253 if id == u64::MAX {
254 return Err(GraphStoreError::IdExhausted(
255 "graph id counter overflow".into(),
256 ));
257 }
258 identifiers.observe(&identifiers.hint_key(kind), id)?;
259 return Ok(id);
260 }
261 }
262
263 pub(super) fn allocate_durable_label(
264 &self,
265 identifiers: &GraphIdentifierScope<'_>,
266 registry: &GraphLabelRegistry,
267 label: u32,
268 kind: LabelKind,
269 ) -> GraphStoreResult<u64> {
270 let kind = entity_kind(kind);
271 let floor = self
272 .prefix_floor(identifiers, kind, label)?
273 .max(registry.sequences.get(&label).copied().unwrap_or(0));
274 let minimum = floor
275 .checked_add(1)
276 .ok_or_else(|| GraphStoreError::IdExhausted("graph sequence overflow".into()))?;
277 let sequence =
278 identifiers.reserve(&identifiers.entity_key(kind, label), minimum, MAX_SEQUENCE)?;
279 let id = crate::make_graphid(label, sequence)?;
280 identifiers.observe(
281 &identifiers.sequence_key(registry.allocation_id, label),
282 sequence,
283 )?;
284 identifiers.observe(&identifiers.hint_key(kind), id)?;
285 Ok(id)
286 }
287
288 pub(super) fn reserve_label_definition(
289 &self,
290 registry: &mut GraphLabelRegistry,
291 label: &str,
292 proposed: u32,
293 ) -> GraphStoreResult<u32> {
294 let Some(identifiers) = self.storage.identifiers()? else {
295 return Ok(proposed);
296 };
297 let allocated = identifiers.reserve(
298 &identifiers.label_key(registry.allocation_id),
299 u64::from(proposed),
300 u64::from(MAX_GRAPHID_LABEL_ID),
301 )?;
302 let allocated = u32::try_from(allocated)
303 .map_err(|_| GraphStoreError::IdExhausted("graph label id overflow".into()))?;
304 registry.labels.insert(label.to_owned(), allocated);
305 registry.next_label_id = allocated + 1;
306 Ok(allocated)
307 }
308
309 pub(super) fn resolve_label(
310 &self,
311 registry: &mut GraphLabelRegistry,
312 label: &str,
313 kind: LabelKind,
314 ) -> GraphStoreResult<u32> {
315 let new = !label.is_empty()
316 && label != kind.default_label_name()
317 && !registry.labels.contains_key(label);
318 let proposed = registry.label_id(label, kind)?;
319 if new {
320 self.reserve_label_definition(registry, label, proposed)
321 } else {
322 Ok(proposed)
323 }
324 }
325
326 pub(super) fn save_registry(
327 &self,
328 graph: &str,
329 registry: &GraphLabelRegistry,
330 ) -> GraphStoreResult<()> {
331 if let Some(identifiers) = self.storage.identifiers()? {
332 for label in registry.labels() {
333 if label.last_sequence != 0 {
334 let kind = entity_kind(label.kind);
335 identifiers.observe(
336 &identifiers.sequence_key(registry.allocation_id, label.id),
337 label.last_sequence,
338 )?;
339 let id = crate::make_graphid(label.id, label.last_sequence)?;
340 self.observe_durable_id(&identifiers, kind, id)?;
341 }
342 }
343 identifiers.observe(
344 &identifiers.label_key(registry.allocation_id),
345 u64::from(registry.next_label_id.saturating_sub(1)),
346 )?;
347 let previous = self.storage.registry(graph)?;
348 let previous_identity = if previous.allocation_id == [0; 16] {
349 identifiers.legacy_graph_identity(graph)
350 } else {
351 previous.allocation_id
352 };
353 if previous_identity == registry.allocation_id
354 && previous.labels == registry.labels
355 && previous.kinds == registry.kinds
356 && previous.dropped_label_ids == registry.dropped_label_ids
357 {
358 return Ok(());
359 }
360 }
361 self.storage.save_registry(graph, registry)
362 }
363}