1#![deny(missing_docs)]
22
23use std::fmt;
24use std::marker::PhantomData;
25use std::sync::Arc;
26use std::time::{Duration, SystemTime, UNIX_EPOCH};
27
28use objsds_store::{CreateError, Location, ObjectStore, ReplaceError, Version, is_path_segment};
29use serde::de::DeserializeOwned;
30use serde::{Deserialize, Serialize};
31use uuid::Uuid;
32
33const FORMAT_VERSION: u32 = 1;
34const KIND: &str = "queue";
35
36pub trait Clock: Send + Sync + 'static {
42 fn now_millis(&self) -> u64;
44}
45
46#[derive(Clone, Copy, Debug, Default)]
48pub struct SystemClock;
49
50impl Clock for SystemClock {
51 fn now_millis(&self) -> u64 {
52 let millis = SystemTime::now()
53 .duration_since(UNIX_EPOCH)
54 .unwrap_or_default()
55 .as_millis();
56 u64::try_from(millis).unwrap_or(u64::MAX)
57 }
58}
59
60#[derive(Clone, Copy, Debug, Deserialize, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize)]
62#[serde(transparent)]
63pub struct MessageId(Uuid);
64
65impl fmt::Display for MessageId {
66 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
67 self.0.fmt(formatter)
68 }
69}
70
71#[derive(Clone, Copy, Debug, Deserialize, Eq, Hash, PartialEq, Serialize)]
73#[serde(transparent)]
74pub struct LeaseToken(Uuid);
75
76impl fmt::Display for LeaseToken {
77 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
78 self.0.fmt(formatter)
79 }
80}
81
82#[derive(Clone, Debug, Eq, PartialEq)]
84pub struct Claim<V> {
85 pub id: MessageId,
87 pub value: V,
89 pub lease_token: LeaseToken,
91 pub attempt: u32,
93 pub lease_expires_at_millis: u64,
95}
96
97#[derive(Clone, Copy, Debug, Eq, PartialEq)]
103pub enum Ack {
104 Acknowledged,
106 NotFound,
108 LeaseMismatch,
110 LeaseExpired,
112}
113
114#[derive(Clone, Copy, Debug, Eq, PartialEq)]
116pub enum BuildError {
117 InvalidNamespace,
119 InvalidName,
121 MissingSchema,
123}
124
125impl fmt::Display for BuildError {
126 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
127 formatter.write_str(match self {
128 Self::InvalidNamespace => "namespace must be one non-empty path segment",
129 Self::InvalidName => "queue name must be one non-empty path segment",
130 Self::MissingSchema => "missing schema identifier",
131 })
132 }
133}
134
135impl std::error::Error for BuildError {}
136
137#[derive(Debug)]
139pub enum Error<E> {
140 Configuration(BuildError),
142 Store(E),
144 Document(serde_json::Error),
146 Corrupt(String),
148 NotFound,
150 AlreadyExists(Version),
152 Conflict {
154 expected: Version,
156 observed: Option<Version>,
158 },
159 Incompatible(String),
161 InvalidLeaseDuration,
163 AttemptOverflow,
165}
166
167impl<E: fmt::Display> fmt::Display for Error<E> {
168 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
169 match self {
170 Self::Configuration(error) => write!(formatter, "invalid configuration: {error}"),
171 Self::Store(error) => write!(formatter, "object store error: {error}"),
172 Self::Document(error) => write!(formatter, "could not process queue JSON: {error}"),
173 Self::Corrupt(reason) => write!(formatter, "persisted queue is corrupt: {reason}"),
174 Self::NotFound => formatter.write_str("queue does not exist"),
175 Self::AlreadyExists(_) => formatter.write_str("queue already exists"),
176 Self::Conflict { .. } => formatter.write_str("object version conflict"),
177 Self::Incompatible(reason) => write!(formatter, "incompatible queue: {reason}"),
178 Self::InvalidLeaseDuration => formatter.write_str("invalid lease duration"),
179 Self::AttemptOverflow => formatter.write_str("message claim count overflowed"),
180 }
181 }
182}
183
184impl<E: std::error::Error + 'static> std::error::Error for Error<E> {
185 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
186 match self {
187 Self::Configuration(error) => Some(error),
188 Self::Store(error) => Some(error),
189 Self::Document(error) => Some(error),
190 _ => None,
191 }
192 }
193}
194
195pub struct QueueBuilder<S, V, C = SystemClock> {
197 store: Arc<S>,
198 namespace: String,
199 name: String,
200 schema: Option<String>,
201 clock: C,
202 value: PhantomData<fn() -> V>,
203}
204
205impl<S, V> QueueBuilder<S, V, SystemClock> {
206 pub fn new(store: S, namespace: impl Into<String>, name: impl Into<String>) -> Self {
211 Self {
212 store: Arc::new(store),
213 namespace: namespace.into(),
214 name: name.into(),
215 schema: None,
216 clock: SystemClock,
217 value: PhantomData,
218 }
219 }
220}
221
222impl<S, V, C> QueueBuilder<S, V, C> {
223 #[must_use]
225 pub fn schema(mut self, schema: impl Into<String>) -> Self {
226 self.schema = Some(schema.into());
227 self
228 }
229
230 #[must_use]
232 pub fn clock<D: Clock>(self, clock: D) -> QueueBuilder<S, V, D> {
233 QueueBuilder {
234 store: self.store,
235 namespace: self.namespace,
236 name: self.name,
237 schema: self.schema,
238 clock,
239 value: PhantomData,
240 }
241 }
242
243 fn finish(self) -> Result<Queue<S, V, C>, BuildError> {
244 if !is_path_segment(&self.namespace) {
245 return Err(BuildError::InvalidNamespace);
246 }
247 if !is_path_segment(&self.name) {
248 return Err(BuildError::InvalidName);
249 }
250 let schema = self
251 .schema
252 .filter(|schema| !schema.is_empty())
253 .ok_or(BuildError::MissingSchema)?;
254 let location = Location::structure(&self.namespace, "queues", &self.name)
255 .map_err(|_| BuildError::InvalidName)?;
256 Ok(Queue {
257 store: self.store,
258 location,
259 schema,
260 clock: self.clock,
261 value: PhantomData,
262 })
263 }
264}
265
266impl<S, V, C> QueueBuilder<S, V, C>
267where
268 S: ObjectStore,
269 V: Serialize + DeserializeOwned,
270 C: Clock,
271{
272 pub fn create(self) -> Result<Queue<S, V, C>, Error<S::Error>> {
274 let queue = self.finish().map_err(Error::Configuration)?;
275 let bytes = queue.empty_bytes()?;
276 queue
277 .store
278 .create(&queue.location, &bytes)
279 .map_err(map_create)?;
280 Ok(queue)
281 }
282
283 pub fn open(self) -> Result<Queue<S, V, C>, Error<S::Error>> {
285 let queue = self.finish().map_err(Error::Configuration)?;
286 queue.read()?;
287 Ok(queue)
288 }
289
290 pub fn open_or_create(self) -> Result<Queue<S, V, C>, Error<S::Error>> {
292 let queue = self.finish().map_err(Error::Configuration)?;
293 if queue
294 .store
295 .get(&queue.location)
296 .map_err(Error::Store)?
297 .is_some()
298 {
299 queue.read()?;
300 return Ok(queue);
301 }
302 let bytes = queue.empty_bytes()?;
303 match queue.store.create(&queue.location, &bytes) {
304 Ok(_) => Ok(queue),
305 Err(CreateError::AlreadyExists { .. }) => {
306 queue.read()?;
307 Ok(queue)
308 }
309 Err(CreateError::Store(error)) => Err(Error::Store(error)),
310 }
311 }
312}
313
314pub struct Queue<S, V, C = SystemClock> {
319 store: Arc<S>,
320 location: Location,
321 schema: String,
322 clock: C,
323 value: PhantomData<fn() -> V>,
324}
325
326impl<S, V, C> Queue<S, V, C>
327where
328 S: ObjectStore,
329 V: Serialize + DeserializeOwned,
330 C: Clock,
331{
332 pub fn publish(&self, value: V) -> Result<MessageId, Error<S::Error>> {
338 let (version, mut document) = self.read()?;
339 let id = MessageId(Uuid::now_v7());
340 let index = document.messages.partition_point(|message| message.id < id);
341 document.messages.insert(
342 index,
343 Message {
344 id,
345 value,
346 attempts: 0,
347 lease: None,
348 },
349 );
350 self.write(&version, &document)?;
351 Ok(id)
352 }
353
354 pub fn claim(&self, lease_duration: Duration) -> Result<Option<Claim<V>>, Error<S::Error>>
360 where
361 V: Clone,
362 {
363 let lease_millis = u64::try_from(lease_duration.as_millis())
364 .ok()
365 .filter(|millis| *millis > 0)
366 .ok_or(Error::InvalidLeaseDuration)?;
367 let now = self.clock.now_millis();
368 let expires_at_millis = now
369 .checked_add(lease_millis)
370 .ok_or(Error::InvalidLeaseDuration)?;
371 let (version, mut document) = self.read()?;
372 let Some(index) = document.messages.iter().position(|message| {
373 message
374 .lease
375 .as_ref()
376 .is_none_or(|lease| lease.expires_at_millis <= now)
377 }) else {
378 return Ok(None);
379 };
380 let token = LeaseToken(Uuid::now_v7());
381 {
382 let message = &mut document.messages[index];
383 message.attempts = message
384 .attempts
385 .checked_add(1)
386 .ok_or(Error::AttemptOverflow)?;
387 message.lease = Some(Lease {
388 token,
389 expires_at_millis,
390 });
391 }
392 self.write(&version, &document)?;
393 let message = &document.messages[index];
394 Ok(Some(Claim {
395 id: message.id,
396 value: message.value.clone(),
397 lease_token: token,
398 attempt: message.attempts,
399 lease_expires_at_millis: expires_at_millis,
400 }))
401 }
402
403 pub fn ack(&self, id: MessageId, token: LeaseToken) -> Result<Ack, Error<S::Error>> {
409 let now = self.clock.now_millis();
410 let (version, mut document) = self.read()?;
411 let Ok(index) = document
412 .messages
413 .binary_search_by_key(&id, |message| message.id)
414 else {
415 return Ok(Ack::NotFound);
416 };
417 let Some(lease) = document.messages[index].lease.as_ref() else {
418 return Ok(Ack::LeaseMismatch);
419 };
420 if lease.token != token {
421 return Ok(Ack::LeaseMismatch);
422 }
423 if lease.expires_at_millis <= now {
424 return Ok(Ack::LeaseExpired);
425 }
426 document.messages.remove(index);
427 self.write(&version, &document)?;
428 Ok(Ack::Acknowledged)
429 }
430
431 pub fn len(&self) -> Result<usize, Error<S::Error>> {
433 Ok(self.read()?.1.messages.len())
434 }
435
436 pub fn is_empty(&self) -> Result<bool, Error<S::Error>> {
438 Ok(self.len()? == 0)
439 }
440
441 fn empty_bytes(&self) -> Result<Vec<u8>, Error<S::Error>> {
442 serde_json::to_vec(&Document::<V> {
443 format_version: FORMAT_VERSION,
444 kind: KIND.to_owned(),
445 schema: self.schema.clone(),
446 messages: Vec::new(),
447 })
448 .map_err(Error::Document)
449 }
450
451 fn read(&self) -> Result<(Version, Document<V>), Error<S::Error>> {
452 let object = self
453 .store
454 .get(&self.location)
455 .map_err(Error::Store)?
456 .ok_or(Error::NotFound)?;
457 let document: Document<V> =
458 serde_json::from_slice(&object.bytes).map_err(Error::Document)?;
459 if document.format_version != FORMAT_VERSION {
460 return Err(Error::Incompatible(format!(
461 "expected format version {FORMAT_VERSION}, observed {}",
462 document.format_version
463 )));
464 }
465 if document.kind != KIND {
466 return Err(Error::Incompatible(format!(
467 "expected kind {KIND}, observed {}",
468 document.kind
469 )));
470 }
471 if document.schema != self.schema {
472 return Err(Error::Incompatible(format!(
473 "expected schema {}, observed {}",
474 self.schema, document.schema
475 )));
476 }
477 if document
478 .messages
479 .windows(2)
480 .any(|messages| messages[0].id >= messages[1].id)
481 {
482 return Err(Error::Corrupt(
483 "message IDs must be strictly increasing".to_owned(),
484 ));
485 }
486 Ok((object.version, document))
487 }
488
489 fn write(&self, expected: &Version, document: &Document<V>) -> Result<(), Error<S::Error>> {
490 let bytes = serde_json::to_vec(document).map_err(Error::Document)?;
491 self.store
492 .replace(&self.location, expected, &bytes)
493 .map_err(|error| match error {
494 ReplaceError::Conflict { observed } => Error::Conflict {
495 expected: expected.clone(),
496 observed,
497 },
498 ReplaceError::Store(error) => Error::Store(error),
499 })?;
500 Ok(())
501 }
502}
503
504fn map_create<E>(error: CreateError<E>) -> Error<E> {
505 match error {
506 CreateError::AlreadyExists { observed } => Error::AlreadyExists(observed),
507 CreateError::Store(error) => Error::Store(error),
508 }
509}
510
511#[derive(Deserialize, Serialize)]
512struct Document<V> {
513 format_version: u32,
514 kind: String,
515 schema: String,
516 messages: Vec<Message<V>>,
517}
518
519#[derive(Deserialize, Serialize)]
520struct Message<V> {
521 id: MessageId,
522 value: V,
523 attempts: u32,
524 lease: Option<Lease>,
525}
526
527#[derive(Deserialize, Serialize)]
528struct Lease {
529 token: LeaseToken,
530 expires_at_millis: u64,
531}
532
533#[cfg(test)]
534mod tests {
535 use std::convert::Infallible;
536 use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
537
538 use objsds_store::{Object, ObjectStore, ReplaceError};
539 use objsds_store_memory::MemoryStore;
540
541 use super::*;
542
543 #[derive(Clone)]
544 struct ManualClock(Arc<AtomicU64>);
545
546 impl ManualClock {
547 fn new(now: u64) -> Self {
548 Self(Arc::new(AtomicU64::new(now)))
549 }
550 fn set(&self, now: u64) {
551 self.0.store(now, Ordering::SeqCst);
552 }
553 }
554
555 impl Clock for ManualClock {
556 fn now_millis(&self) -> u64 {
557 self.0.load(Ordering::SeqCst)
558 }
559 }
560
561 fn queue(clock: ManualClock) -> Queue<MemoryStore, String, ManualClock> {
562 QueueBuilder::new(MemoryStore::default(), "tests", "jobs")
563 .schema("job-v1")
564 .clock(clock)
565 .create()
566 .expect("queue should be created")
567 }
568
569 #[test]
570 fn publish_claim_and_ack_removes_message() {
571 let queue = queue(ManualClock::new(1_000));
572 let id = queue
573 .publish("work".to_owned())
574 .expect("publish should succeed");
575 let claim = queue
576 .claim(Duration::from_millis(100))
577 .expect("claim should succeed")
578 .expect("message should be available");
579 assert_eq!(claim.id, id);
580 assert_eq!(claim.value, "work");
581 assert_eq!(claim.attempt, 1);
582 assert_eq!(
583 queue
584 .ack(id, claim.lease_token)
585 .expect("ack should succeed"),
586 Ack::Acknowledged
587 );
588 assert!(queue.is_empty().expect("read should succeed"));
589 }
590
591 #[test]
592 fn lease_expiry_reclaims_with_new_token_and_attempt() {
593 let clock = ManualClock::new(1_000);
594 let queue = queue(clock.clone());
595 let id = queue
596 .publish("work".to_owned())
597 .expect("publish should succeed");
598 let first = queue
599 .claim(Duration::from_millis(100))
600 .expect("claim should succeed")
601 .expect("message should be available");
602 assert!(
603 queue
604 .claim(Duration::from_millis(100))
605 .expect("claim should succeed")
606 .is_none()
607 );
608 clock.set(1_100);
609 assert_eq!(
610 queue
611 .ack(id, first.lease_token)
612 .expect("ack should be classified"),
613 Ack::LeaseExpired
614 );
615 let second = queue
616 .claim(Duration::from_millis(100))
617 .expect("reclaim should succeed")
618 .expect("expired message should be available");
619 assert_eq!(second.id, id);
620 assert_eq!(second.attempt, 2);
621 assert_ne!(second.lease_token, first.lease_token);
622 assert_eq!(
623 queue
624 .ack(id, first.lease_token)
625 .expect("stale ack should be classified"),
626 Ack::LeaseMismatch
627 );
628 assert_eq!(
629 queue
630 .ack(id, second.lease_token)
631 .expect("ack should succeed"),
632 Ack::Acknowledged
633 );
634 }
635
636 #[test]
637 fn claims_available_messages_in_publish_order() {
638 let queue = queue(ManualClock::new(1_000));
639 let first = queue
640 .publish("first".to_owned())
641 .expect("publish should succeed");
642 let second = queue
643 .publish("second".to_owned())
644 .expect("publish should succeed");
645 let first_claim = queue
646 .claim(Duration::from_secs(1))
647 .expect("claim should succeed")
648 .expect("first message should exist");
649 let second_claim = queue
650 .claim(Duration::from_secs(1))
651 .expect("claim should succeed")
652 .expect("second message should exist");
653 assert_eq!((first_claim.id, second_claim.id), (first, second));
654 }
655
656 #[derive(Clone)]
657 struct FailReplaceOnce {
658 inner: MemoryStore,
659 fail_next: Arc<AtomicBool>,
660 }
661
662 impl ObjectStore for FailReplaceOnce {
663 type Error = Infallible;
664
665 fn get(&self, location: &Location) -> Result<Option<Object>, Self::Error> {
666 self.inner.get(location)
667 }
668
669 fn create(
670 &self,
671 location: &Location,
672 bytes: &[u8],
673 ) -> Result<Version, CreateError<Self::Error>> {
674 self.inner.create(location, bytes)
675 }
676
677 fn replace(
678 &self,
679 location: &Location,
680 expected: &Version,
681 bytes: &[u8],
682 ) -> Result<Version, ReplaceError<Self::Error>> {
683 if self.fail_next.swap(false, Ordering::SeqCst) {
684 let observed = self
685 .inner
686 .get(location)
687 .expect("memory get is infallible")
688 .map(|object| object.version);
689 return Err(ReplaceError::Conflict { observed });
690 }
691 self.inner.replace(location, expected, bytes)
692 }
693 }
694
695 #[test]
696 fn publish_conflict_leaves_queue_unchanged() {
697 let store = FailReplaceOnce {
698 inner: MemoryStore::default(),
699 fail_next: Arc::new(AtomicBool::new(false)),
700 };
701 let queue = QueueBuilder::new(store.clone(), "tests", "jobs")
702 .schema("job-v1")
703 .create()
704 .expect("queue should be created");
705 store.fail_next.store(true, Ordering::SeqCst);
706 assert!(matches!(
707 queue.publish("work".to_owned()),
708 Err(Error::Conflict { .. })
709 ));
710 assert!(queue.is_empty().expect("read should succeed"));
711 }
712
713 #[test]
714 fn open_validates_existing_queue_and_schema() {
715 let store = MemoryStore::default();
716 QueueBuilder::<_, String>::new(store.clone(), "tests", "jobs")
717 .schema("job-v1")
718 .create()
719 .expect("queue should be created");
720 QueueBuilder::<_, String>::new(store.clone(), "tests", "jobs")
721 .schema("job-v1")
722 .open()
723 .expect("existing queue should open");
724 assert!(matches!(
725 QueueBuilder::<_, String>::new(store.clone(), "tests", "jobs")
726 .schema("job-v2")
727 .open(),
728 Err(Error::Incompatible(_))
729 ));
730 assert!(matches!(
731 QueueBuilder::<_, String>::new(store, "tests", "missing")
732 .schema("job-v1")
733 .open(),
734 Err(Error::NotFound)
735 ));
736 }
737
738 #[test]
739 fn open_or_create_is_idempotent() {
740 let store = MemoryStore::default();
741 let created = QueueBuilder::<_, String>::new(store.clone(), "tests", "jobs")
742 .schema("job-v1")
743 .open_or_create()
744 .expect("queue should be created");
745 created
746 .publish("work".to_owned())
747 .expect("publish should succeed");
748 let opened = QueueBuilder::<_, String>::new(store, "tests", "jobs")
749 .schema("job-v1")
750 .open_or_create()
751 .expect("existing queue should open");
752 assert_eq!(opened.len().expect("read should succeed"), 1);
753 }
754
755 #[test]
756 fn rejects_zero_and_sub_millisecond_leases() {
757 let queue = queue(ManualClock::new(1_000));
758 assert!(matches!(
759 queue.claim(Duration::ZERO),
760 Err(Error::InvalidLeaseDuration)
761 ));
762 assert!(matches!(
763 queue.claim(Duration::from_nanos(1)),
764 Err(Error::InvalidLeaseDuration)
765 ));
766 }
767
768 #[test]
769 fn ack_classifies_missing_and_unclaimed_messages() {
770 let queue = queue(ManualClock::new(1_000));
771 let token = LeaseToken(Uuid::nil());
772 assert_eq!(
773 queue
774 .ack(MessageId(Uuid::nil()), token)
775 .expect("ack should be classified"),
776 Ack::NotFound
777 );
778 let id = queue
779 .publish("work".to_owned())
780 .expect("publish should succeed");
781 assert_eq!(
782 queue.ack(id, token).expect("ack should be classified"),
783 Ack::LeaseMismatch
784 );
785 }
786}