-
Notifications
You must be signed in to change notification settings - Fork 35
/
DirectStore.kt
458 lines (412 loc) · 17.9 KB
/
DirectStore.kt
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
/*
* Copyright 2019 Google LLC.
*
* This code may only be used under the BSD style license found at
* http://polymer.github.io/LICENSE.txt
*
* Code distributed by Google as part of this project is also subject to an additional IP rights
* grant found at
* http://polymer.github.io/PATENTS.txt
*/
package arcs.core.storage
import arcs.core.crdt.CrdtChange
import arcs.core.crdt.CrdtData
import arcs.core.crdt.CrdtException
import arcs.core.crdt.CrdtModel
import arcs.core.crdt.CrdtModelType
import arcs.core.crdt.CrdtOperation
import arcs.core.storage.DirectStore.State.Name.AwaitingDriverModel
import arcs.core.storage.DirectStore.State.Name.AwaitingResponse
import arcs.core.storage.DirectStore.State.Name.Idle
import arcs.core.util.TaggedLog
import kotlin.coroutines.coroutineContext
import kotlin.reflect.KClass
import kotlinx.atomicfu.AtomicRef
import kotlinx.atomicfu.atomic
import kotlinx.atomicfu.getAndUpdate
import kotlinx.atomicfu.update
import kotlinx.coroutines.CompletableDeferred
import kotlinx.coroutines.Job
/**
* An [ActiveStore] capable of communicating directly with a [Driver].
*
* This is what *directly* manages a [CrdtSingleton], [CrdtSet], or [CrdtCount].
*/
class DirectStore<Data : CrdtData, Op : CrdtOperation, T> /* internal */ constructor(
options: StoreOptions<Data, Op, T>,
/* internal */
val localModel: CrdtModel<Data, Op, T>,
/* internal */
val driver: Driver<Data>
) : ActiveStore<Data, Op, T>(options) {
override val versionToken: String?
get() = driver.token
private val log = TaggedLog { "DirectStore(${state.value}, $storageKey)" }
/**
* [AtomicRef] of a [CompletableDeferred] which will be completed when the [DirectStore]
* transitions into the Idle state.
*/
private val idleDeferred: AtomicRef<IdleDeferred> = atomic(CompletableDeferred(Unit))
/**
* [AtomicRef] of a list of [PendingDriverModel]s, allowing us to treat it as a copy-on-write,
* threadsafe list using [AtomicRef.update].
*/
private var pendingDriverModels = atomic(listOf<PendingDriverModel<Data>>())
private var version = atomic(0)
private var state: AtomicRef<State<Data>> = atomic(State.Idle(idleDeferred, driver))
private val nextCallbackToken = atomic(1)
private val callbacks = atomic(mapOf<Int, ProxyCallback<Data, Op, T>>())
override suspend fun idle() = state.value.idle()
override suspend fun getLocalData(): Data = synchronized(this) { localModel.data }
override fun on(callback: ProxyCallback<Data, Op, T>): Int {
val token = nextCallbackToken.getAndIncrement()
callbacks.update { it + (token to callback) }
return token
}
override fun off(callbackToken: Int) {
callbacks.update { callbackMap ->
return@update callbackMap - callbackToken
}
}
/**
* Receives operations/model-updates from connected storage proxies.
*
* Additionally, StorageProxy objects may request a SyncRequest, which will result in an
* up-to-date model being sent back to that StorageProxy. A return value of `true` implies that
* the message was accepted, a return value of `false` requires that the proxy send a model
* sync.
*/
override suspend fun onProxyMessage(
message: ProxyMessage<Data, Op, T>
): Boolean {
return when (message) {
is ProxyMessage.SyncRequest -> {
callbacks.value[message.id]?.invoke(
ProxyMessage.ModelUpdate(getLocalData(), message.id)
)
true
}
is ProxyMessage.Operations -> {
val failure =
synchronized(this) {
!message.operations.all { localModel.applyOperation(it) }
}
if (failure) {
callbacks.value[message.id]?.invoke(ProxyMessage.SyncRequest(message.id))
false
} else {
if (message.operations.isNotEmpty()) {
val change = CrdtChange.Operations<Data, Op>(
message.operations.toMutableList()
)
processModelChange(
change,
otherChange = null,
version = version.value,
channel = message.id
)
}
true
}
}
is ProxyMessage.ModelUpdate -> {
val (modelChange, otherChange) = synchronized(this) {
localModel.merge(message.model)
}
processModelChange(
modelChange,
otherChange,
version.value,
channel = message.id
)
true
}
}.also {
log.debug { "Model after proxy message: ${localModel.data}" }
}
}
private suspend fun processModelChange(
modelChange: CrdtChange<Data, Op>,
otherChange: CrdtChange<Data, Op>?,
version: Int,
channel: Int?
) {
if (modelChange.isEmpty() && otherChange?.isEmpty() == true) return
deliverCallbacks(modelChange, messageFromDriver = false, channel = channel)
updateStateAndAct(
noDriverSideChanges(modelChange, otherChange, false),
version,
messageFromDriver = false
)
}
/* internal */ suspend fun onReceive(data: Data, version: Int) {
log.debug { "onReceive($data, $version)" }
if (state.value.shouldApplyPendingDriverModelsOnReceive(data, version)) {
val pending = pendingDriverModels.getAndUpdate { emptyList() }
applyPendingDriverModels(pending + PendingDriverModel(data, version))
} else {
// If the current state doesn't allow us to apply the models yet, tack it onto our
// pending list.
pendingDriverModels.getAndUpdate { it + PendingDriverModel(data, version) }
}
}
private suspend fun applyPendingDriverModels(models: List<PendingDriverModel<Data>>) {
if (models.isEmpty()) return
log.debug { "Applying ${models.size} pending models: $models" }
var noDriverSideChanges = true
var theVersion = 0
models.forEach { (model, version) ->
try {
log.debug { "Merging $model into ${localModel.data}" }
val (modelChange, otherChange) = synchronized(this) { localModel.merge(model) }
log.debug { "ModelChange: $modelChange" }
log.debug { "OtherChange: $otherChange" }
theVersion = version
if (modelChange.isEmpty() && otherChange.isEmpty()) return@forEach
deliverCallbacks(modelChange, messageFromDriver = true, channel = 0)
noDriverSideChanges =
noDriverSideChanges && noDriverSideChanges(
modelChange,
otherChange,
messageFromDriver = true
)
log.debug { "No driver side changes? $noDriverSideChanges" }
} catch (e: Exception) {
log.error(e) { "Error while applying pending driver models." }
idleDeferred.value.completeExceptionally(e)
throw e
}
}
updateStateAndAct(noDriverSideChanges, theVersion, messageFromDriver = true)
}
/**
* Note that driver-side changes are stored in 'otherChange' when the merged operations/model is
* sent from the driver, and 'thisChange' when the merged operations/model is sent from a
* storageProxy. In the former case, we want to look at what has changed between what the driver
* sent us and what we now have. In the latter, the driver is only as up-to-date as our local
* model before we've applied the operations.
*/
private fun noDriverSideChanges(
thisChange: CrdtChange<Data, Op>,
otherChange: CrdtChange<Data, Op>?,
messageFromDriver: Boolean
): Boolean {
return if (messageFromDriver) {
otherChange?.isEmpty() ?: true
} else {
thisChange.isEmpty()
}
}
private suspend fun deliverCallbacks(
thisChange: CrdtChange<Data, Op>,
messageFromDriver: Boolean,
channel: Int?
) {
when {
thisChange is CrdtChange.Operations && thisChange.ops.isNotEmpty() -> {
callbacks.value.filter { messageFromDriver || channel != it.key }
.forEach { (id, callback) ->
callback(ProxyMessage.Operations(thisChange.ops, id))
}
}
thisChange is CrdtChange.Data -> {
callbacks.value.filter { messageFromDriver || channel != it.key }
.forEach { (id, callback) ->
callback(ProxyMessage.ModelUpdate(thisChange.data, id))
}
}
}
}
/**
* This function implements a state machine that controls when data is sent to the driver.
*
* You can see the state machine in all its glory
* [here](https://github.com/PolymerLabs/arcs/wiki/Store-object-State-Machine).
*/
private suspend fun updateStateAndAct(
noDriverSideChanges: Boolean,
version: Int,
messageFromDriver: Boolean
) {
if (noDriverSideChanges) {
// TODO: use a single lock here, rather than two separate atomics.
this.state.value = State.Idle(idleDeferred, driver)
this.version.value = version
return
}
// Wait until we're idle before we continue, unless - of course - we've been waiting on
// driver model information, in which case - we can start without being idle.
if (state.value !is State.AwaitingDriverModel<Data>) {
// Await is called on the old value of idleDeferred.
idleDeferred.getAndSet(IdleDeferred()).await()
}
var currentState = state.value
var currentVersion = version
var spins = 0
do {
val localModel = synchronized(this) { localModel.data }
val (newVersion, newState) =
currentState.update(currentVersion, messageFromDriver, localModel)
// TODO: use a lock instead here, rather than two separate atomics.
this.state.value = newState
this.version.value = currentVersion
currentState = newState
currentVersion = newVersion
// Make sure we don't loop infinitely.
check(++spins < MAX_UPDATE_SPINS) {
"updateAndAct iterated too many times, limit: $MAX_UPDATE_SPINS"
}
} while (newState !is State.Idle<Data> && newState !is State.AwaitingDriverModel<Data>)
// Finish applying the models from the driver, if we have any.
val models = pendingDriverModels.value
if (models.isNotEmpty()) {
applyPendingDriverModels(models)
}
}
private data class PendingDriverModel<Data : CrdtData>(val model: Data, val version: Int)
private suspend fun IdleDeferred(): CompletableDeferred<Unit> =
CompletableDeferred(coroutineContext[Job.Key])
private sealed class State<Data : CrdtData>(
val stateName: Name,
val idleDeferred: AtomicRef<IdleDeferred>,
val driver: Driver<Data>
) {
/** Simple names for each [State]. */
enum class Name { Idle, AwaitingResponse, AwaitingDriverModel }
/**
* The [DirectStore] is currently idle.
*/
class Idle<Data : CrdtData>(
idleDeferred: AtomicRef<IdleDeferred>,
driver: Driver<Data>
) : State<Data>(Idle, idleDeferred, driver) {
init {
// When a new idle state is created, complete the deferred so anything waiting on it
// will unblock.
idleDeferred.value.complete(Unit)
}
// We're already in idle state, so no need to do anything.
override suspend fun idle() = Unit
override suspend fun update(
version: Int,
messageFromDriver: Boolean,
localModel: Data
): Pair<Int, State<Data>> {
// On update() and when idle, we're ready to await the next version.
return (version + 1) to AwaitingResponse(idleDeferred, driver)
}
}
/**
* On update: sends the local model to the driver and awaits a response.
*/
class AwaitingResponse<Data : CrdtData>(
idleDeferred: AtomicRef<IdleDeferred>,
driver: Driver<Data>
) : State<Data>(AwaitingResponse, idleDeferred, driver) {
override fun shouldApplyPendingDriverModelsOnReceive(data: Data, version: Int) =
false
override suspend fun update(
version: Int,
messageFromDriver: Boolean,
localModel: Data
): Pair<Int, State<Data>> {
val response = driver.send(localModel, version)
return if (response) {
// The driver ack'd our send, we can move to idle state.
version to Idle(idleDeferred, driver)
} else {
// The driver didn't ack, so we need to move to AwaitingDriverModel.
version to AwaitingDriverModel(idleDeferred, driver)
}
}
}
/**
* Awaiting a model from the driver after a failed send.
*/
class AwaitingDriverModel<Data : CrdtData>(
idleDeferred: AtomicRef<IdleDeferred>,
driver: Driver<Data>
) : State<Data>(AwaitingDriverModel, idleDeferred, driver) {
override suspend fun update(
version: Int,
messageFromDriver: Boolean,
localModel: Data
): Pair<Int, State<Data>> {
// If the message didn't come from the driver, we can't do anything.
if (!messageFromDriver) return version to this
// This loop implements:
// sending -> AwaitingResponse -> AwaitingResponseDirty -> sending.
// Breakouts happen if:
// (1) a response arrives while still AwaitingResponse. This returns the store to
// Idle.
// (2) a negative response arrives. This means we're now waiting for driver models
// (AwaitingDriverModel). Note that in this case we are likely to end up back
// in this loop when a driver model arrives.
return (version + 1) to AwaitingResponse(idleDeferred, driver)
}
}
/** Waits until the [idleDeferred] signal is triggered. */
open suspend fun idle() = idleDeferred.value.await()
/**
* Determines the next state and version of the model while acting. (e.g. sending the
* [localModel] to the [Driver])
*
* Core component of the state machine, called by [DirectStore.updateStateAndAct] to
* determine what state to transition into and perform any necessary operations.
*/
open suspend fun update(
version: Int,
messageFromDriver: Boolean,
localModel: Data
): Pair<Int, State<Data>> = version to this
/**
* Returns whether or not, given the machine being in this state, we should apply any
* pending driver models to the local model.
*/
open fun shouldApplyPendingDriverModelsOnReceive(data: Data, version: Int): Boolean =
true
override fun toString(): String = "$stateName"
}
companion object {
/**
* To avoid an infinite loop OMG situation, set a maximum number of update spins for the
* state machine to something large, but not *infinite*.
*/
private const val MAX_UPDATE_SPINS = 1000
suspend inline fun <reified Data : CrdtData, Op : CrdtOperation, T> create(
options: StoreOptions<Data, Op, T>,
type: CrdtModelType<Data, Op, T>
): DirectStore<Data, Op, T> {
val driver = CrdtException.requireNotNull(
DriverFactory.getDriver<Data>(options.storageKey)
) { "No driver exists to support storage key ${options.storageKey}" }
return DirectStore(options.copy(type = type), type.createCrdtModel(), driver)
}
@Suppress("UNCHECKED_CAST")
// TODO: generics here are sub-optimal, can we make this constructor generic itself?
val CONSTRUCTOR = StoreConstructor<CrdtData, CrdtOperation, Any?> { options, dataClass ->
val localModel =
requireNotNull(options.type as? CrdtModelType<CrdtData, CrdtOperation, Any?>) {
"Specified type ${options.type} does not implement CrdtModelType"
}.createCrdtModel()
options.model?.let { localModel.merge(it) }
val driver =
CrdtException.requireNotNull(
DriverFactory.getDriver(
options.storageKey,
dataClass as KClass<out CrdtData>
)
) { "No driver exists to support storage key ${options.storageKey}" }
return@StoreConstructor DirectStore(
options as StoreOptions<CrdtData, CrdtOperation, Any?>,
localModel = localModel,
driver = driver as Driver<CrdtData>
).also { store ->
driver.registerReceiver(options.versionToken) { data, version ->
store.onReceive(data, version)
}
}
}
}
}
private typealias IdleDeferred = CompletableDeferred<Unit>