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… Read More »
short polling ajax based call. Every fixed amount of time, it calls server and get the result(the result might be empty as well). long polling When client and server has opened a TCP connection, it won’t close. Client just wait. Whenever there is message in server side, it sends to client. web socket client builds a… Read More »
space complexity O(n), time complexity for both union and find , in practice is normally less than 5. So can be treated as O(1) constant time. https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86 空间复杂度[编辑] 容易看出，不交集森林的空间复杂度是{\displaystyle \mathrm {O} \left(n\right)}。 时间复杂度[编辑] 对于同时使用路径压缩和按秩合并优化的不交集森林，每个查询和合并操作的平均时间复杂度仅为{\displaystyle O(\alpha (n))}，{\displaystyle \alpha (n)}是反阿克曼函数。由于阿克曼函数{\displaystyle A}增加极度迅速，所以{\displaystyle \alpha (n)}增长极度缓慢，对于任何在实践中有意义的元素数目{\displaystyle n}，{\displaystyle \alpha (n)}均小于5，因此，也可以粗略地认为，并查集的操作有常数的时间复杂度。
scenario, intensive write. Also once written in DB, can be used immediately. Such as LSM Tree, (Log Structured Merge Tree) In memory, calld memtable. In disk called sstable(Sorted String Table) 1. append to WAL first, then append to memtable. In any case system is crashed, can recover from WAL. memtable is sorted. When it reaches… Read More »
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… Read More »
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… Read More »
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 More »
Rewrite lock. Lock a data, then write it, then release the lock. copy-on-write, copy the data into a new place, update the date in new place. Then update the data’s reference to the new place.
WAL persistents operation to disk, then write to cache. If each operation needs to persistent to disk, then it is low efficient. Instead, do batching, this helps to improve performance, also reduce the error to batch level. https://martinfowler.com/articles/patterns-of-distributed-systems/wal.html Flushing every log write to the disk gives a strong durability guarantee (which is the main purpose… Read More »