DOCSEARCHbyAlgolia
Submit Docs

taobo.site Technical Blog and Algorithm Docs

website·Indexed 31 days ago

https://taobo.site/

A collection of technical study notes and algorithm solutions. It features LeetCode problem implementations in Go and Rust, guides on Linux fundamentals and Python, and deep dives into distributed systems, including Paxos, Raft, and design patterns like Consistent Hashing and Write-Ahead Logging.

Tokens
76.3K
Snippets
323
Records
403
Agent score
48%

What's inside taobo.site

  1. Overview of Paxos and Raft consensus algorithms

    When basic replication strategies fail to provide strong consistency, consensus algorithms like Paxos and Raft are used:

    • Paxos: A family of protocols used to reach agreement on a single result among a group of unreliable processors. It can be viewed as a rigorous evolution of quorum read/write, using two phases of majority-based communication to achieve strong consistency.
    • Raft: Designed as a more understandable and implementable alternative to Paxos. Its core architecture consists of three components: Leader Election, Log Replication, and an Application State Machine.

  2. Overview of Tkinter GUI Widgets

    Tkinter provides a variety of widgets for building graphical user interfaces in Python. Common widgets include:

    • Button: A clickable button to trigger actions.
    • Canvas: Used for drawing shapes, lines, or text.
    • Checkbutton: A checkbox for multiple-choice selections.
    • Entry: A single-line text input field.
    • Frame: A container used to organize other widgets.
    • Label: Displays text or bitmaps.
    • Listbox: Displays a list of strings.
    • Menu/Menubutton: Used for creating menu bars and dropdowns.
    • Message: Displays multi-line text (similar to Label).
    • Radiobutton: A button for single-choice selection.
    • Scale: A slider for selecting a numeric value within a range.
    • Scrollbar: Adds scrolling capability to other widgets.
    • Text: A multi-line text input/display area.
    • Toplevel: A separate window/dialog box.
    • Spinbox: An entry field with up/down arrows for a range of values.
    • PanedWindow: A layout manager containing one or more sub-widgets.
    • LabelFrame: A container with a label, often used for complex layouts.
    • tkMessageBox: Used to display alert/information dialogs.

  3. Overview of Paxos and Raft consensus algorithms

    Consensus algorithms ensure that multiple servers in a cluster agree on a single result, maintaining data consistency across replicas.

    • Paxos: A family of protocols for solving consensus in networks of unreliable processors. It can be viewed as an evolution of quorum read/write, using two phases of majority-based operations to achieve strong consistency. It is often considered complex to implement and understand.
    • Raft: Designed as a more understandable alternative to Paxos. The core of Raft consists of three components: Leader Election, Log Replication, and the Application State Machine.

  4. Evaluate Git backend storage architectures

    When designing a Git backend service, the primary challenges are storage capacity limits and high concurrent access loads. Different architectural patterns offer different trade-offs:

    1. Single Machine + Cold Backup: Uses git hooks to trigger sync tasks to a backup machine. Issues include sync failures, data inconsistency, and the inability to use the backup for read services.
    2. Single Machine + Distributed Storage: Attempts to solve capacity limits via a distributed file system. This is generally discouraged for Git because Git operations involve traversing massive amounts of small files, leading to high latency and performance degradation.
    3. Data Sharding + Master-Slave: Distributes data across shards.
      • Sharding only: All read/write requests go to the master; slaves are updated via hooks but are unreliable for reads.
      • Sharding + Read/Write Splitting: Implements a hash-based verification system to ensure a slave is up-to-date before routing read requests to it.
    4. Multi-Read Multi-Write: A more advanced approach (used by Alibaba) featuring copy-on-write for writes, stateless services, and fast repository consistency verification.

  5. Use Bloom Filters to reduce disk I/O in distributed storage

    A Bloom Filter is a space-efficient probabilistic data structure used to determine if an element is a member of a set. In distributed storage systems like BigTable, Bloom Filters are used to avoid expensive disk I/O by checking if an SSTable contains a specific key before attempting to read it from disk.

  6. Implement data distribution using Consistent Hashing

    Consistent Hashing allows for efficient scaling and replication of data with high availability and fault tolerance. Data items (identified by keys) are mapped to a hash ring. A key is assigned to the first node encountered when moving clockwise from the key's hash position on the ring. The primary advantage is incremental stability: adding or removing a node only affects its immediate neighbors, leaving the rest of the cluster undisturbed.

  7. Ensure consistency using Quorum in distributed systems

    Quorum is the minimum number of nodes that must successfully execute a distributed operation for it to be considered successful.

    • Cassandra: Configures write requests to succeed only when a quorum of replica nodes acknowledges the write to ensure consistency.
    • Chubby: Uses Paxos and quorum to guarantee strong consistency during leader election.
    • Dynamo: Writes data to a quorum of nodes in the system (not necessarily a strict majority) based on a preference list.

  8. Evaluate Git backend storage architectures

    Different architectures address storage capacity and high concurrency in Git services:

    1. Single Machine + Cold Backup: Uses git hooks for synchronization. Prone to sync failures, data loss, and lack of real-time updates on backups.
    2. Single Machine + Distributed Storage: Uses a distributed file system to scale capacity. This is often inefficient for Git because Git involves massive amounts of small files; traversing references and objects over a distributed file system causes high latency.
    3. Data Sharding + Master-Slave: Distributes data across shards. In a basic sharding model, only the master handles read/write requests to ensure data integrity, which can lead to performance bottlenecks when QPS exceeds the master's capacity.

  9. Manage cluster state with Leader and Follower patterns

    To ensure fault tolerance, data is replicated across multiple servers. A leader is elected to make decisions for the cluster and propagate those decisions to follower nodes. Heartbeat mechanisms are used to monitor the leader's health; if the leader fails, a new election is triggered.

  10. Prevent split-brain scenarios using Fencing

    Fencing prevents a failed or partitioned leader (which may still believe it is active) from processing requests or accessing resources. There are two primary implementation strategies:

    1. Resource Fencing: The system blocks the old leader from accessing the specific resources required to perform its tasks.
    2. Node Fencing: The system blocks the old leader from accessing all resources, typically by shutting down or resetting the node.

  11. Understand Linux File System Architecture

    The Linux file system (specifically Ext2/Ext4) is composed of several key elements:

    • inode: Each file occupies one inode. It stores file attributes (permissions, owner, size, timestamps) and pointers to the data blocks where the content resides. Inodes are typically 128 bytes (up to 256 bytes in ext4/xfs).
    • block: The actual storage unit for file content. Larger files span multiple blocks. Common block sizes are 1K, 2K, and 4K, which determine the maximum single file and file system size.
    • superblock: Contains global file system information, including total/used/free counts of inodes and blocks, and the file system format.
    • block bitmap: A map tracking which blocks are currently in use.

    Key Concepts:

    • Indirect Referencing: Since an inode has limited space, it uses indirect, double-indirect, and triple-indirect pointers to reference a large number of data blocks for large files.
    • Directories: A directory is a special file with its own inode and block. Its block contains a list of filenames and their corresponding inode numbers. This is why renaming or deleting files requires write permission on the directory, not necessarily the file itself.
    • Journaling: Ext3/Ext4 use logs to prevent file system corruption during sudden power loss by recording changes before they are committed to the main blocks.

  12. Understand the Paxos and Raft consensus algorithms

    Consensus algorithms ensure that multiple servers in a cluster agree on a single result, maintaining strong consistency across replicas.

    • Paxos: A family of protocols that achieves strong consistency through two rounds of quorum-based communication. It is considered the foundation for many consensus systems but is often criticized for being complex to implement and understand.
    • Raft: Designed as a more understandable alternative to Paxos. Its core consists of three components: Leader Election, Log Replication, and an Application State Machine.