/Users/deen/code/yugabyte-db/src/yb/common/doc_hybrid_time.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) YugaByte, Inc. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
4 | | // in compliance with the License. You may obtain a copy of the License at |
5 | | // |
6 | | // http://www.apache.org/licenses/LICENSE-2.0 |
7 | | // |
8 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
9 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
10 | | // or implied. See the License for the specific language governing permissions and limitations |
11 | | // under the License. |
12 | | // |
13 | | |
14 | | #include "yb/common/doc_hybrid_time.h" |
15 | | |
16 | | #include "yb/gutil/casts.h" |
17 | | |
18 | | #include "yb/util/bytes_formatter.h" |
19 | | #include "yb/util/cast.h" |
20 | | #include "yb/util/debug-util.h" |
21 | | #include "yb/util/fast_varint.h" |
22 | | #include "yb/util/result.h" |
23 | | #include "yb/util/status.h" |
24 | | #include "yb/util/status_format.h" |
25 | | #include "yb/util/varint.h" |
26 | | |
27 | | using yb::util::VarInt; |
28 | | using yb::util::FastEncodeDescendingSignedVarInt; |
29 | | using yb::util::FastDecodeDescendingSignedVarIntUnsafe; |
30 | | using yb::FormatBytesAsStr; |
31 | | using yb::FormatSliceAsStr; |
32 | | using yb::QuotesType; |
33 | | |
34 | | using strings::Substitute; |
35 | | using strings::SubstituteAndAppend; |
36 | | |
37 | | namespace yb { |
38 | | |
39 | | // It does not really matter what write id we use here. We determine DocHybridTime validity based |
40 | | // on its HybridTime component's validity. However, given that HybridTime::kInvalid is close to the |
41 | | // highest possible value of the underlying in-memory representation of HybridTime, we use |
42 | | // kMaxWriteId for the write id portion of this constant for consistency. |
43 | | const DocHybridTime DocHybridTime::kInvalid = DocHybridTime(HybridTime::kInvalid, kMaxWriteId); |
44 | | |
45 | | const DocHybridTime DocHybridTime::kMin = DocHybridTime(HybridTime::kMin, 0); |
46 | | const DocHybridTime DocHybridTime::kMax = DocHybridTime(HybridTime::kMax, kMaxWriteId); |
47 | | |
48 | | constexpr int kNumBitsForHybridTimeSize = 5; |
49 | | constexpr int kHybridTimeSizeMask = (1 << kNumBitsForHybridTimeSize) - 1; |
50 | | |
51 | 436M | char* DocHybridTime::EncodedInDocDbFormat(char* dest) const { |
52 | | // We compute the difference between the physical time as microseconds since the UNIX epoch and |
53 | | // the "YugaByte epoch" as a signed operation, so that we can still represent hybrid times earlier |
54 | | // than the YugaByte epoch. |
55 | 436M | char* out = dest; |
56 | | |
57 | | // Hybrid time generation number. This is currently always 0. In the future this can be used to |
58 | | // reset hybrid time throughout the entire cluster back to a lower value if it gets stuck at some |
59 | | // far-in-the-future point due to a temporary clock issue. |
60 | 436M | out = FastEncodeDescendingSignedVarInt(0, out); |
61 | | |
62 | 436M | out = FastEncodeDescendingSignedVarInt( |
63 | 436M | static_cast<int64_t>(hybrid_time_.GetPhysicalValueMicros() - kYugaByteMicrosecondEpoch), |
64 | 436M | out); |
65 | 436M | out = FastEncodeDescendingSignedVarInt(hybrid_time_.GetLogicalValue(), out); |
66 | | |
67 | | // We add one to write_id to ensure the negated value used in the encoding is always negative |
68 | | // (i.e. is never zero). Then we shift it left by kNumBitsForHybridTimeSize bits so that we |
69 | | // always have kNumBitsForHybridTimeSize lowest bits to store the encoded size. This way we can |
70 | | // also decode the VarInt, negate it, obtain an always-positive value, and look at the lowest |
71 | | // kNumBitsForHybridTimeSize bits to get the encoded size of the entire DocHybridTime. |
72 | | // |
73 | | // It is important that we cast to int64_t before adding 1, otherwise WriteId might overflow. |
74 | | // (As of 04/17/2017 we're using a 32-bit unsigned int for WriteId). |
75 | 436M | out = FastEncodeDescendingSignedVarInt( |
76 | 436M | (static_cast<int64_t>(write_id_) + 1) << kNumBitsForHybridTimeSize, out); |
77 | | |
78 | | // Store the encoded DocHybridTime size in the last kNumBitsForHybridTimeSize bits so we |
79 | | // can decode the hybrid time from the end of an encoded DocKey efficiently. |
80 | 436M | const uint8_t last_byte = static_cast<uint8_t>(out[-1]); |
81 | | |
82 | 436M | const uint8_t encoded_size = static_cast<uint8_t>(out - dest); |
83 | 436M | DCHECK_LE(1, encoded_size); |
84 | 436M | DCHECK_LE(encoded_size, kMaxBytesPerEncodedHybridTime); |
85 | 436M | out[-1] = static_cast<char>((last_byte & ~kHybridTimeSizeMask) | encoded_size); |
86 | 436M | return out; |
87 | 436M | } |
88 | | |
89 | 1.36G | Result<DocHybridTime> DocHybridTime::DecodeFrom(Slice *slice) { |
90 | 1.36G | DocHybridTime result; |
91 | 1.36G | const size_t previous_size = slice->size(); |
92 | 1.36G | { |
93 | | // Currently we just ignore the generation number as it should always be 0. |
94 | 1.36G | RETURN_NOT_OK(FastDecodeDescendingSignedVarIntUnsafe(slice)); |
95 | 1.36G | int64_t decoded_micros = |
96 | 1.36G | kYugaByteMicrosecondEpoch + VERIFY_RESULT(FastDecodeDescendingSignedVarIntUnsafe(slice)); |
97 | | |
98 | 0 | auto decoded_logical = narrow_cast<LogicalTimeComponent>( |
99 | 1.36G | VERIFY_RESULT(FastDecodeDescendingSignedVarIntUnsafe(slice))); |
100 | | |
101 | 0 | result.hybrid_time_ = HybridTime::FromMicrosecondsAndLogicalValue( |
102 | 1.36G | decoded_micros, decoded_logical); |
103 | 1.36G | } |
104 | | |
105 | 0 | const auto ptr_before_decoding_write_id = slice->data(); |
106 | 1.36G | int64_t decoded_shifted_write_id = VERIFY_RESULT(FastDecodeDescendingSignedVarIntUnsafe(slice)); |
107 | | |
108 | 1.36G | if (decoded_shifted_write_id < 0) { |
109 | 0 | return STATUS_SUBSTITUTE( |
110 | 0 | Corruption, |
111 | 0 | "Negative decoded_shifted_write_id: $0. Was trying to decode from: $1", |
112 | 0 | decoded_shifted_write_id, |
113 | 0 | Slice(ptr_before_decoding_write_id, |
114 | 0 | slice->data() + slice->size() - ptr_before_decoding_write_id).ToDebugHexString()); |
115 | 0 | } |
116 | 1.36G | result.write_id_ = narrow_cast<IntraTxnWriteId>( |
117 | 1.36G | (decoded_shifted_write_id >> kNumBitsForHybridTimeSize) - 1); |
118 | | |
119 | 1.36G | const size_t bytes_decoded = previous_size - slice->size(); |
120 | 1.36G | const size_t size_at_the_end = (*(slice->data() - 1)) & kHybridTimeSizeMask; |
121 | 1.36G | if (size_at_the_end != bytes_decoded) { |
122 | 0 | return STATUS_SUBSTITUTE( |
123 | 0 | Corruption, |
124 | 0 | "Wrong encoded DocHybridTime size at the end: $0. Expected: $1. " |
125 | 0 | "Encoded timestamp: $2.", |
126 | 0 | size_at_the_end, |
127 | 0 | bytes_decoded, |
128 | 0 | Slice(to_char_ptr(slice->data() - bytes_decoded), bytes_decoded).ToDebugHexString()); |
129 | 0 | } |
130 | | |
131 | 1.36G | return result; |
132 | 1.36G | } |
133 | | |
134 | 968M | Result<DocHybridTime> DocHybridTime::FullyDecodeFrom(const Slice& encoded) { |
135 | 968M | Slice s = encoded; |
136 | 968M | auto result = DecodeFrom(&s); |
137 | 969M | if (result.ok()968M && !s.empty()) { |
138 | 0 | return STATUS_SUBSTITUTE( |
139 | 0 | Corruption, |
140 | 0 | "$0 extra bytes left when decoding a DocHybridTime $1", |
141 | 0 | s.size(), FormatSliceAsStr(encoded, QuotesType::kDoubleQuotes, /* max_length = */ 32)); |
142 | 0 | } |
143 | 968M | return result; |
144 | 968M | } |
145 | | |
146 | 870M | Result<DocHybridTime> DocHybridTime::DecodeFromEnd(Slice* encoded_key_with_ht_at_end) { |
147 | 870M | size_t encoded_size = 0; |
148 | 870M | RETURN_NOT_OK(CheckAndGetEncodedSize(*encoded_key_with_ht_at_end, &encoded_size)); |
149 | 870M | Slice s(encoded_key_with_ht_at_end->end() - encoded_size, encoded_size); |
150 | 870M | DocHybridTime result = VERIFY_RESULT(FullyDecodeFrom(s)); |
151 | 0 | encoded_key_with_ht_at_end->remove_suffix(encoded_size); |
152 | 870M | return result; |
153 | 870M | } |
154 | | |
155 | 20.3M | Result<DocHybridTime> DocHybridTime::DecodeFromEnd(Slice encoded_key_with_ht_at_end) { |
156 | 20.3M | return DecodeFromEnd(&encoded_key_with_ht_at_end); |
157 | 20.3M | } |
158 | | |
159 | 228k | string DocHybridTime::ToString() const { |
160 | 228k | if (write_id_ == 0) { |
161 | 23.1k | return hybrid_time_.ToDebugString(); |
162 | 23.1k | } |
163 | | |
164 | 205k | string s = hybrid_time_.ToDebugString(); |
165 | 205k | if (s[s.length() - 1] == '}') { |
166 | 205k | s.resize(s.length() - 2); |
167 | 205k | } else { |
168 | 13 | s.insert(2, "{ "); |
169 | 13 | } |
170 | 205k | if (write_id_ == kMaxWriteId) { |
171 | 3 | s += " w: Max }"; |
172 | 205k | } else { |
173 | 205k | SubstituteAndAppend(&s, " w: $0 }", write_id_); |
174 | 205k | } |
175 | 205k | return s; |
176 | 228k | } |
177 | | |
178 | 2.20G | Status DocHybridTime::CheckEncodedSize(size_t encoded_ht_size, size_t encoded_key_size) { |
179 | 2.20G | if (encoded_key_size == 0) { |
180 | 0 | return STATUS(RuntimeError, |
181 | 0 | "Got an empty encoded key when looking for a DocHybridTime at the end."); |
182 | 0 | } |
183 | | |
184 | 2.20G | SCHECK_GE(encoded_ht_size, |
185 | 2.20G | 1U, |
186 | 2.20G | Corruption, |
187 | 2.20G | Substitute("Encoded HybridTime must be at least one byte, found $0.", encoded_ht_size)); |
188 | | |
189 | 2.20G | SCHECK_LE(encoded_ht_size, |
190 | 2.20G | kMaxBytesPerEncodedHybridTime, |
191 | 2.20G | Corruption, |
192 | 2.20G | Substitute("Encoded HybridTime can't be more than $0 bytes, found $1.", |
193 | 2.20G | kMaxBytesPerEncodedHybridTime, encoded_ht_size)); |
194 | | |
195 | | |
196 | 2.20G | SCHECK_LT(encoded_ht_size, |
197 | 2.20G | encoded_key_size, |
198 | 2.20G | Corruption, |
199 | 2.20G | Substitute( |
200 | 2.20G | "Trying to extract an encoded HybridTime with a size of $0 bytes from " |
201 | 2.20G | "an encoded key of length $1 bytes (must be strictly less -- one byte is " |
202 | 2.20G | "used for value type).", |
203 | 2.20G | encoded_ht_size, encoded_key_size)); |
204 | | |
205 | 2.20G | return Status::OK(); |
206 | 2.20G | } |
207 | | |
208 | 2.21G | int DocHybridTime::GetEncodedSize(const Slice& encoded_key) { |
209 | | // We are not checking for errors here -- see CheckEncodedSize for that. We return something |
210 | | // even for a zero-size slice. |
211 | 2.21G | return encoded_key.empty() ? 00 |
212 | 2.21G | : static_cast<uint8_t>(encoded_key.end()[-1]) & kHybridTimeSizeMask; |
213 | 2.21G | } |
214 | | |
215 | | CHECKED_STATUS DocHybridTime::CheckAndGetEncodedSize( |
216 | 2.21G | const Slice& encoded_key, size_t* encoded_ht_size) { |
217 | 2.21G | *encoded_ht_size = GetEncodedSize(encoded_key); |
218 | 2.21G | return CheckEncodedSize(*encoded_ht_size, encoded_key.size()); |
219 | 2.21G | } |
220 | | |
221 | 0 | std::string DocHybridTime::DebugSliceToString(Slice input) { |
222 | 0 | auto temp = FullyDecodeFrom(input); |
223 | 0 | if (!temp.ok()) { |
224 | 0 | LOG(WARNING) << "Failed to decode DocHybridTime: " << temp.status(); |
225 | 0 | return input.ToDebugHexString(); |
226 | 0 | } |
227 | 0 | return temp->ToString(); |
228 | 0 | } |
229 | | |
230 | | } // namespace yb |