1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

"""
NTP Offset and Delay Calculation
 
NTP uses four timestamps to calculate clock offset:
t1: Client send time (client clock)
t2: Server receive time (server clock)  
t3: Server send time (server clock)
t4: Client receive time (client clock)
 
                    Client                    Server
                    ------                    ------
    t1 ──────────────►                            
                          ─────────────────► t2
                                            [process]
    t4 ◄──────────────                      t3
           ◄─────────────────
 
The network delays are:
- Outbound (client→server): d1 = t2 - t1 - θ  (where θ is clock offset)
- Return (server→client):   d2 = t4 - t3 + θ
 
Total round-trip delay (RTT) = d1 + d2 = (t4 - t1) - (t3 - t2)
"""
 
def calculate_ntp_offset_and_delay(t1: float, t2: float, t3: float, t4: float):
    """
    Calculate clock offset and round-trip delay from NTP timestamps.
    
    Args:
        t1: Client timestamp when request was sent
        t2: Server timestamp when request was received
        t3: Server timestamp when response was sent
        t4: Client timestamp when response was received
    
    Returns:
        Tuple of (offset, delay)
        - offset: How much client clock is ahead of server (positive = client ahead)
        - delay: Round-trip network delay
    """
    # Round-trip delay
    # This is the total time the packets spent in the network
    delay = (t4 - t1) - (t3 - t2)
    
    # Offset estimation
    # NTP assumes symmetric delays: outbound = return = delay/2
    # Under this assumption, offset can be calculated as:
    offset = ((t2 - t1) + (t3 - t4)) / 2
    
    return offset, delay
 
 
# Example: Calculate offset from real timestamps
# Server is authoritative; client clock is ahead by ~50ms
t1 = 1000.000  # Client sends at its local 1000.000
t2 = 999.955   # Server receives at its local 999.955 (server is 50ms behind client)
t3 = 999.960   # Server responds at its local 999.960 (5ms processing)
t4 = 1000.080  # Client receives at its local 1000.080 (75ms network delay total)
 
offset, delay = calculate_ntp_offset_and_delay(t1, t2, t3, t4)
print(f"Calculated offset: {offset * 1000:.1f} ms")  # ~50 ms
print(f"Round-trip delay:  {delay * 1000:.1f} ms")   # ~75 ms
 
 
# THE FUNDAMENTAL LIMITATION:
# NTP assumes symmetric network delay (d1 ≈ d2). If outbound delay is 20ms
# and return delay is 55ms (asymmetric), the offset estimate will be wrong
# by (55-20)/2 = 17.5ms. NTP cannot detect or correct for asymmetric delays.
 
def calculate_offset_error_from_asymmetry(outbound_delay: float, return_delay: float):
    """
    Calculate the error in offset estimation due to asymmetric delays.
    
    This is the fundamental limit of NTP's accuracy.
    """
    asymmetry = abs(return_delay - outbound_delay)
    # Error is half the asymmetry, because NTP splits total delay equally
    return asymmetry / 2
 
 
# If network has 20ms asymmetry, NTP's offset could be wrong by ±10ms
asymmetry_error = calculate_offset_error_from_asymmetry(20, 55)
print(f"Max error from 35ms asymmetry: ±{asymmetry_error * 1000:.1f} ms")  # ±17.5 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

"""
Understanding NTP Adjustment Behavior
 
NTP uses different strategies based on offset magnitude:
- Small offset: Slew (gradual frequency adjustment)
- Large offset: Step (instant jump)
 
This has implications for application design!
"""
 
# NTP default thresholds (configurable in ntpd/chronyd)
STEP_THRESHOLD = 0.128  # 128 milliseconds
MAX_SLEW_RATE = 0.0005  # 500 ppm = 500 μs/second
 
def correction_strategy(offset_seconds: float) -> str:
    """Determine which correction strategy NTP will use."""
    if abs(offset_seconds) > STEP_THRESHOLD:
        return "STEP"
    else:
        return "SLEW"
 
def slew_duration(offset_seconds: float) -> float:
    """
    Calculate how long it takes to correct an offset via slewing.
    
    Returns time in seconds to complete the correction.
    """
    return abs(offset_seconds) / MAX_SLEW_RATE
 
 
# Examples
scenarios = [
    ("Quick sync check", 0.005),      # 5ms offset
    ("Typical drift correction", 0.020),  # 20ms offset  
    ("Large network delay spike", 0.100),  # 100ms offset
    ("Initial sync / after reboot", 0.500),  # 500ms offset
    ("Severe clock drift", 2.0),      # 2 second offset
    ("VM migration discontinuity", 60.0),  # 1 minute offset
]
 
