1 /*
2 * KeyRangeMap.actor.cpp
3 *
4 * This source file is part of the FoundationDB open source project
5 *
6 * Copyright 2013-2018 Apple Inc. and the FoundationDB project authors
7 *
8 * Licensed under the Apache License, Version 2.0 (the "License");
9 * you may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
11 *
12 * http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing, software
15 * distributed under the License is distributed on an "AS IS" BASIS,
16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17 * See the License for the specific language governing permissions and
18 * limitations under the License.
19 */
20
21 #include "fdbclient/KeyRangeMap.h"
22 #include "fdbclient/NativeAPI.actor.h"
23 #include "fdbclient/CommitTransaction.h"
24 #include "fdbclient/FDBTypes.h"
25 #include "fdbclient/ReadYourWrites.h"
26 #include "flow/actorcompiler.h" // has to be last include
27
getRangesAffectedByInsertion(const KeyRangeRef & keys,vector<KeyRange> & affectedRanges)28 void KeyRangeActorMap::getRangesAffectedByInsertion( const KeyRangeRef& keys, vector< KeyRange >& affectedRanges ) {
29 auto s = map.rangeContaining( keys.begin );
30 if (s.begin() != keys.begin && s.value().isValid() && !s.value().isReady())
31 affectedRanges.push_back( KeyRangeRef( s.begin(), keys.begin ) );
32 affectedRanges.push_back( keys );
33 auto e = map.rangeContaining( keys.end );
34 if (e.begin() != keys.end && e.value().isValid() && !e.value().isReady())
35 affectedRanges.push_back( KeyRangeRef( keys.end, e.end() ) );
36 }
37
krmDecodeRanges(KeyRef mapPrefix,KeyRange keys,Standalone<RangeResultRef> kv)38 Standalone<RangeResultRef> krmDecodeRanges(
39 KeyRef mapPrefix,
40 KeyRange keys,
41 Standalone<RangeResultRef> kv )
42 {
43 ASSERT(!kv.more || kv.size() > 1);
44 KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + keys.begin.toString(), mapPrefix.toString() + keys.end.toString() );
45
46 ValueRef beginValue, endValue;
47 if (kv.size() && kv[0].key.startsWith(mapPrefix))
48 beginValue = kv[0].value;
49 if (kv.size() && kv.end()[-1].key.startsWith(mapPrefix))
50 endValue = kv.end()[-1].value;
51
52 Standalone<RangeResultRef> result;
53 result.arena().dependsOn( kv.arena() );
54 result.arena().dependsOn( keys.arena() );
55
56 result.push_back(result.arena(), KeyValueRef(keys.begin, beginValue));
57 for(int i=0; i<kv.size(); i++) {
58 if (kv[i].key > withPrefix.begin && kv[i].key < withPrefix.end) {
59 KeyRef k = kv[i].key.removePrefix(mapPrefix);
60 result.push_back(result.arena(), KeyValueRef( k, kv[i].value ));
61 }
62 else if(kv[i].key >= withPrefix.end)
63 kv.more = false;
64 }
65
66 if(!kv.more)
67 result.push_back(result.arena(), KeyValueRef(keys.end, endValue));
68 result.more = kv.more;
69
70 return result;
71 }
72
73 // Returns keys.begin, all transitional points in keys, and keys.end, and their values
krmGetRanges(Transaction * tr,Key mapPrefix,KeyRange keys,int limit,int limitBytes)74 ACTOR Future<Standalone<RangeResultRef>> krmGetRanges( Transaction* tr, Key mapPrefix, KeyRange keys, int limit, int limitBytes )
75 {
76 KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + keys.begin.toString(), mapPrefix.toString() + keys.end.toString() );
77
78 state GetRangeLimits limits(limit, limitBytes);
79 limits.minRows = 2;
80 Standalone<RangeResultRef> kv = wait( tr->getRange( lastLessOrEqual(withPrefix.begin), firstGreaterThan(withPrefix.end), limits ) );
81
82 return krmDecodeRanges( mapPrefix, keys, kv );
83 }
84
krmGetRanges(Reference<ReadYourWritesTransaction> tr,Key mapPrefix,KeyRange keys,int limit,int limitBytes)85 ACTOR Future<Standalone<RangeResultRef>> krmGetRanges( Reference<ReadYourWritesTransaction> tr, Key mapPrefix, KeyRange keys, int limit, int limitBytes )
86 {
87 KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + keys.begin.toString(), mapPrefix.toString() + keys.end.toString() );
88
89 state GetRangeLimits limits(limit, limitBytes);
90 limits.minRows = 2;
91 Standalone<RangeResultRef> kv = wait( tr->getRange( lastLessOrEqual(withPrefix.begin), firstGreaterThan(withPrefix.end), limits ) );
92
93 return krmDecodeRanges( mapPrefix, keys, kv );
94 }
95
krmSetPreviouslyEmptyRange(Transaction * tr,const KeyRef & mapPrefix,const KeyRangeRef & keys,const ValueRef & newValue,const ValueRef & oldEndValue)96 void krmSetPreviouslyEmptyRange( Transaction* tr, const KeyRef& mapPrefix, const KeyRangeRef& keys, const ValueRef& newValue, const ValueRef& oldEndValue )
97 {
98 KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + keys.begin.toString(), mapPrefix.toString() + keys.end.toString() );
99 tr->set( withPrefix.begin, newValue );
100 tr->set( withPrefix.end, oldEndValue );
101 }
102
krmSetPreviouslyEmptyRange(CommitTransactionRef & tr,Arena & trArena,const KeyRef & mapPrefix,const KeyRangeRef & keys,const ValueRef & newValue,const ValueRef & oldEndValue)103 void krmSetPreviouslyEmptyRange( CommitTransactionRef& tr, Arena& trArena, const KeyRef& mapPrefix, const KeyRangeRef& keys, const ValueRef& newValue, const ValueRef& oldEndValue )
104 {
105 KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + keys.begin.toString(), mapPrefix.toString() + keys.end.toString() );
106 tr.set( trArena, withPrefix.begin, newValue );
107 tr.set( trArena, withPrefix.end, oldEndValue );
108 }
109
krmSetRange(Transaction * tr,Key mapPrefix,KeyRange range,Value value)110 ACTOR Future<Void> krmSetRange( Transaction* tr, Key mapPrefix, KeyRange range, Value value ) {
111 state KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + range.begin.toString(), mapPrefix.toString() + range.end.toString() );
112 Standalone<RangeResultRef> old = wait(tr->getRange(lastLessOrEqual(withPrefix.end), firstGreaterThan(withPrefix.end), 1, true));
113
114 Value oldValue;
115 bool hasResult = old.size() > 0 && old[0].key.startsWith(mapPrefix);
116 if(hasResult)
117 oldValue = old[0].value;
118
119 KeyRange conflictRange = KeyRangeRef( hasResult ? old[0].key : mapPrefix.toString(), keyAfter(withPrefix.end) );
120 if( !conflictRange.empty() )
121 tr->addReadConflictRange( conflictRange );
122
123 tr->clear(withPrefix);
124 tr->set( withPrefix.begin, value );
125 tr->set( withPrefix.end, oldValue );
126
127 return Void();
128 }
129
krmSetRange(Reference<ReadYourWritesTransaction> tr,Key mapPrefix,KeyRange range,Value value)130 ACTOR Future<Void> krmSetRange( Reference<ReadYourWritesTransaction> tr, Key mapPrefix, KeyRange range, Value value ) {
131 state KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + range.begin.toString(), mapPrefix.toString() + range.end.toString() );
132 Standalone<RangeResultRef> old = wait(tr->getRange(lastLessOrEqual(withPrefix.end), firstGreaterThan(withPrefix.end), 1, true));
133
134 Value oldValue;
135 bool hasResult = old.size() > 0 && old[0].key.startsWith(mapPrefix);
136 if(hasResult)
137 oldValue = old[0].value;
138
139 KeyRange conflictRange = KeyRangeRef( hasResult ? old[0].key : mapPrefix.toString(), keyAfter(withPrefix.end) );
140 if( !conflictRange.empty() )
141 tr->addReadConflictRange( conflictRange );
142
143 tr->clear(withPrefix);
144 tr->set( withPrefix.begin, value );
145 tr->set( withPrefix.end, oldValue );
146
147 return Void();
148 }
149
150 //Sets a range of keys in a key range map, coalescing with adjacent regions if the values match
151 //Ranges outside of maxRange will not be coalesced
152 //CAUTION: use care when attempting to coalesce multiple ranges in the same prefix in a single transaction
krmSetRangeCoalescing(Transaction * tr,Key mapPrefix,KeyRange range,KeyRange maxRange,Value value)153 ACTOR Future<Void> krmSetRangeCoalescing( Transaction *tr, Key mapPrefix, KeyRange range, KeyRange maxRange, Value value ) {
154 ASSERT(maxRange.contains(range));
155
156 state KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + range.begin.toString(), mapPrefix.toString() + range.end.toString() );
157 state KeyRange maxWithPrefix = KeyRangeRef( mapPrefix.toString() + maxRange.begin.toString(), mapPrefix.toString() + maxRange.end.toString() );
158
159 state vector<Future<Standalone<RangeResultRef>>> keys;
160 keys.push_back(tr->getRange(lastLessThan(withPrefix.begin), firstGreaterOrEqual(withPrefix.begin), 1, true));
161 keys.push_back(tr->getRange(lastLessOrEqual(withPrefix.end), firstGreaterThan(withPrefix.end) + 1, 2, true));
162 wait(waitForAll(keys));
163
164 //Determine how far to extend this range at the beginning
165 auto beginRange = keys[0].get();
166 bool hasBegin = beginRange.size() > 0 && beginRange[0].key.startsWith(mapPrefix);
167 Value beginValue = hasBegin ? beginRange[0].value : LiteralStringRef("");
168
169 state Key beginKey = withPrefix.begin;
170 if(beginValue == value) {
171 bool outsideRange = !hasBegin || beginRange[0].key < maxWithPrefix.begin;
172 beginKey = outsideRange ? maxWithPrefix.begin : beginRange[0].key;
173 }
174
175 //Determine how far to extend this range at the end
176 auto endRange = keys[1].get();
177 bool hasEnd = endRange.size() >= 1 && endRange[0].key.startsWith(mapPrefix) && endRange[0].key <= withPrefix.end;
178 bool hasNext = (endRange.size() == 2 && endRange[1].key.startsWith(mapPrefix)) || (endRange.size() == 1 && withPrefix.end < endRange[0].key && endRange[0].key.startsWith(mapPrefix));
179 Value existingValue = hasEnd ? endRange[0].value : LiteralStringRef("");
180 bool valueMatches = value == existingValue;
181
182 KeyRange conflictRange = KeyRangeRef( hasBegin ? beginRange[0].key : mapPrefix, withPrefix.begin );
183 if( !conflictRange.empty() )
184 tr->addReadConflictRange( conflictRange );
185
186 conflictRange = KeyRangeRef( hasEnd ? endRange[0].key : mapPrefix, hasNext ? keyAfter(endRange.end()[-1].key) : strinc( mapPrefix ) );
187 if( !conflictRange.empty() )
188 tr->addReadConflictRange( conflictRange );
189
190 state Key endKey;
191 state Value endValue;
192
193 //Case 1: Coalesce completely with the following range
194 if(hasNext && endRange.end()[-1].key <= maxWithPrefix.end && valueMatches) {
195 endKey = endRange.end()[-1].key;
196 endValue = endRange.end()[-1].value;
197 }
198
199 //Case 2: Coalesce with the following range only up to the end of maxRange
200 else if(valueMatches) {
201 endKey = maxWithPrefix.end;
202 endValue = existingValue;
203 }
204
205 //Case 3: Don't coalesce
206 else {
207 endKey = withPrefix.end;
208 endValue = existingValue;
209 }
210
211 tr->clear(KeyRangeRef(beginKey, endKey));
212
213 ASSERT(value != endValue || endKey == maxWithPrefix.end);
214 tr->set(beginKey, value);
215 tr->set(endKey, endValue);
216
217 return Void();
218 }
219