1
\$\begingroup\$

I needed a very basic hybrid linear clock implementation for a project implementing MVCC. It gives me a perfectly incrementing clock that I can use to compare timestamps that can handle high load periods. It's not designed to synchronize across a network, just across threads.

use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicU128};
use std::sync::atomic::Ordering::Relaxed;
use std::thread;
use std::thread::JoinHandle;
use std::time::{Duration, SystemTime};

/// How often the clock is synchronized with the source.
pub const TICK_FREQUENCY_IN_NS: u64 = 500;

pub struct HybridLogicalClock {
    initial_clock: u128,
    last_tick: Arc<AtomicU128>,
    updater: JoinHandle<()>,
    done: Arc<AtomicBool>,
}

#[allow(clippy::new_without_default)]
impl HybridLogicalClock {
    pub fn new() -> Self {
        let now = SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap().as_nanos();
        let last_tick = Arc::new(AtomicU128::new(now));

        let done = Arc::new(AtomicBool::new(false));

        let last_tick_clone = last_tick.clone();
        let done_clone = done.clone();
        let updater = thread::spawn(move || {
            while !done_clone.load(Relaxed) {
                thread::sleep(Duration::from_nanos(TICK_FREQUENCY_IN_NS));
                let now = SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap().as_nanos();
                let diff = now - last_tick_clone.load(Relaxed);
                if diff == 0 {
                    continue;
                }
                last_tick_clone.fetch_add(diff, Relaxed);
            }
        });

        Self {
            initial_clock: now,
            last_tick,
            updater,
            done,
        }
    }

    #[inline]
    pub fn time(&self) -> u128 {
        self.last_tick.store(self.last_tick.load(Relaxed) + 1, Relaxed);
        self.last_tick.load(Relaxed)
    }
}

impl Drop for HybridLogicalClock {
    fn drop(&mut self) {
        self.done.store(true, Relaxed);
    }
}

#[cfg(all(test, not(miri)))]
mod tests {
    use crate::hlc::HybridLogicalClock;

    #[test]
    fn test_time() {
        let clock = HybridLogicalClock::new();
        let mut last_time = 0;
        for _ in 0..100 {
            let now = clock.time();
            assert_ne!(now, 0, "clock must never be zero");
            assert!(now > last_time, "now must be greater than last");
        }
    }
}

It's pretty performant with criterion:

pub fn clock_gettime(c: &mut Criterion) {
    let clock = HybridLogicalClock::new();
    c.bench_function("HybridLogicalClock::time()", |b| b.iter(|| clock.time()));
}

produces (on my Mac M1 Pro)

     Running benches/hlc.rs (target/release/deps/hlc-f01a21dc13fa8cc7)
HybridLogicalClock::time()
                        time:   [2.5062 ns 2.5085 ns 2.5108 ns]
                        change: [-2.1275% -1.7493% -1.3941%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 20 outliers among 100 measurements (20.00%)
  6 (6.00%) low severe
  5 (5.00%) low mild
  3 (3.00%) high mild
  6 (6.00%) high severe

I have hit the limit of my knowledge of Rust and memory atomics, so I'm happy with the average results of 2.5ns to fetch the "timestamp".

What are some ways that I can improve the performance of this implementation?

\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

Test

Let's start backward, by having a look at the test.

Bug: not testing forward progress

The last_time variable is never written to after the initial assignment, which means it's always 0.

A nifty way to test would be to use the power of iterators:

#[test]
fn test_time() {
    let clock = HybridLogicalClock::new();

    iter::repeat_with(|| clock.time())
        .take(100)
        .fold(0, |last, current| {
            assert!(current > last,
                "current ({current}) not greater than last ({last})");

            current
        });
}

Nit: awkward import

For unit-tests, you can just use use super::*; at the top of the mod tests {} to import everything from the parent module.

It's a bit quicker, but more importantly it makes it more visual what's imported that is NOT from the parent module.

Clock

Bug: non-linear time.

The current time method is not atomic:

    #[inline]
    pub fn time(&self) -> u128 {
        self.last_tick.store(self.last_tick.load(Relaxed) + 1, Relaxed);
        self.last_tick.load(Relaxed)
    }

Using atomic operations is not sufficient to make a function atomic, and in fact the following could occur:

  1. Thread A calls time, loads the tick (42), is interrupted.
  2. Thread B calls time multiple times in a row, last stores 49.
  3. Thread A is resumed, writes and returns 43.
  4. Thread B calls time, writes and returns 44 < 49.

You must use a Read-Modify-Write atomic operation instead. And yes, it'll be a wee bit slower... but correctness has a cost.

    #[inline]
    pub fn time(&self) -> u128 {
        self.last_tick.fetch_add(1, Relaxed) + 1
    }

Performance: don't use u128

There's no reason to use u128 for nanosecond resolution clocks, for most use cases.

63-bits in nanosecond resolution cover over 300 years, so that an i64 covers from 1670 to 2270, and a u64 covers from 1970 to 2570.

Since using u128 -- especially AtomicU128 -- is likely to incur performance penalties, I heartily suggest switching to AtomicU64 instead.

Meh: No Default

Instead of silencing the Clippy lint #[allow(clippy::new_without_default)], why not implement Default?

Nit: Unused fields

The initial_clock field is never used, and prevents the clock from being Sync.

The updater field is never used, and prevents the clock from being Clone.

I suggest removing both, and implementing Clone.

Benchmark

Since this clock contains Arc and AtomicXXX it's pretty clear it's meant to be used from multiple threads at once.

Yet, you do not benchmark the performance when used from multiple threads simultaneously.

A word of warning: the contention on the last_tick field will significantly reduce multi-threaded performance. You'll have to accept it -- it's the cost to pay for a HLC -- but you would do well to measure it.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.