Skip to main content

uqa_graph/persistent_store/
identifiers.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Durable entity reservations are shared by every graph using the same physical identity space. Label definitions remain transactional.
8
9use 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
23/// A database-local physical graph namespace. Catalog graphs share one namespace; standalone families use their canonical provider scope. A transactional clear selects a new generation.
24pub 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    /// Seed only an uninitialized physical prefix. Identity pages omit payloads and retain a fixed upper bound on workspace.
154    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}