print("NTP Correction Behavior Analysis")
print("-" * 55)
for name, offset in scenarios:
    strategy = correction_strategy(offset)
    if strategy == "SLEW":
        duration = slew_duration(offset)
        print(f"{name} ({offset*1000:.1f}ms offset):")
        print(f"  Strategy: SLEW over {duration:.1f} seconds")
    else:
        print(f"{name} ({offset*1000:.1f}ms offset):")
        print(f"  Strategy: STEP (instant jump)")
 
 
# CRITICAL INSIGHT: During slewing, the clock runs at the wrong rate!
# 
# If correcting -100ms offset (clock is fast), NTP slews by slowing the clock.
# During the ~200 seconds of slewing:
# - 200 seconds of real time passes
# - Clock only advances 199.9 seconds  
# - Timeouts and intervals based on wall-clock are affected
#
# This is why monotonic clocks are essential for duration measurements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

"""
Conceptual implementation of TrueTime-style bounded time.
 
In reality, TrueTime requires GPS receivers and atomic clocks.
This demonstrates the API and how bounded uncertainty enables
correct distributed protocols.
"""
 
from dataclasses import dataclass
import time
 
@dataclass
class TimeInterval:
    """A time interval guaranteed to contain true time."""
    earliest: float  # Lower bound (true time is >= this)
    latest: float    # Upper bound (true time is <= this)
    
    @property
    def uncertainty(self) -> float:
        """Width of uncertainty window in seconds."""
        return self.latest - self.earliest
    
    def definitely_before(self, timestamp: float) -> bool:
        """True if current time is definitely before timestamp."""
        return self.latest < timestamp
    
    def definitely_after(self, timestamp: float) -> bool:
        """True if current time is definitely after timestamp."""
        return self.earliest > timestamp
 
 
class TrueTimeSimulator:
    """
    Simulates TrueTime behavior using local clock.
    
    WARNING: This is for educational purposes only!
    Real TrueTime requires GPS + atomic clocks.
    """
    
    def __init__(self, base_uncertainty_ms: float = 5.0):
        """
        Args:
            base_uncertainty_ms: Simulated uncertainty in milliseconds
        """
        self.base_uncertainty = base_uncertainty_ms / 1000.0
        self._last_sync = time.monotonic()
        
    def now(self) -> TimeInterval:
        """
        Return a time interval containing true time.
        
        Uncertainty grows with time since last 'sync' (simulated).
        """
        current = time.time()
        
        # Simulate uncertainty growth (drift between syncs)
        time_since_sync = time.monotonic() - self._last_sync
        drift_uncertainty = time_since_sync * 0.00005  # 50 ppm drift
        
        total_uncertainty = self.base_uncertainty + drift_uncertainty
        
        return TimeInterval(
            earliest=current - total_uncertainty,
            latest=current + total_uncertainty
        )
    
    def sync(self):
        """Simulate synchronization with time master."""
        self._last_sync = time.monotonic()
 
 
# Demonstration: Spanner-style commit-wait
class SpannerCommitWait:
    """
    Demonstrates the commit-wait protocol that enables
    Spanner's external consistency using TrueTime.
    """
    
    def __init__(self, truetime: TrueTimeSimulator):
        self.tt = truetime
    
    def commit_transaction(self, data: str) -> tuple[float, float]:
        """
        Commit a transaction with Spanner-style commit-wait.
        
        Returns:
            Tuple of (commit_timestamp, wait_duration)
        """
        # Get commit timestamp
        t_commit = self.tt.now()
        commit_ts = t_commit.latest  # Use upper bound as commit time
        
        # Commit-wait: wait until we're DEFINITELY past commit time
        # This ensures any transaction starting after this returns
        # will see our timestamp as in the past
        wait_start = time.monotonic()
        
        while True:
            current = self.tt.now()
            if current.definitely_after(commit_ts):
                break
            # Still uncertain, keep waiting
            time.sleep(0.001)  # 1ms poll
        
        wait_duration = time.monotonic() - wait_start
        
        print(f"Committed at timestamp {commit_ts:.6f}")
        print(f"Commit-wait duration: {wait_duration*1000:.2f}ms")
        print(f"  (Wait covers {t_commit.uncertainty*1000:.2f}ms uncertainty)")
        
        return commit_ts, wait_duration
 
 
# Example usage
tt = TrueTimeSimulator(base_uncertainty_ms=5.0)  # 5ms base uncertainty
spanner = SpannerCommitWait(tt)
 
print("Simulating Spanner commit-wait:")
print("-" * 40)
spanner.commit_transaction("user_account_update")
 
