1/*
2 * hlc.h
3 *
4 * Copyright (C) 2008-2016 Aerospike, Inc.
5 *
6 * Portions may be licensed to Aerospike, Inc. under one or more contributor
7 * license agreements.
8 *
9 * This program is free software: you can redistribute it and/or modify it under
10 * the terms of the GNU Affero General Public License as published by the Free
11 * Software Foundation, either version 3 of the License, or (at your option) any
12 * later version.
13 *
14 * This program is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 * FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
17 * details.
18 *
19 * You should have received a copy of the GNU Affero General Public License
20 * along with this program. If not, see http://www.gnu.org/licenses/
21 */
22
23/*
24 * Hybrid logical clock as described in
25 * http://www.cse.buffalo.edu/tech-reports/2014-04.pdf.
26 *
27 */
28
29#pragma once
30
31#include <stdbool.h>
32#include <stdint.h>
33
34#include "citrusleaf/cf_clock.h"
35
36#include "node.h"
37
38/**
39 * A hybrid logical clock timestamp.
40 *
41 * The most significant 48 bits represent the physical component of the hlc and
42 * the least significant 16 bits represent the logical component.
43 */
44typedef uint64_t as_hlc_timestamp;
45
46/**
47 * Timestamp for a message receive event.
48 */
49typedef struct as_hlc_msg_timestamp_s
50{
51 /**
52 * The sender's HLC timestamp at time when the message was sent.
53 */
54 as_hlc_timestamp send_ts;
55 /**
56 * Local HLC timestamp at message receipt.
57 */
58 as_hlc_timestamp recv_ts;
59} as_hlc_msg_timestamp;
60
61/**
62 * Result of ordering two hlc timestamps.
63 */
64typedef enum as_hlc_timestamp_order_e {
65 /**
66 * The event with first timestamp happened before.
67 */
68 AS_HLC_HAPPENS_BEFORE,
69 /**
70 * The event with first timestamp happened after.
71 */
72 AS_HLC_HAPPENS_AFTER,
73 /**
74 * The order of the timestamps is indeterminated.
75 */
76 AS_HLC_ORDER_INDETERMINATE
77} as_hlc_timestamp_order;
78
79/*----------------------------------------------------------------------------
80 * Public API.
81 *----------------------------------------------------------------------------*/
82/**
83 * Initialize hybrid logical clock.
84 */
85void as_hlc_init();
86
87/**
88 * Return a hlc timestamp representing the hlc time "now".
89 */
90as_hlc_timestamp as_hlc_timestamp_now();
91
92/**
93 * Return the physical component of a hlc timstamp
94 * @param hlc_ts the hybrid logical clock timestamp.
95 */
96cf_clock as_hlc_physical_ts_get(as_hlc_timestamp hlc_ts);
97
98/**
99 * Update the HLC on receipt of a remote message. The notion is to adjust this
100 * node's hlc to ensure the receive hlc ts > the send hlc ts.
101 *
102 * @param source for debugging and tracking only.
103 * @param send_timestamp the hlc timestamp when this message was sent.
104 * @param recv_timestamp (output) the message receive timestamp which will be
105 * populated. Can be NULL in which case it will be ignored.
106 */
107void as_hlc_timestamp_update(cf_node source, as_hlc_timestamp send_ts,
108 as_hlc_msg_timestamp* msg_ts);
109
110/**
111 * Return the difference in milliseconds between two hlc timestamps. Note this
112 * difference may be greater than or equal to the physical wall call difference,
113 * because HLC can have non linear jumps, whenever the clock is adjusted. The
114 * difference should be used as an estimate rather than an absolute difference.
115 * For e.g. use the difference to check that the time difference is at least
116 * some number of milliseconds. However do not use this for interval statistics
117 * or to check if the difference in time is at the most some number of
118 * milliseconds.
119 *
120 * @param ts1 the first timestamp.
121 * @param ts2 the seconds timestamp.
122 * @return ts1 - ts2 in milliseconds.
123 */
124int64_t as_hlc_timestamp_diff_ms(as_hlc_timestamp ts1, as_hlc_timestamp ts2);
125
126/**
127 * Orders a local timestamp and remote message send timestamp.
128 *
129 * @param local_ts the local timestamp.
130 * @param msg_ts message receive timestamp containing the remote send and the
131 * local receive timestamp.
132 * @return the order between the local and the message timestamp.
133 */
134as_hlc_timestamp_order as_hlc_send_timestamp_order(
135 as_hlc_timestamp local_ts, as_hlc_msg_timestamp* msg_ts);
136
137/**
138 * Orders two timestamp generated by the same node / process.
139 *
140 * @param ts1 the first timestamp.
141 * @param ts2 the second timestamp.
142 * @return AS_HLC_HAPPENS_BEFORE if ts1 happens before ts2 else
143 * AS_HLC_HAPPENS_AFTER if ts1 happens after ts2 else
144 * AS_HLC_ORDER_INDETERMINATE.
145 */
146as_hlc_timestamp_order as_hlc_timestamp_order_get(as_hlc_timestamp ts1,
147 as_hlc_timestamp ts2);
148
149/**
150 * Subtract milliseconds worth of time from the timestamp.
151 * @param timestamp the input timestamp.
152 * @param ms the number of milliseconds to subtract.
153 */
154as_hlc_timestamp as_hlc_timestamp_subtract_ms(as_hlc_timestamp timestamp,
155 int ms);
156
157/**
158 * Dump some debugging information to the logs.
159 */
160void as_hlc_dump(bool verbose);
161