Daily Archives: April 19, 2021

Linearizability, 强调分布式中并发执行的顺序

Serializability, in DB, repeatable read doesn’t guarantee whole data has other data updated, deleted, or inserted. refer to isolation level.

leader based repliaction, elasticache
replica pulls master replication log

sync, async, semi-sync(only 1 replica is sync, other replicas are async)

setup a new replica, or replica is down
1. copy snapshot
2. start sync from the log sequence number

master is down
1. replica votes a new master
2. new master has data almost same as old master
3. when old master came back, let old master be a replica

How to sync to replica?
1. statement based. INSERT/UPDATE/DELETE, but it may have nondeterministic statement, such as random(). Or where conditions. But different replica are not synced
2. WAL, consistent, low level, binary. But it’s highly relates to database product and maybe version.
3. row/record based. change data capatured

Async replica could cause data inconsistency between master and replica. In order to conquer this, there is read-after-write consistency. It enforces that replica are all updated.

facebook tao system.
single leader replication.

collaborative editing
https://www.zhihu.com/question/274573543
https://operational-transformation.github.io/index.html

OT, operational transaction

write through cache, read through cache

2 leaders

ddia figure 5-8

ring replication

tungstn

master-master replication
Conflict-free replicated data type

distributed lock -> distributed cache, chubby

读写异步
写异步->写事件流

paxos
multi-paxos

read after write, cascading rollback
write after read, non repeatable read.

https://jepsen.io/consistency

ACID vs BASE

cockroachDB vs spanner

compare and swap

sharding, replica

single leader
multiple leader
leaderless

sync只比async快一点点，从多个replica上读，能够确保一致性。
redis sync replication, use wait timeout，still can’t gurantee strong consistency.
Kafka单个partition其实read和write都在leader

Chandy Lamport algo, 增量snapshot, which is used by flink
WAL, use UPS to keep not down.
snapshot is actually compact for WAL.

zookeeper, need to review, how the CP works.
raft

paxos
consensus, agree on one result
3 roles: proposers, acceptors, learners
single node can take multiple roles, all all of roles.

Optimistic lock, when do transaction, read the version I’d and timestamp. Dismiss when version is or timestamp changed. Good for a lot of read scenario

Pessimistic lock, when do transaction, lock the record

3 types of read anomaly:
Dirty read
Non repeatable read
Phantom read

4 Isolation levels

Uncommitted read
read an uncommitted data. After read the, data change is committed. There might be dirty read.

Committed read

Make sure the data to read is committed. But when read the data 2nd time, might be different

Non-repeatable read

In same transaction, when reading a record for several times. Need to make sure it reads same value.

Snapshot isolation(MVCC)

It is same as repeatable read. It solves non repeatable read problem. Can do read, write at same time, no need lock. Compared with lock way.

Serializable