# This demonstrates: commit-wait duration ≈ 2 × uncertainty
# because we need to wait out the full uncertainty window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# /etc/chrony/chrony.conf
# Best practices configuration for production Linux servers
 
# Use multiple high-quality public servers
# 'iburst' sends 4 requests at startup for faster initial sync
server time.google.com iburst prefer
server time.cloudflare.com iburst
server time.amazon.com iburst
server time.facebook.com iburst
 
# If in AWS, prefer the local time sync service
# (uncomment if running on AWS EC2)
# server 169.254.169.123 iburst prefer minpoll 4 maxpoll 4
 
# Allow NTP to make large adjustments at startup only
# After initial sync, prevent large steps (protects applications)
makestep 1.0 3  # Step if offset > 1s, but only first 3 updates
 
# Record clock drift to survive reboots
driftfile /var/lib/chrony/drift
 
# Enable logging for troubleshooting
log tracking measurements statistics
 
# Log directory
logdir /var/log/chrony
 
# Avoid stepping the clock after initial sync
# Instead, slew gradually (safer for applications)
# maxslewrate limits how fast time changes during slew
maxslewrate 500  # 500 ppm maximum slew rate
 
# If using hardware timestamping (for better accuracy)
# Uncomment if your NIC supports it:
# hwtimestamp eth0
 
# Security: don't serve time to others unless needed
# Allow only localhost to query this host
allow 127.0.0.1
allow ::1
 
# Drop root privileges after setup
user chronyd
 
# Leap second handling: prefer smear if using Google time
# Google servers smear leap seconds over 24 hours
# If using NIST/pool.ntp.org, comment out and handle leap seconds
leapsecmode smear

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#!/bin/bash
# NTP Health Monitoring Script
# Run periodically (e.g., every 1 minute) and alert on issues
 
set -euo pipefail
 
# Check if chrony or ntpd is running
if command -v chronyc &> /dev/null; then
    NTP_CMD="chrony"
elif command -v ntpq &> /dev/null; then
    NTP_CMD="ntp"
else
    echo "CRITICAL: No NTP daemon found"
    exit 2
fi
 
if [ "$NTP_CMD" = "chrony" ]; then
    # Get chrony tracking information
    OFFSET=$(chronyc tracking | grep "Last offset" | awk '{print $4}')
    STRATUM=$(chronyc tracking | grep "Stratum" | awk '{print $3}')
    STATUS=$(chronyc tracking | grep "Leap status" | awk '{print $4}')
    
    # Convert offset to milliseconds (chronyc reports in seconds)
    OFFSET_MS=$(echo "$OFFSET * 1000" | bc -l)
    OFFSET_ABS=$(echo "${OFFSET_MS#-}")  # Absolute value
else
    # ntpd alternative(using ntpq)
    OFFSET_MS=$(ntpq - c rv | grep offset | awk - F= '{print $2}' | awk - F, '{print $1}')
    STRATUM=$(ntpq - c rv | grep stratum | awk - F= '{print $2}' | awk - F, '{print $1}')
    OFFSET_ABS=${ OFFSET_MS#-}
fi
 
# Alert thresholds
OFFSET_WARN = 10    # Warn if offset > 10ms
OFFSET_CRIT=50    # Critical if offset > 50ms  
STRATUM_WARN=4    # Warn if stratum > 4
STRATUM_CRIT=6    # Critical if stratum > 6
 
# Evaluate offset
if(($(echo "$OFFSET_ABS > $OFFSET_CRIT" | bc - l))); then
    echo "CRITICAL: Clock offset is ${OFFSET_MS}ms (threshold: ${OFFSET_CRIT}ms)"
    exit 2
    elif(($(echo "$OFFSET_ABS > $OFFSET_WARN" | bc - l))); then
    echo "WARNING: Clock offset is ${OFFSET_MS}ms (threshold: ${OFFSET_WARN}ms)"
    exit 1
    fi
 
# Evaluate stratum
    if ["$STRATUM" - gt "$STRATUM_CRIT"]; then
    echo "CRITICAL: NTP stratum is $STRATUM (threshold: $STRATUM_CRIT)"
    exit 2
    elif["$STRATUM" - gt "$STRATUM_WARN" ]; then
    echo "WARNING: NTP stratum is $STRATUM (threshold: $STRATUM_WARN)"
    exit 1
    fi
 
# Check for leap second issues
if ["$STATUS" = "Not synchronised"]; then
    echo "CRITICAL: NTP not synchronized"
    exit 2
    fi
 
echo "OK: NTP healthy - offset: ${OFFSET_MS}ms, stratum: ${STRATUM}"
exit 0