Strictly Serializable

support transaction, Spanner

Linearizable

Doesn’t support transaction. There is global timer. Things in different machine happens with the global timer.

Sequential consistency

Above example satisfies sequential consistency. P3, P4, P5 all observe that W(x)1 happens before W(x)3. They are globally making sense. So it is sequential consistent. But considering the time when W(x)3 happens is early than W(x)1, so it is not linearizable consistent.

应用: zookeeper

Causal consistency

by using lamport timestamp

In (a), P2 observes that W(x)a should be before W(x)b. value b maybe depends on the value a. a -> b. But P3 observes that W(x)b -> R(x)a. So this doesn’t make sense. So, not causal.

Another example is that Alice asks a question, then Alice tells the answer. But person B observes the answer before the question. So it is not causal.

In (b), P3 observes W(x)b -> W(x)a. P4 observes W(x)a -> W(x)b. But W(x)a, W(x)b happens concurrently, it still makes sense. Causal consistency doesn’t require consistent in global. But (b) is not sequential consistency, because it is not consistent globally.

应用: 朋友圈. 朋友圈的发生顺序要make sense. 要因果一致.

Eventual consistency

weakest one.

https://jepsen.io/consistency

1. partition by key range
2. partition by hash

HBase, key is sorted
partition内部再sort.
read intensive, 1. replication, 2. cache?
read intensive
leaderless, 加名人list，加cache
leader-replica, 加replica

vertical scale, 加CPU, memory, disk
vertical split table. 将不同的column放在不同的node中

normalize, 归一化, no redundancy
denormalize, large table
global secondary index, local secondary index.

consistency hashing rebalancing, 并不能彻底解决hotspot

fixed number of partition，新加入的node，从其它node中偷partition过来
partition是事先定好的
node layer, leaderless, each node knows metadata
routing tier, redis, visit node1, but not in node1, node1 works as delegate to query node2.
client knows

MPP, SMP, NUMA
MPP, multi core processor
semantic body processor

Dynamo database, leaderless, quorum read/write, vector clock.

database, ACID
cache coherent, consistency

linearizable, 用户写的action发生了，那么read的时候就要读出write的内容
leaderless, quoram write, quoram read
read repair
or a background process to detect the stale data in replica
如果是read repair，某些data一直没有被read repair过，有些机器down了。good data node不在了。所以一定要有background process

anti-entrophy
the higher entropy, the greater the disorder

3 nodes.
r+w>n.
when w=1, r=3.
user1 only write (“a”, 1) in replica1, vector = [1, 0, 0].
user2 only write (“a”, 2) in replica2, vector = [0, 0, 1].
2 writes persistent in different replicas.
In this way, there will be conflict when reading from 3 replicas.

sloppy quorum, r+w is not greater than n

sloppy quorums and hinted handoff

redo log, undo log
snowflake calculate UUID, no conflict UUID

write conflicts的时候，如何resolve conflict?
This is a isolation problem. 2 users both write same record at same time.
MVCC(multi version concurrent control)

CRDT

959, in Base64 is O/. / is not uri-safe. An althernative is transform it to ASCII %47%.
But this lengthens the URL.
So in Base64,
+ -> –
/ -> _

Or use Base62. But Base62 transformation is too complex.

In Base64, each char takes up 6 bits. So always make the coding 24 bits, or 3 bytes的整数. If not enough, use = as padding

https://code.tutsplus.com/tutorials/base-what-a-practical-introduction-to-base-encoding–net-27590

https://en.wikipedia.org/wiki/Base64#Decoding_Base64_with_padding