Yitao's Blog

Spanner Introduce Spanner is Google’s scalable, multi-version, globally-distributed, and synchronously-replicated data. Spanner is the first global distributed Database and support external consistency. It is a big framework, but I just want to focus on some particular points – Mainly about external consistency and True-Time mechanism. You may look for more detailed illustration on Google’s Spanner paper or other’s blog about spanner. Consistency Assume that if we have 3 Data Centers, we ha ...

Frangipani(To be updaed) Introduce While Frangipani is a paper published in 1997, I just want to talk about cache consistency in detail. The paper are mainly discussed following 3 aspects: cache coherence distributed transactions distributed crash recovery Cache consistency Rules for cache coherence No cached data without data’s lock acquire lock then read from petal write to petal then release lock Extends For more details, you may refer to this BlogFrangipani: A Scalable Distributed Fi ...

CRAQ Introduce Start with awareness that Paxos, Raft’s consensus algorithms have bottleneck in leader, because leader need to send logs to all followers and wait for majority of their reply. Chain replication is purposed in 2004, its scheme ensures serializability meanwhile the whole workload is distributed among the system(to each node). CRAQ is an improvement on Chain Replication, maintains strong consistency while greatly improving read throughput. But in this article, I will just mainly ta ...

Aurora Introduce Amazon Aurora is a relational database service for OLTP workloads offered as part of Amazon Web Services. Aurora is designed to address the constraint of bottleneck of network throughput, it also allows for fast crash recovery, failovers to replicas and fault-tolerant. History EC2 EC2 is Elastic Cloud 2 for short. Users can rent instances of EC to deploy their Web Server or DB services. Each instance of EC2 are running in the Virtual Machine on the physical node, and all ...

Conclusion After finish 3 parts of Lab, I have implemented a basic raft protocol and it can used to build a K-V storage server. It is fascinating for its understandability and straight idea to build this consensus system. In past 3 parts, I achieved timeout election, append entries, persist and many subtle details to ensure the consistency. My implementation may seem somehow ungraceful especially when I looked the tutorial course 'Go thread and Raft', so I do recommend you to have a look at it ...

1036. Escape a Large Maze tag: BFS Description Solution BFS + early quit. Because 1M * 1M is too large for BFS, so we need to find a way to return quickly. blocked.length <= 200 is a good quality we can look into. In a square, the best way to lock an area is laying all blocks 45° as following: 1234567890th _________________________ |O O O O O O O X |O O O O O O X |O O O O O X |O O O O X ...

1792.Maximum Average Pass Ratio tag : Heap, No AC first time Description Solution I feel shamed for I failed to AC it at first time… Use a heap to store the whole develop rate for each class, and find the max dr and use it. O(NlogN) Code 1234567891011121314151617181920212223class Solution {public: double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) { priority_queue<pair<double, int>, vector<pair<double, int>>, les ...

457. Circular Array Loop Tag: Fast-Slow pointers, No AC first time Description Solution To determine a cycle, Fast-Slow pointers is a good way for solving it in linear time and constant space. Some tricky points Determine all positive or all negative Determine length k>1 We can do a product of two nums to judge whether they are same positive or not, and do slow == Next(slow) to judge loop’s length == 1 Code 12345678910111213141516171819202122232425262728293031323334353637class Soluti ...

847. Shortest Path Visiting All Nodes Tag: State Compression, BFS, No AC first time Description Solutions We can see from constrains that n<=12, so we can use state compression. Also, the weight of each edge is 1, which reminds us of BFS to search for the lowest distance to reach final state 1<<n - 1 Some tricky points Use tuple to store a three tuple, {node, mask, dist} for the current node, mask and current distance. Use a array or map to store the visited state, stat ...

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick StartCreate a new post1$ hexo new "My New Post" More info: Writing Run server1$ hexo server More info: Server Generate static files1$ hexo generate More info: Generating Deploy to remote sites1$ hexo deploy More info: Deployment