DEV Community: Lorain

How to Implement Serializable Snapshot Isolation for Transactions

Lorain — Mon, 28 Apr 2025 15:52:00 +0000

Introduction

This article will start with the basic concepts of transactions, introduce the various problems faced by concurrent transactions along with their corresponding solutions, and provide a detailed explanation and analysis of Serializable Snapshot Isolation (SSI), including its concept and implementation.

Basic Concepts

A transaction in a database is a way to group multiple read and write operations into a single logical unit. A transaction either commits successfully or aborts (or rolls back). This characteristic of transactions greatly simplifies the issues that application developers need to consider when interacting with a database (e.g., partial failures).

The safety guarantees provided by transactions are commonly described by the ACID properties:

Atomicity
Consistency
Isolation
Durability

We will focus on the implementation of Isolation, which describes the behavior of a database when handling concurrent transactions. In the case of concurrent transactions, the database faces problems such as dirty reads, dirty writes, and nonrepeatable reads. To address these issues, different transaction isolation levels provide corresponding guarantees.

Dirty Read: A transaction reads modifications made by another concurrent, uncommitted transaction.
Dirty Write: A transaction's modifications overwrite changes made by another concurrent, uncommitted transaction.
Read Skew (Nonrepeatable Read): Reading the same value at different times within a transaction yields different results.
Lost Update: When concurrent transactions modify the same record, the changes made by the earlier (committed) transaction might be lost, as the later transaction overwrites them.
Write Skew: Two concurrent transactions read the same data and update different records based on that data, ultimately violating the expected consistency constraints.
Phantom Read: A transaction’s writes change the result set of a range query executed by another transaction.

Dirty Write refers to a transaction overwriting modifications made by another uncommitted transaction.

Lost Update occurs when concurrent transactions read the same object and then update the same object based on stale data, causing updates to be lost.

Write Skew happens when concurrent transactions read the same data under specific conditions and then update different objects based on those reads. Although these updates do not conflict directly, they may violate business constraints.

Snapshot Isolation

To address nonrepeatable reads or read skew, we can use Snapshot Isolation (SI).

As the name suggests, snapshot isolation means that the visibility scope of a transaction is a consistent snapshot of the database taken at the start of the transaction. During the lifetime of the transaction, modifications made by other concurrent transactions are not visible.

Snapshot isolation is usually implemented in conjunction with MVCC (Multi-Version Concurrency Control) because different transactions need to see the state of the database at different points in time, which requires maintaining multiple versions of the data.

In MySQL’s InnoDB storage engine, each transaction is assigned a monotonically increasing unique transaction ID (transaction id) based on its creation time. To implement MVCC, each data row in the database maintains multiple versions (managed through undo logs), and each version is tagged with the transaction id of the transaction that created it.

To determine which versions of the data are visible to the current transaction and which are not, InnoDB constructs a consistent view (read view) when the transaction is created. The consistent view contains four important fields:

trx_ids: A list of IDs for all uncommitted transactions at the time the view was constructed.
up_limit_id: The smallest transaction ID in trx_ids. All transaction IDs smaller than this value are considered committed.
low_limit_id: The next transaction ID that has not yet been assigned at the time the Read View was created.
creator_trx_id: The transaction ID of the transaction that created this consistent view.

We can visualize this consistent view as follows:

Transaction IDs greater than or equal to up_limit_id do not necessarily mean that those transactions have not committed. up_limit_id only guarantees that all transaction IDs smaller than it have committed, but it does not imply that all IDs greater than or equal to it are uncommitted.

With this view, we can determine the visibility of each data row version to the current transaction by comparing the row’s transaction id with the fields of the read view:

If the transaction id falls in the green area (txn_id < up_limit_id), the data version was created by a committed transaction and is visible.
If the transaction id falls in the red area (txn_id >= low_limit_id), the data version was created by a transaction that has not yet started and is not visible.
If the transaction id falls in the orange area (up_limit_id <= txn_id < low_limit_id), there are two cases:
- If txn_id is in the trx_ids array, it means the transaction is uncommitted and the data version is not visible.
- If txn_id is not in the trx_ids array, it means the transaction has committed and the data version is visible.

Through the Read View and visibility rules, we ensure that a transaction always sees a consistent snapshot of the database during its execution, thus implementing the snapshot isolation level.

Serializable

Snapshot isolation cannot handle write skew and phantom read scenarios. To address these issues, we need Serializable isolation.

Let’s start with an example of write skew:

In this scenario, we need to ensure that at least one doctor remains on-call. Suppose Doctors Alice and Bob both submit leave requests (removing their on-call status) at the same time. Because their requests start concurrently, they both see the same consistent snapshot of the database. This leads them to believe there are still multiple doctors on-call, so they both remove themselves from on-call status and successfully commit their transactions. While this behavior is acceptable under snapshot isolation, it violates the rule that at least one doctor must remain on-call.

Under the serializable isolation level, this kind of situation can be avoided. Depending on the implementation, one of the concurrent transactions may be blocked or aborted.

Serializable isolation ensures that multiple transactions appear to execute in a serial order, even though they are actually executed concurrently. This prevents all possible race conditions. There are generally three approaches to achieve serializability:

Truly serial execution: Transactions are executed one at a time in a single thread, limiting transaction throughput to the speed of a single core. Alternatively, if the dataset supports partitioning without cross-partition coordination, each partition can utilize its own CPU core independently.
Two-Phase Locking (2PL): This approach uses locks on data objects. Locks are divided into shared locks (Share mode) for reading and exclusive locks (Exclusive mode) for writing or modifying data. Shared and exclusive locks conflict with each other, and exclusive locks conflict with other exclusive locks. However, 2PL can lead to deadlocks and lock waits, making its performance much worse than weaker isolation levels.

Mechanisms like Next-Key Lock and Record Lock also have shared and exclusive modes.

Optimistic Concurrency Control (OCC): While 2PL is a pessimistic concurrency control mechanism (using locks and only releasing them once safety is ensured), Serializable Snapshot Isolation (SSI) is based on optimistic concurrency control. Even though potential conflicts may occur during transaction execution, these conflicts are only checked at commit time to verify whether isolation guarantees have been violated. When transaction contention is low, optimistic concurrency control performs well.

The goal of Serializable isolation is to ensure that the overall effect of transaction execution is equivalent to some serial order. However, it does not guarantee that every read sees the most recent value (i.e., the latest write).

Serializable Snapshot Isolation (SSI)

Serializable Snapshot Isolation (SSI) provides full serializability with only minimal overhead compared to standard snapshot isolation. SSI can be viewed as adding a conflict detection algorithm on top of snapshot isolation to detect serialization conflicts between writes. All reads still operate on a consistent snapshot taken at the start of the transaction.

The root cause of write skew under snapshot isolation is that transactions make decisions based on outdated consistent snapshots. Since the data read from the snapshot might have been modified by another committed concurrent transaction, the transaction could be working with stale data.

In other words, we need an algorithm that can detect whether the data read by the current transaction has been modified by a concurrent transaction that committed before us.

The concurrent transactions referred to here are the two types of invisible transactions discussed in the visibility rules of snapshot isolation. In both cases, these transactions' modifications are not visible to our current transaction's consistent snapshot:

Transactions that have not yet started;

Transactions that have started but not yet committed.

Let’s revisit the previous write skew example and consider two possible scenarios:

Write-then-Read

In this scenario, Transactions 43 and 42 operate on the same consistent snapshot. Transaction 43 reads data, while Transaction 42 modifies that data (although the modification is not yet committed). If Transaction 42 commits before Transaction 43, it means that Transaction 43 has read stale data. Therefore, when Transaction 43 attempts to commit, it must be aborted.

Why wait until commit time to abort?

Transaction 42 might abort first, invalidating its modifications.

Transaction 42 might commit later, which wouldn't conflict.

Transaction 43 might be a read-only transaction, meaning it wouldn’t cause write skew.

Read-then-Write

In this scenario, Transactions 43 and 42 also operate on the same consistent snapshot. Transaction 43 performs reads before Transaction 42 modifies the data. However, if Transaction 42 commits before Transaction 43, the data read by Transaction 43 becomes stale. As a result, when Transaction 43 tries to commit, it is aborted.

To implement this conflict detection algorithm, we need to either:

Notify concurrent transactions that read data modified by the current transaction at commit time; or
Record the data modified by concurrent transactions and check at commit time whether the current transaction has read any of this data.

This ensures that no transaction can commit based on stale reads, thus achieving serializability.

Implementation

In this section, we will implement Serializable Snapshot Isolation (SSI) ourselves to provide transaction support for the database. However, the database we are working with is a key-value store (NoSQL) that uses an LSM-Tree storage engine, rather than the more common relational database (RDBMS).

Building an LSM-Tree Storage Engine from Scratch

That said, the core idea behind implementing SSI is shared between both systems. Providing SSI support for a key-value database is relatively simpler.

As mentioned in the concept introduction section, SSI is built on top of the snapshot isolation (SI) transaction isolation level. This means we first need to implement snapshot isolation, and then, on top of that, implement an algorithm to detect serialization conflicts between concurrent transactions.

In this implementation section, we won’t dive too deeply into specific code details. Instead, we will focus on how the various components work together. For the complete code, please refer to the implementation at https://github.com/B1NARY-GR0UP/originium.

Transaction Start and Commit Timestamps

The first problem we need to solve is: How do we determine the start and commit timestamps of a transaction?

The start timestamp is used to determine the range of the consistent snapshot that the transaction can see.
The commit timestamp is used in SSI to determine the commit order between concurrent transactions.

By comparing the commit timestamp of other transactions with the start timestamp of the current transaction, we can determine whether there might be a serialization conflict between the two transactions. Additionally, the commit timestamp serves as a version identifier for the data we store. When paired with the transaction’s start timestamp, this enables snapshot isolation.

For simplicity, we use readTs to represent a transaction’s start timestamp and commitTs to represent its commit timestamp. The rules for managing readTs and commitTs are as follows:

Both readTs and commitTs are integer timestamps starting from 0.
Each transaction is assigned a monotonically increasing commitTs at commit time.
Each transaction is assigned a readTs at the start, which equals the current global maximum commitTs. Before starting, the transaction waits for all transactions with commitTs less than or equal to this value to either commit or abort.
A transaction can only see data versions whose commit timestamps are less than or equal to its readTs.

Let’s walk through a simple example to illustrate:

Before TxnA and TxnB start, our database contains three key-value pairs. The value after the @ symbol represents the version of the key. For example, k:a@2 v:a2 indicates that the key a has the value a2 at version 2. When TxnA and TxnB begin, there are no active transactions in the database. Both transactions receive a readTs of 2 (which is the current maximum commitTs in the database). TxnA commits a new value for key a and gets a commitTs of 3, which is monotonically increasing. TxnB, during its transaction, reads the value of key a. Since its readTs is 2, it does not see TxnA’s newly committed version 3 of key a. Instead, it reads the previous version of key a with value a2. TxnB also sets a new value for key b and commits, receiving a commitTs of 4, which again increases monotonically.

Conflict Detection

The second issue we need to address is: How do we detect serialization conflicts caused by concurrent transactions?

In our earlier discussion, we considered two scenarios that can lead to write skew and concluded that the key to detection is determining whether the data read by the current transaction has been modified by a concurrent transaction that committed before the current one. The detection logic we use here is simple and straightforward: we only need to record the keys read by the current transaction and the keys modified by concurrently committed transactions, then check if there’s any overlap between them.

Let’s first walk through the general execution flow before diving into the details of conflict detection:

Record the keys read and written by a transaction.
Perform conflict detection at commit time; if a conflict is found, abort the transaction immediately.
If no conflict is found, record the keys written by the transaction along with its assigned commitTs in a globally maintained array.

This globally maintained array is the core mechanism we use to implement conflict detection. It keeps track of the keys modified by all transactions that could potentially conflict with the current transaction. Here’s how our conflict detection process works:

func (o *oracle) hasConflict(txn *Txn) bool {
    if len(txn.readsFp) == 0 {
        return false
    }
    for _, ct := range o.committedTxns {
        if ct.ts <= txn.readTs {
            continue
        }

        for _, fp := range txn.readsFp {
            // a conflict occurred when curr txn read a key that be modified by a committed txn
            if _, ok := ct.writesFp[fp]; ok {
                return true
            }
        }
    }
    return false
}

The array, called committedTxns, holds information about all committed transactions. At commit time, we select the transactions from this array that committed after the current transaction’s readTs (> txn.readTs), and check whether any of their written keys overlap with the keys read by the current transaction. If there’s an overlap, it means the data read by the current transaction’s consistent snapshot has already been modified by another committed concurrent transaction, and we return true to indicate a conflict.

One important detail to note is that we cannot allow the committedTxns array to grow indefinitely. We need to periodically clean up the committed transactions that are no longer needed—specifically, those whose commitTs is earlier than the earliest active transaction in the system. These transactions can no longer conflict with any active transactions.

Let’s revisit the write-then-read example we discussed earlier and walk through the process again to see how our implementation handles write skew:

As shown in the diagram, the committedTxns array is initially empty because there are no transactions with commitTs > 1 in the system. TxnA modifies a key and commits before TxnB. At this point, TxnA’s modified keys are recorded in committedTxns. When TxnB tries to commit, TxnA’s commitTs is greater than TxnB’s readTs, and TxnB has read a key that TxnA modified. Since there is an overlap, a conflict is detected, and TxnB is aborted.

Discarding Old Data Versions

Handling old data versions is the final issue we need to consider. If we do not periodically clean up old data versions, the database will accumulate a large number of obsolete versions, wasting storage space and degrading overall performance.

Different databases have their own strategies and implementations for when and how frequently to clean up old data versions. Here, we mainly focus on defining the scope of data version cleanup—specifically, which versions can be safely discarded.

Our conclusion is: for each key-value pair, we retain all versions with a version number greater than or equal to the readTs of the earliest active transaction in the system. For versions with a version number less than the readTs of the earliest active transaction, we only keep the latest version.

This cleanup rule is similar to InnoDB’s mechanism, where InnoDB removes undo logs for all data versions whose transaction IDs are less than the ID of the earliest active transaction. Since the latest version resides in the main table, it is not removed.

Once we understand this cleanup rule, the next question is: how do we determine the readTs of the earliest active transaction in the system, and how is this value maintained? In InnoDB, each transaction maintains a list of active transaction IDs at the time it is created. This list is generated from a global list of active transactions, which allows InnoDB to determine the ID of the earliest active transaction for cleanup and other purposes.

In our implementation, we can adopt a similar approach by using a structure that globally tracks the active state of transactions in the system. We call this structure WaterMark.

The main methods of WaterMark are as follows:

Begin: Starts tracking a timestamp.
Done: Stops tracking a timestamp.
DoneUntil: Returns a value, indicating that all timestamps less than or equal to this value have been completed.

Using these three core methods, we can track the active transactions in the system. When a transaction starts, we track its readTs, and when it commits or aborts, we stop tracking that readTs. By calling DoneUntil, we can obtain the safe range for cleaning up old data versions.

Conclusion

Starting from the concept of transactions, we explored the various issues that arise with concurrent transactions and completed an analysis of how to implement Serializable Snapshot Isolation (SSI). We hope this helps deepen your understanding of these concepts.

That wraps up the content of this article. If there are any mistakes or issues, feel free to reach out via private message or leave a comment below.

Reference

Building an LSM-Tree Storage Engine from Scratch

Lorain — Thu, 02 Jan 2025 18:44:17 +0000

Preface

This article will guide you through understanding the Log-Structured Merge-Tree (LSM-Tree), including its core concepts and structure. By the end, you'll be able to build your own storage engine based on LSM-Tree from scratch.

What is LSM-Tree?

Basic Concepts

The Log-Structured Merge-Tree (LSM-Tree) is a data structure optimized for high-throughput write operations. It is widely used in databases and storage systems, such as Cassandra, RocksDB, and LevelDB.

The key idea of LSM-Tree is to first write operations into an in-memory data structure (typically an ordered structure like a skip list or AVL tree). Later, these writes are batched and sequentially written to disk as SSTables, thereby minimizing random I/O.

Basic Structure

The LSM-Tree is divided into two main components:

In-Memory Storage
- The core structure in memory is the Memtable.
- All write operations (e.g., set, delete) first go to the Memtable, which inserts these operations into an ordered data structure (e.g., an ordered tree in the diagram).
- Once the Memtable reaches a certain size threshold, it is flushed to disk as an SSTable (written sequentially).
- New write operations continue on a fresh Memtable.
Disk Storage
- Disk storage involves WAL and SSTable files.
- The WAL (Write-Ahead Log) ensures that recent writes (stored in the Memtable but not yet persisted to disk) are not lost in case of a database crash. Every write to the Memtable is appended to the WAL. Upon restarting the database, entries from the WAL can be replayed in order to restore the Memtable to its pre-crash state.
- The SSTable (Sorted String Table) is a data storage format that holds a series of ordered key-value pairs.
- When the Memtable reaches its size threshold, it generates a new SSTable and persists it to disk. Since the Memtable relies on an in-memory ordered data structure, no additional sorting is required when constructing the SSTable.
- SSTables on disk are organized into multiple levels. Newly flushed SSTables are stored in Level 0. During subsequent compaction phases, SSTables in L0 are merged into Level 1 and higher levels.
- When the size of a level exceeds a threshold, an SSTable compaction process is triggered. During compaction, SSTables in the current level are merged into higher levels, producing larger, more ordered files. This reduces fragmentation and improves query efficiency.

Typically, the structure of an SSTable includes more than just a series of ordered key-value pairs (data blocks). It also contains an index block, metadata block, and other components. These details will be discussed in-depth during the implementation section.

Writing Data

Writing data involves adding a new key-value pair or updating an existing one. Updates overwrite old key-value pairs, which are later removed during the compaction process.

When data is written, it first goes to the Memtable, where the key-value pair is added to the in-memory ordered data structure. Simultaneously, the write operation is logged in the WAL and persisted to disk to prevent data loss in the event of a database crash.

The Memtable has a defined threshold (usually based on size). When the Memtable exceeds this threshold, it is switched to read-only mode and converted into a new SSTable, which is then persisted to Level 0 on disk.

Once the Memtable is flushed as an SSTable, the corresponding WAL file can be safely deleted. Subsequent write operations will proceed on a new Memtable (and a new WAL).

Deleting Data

In LSM-Tree, data is not immediately removed. Instead, deletions are handled using a mechanism called tombstones (similar to soft deletes). When a key-value pair is deleted, a new entry marked with a "tombstone" is written, indicating the deletion of the corresponding key-value pair. The actual removal occurs during the compaction process.

This tombstone-based deletion ensures the append-only property of LSM-Tree, avoiding random I/O and maintaining sequential writes to disk.

Querying Data

The process of querying data starts with a search in the Memtable. If the key-value pair is found, it is returned to the client. If a tombstone-marked key-value pair is found, it indicates that the requested data has been deleted, and this information is also returned. If the key is not found in the Memtable, the query proceeds to search the SSTables from Level 0 to Level N.

Since querying data may involve searching multiple SSTable files and can lead to random disk I/O, LSM-Tree is generally better suited for write-heavy workloads rather than read-intensive ones.

One common optimization for query performance is the use of a Bloom filter. A Bloom filter can quickly determine whether a key-value pair exists in a specific SSTable, reducing unnecessary disk I/O. Additionally, the sorted nature of SSTables enables efficient search algorithms, such as binary search, to be employed for faster lookups.

Data Compaction

Here, we introduce the Leveled Compaction Strategy, which is used by LevelDB and RocksDB.

Another common strategy is the Size-Tiered Compaction Strategy, where newer and smaller SSTables are successively merged into older and larger SSTables.

As previously mentioned, an SSTable stores a series of entries sorted by key. In the Leveled Compaction Strategy, SSTables are organized into multiple levels (Level 0 to Level N).

In Level 0, SSTables can have overlapping key ranges, as they are directly flushed from the Memtable. However, in Levels 1 through N, SSTables within the same level do not have overlapping key ranges, although key range overlaps are allowed between SSTables in different levels.

An illustrative (though not entirely accurate) example is shown below. In Level 0, the key ranges of the first and second SSTables overlap, while in Level 1 and Level 2, the SSTables within each level have disjoint key ranges. However, SSTables between different levels (e.g., Level 0 and Level 1, or Level 1 and Level 2) may have overlapping key ranges.

Let’s now explore how the Leveled Compaction Strategy maintains this organizational structure.

Since Level 0 is a special case, the compaction strategy discussion is divided into two parts:

Level 0 to Level 1 Since Level 0 allows overlapping keys among SSTables, compaction begins by selecting an SSTable from Level 0, along with all other SSTables in Level 0 that have overlapping key ranges with it. Next, all SSTables in Level 1 with overlapping key ranges are selected. These selected SSTables are merged and compacted into a single new SSTable, which is then inserted into Level 1. All old SSTables involved in the compaction process are deleted.
Level N to Level N+1 (N > 0) From Level 1 onwards, SSTables within the same level do not have overlapping key ranges. During compaction, an SSTable is selected from Level N, and all SSTables in Level N+1 with overlapping key ranges are also selected. These SSTables are merged and compacted into one or more new SSTables, which are inserted into Level N+1, while the old SSTables are deleted.

The primary difference between Level 0 to Level 1 compaction and Level N to Level N+1 (N > 0) compaction lies in the selection of SSTables at lower levels (Level 0 or Level N).

The multi-SSTable compaction and merging process is illustrated below. During the merge, only the latest value for each key is retained. If the latest value has a "tombstone" marker, the key is deleted. In the implementation, we use the k-way merge algorithm to perform this process.

It is important to note that the above description of the compaction process provides only a high-level overview. Many details need to be addressed during actual implementation.

For example, in LevelDB, when constructing new SSTables for Level N+1 during compaction, if the new SSTable overlaps with more than 10 SSTables in Level N+2, the process switches to constructing another SSTable. This limits the data size involved in a single compaction.

Implementation

Based on the overview of LSM-Tree above, I believe you now have a basic understanding of LSM-Tree and some ideas about its implementation. Next, we will build a storage engine based on LSM-Tree from scratch. Below, we will introduce only the core code; for the complete code, please refer to https://github.com/B1NARY-GR0UP/originium.

We will break down the implementation of LSM-Tree into the following core components and implement them one by one:

Skip List
WAL
Memtable
SSTable
K-Way Merge
Bloom Filter
Leveled Compaction

Skip List

In the process of introducing data writing, we mentioned that the LSM-Tree first writes data into an in-memory ordered data structure. Some common ordered data structures and the time complexity of their operations are as follows:

Data Structure	Insert	Delete	Search	Traverse
Skip List	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)
AVL Tree	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)
Red-Black Tree	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)

We chose the Skip List for two main reasons: it is simpler to implement and maintain (KISS principle), and the underlying linked list structure facilitates sequential traversal, making it easier to persist in-memory data to disk.

Core Struct

The complete implementation of the Skip List is available at https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go .

A Skip List consists of a base linked list and multiple levels of indices built on top of it. For large datasets, the index layers significantly shorten the search path.

In our implementation, the core structure of the Skip List is defined as follows:

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

maxLevel: The maximum number of levels in the Skip List (the base linked list has one level).
level: The current number of levels in the Skip List.
p: The probability of a node being promoted to a higher level. For example, if p = 0.5, a linked list with 10 nodes at the base level will have approximately 5 nodes in the next level of indices.
rand: A random number generator used to compare against p.
size: The number of bytes occupied by the stored key-value pairs in the Skip List, used to determine if the Memtable exceeds its size threshold.
head: The head node, which holds references to the first node in each level.

The structure of the elements stored in the Skip List is defined as follows:

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

types.Entry represents a key-value pair in the storage engine, including the key, value, and a tombstone flag for deletion.
next: Contains pointers to the next element at each level.

This structure may seem abstract, so let's illustrate it with an example:

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

In this three-level Skip List, the next pointers of the head node reference the first node at each level. Elements 3 and 6 store the next element for each of their levels.

For example, if we want to find the next node of element 19 at Level 2, we use e19.next[2-1].

Set

func (s *SkipList) Set(entry types.Entry)

The LSM-Tree uses tombstones to perform deletions, so we don’t need a Delete method in the skip list implementation. To delete an element, simply set the Tombstone of the entry to true. Thus, the Set method handles inserting new key-value pairs, updating existing ones, and deleting elements.

Let’s explore the implementation of the Set method. By traversing the nodes in each level from the highest, the last element smaller than the key to be set is saved in the update slice.

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

At the end of this traversal, curr points to the last element smaller than the key to be set in the bottom-level linked list. So, we only need to check if the next element of curr equals the key we want to set. If it matches, the element has already been inserted; we update the existing element and return.

// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

If the element is not found, it is inserted as a new element. Using randomLevel, we calculate the index level of this element. If it exceeds the current number of levels in the skip list, we add the head node to the update slice and update s.level to the new level count.

// add entry
level := s.randomLevel()

if level > s.level {
    for i := s.level; i < level; i++ {
        update[i] = s.head
    }
    s.level = level
}

Next, construct the element to be inserted, and the next pointers of each level are updated to complete the insertion.

e := &Element{
    Entry: types.Entry{
        Key:       entry.Key,
        Value:     entry.Value,
        Tombstone: entry.Tombstone,
    },
    next: make([]*Element, level),
}

for i := range level {
    e.next[i] = update[i].next[i]
    update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))

Get

The skip list can perform fast search operations by relying on multiple layers of indexes. The nested for loops in the implementation represent the index-based search operation. If the corresponding element is eventually found in the bottom-level linked list, it will be returned.

func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
    curr := s.head

    for i := s.maxLevel - 1; i >= 0; i-- {
        for curr.next[i] != nil && curr.next[i].Key < key {
            curr = curr.next[i]
        }
    }

    curr = curr.next[0]

    if curr != nil && curr.Key == key {
        return types.Entry{
            Key:       curr.Key,
            Value:     curr.Value,
            Tombstone: curr.Tombstone,
        }, true
    }
    return types.Entry{}, false
}

All

One reason we chose the skip list is its convenient sequential traversal, which is made possible by simply traversing the bottom-level linked list.

func (s *SkipList) All() []types.Entry {
    var all []types.Entry

    for curr := s.head.next[0]; curr != nil; curr = curr.next[0] {
        all = append(all, types.Entry{
            Key:       curr.Key,
            Value:     curr.Value,
            Tombstone: curr.Tombstone,
        })
    }

    return all
}

WAL

The complete implementation of WAL can be found at https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go.

As mentioned earlier, the purpose of WAL (Write-Ahead Logging) is to prevent data loss in the Memtable caused by database crashes. Therefore, WAL needs to record operations on the Memtable and recover the Memtable from the WAL file when the database restarts.

Core Struct

The core structure of WAL is as follows, where fd stores the file descriptor of the WAL file:

type WAL struct {
    mu      sync.Mutex
    logger  logger.Logger
    fd      *os.File
    dir     string
    path    string
    version string
}

Write

Since we need to record operations on the Memtable, this essentially involves writing each operation (Set, Delete) as an Entry into the WAL. The definition of the Write method is as follows:

func (w *WAL) Write(entries ...types.Entry) error

When writing these entries to the file, we need to standardize the WAL file format. The format we use here is length + data. First, we serialize the Entry, then calculate the length of the serialized data, and finally write the length and serialized data sequentially into the WAL file.

The core code is as follows:

data, err := utils.TMarshal(&entry)
if err != nil {
    return err
}

// data length
n := int64(len(data))
err = binary.Write(buf, binary.LittleEndian, n)
if err != nil {
    return err
}
// data body
err = binary.Write(buf, binary.LittleEndian, data)
if err != nil {
    return err
}

Read

Since we use the WAL file format length + data, during reading, we first read 8 bytes (int64) to obtain the length of the data, and then read the data based on this length and deserialize it to retrieve the Entry.

The core code is as follows:

var entries []types.Entry
reader := bytes.NewReader(buf.Bytes())
for reader.Len() > 0 {
    // data length
    var n int64
    if err = binary.Read(reader, binary.LittleEndian, &n); err != nil {
        return nil, err
    }

    // data body
    data := make([]byte, n)
    if err = binary.Read(reader, binary.LittleEndian, &data); err != nil {
        return nil, err
    }

    var entry types.Entry
    if err = utils.TUnmarshal(data, &entry); err != nil {
        return nil, err
    }
    entries = append(entries, entry)
}

Memtable

The complete implementation of Memtable can be found at https://github.com/B1NARY-GR0UP/originium/blob/main/memtable.go.

The Memtable is responsible for writing client operations into the skip list and recording them in the WAL. It can also recover data from the WAL when the database starts.

Core Struct

The core structure of the Memtable is as follows, which includes two main components skiplist and wal:

type memtable struct {
    mu       sync.RWMutex
    logger   logger.Logger
    skiplist *skiplist.SkipList
    wal      *wal.WAL
    dir      string
    readOnly bool
}

Set

When performing a Set operation, both the skip list and the WAL need to be updated simultaneously.

func (mt *memtable) set(entry types.Entry) {
    mt.mu.Lock()
    defer mt.mu.Unlock()

    mt.skiplist.Set(entry)
    if err := mt.wal.Write(entry); err != nil {
        mt.logger.Panicf("write wal failed: %v", err)
    }
    mt.logger.Infof("memtable set [key: %v] [value: %v] [tombstone: %v]", entry.Key, string(entry.Value), entry.Tombstone)
}

Get

To retrieve a value, simply return the result of the skip list's Get operation.

func (mt *memtable) get(key types.Key) (types.Entry, bool) {
    mt.mu.RLock()
    defer mt.mu.RUnlock()

    return mt.skiplist.Get(key)
}

Recover

Recovering the Memtable from the WAL file involves first reading the WAL file, then sequentially applying the Entry records from the WAL file to the Memtable, and finally deleting the recovered WAL file.

Retrieve the list of WAL files:

files, err := os.ReadDir(mt.dir)
if err != nil {
    mt.logger.Panicf("read dir %v failed: %v", mt.dir, err)
}

var walFiles []string
for _, file := range files {
    if !file.IsDir() && path.Ext(file.Name()) == ".log" && wal.CompareVersion(wal.ParseVersion(file.Name()), mt.wal.Version()) < 0 {
        walFiles = append(walFiles, path.Join(mt.dir, file.Name()))
    }
}

Read the WAL and recover the Memtable:

for _, file := range walFiles {
    l, err := wal.Open(file)
    if err != nil {
        mt.logger.Panicf("open wal %v failed: %v", file, err)
    }
    entries, err := l.Read()
    if err != nil {
        mt.logger.Panicf("read wal %v failed: %v", file, err)
    }
    for _, entry := range entries {
        mt.skiplist.Set(entry)
        if err = mt.wal.Write(entry); err != nil {
            mt.logger.Panicf("write wal failed: %v", err)
        }
    }
    if err = l.Delete(); err != nil {
        mt.logger.Panicf("delete wal %v failed: %v", file, err)
    }
}

SSTable

LevelDB SSTable

In the previous introduction, we only mentioned that "SSTable (Sorted String Table) is a data storage format that maintains a series of ordered key-value pairs." Here, we will provide a more detailed explanation of the structure of SSTable.

In LevelDB, an SSTable consists of multiple blocks with different purposes. A schematic diagram is shown below:

Data Block: Stores a sequence of ordered key-value pairs.
Meta Block: Includes two types: filter and stats. The filter type stores data for Bloom filters, while the stats type stores statistical information about the Data Blocks.
MetaIndex Block: Stores index information for the Meta Blocks.
Index Block: Stores index information for the Data Blocks.
Footer: Fixed in length, it stores the index information of the MetaIndex Block and Index Block, as well as a magic number.

The index information is essentially a pointer structure called a BlockHandle, which includes two attributes: offset and size, used to locate the corresponding Block.

Our SSTable

In our implementation of SSTable, we have simplified the LevelDB SSTable structure. A schematic diagram is shown below:

Data Block: Stores a sequence of ordered key-value pairs.
Meta Block: Stores some metadata for the SSTable.
Index Block: Stores index information for the Data Blocks.
Footer: Fixed in length, it stores the index information of the Meta Block and Index Block.

The complete implementation of SSTable can be found at https://github.com/B1NARY-GR0UP/originium/tree/main/sstable.

Data Block

The structure of the Data Block is defined as follows, storing an ordered sequence of entries.

// Data Block
type Data struct {
    Entries []types.Entry
}

We implemented three primary methods for the Data Block:

Encode: Encodes the Data Block into binary data.

func (d *Data) Encode() ([]byte, error)

We use prefix compression to encode the key-value sequence. In the buffer, we sequentially write the length of the common prefix, the length of the suffix, the suffix itself, the length of the value, the value, and the "tombstone" marker.

var prevKey string
for _, entry := range d.Entries {
    lcp := utils.LCP(entry.Key, prevKey)
    suffix := entry.Key[lcp:]

    // lcp
    if err := binary.Write(buf, binary.LittleEndian, uint16(lcp)); err != nil {
        return nil, err
    }

    // suffix length
    if err := binary.Write(buf, binary.LittleEndian, uint16(len(suffix))); err != nil {
        return nil, err
    }
    // suffix
    if err := binary.Write(buf, binary.LittleEndian, []byte(suffix)); err != nil {
        return nil, err
    }

    // value length
    if err := binary.Write(buf, binary.LittleEndian, uint16(len(entry.Value))); err != nil {
        return nil, err
    }
    // value
    if err := binary.Write(buf, binary.LittleEndian, entry.Value); err != nil {
        return nil, err
    }

    // tombstone
    tombstone := uint8(0)
    if entry.Tombstone {
        tombstone = 1
    }
    if err := binary.Write(buf, binary.LittleEndian, tombstone); err != nil {
        return nil, err
    }

    prevKey = entry.Key
}

Finally, we compress the data using s2.

S2 is a high-performance extension of the Snappy compression algorithm.

// s2 compress
if err := utils.Compress(buf, compressed); err != nil {
    return nil, err
}
return compressed.Bytes(), nil

Decode: Decodes binary data into a Data Block.

func (d *Data) Decode(data []byte) error

During decoding, the process is simply reversed. The full key-value pair is reconstructed using the prefix and suffix.

reader := bytes.NewReader(buf.Bytes())
var prevKey string
for reader.Len() > 0 {
    // lcp
    var lcp uint16
    if err := binary.Read(reader, binary.LittleEndian, &lcp); err != nil {
        return err
    }

    // suffix length
    var suffixLen uint16
    if err := binary.Read(reader, binary.LittleEndian, &suffixLen); err != nil {
        return err
    }
    // suffix
    suffix := make([]byte, suffixLen)
    if err := binary.Read(reader, binary.LittleEndian, &suffix); err != nil {
        return err
    }

    // value length
    var valueLen uint16
    if err := binary.Read(reader, binary.LittleEndian, &valueLen); err != nil {
        return err
    }
    // value
    value := make([]byte, valueLen)
    if err := binary.Read(reader, binary.LittleEndian, &value); err != nil {
        return err
    }

    var tombstone uint8
    if err := binary.Read(reader, binary.LittleEndian, &tombstone); err != nil {
        return err
    }

    key := prevKey[:lcp] + string(suffix)
    d.Entries = append(d.Entries, types.Entry{
        Key:       key,
        Value:     value,
        Tombstone: tombstone == 1,
    })

    prevKey = key
}

Search: Locates key-value pairs using binary search.

func (d *Data) Search(key types.Key) (types.Entry, bool) {
    low, high := 0, len(d.Entries)-1
    for low <= high {
        mid := low + ((high - low) >> 1)
        if d.Entries[mid].Key < key {
            low = mid + 1
        } else if d.Entries[mid].Key > key {
            high = mid - 1
        } else {
            return d.Entries[mid], true
        }
    }
    return types.Entry{}, false
}

Index Block

The structure of the Index Block is defined as follows. It stores the first and last key of each Data Block, along with the BlockHandle of the corresponding Data Block.

// Index Block
type Index struct {
    // BlockHandle of all data blocks of this sstable
    DataBlock BlockHandle
    Entries   []IndexEntry
}

// IndexEntry include index of a sstable data block
type IndexEntry struct {
    // StartKey of each Data block
    StartKey string
    // EndKey of each Data block
    EndKey string
    // offset and length of each data block
    DataHandle BlockHandle
}

type BlockHandle struct {
    Offset uint64
    Length uint64
}

Similarly, the Index Block implements three primary methods: Encode, Decode, and Search. The implementation ideas for the Encode and Decode methods are essentially the same, so we will focus on the Search method.

The Search method of the Data Block is designed to locate a specific key-value pair within the ordered key-value sequence stored in a single Data Block. In contrast, the Search method of the Index Block is used to locate the Data Block containing the given key within the entire SSTable.

// Search data block included the key
func (i *Index) Search(key types.Key) (BlockHandle, bool) {
    n := len(i.Entries)
    if n == 0 {
        return BlockHandle{}, false
    }

    // check if the key is beyond this sstable
    if key > i.Entries[n-1].EndKey {
        return BlockHandle{}, false
    }

    low, high := 0, n-1
    for low <= high {
        mid := low + ((high - low) >> 1)
        if i.Entries[mid].StartKey > key {
            high = mid - 1
        } else {
            if mid == n-1 || i.Entries[mid+1].StartKey > key {
                return i.Entries[mid].DataHandle, true
            }
            low = mid + 1
        }
    }
    return BlockHandle{}, false
}

Meta Block And Footer

type Meta struct {
    CreatedUnix int64
    Level       uint64
}

type Footer struct {
    MetaBlock  BlockHandle
    IndexBlock BlockHandle
    Magic      uint64
}

The implementations of these two Blocks are quite straightforward, with both requiring only the Encode and Decode methods.

Build

After introducing all the Blocks in our SSTable, constructing an SSTable simply involves building each Block step by step based on the key-value pairs. Finally, the in-memory index and the encoded SSTable are returned.

func Build(entries []types.Entry, dataBlockSize, level int) (Index, []byte)

K-Way Merge

The complete implementation of K-Way Merge is available at https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway.

In the conceptual section, we illustrate the process of compressing and merging multiple SSTables through diagrams. This process is accomplished using the k-way merge algorithm.

The k-way merge algorithm is a method to merge k sorted sequences into a single sorted sequence, with a time complexity of O(knlogk).

One implementation of this algorithm uses a min-heap as an auxiliary structure:

Insert the first element of each sequence into the heap.
Pop the smallest value from the heap and add it to the result set. If the popped element's sequence still has more elements, insert the next element from that sequence into the heap.
Repeat this process until all elements from all sequences are merged.

Heap

The standard library provides a heap implementation in container/heap. By implementing the heap.Interface, we can build a min-heap.

First, define the basic structure of the min-heap. A slice is used to store the elements. Each element includes not only an Entry but also an LI to indicate which sorted sequence this element originates from.

type Element struct {
    types.Entry
    // list index
    LI int
}

// Heap min heap
type Heap []Element

Implement the sort.Interface methods to sort elements in the heap. Special attention is needed for the Less method: by comparing the LI of the elements, we ensure that when elements have the same key, those from earlier sequences are ordered first. This facilitates deduplication when merging elements into the result set. This requirement also means that the sorted sequences should be arranged in order from oldest to newest when using the k-way merge algorithm.

func (h *Heap) Len() int {
    return len(*h)
}

func (h *Heap) Less(i, j int) bool {
    return (*h)[i].Key < (*h)[j].Key && (*h)[i].LI == (*h)[j].LI || (*h)[i].Key == (*h)[j].Key && (*h)[i].LI < (*h)[j].LI
}

func (h *Heap) Swap(i, j int) {
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

Finally, implement the Push and Pop methods. Push appends an element to the end of the slice, while Pop removes the last element from the slice.

func (h *Heap) Push(x any) {
    *h = append(*h, x.(Element))
}

// Pop the minimum element in heap
// 1. move the minimum element to the end of slice
// 2. pop it (what this method does)
// 3. heapify
func (h *Heap) Pop() any {
    curr := *h
    n := len(curr)
    e := curr[n-1]
    *h = curr[0 : n-1]
    return e
}

Merge

The function definition of the Merge method:

func Merge(lists ...[]types.Entry) []types.Entry

Follows the k-way merge algorithm process.

First, insert the first element of each sorted sequence into the min-heap.

h := &Heap{}
heap.Init(h)

// push first element of each list
for i, list := range lists {
    if len(list) > 0 {
        heap.Push(h, Element{
            Entry: list[0],
            LI:    i,
        })
        lists[i] = list[1:]
    }
}

Iteratively pop an element from the min-heap and add it to the result queue. If the popped element’s sequence still has more elements, insert the next element from that sequence into the heap. Here, a map is used instead of a result sequence. The map automatically handles deduplication, with newer keys always overwriting older ones.

latest := make(map[string]types.Entry)

for h.Len() > 0 {
    // pop minimum element
    e := heap.Pop(h).(Element)
    latest[e.Key] = e.Entry
    // push next element
    if len(lists[e.LI]) > 0 {
        heap.Push(h, Element{
            Entry: lists[e.LI][0],
            LI:    e.LI,
        })
        lists[e.LI] = lists[e.LI][1:]
    }
}

Finally, traverse the map to add elements to the result queue, removing any key-value pairs marked as "tombstones." Since the map is unordered, the result queue needs to be sorted before being returned.

var merged []types.Entry

for _, entry := range latest {
    if entry.Tombstone {
        continue
    }
    merged = append(merged, entry)
}

slices.SortFunc(merged, func(a, b types.Entry) int {
    return cmp.Compare(a.Key, b.Key)
})

return merged

Bloom Filter

The complete implementation of the Bloom Filter can be found at https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/filter/filter.go.

A Bloom Filter is a data structure that efficiently checks whether an element is a member of a set.

It uses a bit array and multiple hash functions.
When adding an element, the element is hashed using multiple hash functions, which map it to different positions in the bit array, setting those positions to 1.
During a query, if all positions mapped by the hash functions are 1, the element might exist. If any position is 0, the element definitely does not exist.

The time complexity for both insertion and query operations is O(k), where k is the number of hash functions. False positives may occur (the Bloom Filter predicts that an element is in the set, but it is not), but false negatives cannot occur (the Bloom Filter predicts that an element is not in the set, but it actually is).

True Positive (TP): The system predicts an event as "positive," and it is indeed positive.
False Positive (FP): The system predicts an event as "positive," but it is actually negative.
True Negative (TN): The system predicts an event as "negative," and it is indeed negative.
False Negative (FN): The system predicts an event as "negative," but it is actually positive.

Core Struct

The core structure of a Bloom Filter includes the bit array (which can be optimized to use uint8) and multiple hash functions.

type Filter struct {
    bitset  []bool
    hashFns []hash.Hash32
}

New

The method to create a Bloom Filter instance accepts two parameters: n (the expected number of elements) and p (the desired false positive rate).

First, the parameters are validated. Then, the size of the bit array (m) and the number of hash functions (k) are calculated using specific formulas. Finally, the bit array and hash functions are initialized based on m and k.

// New creates a new BloomFilter with the given size and number of hash functions.
// n: expected nums of elements
// p: expected rate of false errors
func New(n int, p float64) *Filter {
    if n <= 0 || (p <= 0 || p >= 1) {
        panic("invalid parameters")
    }

    // size of bitset
    // m = -(n * ln(p)) / (ln(2)^2)
    m := int(math.Ceil(-float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))
    // nums of hash functions used
    // k = (m/n) * ln(2)
    k := int(math.Round((float64(m) / float64(n)) * math.Log(2)))

    hashFns := make([]hash.Hash32, k)
    for i := range k {
        hashFns[i] = murmur3.New32WithSeed(uint32(i))
    }

    return &Filter{
        bitset:  make([]bool, m),
        hashFns: hashFns,
    }
}

Add

When adding an element, all hash functions are used to compute hash values for the key. These values are then mapped to indices in the bit array, and the corresponding positions are set to true.

// Add adds an element to the BloomFilter.
func (f *Filter) Add(key string) {
    for _, fn := range f.hashFns {
        _, _ = fn.Write([]byte(key))
        index := int(fn.Sum32()) % len(f.bitset)
        f.bitset[index] = true
        fn.Reset()
    }
}

Contains

To check if a key is in the set, the hash functions compute hash values and map them to indices in the bit array. If any of these positions is not true, the element is not in the set, and false is returned.

// Contains checks if an element is in the BloomFilter.
func (f *Filter) Contains(key string) bool {
    for _, fn := range f.hashFns {
        _, _ = fn.Write([]byte(key))
        index := int(fn.Sum32()) % len(f.bitset)
        fn.Reset()
        if !f.bitset[index] {
            return false
        }
    }
    return true
}

Leveled Compaction

The complete implementation of Leveled Compaction can be found at https://github.com/B1NARY-GR0UP/originium/blob/main/level.go.

After implementing components like K-Way Merge and Bloom Filter, we can complete the final part of our implementation, the most crucial SSTable compaction process in the LSM-Tree storage engine. This implementation follows the Leveled Compaction Strategy described in the "Data Compaction" section.

In the Leveled Compaction Strategy, SSTables are organized into multiple levels (Level 0 - Level N). We need a structure to store this information and manage SSTables across different levels.

Thus, we implemented a structure called levelManager. We use a []*list.List to store SSTable information for each level, where the index of the slice corresponds to the level. Each element in the slice is a list.List, a doubly-linked list that holds information about all SSTables in a specific level.

type levelManager struct {
    mu            sync.Mutex
    dir           string
    l0TargetNum   int
    ratio         int
    dataBlockSize int
    // list.Element: tableHandle
    levels []*list.List
    logger logger.Logger
}

type tableHandle struct {
    // list index of table within a level
    levelIdx int
    // bloom filter
    filter filter.Filter
    // index of data blocks in this sstable
    dataBlockIndex sstable.Index
}

compactLN

The compactLN method is responsible for Level N to Level N+1 (N > 0) compaction. It selects the oldest SSTable from LN and all SSTables from LN+1 that have overlapping key ranges with this SSTable.

lnTable := lm.levels[n].Front()
start, end := boundary(lnTable)

// overlap sstables in LN+1
ln1Tables := lm.overlapLN(n+1, start, end)

The selected SSTables are processed in order from oldest to newest. Key-value pairs from their data blocks are added to a two-dimensional slice and then merged using the K-Way Merge algorithm.

// old -> new (append LN+1 first)
var dataBlockList [][]types.Entry
// LN+1 data block entries
for _, table := range ln1Tables {
    th := table.Value.(tableHandle)
    dataBlockLN1 := lm.fetch(n+1, th.levelIdx, th.dataBlockIndex.DataBlock)
    dataBlockList = append(dataBlockList, dataBlockLN1.Entries)
}
// LN data block entries
dataBlockLN := lm.fetch(n, lnTable.Value.(tableHandle).levelIdx, lnTable.Value.(tableHandle).dataBlockIndex.DataBlock)
dataBlockList = append(dataBlockList, dataBlockLN.Entries)

// merge sstables
mergedEntries := kway.Merge(dataBlockList...)

With the merged key-value pairs, we construct a new Bloom Filter and SSTable. The relevant information about the new SSTable is appended to the end of Level N+1.

// build new bloom filter
bf := filter.Build(mergedEntries)
// build new sstable
dataBlockIndex, tableBytes := sstable.Build(mergedEntries, lm.dataBlockSize, n+1)

// table handle
th := tableHandle{
    levelIdx:       lm.maxLevelIdx(n+1) + 1,
    filter:         *bf,
    dataBlockIndex: dataBlockIndex,
}

// update index
// add new index to LN+1
lm.levels[n+1].PushBack(th)

Finally, the old SSTables are deleted, and the newly constructed SSTable is written to disk.

// remove old sstable index from LN
lm.levels[n].Remove(lnTable)
// remove old sstable index from LN+1
for _, e := range ln1Tables {
    lm.levels[n+1].Remove(e)
}

// delete old sstables from LN
if err := os.Remove(lm.fileName(n, lnTable.Value.(tableHandle).levelIdx)); err != nil {
    lm.logger.Panicf("failed to delete old sstable: %v", err)
}
// delete old sstables from LN+1
for _, e := range ln1Tables {
    if err := os.Remove(lm.fileName(n+1, e.Value.(tableHandle).levelIdx)); err != nil {
        lm.logger.Panicf("failed to delete old sstable: %v", err)
    }
}

// write new sstable
fd, err := os.OpenFile(lm.fileName(n+1, th.levelIdx), os.O_CREATE|os.O_RDWR|os.O_TRUNC, 0600)
if err != nil {
    lm.logger.Panicf("failed to open sstable: %v", err)
}
defer func() {
    if err = fd.Close(); err != nil {
        lm.logger.Errorf("failed to close file: %v", err)
    }
}()

_, err = fd.Write(tableBytes)

The compactL0 method handles Level 0 to Level 1 compaction. Unlike compactLN, it selects not only one SSTable from L0 but also all overlapping SSTables in L0. The rest of the process is identical to compactLN.

search

The search method locates the corresponding key-value pairs across all SSTables. It starts from L0 and iterates through each level up to LN. By leveraging the Bloom Filter and the ordered structure of SSTables, SSTables that do not contain the desired key-value pairs can be skipped efficiently.

func (lm *levelManager) search(key types.Key) (types.Entry, bool) {
    lm.mu.Lock()
    defer lm.mu.Unlock()

    if len(lm.levels) == 0 {
        return types.Entry{}, false
    }

    for level, tables := range lm.levels {
        for e := tables.Front(); e != nil; e = e.Next() {
            th := e.Value.(tableHandle)

            // search bloom filter
            if !th.filter.Contains(key) {
                // not in this sstable, search next one
                continue
            }

            // determine which data block the key is in
            dataBlockHandle, ok := th.dataBlockIndex.Search(key)
            if !ok {
                // not in this sstable, search next one
                continue
            }

            // in this sstable, search according to data block
            entry, ok := lm.fetchAndSearch(key, level, th.levelIdx, dataBlockHandle)
            if ok {
                return entry, true
            }
        }
    }

    return types.Entry{}, false
}

DB

With this, we have implemented all core components of the LSM-Tree-based storage engine. By assembling these components as described in the LSM-Tree introduction, we can finalize the database interface.

Complete code: https://github.com/B1NARY-GR0UP/originium/blob/main/db.go
Documentation: https://github.com/B1NARY-GR0UP/originium?tab=readme-ov-file#usage

Summary

We began by understanding LSM-Tree, familiarizing ourselves with its core components and the process of handling client requests. Ultimately, we built our own LSM-Tree storage engine from scratch.

Of course, this implementation is just a prototype. A production-grade storage engine requires consideration of many more details. ORIGINIUM will continue to receive optimizations and improvements in the future. Hope this article and ORIGINIUM help deepen your understanding of LSM-Tree.

That concludes everything covered in this article. If there are any errors or questions, feel free to reach out via private message or leave a comment. Thank you!

Reference

Understanding etcd's Raft Implementation: A Deep Dive into Raft Log

Lorain — Mon, 11 Nov 2024 15:43:11 +0000

Introduction

This article will introduce and analyze the design and implementation of the Raft Log module in etcd's Raft, starting from the log in the Raft consensus algorithm. The goal is to help readers better understand the implementation of etcd's Raft and provide a possible approach for implementing similar scenarios.

Raft Log Overview

The Raft consensus algorithm is essentially a replicated state machine, with the goal of replicating a series of logs in the same way across a server cluster. These logs enable the servers in the cluster to reach a consistent state.

In this context, the logs refer to the Raft Log. Each node in the cluster has its own Raft Log, which is composed of a series of log entries. A log entry typically contains three fields:

Index: The index of the log entry
Term: The leader's term when the log entry was created
Data: The data contained in the log entry, which could be specific commands, etc.

It's important to note that the index of the Raft Log starts at 1, and only the leader node can create and replicate the Raft Log to follower nodes.

When a log entry is persistently stored on the majority of nodes in the cluster (e.g., 2/3, 3/5, 4/7), it is considered committed.

When a log entry is applied to the state machine, it is considered applied.

etcd's raft implementation overview

etcd raft is a Raft algorithm library written in Go, widely used in systems like etcd, Kubernetes, CockroachDB, and others.

The primary characteristic of etcd raft is that it only implements the core part of the Raft algorithm. Users must implement network transmission, disk storage, and other components involved in the Raft process themselves (although etcd provides default implementations).

Interacting with the etcd raft library is somewhat straightforward: it tells you which data needs to be persisted and which messages need to be sent to other nodes. Your responsibility is to handle the storage and network transmission processes and inform it accordingly. It doesn’t concern itself with the details of how you implement these operations; it simply processes the data you submit and, based on the Raft algorithm, tells you the next steps.

In the implementation of etcd raft’s code, this interaction model is seamlessly combined with Go's unique channel feature, making the etcd raft library truly distinctive.

How to Implement Raft Log

log and log_unstable

In etcd raft, the main implementation of Raft Log is located in the log.go and log_unstable.go files, with the primary structures being raftLog and unstable. The unstable structure is also a field within raftLog.

raftLog is responsible for the main logic of the Raft Log. It can access the node’s log storage state through the Storage interface provided to the user.
unstable, as its name suggests, contains log entries that haven’t been persisted yet, meaning uncommitted logs.

etcd raft manages the logs within the algorithm by coordinating raftLog and unstable.

Core Fields of raftLog and unstable

To simplify the discussion, this article will focus only on the processing logic of log entries, without addressing snapshot handling in etcd raft.

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

Core fields of raftLog:

storage: A storage interface implemented by the user, used to retrieve log entries that have already been persisted.
unstable: Stores unpersisted logs. For example, when the Leader receives a request from a client, it creates a log entry with its Term and appends it to the unstable logs.
committed: Known as commitIndex in the Raft paper, it represents the index of the last known committed log entry.
applying: The highest index of a log entry that is currently being applied.
applied: Known as lastApplied in the Raft paper, it is the highest index of a log entry that has been applied to the state machine.

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

Core fields of unstable:

entries: The unpersisted log entries, stored in memory as a slice.
offset: Used to map log entries in entries to the Raft Log, where entries[i] = Raft Log[i+offset].
offsetInProgress: Indicates entries that are currently being persisted. The entries in progress are represented by entries[:offsetInProgress-offset].

The core fields in raftLog are straightforward and can easily be related to the implementation in the Raft paper. However, the fields in unstable might seem more abstract. The following example aims to help clarify these concepts.

Assume we already have 5 log entries persisted in our Raft Log. Now, we have 3 log entries stored in unstable, and these 3 log entries are currently being persisted. The situation is as shown below:

offset=6 indicates that the log entries at positions 0, 1, and 2 in unstable.entries correspond to positions 6 (0+6), 7 (1+6), and 8 (2+6) in the actual Raft Log. With offsetInProgress=9, we know that unstable.entries[:9-6], which includes the three log entries at positions 0, 1, and 2, are all being persisted.

The reason offset and offsetInProgress are used in unstable is that unstable does not store all Raft Log entries.

When to Interact

Since we are focusing only on the Raft Log processing logic, "when to interact" here refers to when etcd raft will pass the log entries that need to be persisted by the user.

User Side

etcd raft interacts with the user primarily through methods in the Node interface. The Ready method returns a channel that allows the user to receive data or instructions from etcd raft.

type Node interface {
    ...
    Ready() <-chan Ready
    ...
}

The Ready struct received from this channel contains log entries that need processing, messages that should be sent to other nodes, the current state of the node, and more.

For our discussion on Raft Log, we only need to focus on the Entries and CommittedEntries fields:

Entries: Log entries that need to be persisted. Once these entries are persisted, they can be retrieved using the Storage interface.
CommittedEntries: Log entries that need to be applied to the state machine.

type Ready struct {
    *SoftState
    pb.HardState
    ReadStates []ReadState
    Entries []pb.Entry // persist it
    Snapshot pb.Snapshot
    CommittedEntries []pb.Entry // commit it
    Messages []pb.Message
    MustSync bool
}

After processing the logs, messages, and other data passed through Ready, we can call the Advance method in the Node interface to inform etcd raft that we have completed its instructions, allowing it to receive and process the next Ready.

etcd raft offers an AsyncStorageWrites option, which can enhance node performance to some extent. However, we are not considering this option here.

etcd raft Side

On the user side, the focus is on handling the data in the received Ready struct. On the etcd raft side, the focus is on determining when to pass a Ready struct to the user and what actions to take afterward.

I have summarized the main methods involved in this process in the following diagram, which shows the general sequence of method calls (note that this only represents the approximate order of calls):

You can see that the entire process is a loop. Here, we'll outline the general function of these methods, and in the subsequent write-flow analysis, we’ll delve into how these methods operate on the core fields of raftLog and unstable.

HasReady: As the name suggests, it checks whether there is a Ready struct that needs to be passed to the user. For example, if there are unpersisted log entries in unstable that are not currently in the process of being persisted, HasReady will return true.
readyWithoutAccept: Called after HasReady returns true, this method creates the Ready struct to be returned to the user, including the log entries that need to be persisted and those marked as committed.
acceptReady: Called after etcd raft passes the Ready struct created by readyWithoutAccept to the user. It marks the log entries returned in Ready as in the process of being persisted and applied, and creates a “callback” to be invoked when the user calls Node.Advance, marking the log entries as persisted and applied.
Advance: Executes the “callback” created in acceptReady after the user calls Node.Advance.

How to Define Committed and Applied

There are two important points to consider here:

1. Persisted ≠ Committed

As defined initially, a log entry is considered committed only when it has been persisted by the majority of nodes in the Raft cluster. So even if we persist the Entries returned by etcd raft through Ready, these entries cannot yet be marked as committed.

However, when we call the Advance method to inform etcd raft that we have completed the persistence step, etcd raft will evaluate the persistence status across other nodes in the cluster and mark some log entries as committed. These entries are then provided to us through the CommittedEntries field of the Ready struct so we can apply them to the state machine.

Thus, when using etcd raft, the timing for marking entries as committed is managed internally, and users only need to fulfill the persistence prerequisites.

Internally, commitment is achieved by calling the raftLog.commitTo method, which updates raftLog.committed, corresponding to the commitIndex in the Raft paper.

2. Committed ≠ Applied

After the raftLog.commitTo method is called within etcd raft, the log entries up to the raft.committed index are considered committed. However, entries with indices in the range lastApplied < index <= committedIndex have not yet been applied to the state machine. etcd raft will return these committed but un-applied entries in the CommittedEntries field of Ready, allowing us to apply them to the state machine. Once we call Advance, etcd raft will mark these entries as applied.

The timing for marking entries as applied is also handled internally in etcd raft; users only need to apply the committed entries from Ready to the state machine.

Another subtle point is that, in Raft, only the Leader can commit entries, but all nodes can apply them.

Processing Flow of a Write Request

Here, we’ll connect all the previously discussed concepts by analyzing the flow of etcd raft as it handles a write request.

Initial State

To discuss a more general scenario, we’ll start with a Raft Log that has already committed and applied three log entries.

In the illustration, green represents raftLog fields and the stored log entries in Storage, while red represents unstable fields and the unpersisted log entries stored in entries.

Since we have committed and applied three log entries, both committed and applied are set to 3. The applying field holds the index of the highest log entry from the previous application, which is also 3 in this case.

At this point, no requests have been initiated, so unstable.entries is empty. The next log index in the Raft Log is 4, making offset 4. Since no logs are currently being persisted, offsetInProgress is also set to 4.

Issue a Request

Now, we initiate a request to append two log entries to the Raft Log.

As shown in the illustration, the appended log entries are stored in unstable.entries. At this stage, no changes are made to the index values recorded in the core fields.

HasReady

Remember the HasReady method? HasReady checks if there are unpersisted log entries and, if so, returns true.

The logic for determining the presence of unpersisted log entries is based on whether the length of unstable.entries[offsetInProgress-offset:] is greater than 0. Clearly, in our case:

len(unstable.entries[4 - 4:]) == 2

indicating that there are two unpersisted log entries, so HasReady returns true.

readyWithoutAccept

The purpose of readyWithoutAccept is to create the Ready struct to be returned to the user. Since we have two unpersisted log entries, readyWithoutAccept will include these two log entries in the Entries field of the returned Ready.

acceptReady

acceptReady is called after the Ready struct is passed to the user.

acceptReady updates the index of log entries that are in the process of being persisted to 6, meaning that log entries within the range [4, 6) are now marked as being persisted.

Advance

After the user persists the Entries in Ready, they call Node.Advance to notify etcd raft. Then, etcd raft can execute the "callback" created in acceptReady.

This "callback" clears the already persisted log entries in unstable.entries, then sets offset to Storage.LastIndex + 1, which is 6.

Commit Log Entries

We assume that these two log entries have already been persisted by the majority of nodes in the Raft cluster, so we can mark these two log entries as committed.

HasReady

Continuing with our loop, HasReady detects the presence of log entries that are committed but not yet applied, so it returns true.

readyWithoutAccept

readyWithoutAccept returns a Ready containing log entries (4, 5) that are committed but have not been applied to the state machine.

These entries are calculated as low, high := applying+1, committed+1, in a left-open, right-closed interval.

acceptReady

acceptReady then marks the log entries [4, 5] returned in Ready as being applied to the state machine.

Advance

After the user calls Node.Advance, etcd raft executes the "callback" and updates applied to 5, indicating that the log entries at index 5 and earlier have all been applied to the state machine.

Final State

This completes the processing flow for a write request. The final state is as shown below, which can be compared to the initial state.

Summary

We started with an overview of the Raft Log, gaining an understanding of its basic concepts, followed by an initial look at the etcd raft implementation. We then delved deeper into the core modules of Raft Log within etcd raft and considered important questions. Finally, we tied everything together through a complete analysis of a write request flow.

I hope this approach helps you gain a clear understanding of the etcd raft implementation and develop your own insights into the Raft Log.

That concludes this article. If there are any mistakes or questions, feel free to reach out via private message or leave a comment.

BTW, raft-foiver is a simplified version of etcd raft that I implemented, retaining all the core logic of Raft and optimized according to the process in the Raft paper. I’ll release a separate post introducing this library in the future. If you're interested, feel free to Star, Fork, or PR!

Reference

One-Year Summary of Using VIM

Lorain — Mon, 29 Jul 2024 09:39:47 +0000

Introduction

This article is a personal summary of my experience using VIM after one year. It includes the story of how I started with VIM, beginner tips, my frequently used VIM shortcuts, and a share of my ideavim configuration. I hope it will help readers get started with and make better use of VIM.

My Journey with VIM

The first time I encountered VIM was during my Linux studies. Following the tutorial commands, I used VIM to edit a file and initially found this editor to be quite user-unfriendly. The various strange modes and commands made my head spin.

Around this time last year, VIM’s author, Bram Moolenaar, passed away. After reading an article that shared the story of Bram Moolenaar and VIM, I decided to learn this editor created by such a great programmer.

Today, one year later, VIM has become an indispensable part of my daily development: in my browser, for note-taking, and in my IDE.

How to Get Started

Many people mention that VIM has a very steep learning curve, but I didn't encounter too many insurmountable difficulties when I started. Instead, as you gradually begin to use this editor and encounter points that feel "awkward," you can learn more shortcuts and configurations to make VIM fit your personal habits rather than forcing yourself to use methods you're uncomfortable with.

To get started, VIM Tutor was the method I initially used. It is a classic tutorial built into VIM.

If you use VIM, you can open it with the following command:

vimtutor

If you use Neovim, you can open it in Neovim's Normal mode with the following command:

:Tutor

VIM Tutor provides an interactive tutorial that takes about 30 minutes and covers the most commonly used shortcuts and modes in VIM.

Once you are familiar with and remember most of the content in VIM Tutor, I believe you will be able to "survive" in VIM. Next, you can read some blogs introducing VIM usage. These blogs usually include some very useful shortcuts not covered in VIM Tutor and basic tutorials, helping you build your own shortcut library.

Here are some excellent blogs that helped me when I started, which you can refer to:

If you find these blogs insufficiently official and want to learn in a more formal way, I suggest reading the VIM User Manual. It is written by Bram Moolenaar and community contributors and is very comprehensive and detailed. You can open it in VIM or Neovim's Normal mode with the following command:

:help user-manual

Common Shortcuts

This section mainly shares some shortcuts I commonly use in VIM. I hope you find them helpful.

ci": Delete all content inside the quotes and enter Insert mode.

These kinds of shortcuts are very convenient when you need to operate on content within various types of quotes or parentheses. You can also use other operators to build similar shortcuts, such as:

yi(: Copy all content inside the parentheses.
va': Select the single quotes and all content inside them, entering Visual mode.
di<: Delete all content inside the angle brackets.

For easier understanding and memorization, i stands for "inner," meaning to operate on the content inside the quotes or parentheses, and a stands for "around," meaning to operate on the content around the quotes or parentheses.

daw: Delete the word under the cursor.

This type of shortcut is very useful when you need to operate on a word, sentence, or paragraph. Since commands like cw and dw need to be used at the beginning of a word to operate on the whole word, you might have to use shortcuts like b and w to move to the beginning first. The daw command allows you to operate on the entire word as long as the cursor is within the word, making it very convenient. Similar shortcuts include:

caw: Delete a word and the space after it, entering Insert mode.
das: Delete a sentence.
cap: Delete a paragraph and enter Insert mode.

zz: Center the current line in the middle of the screen.
zt: Move the current line to the top of the screen.
zb: Move the current line to the bottom of the screen.

H: Move the cursor to the top line of the screen.
M: Move the cursor to the middle line of the screen.
L: Move the cursor to the bottom line of the screen.

<C-y>: Scroll the content of the current window up one line while keeping the cursor position unchanged.
<C-e>: Scroll the content of the current window down one line while keeping the cursor position unchanged.

<C-w>v: Split the current window vertically.
<C-w>s: Split the current window horizontally.
<C-w>w: Switch between windows.
<C-w>c: Close the current window.
<C-w>h: Move focus to the window on the left.
<C-w>j: Move focus to the window below.
<C-w>k: Move focus to the window above.
<C-w>l: Move focus to the window on the right.

IDEAVIM Configuration

As a JetBrains user, after learning VIM, I configured the ideavim plugin to enjoy the convenience of both JetBrains IDE and VIM in my IDE. Below is a set of ideavim configurations tailored to my personal habits. I hope it can provide you with some reference:

You can also find it here: https://github.com/justlorain/euphonium

" Vim mode toggle
nmap <leader>vim <Action>(VimPluginToggle)

" --- Basic Configuration ---

" leader key
let mapleader = " "

" Move to the previous/next line when pressing h/l at the beginning/end of a line
set whichwrap=b,s,<,>,h,l,[,]

"" visual shifting (builtin-repeat)
vnoremap < <gv
vnoremap > >gv

" Vertical scroll offset
set scrolloff=5

" Search
set incsearch
set nohls
set ic
set smartcase
nnoremap <leader>ss :set invhlsearch<CR>

" Clipboard mapping
set clipboard+=unnamed

" Show line numbers
set number
" Set relative line numbers
set relativenumber

" Don't use Ex mode, use Q for formatting.
map Q gq

" --- Plugin Configuration ---

" Highlight copied text
Plug 'machakann/vim-highlightedyank'
" Commentary plugin
Plug 'tpope/vim-commentary'
" vim-surround
set surround
" easymotion
set easymotion
" nerdtree
set NERDTree
nnoremap <leader>nf :NERDTreeFind<CR>
" quickscope
set quickscope
let g:qs_highlight_on_keys = ['f', 'F', 't', 'T']
" which-key
set which-key
set notimeout

" --- Coding Configuration ---

" Show file structure
let g:WhichKeyDesc_FileStructure = "<leader>fs FileStructure"
nmap <leader>fs <action>(FileStructurePopup)
let g:WhichKeyDesc_FindFile = "<leader>ff FindFile"
nmap <leader>ff <action>(GotoFile)
" Close tab
let g:WhichKeyDesc_CloseCurrentTab = "<leader>xx CloseCurrentTab"
nmap <leader>xx <action>(CloseContent)
let g:WhichKeyDesc_CloseOtherTabs = "<leader>xo CloseOtherTabs"
nmap <leader>xo <action>(CloseAllEditorsButActive)
let g:WhichKeyDesc_CloseAllTabsOnTheLeft = "<leader>x[ CloseAllTabsOnTheLeft"
nmap <leader>x[ <action>(CloseAllToTheLeft)
let g:WhichKeyDesc_CloseAllTabsOnTheRight = "<leader>x] CloseAllTabsOnTheRight"
nmap <leader>x] <action>(CloseAllToTheRight)
" Scroll page
let g:WhichKeyDesc_EditorScrollUp = "<C-k> EditorScrollUp"
nmap <C-k> <action>(EditorScrollUp)
let g:WhichKeyDesc_EditorScrollDown = "<C-j> EditorScrollDown"
nmap <C-j> <action>(EditorScrollDown)
" Go to definition or reference
let g:WhichKeyDesc_GotoDeclaration = "gd GotoDeclaration"
nmap gd <action>(GotoDeclaration)
" Go to usage
let g:WhichKeyDesc_FindUsages = "<leader>gr FindUsages"
nmap <leader>gr <action>(FindUsages)
" Go to superclass
let g:WhichKeyDesc_GotoSuperMethod = "<leader>gs GotoSuperMethod"
nmap <leader>gs <action>(GotoSuperMethod)
" Go to implementation
let g:WhichKeyDesc_GotoImplementation = "<leader>gi GotoImplementation"
nmap <leader>gi <action>(GotoImplementation)
" Jump to method
let g:WhichKeyDesc_MethodUp = "<M-k> MethodUp"
nmap <M-k> <Action>(MethodUp)
let g:WhichKeyDesc_MethodDown = "<M-j> MethodDown"
nmap <M-j> <Action>(MethodDown)
let g:WhichKeyDesc_ExtractMethod = "<leader>em ExtractMethod"
vmap <leader>em <Action>(ExtractMethod)
" Jump tab
let g:WhichKeyDesc_PreviousTab = "<M-h> PreviousTab"
nmap <M-h> <action>(PreviousTab)
let g:WhichKeyDesc_NextTab = "<M-l> NextTab"
nmap <M-l> <action>(NextTab)
" Translation
let g:WhichKeyDesc_EditorTranslate = "<leader>t EditorTranslate"
vmap <leader>t <action>($EditorTranslateAction)
" Cursor back
let g:WhichKeyDesc_Back = "<C-i> Back"
nmap <C-i> <action>(Back)
" Cursor forward
let g:WhichKeyDesc_Forward = "<C-o> Forward"
nmap <C-o> <action>(Forward)
" Open recent project
let g:WhichKeyDesc_OpenRecentProject = "<leader>p OpenRecentProject"
nmap <leader>p <action>($LRU)
" Replace
let g:WhichKeyDesc_ReplaceInFile = "<leader>rif ReplaceInFile"
nmap <leader>rif <action>(Replace)
vmap <leader>rif <action>(Replace)
let g:WhichKeyDesc_ReplaceInProject = "<leader>rip ReplaceInProject"
nmap <leader>rip <action>(ReplaceInPath)
vmap <leader>rip <action>(ReplaceInPath)
" Find
let g:WhichKeyDesc_FindInFile = "<leader>fif FindInFile"
nmap <leader>fif <action>(Find)
vmap <leader>fif <action>(Find)
let g:WhichKeyDesc_FindInProject = "<leader>fip FindInProject"
nmap <leader>fip <action>(FindInPath)
vmap <leader>fip <action>(FindInPath)
" New line
let g:WhichKeyDesc_NewLine = "<M-o> NewLine"
nnoremap <M-o> :normal o<CR>
" Toggle breakpoint
let g:WhichKeyDesc_ToggleLineBreakpoint = "<leader>bb ToggleLineBreakpoint"
nmap <leader>bb <action>(ToggleLineBreakpoint)
" Show expression type
let g:WhichKeyDesc_ExpressionTypeInfo = "<leader>et ExpressionTypeInfo"
nmap <leader>et <action>(ExpressionTypeInfo)
" Show method parameters
let g:WhichKeyDesc_ParameterInfo = "<leader>et ParameterInfo"
nmap <leader>pp <action>(ParameterInfo)
" Recent files
let g:WhichKeyDesc_RecentFiles = "<leader>ee RecentFiles"
nmap <leader>ee <action>(RecentFiles)

sethandler <C-j> a:vim i:ide
sethandler <C-k> a:vim i:ide

Summary

That's all for this article. I hope this personal summary helps you use VIM more effectively.

Once again, thanks to Bram Moolenaar for bringing us such a wonderful software. R.I.P.

If there are any mistakes or issues, feel free to comment or message me privately. Thank you.

Reference

How to Build Your Own Distributed KV Storage System Using the etcd Raft Library (2)

Lorain — Tue, 23 Jul 2024 11:18:14 +0000

This is the second article in the series "How to Build Your Own Distributed KV Storage System Using the etcd raft Library" - raftexample Log Compaction and Snapshot.

Introduction

In the first article, we learned and became familiar with the structure of raftexample and the processing flow of a write request. In this article, we will interpret the log compaction and snapshot handling logic in raftexample.

Log Compaction and Snapshot

The Raft log continuously grows as the cluster operates normally and processes client requests. In practical applications, we need a mechanism to limit the unlimited growth of the log to avoid causing availability issues. Raft uses the snapshot mechanism to compact the log, as shown in the figure below:

After creating a snapshot, all committed entries in the Raft log are included in a snapshot. This snapshot compresses and merges the state of the state machine for the last committed entry and all previous entries and saves the Index and Term of the last entry included in the snapshot for consistency checks during the AppendEntries RPC (log synchronization). To support cluster membership changes, the snapshot should also save the latest cluster configuration (for simplicity, this is not shown in the figure).

The timing of snapshot creation is also a topic worth discussing. A simple strategy is to create a snapshot when the log reaches a configured size threshold (in bytes).

Creating Snapshots

1. In raftexample, the strategy for creating snapshots is to do so when the number of log entries reaches a specified threshold. This strategy is executed by the maybeTriggerSnapshot method, which is called every time data is received from the raft library (Ready).

This method first calculates the number of committed log entries since the last snapshot. If this number has not reached the specified threshold (snapCount), it returns immediately without creating a snapshot.

if rc.appliedIndex - rc.snapshotIndex <= rc.snapCount {
    return
}

Next, it blocks and waits until all the committed log entries received from the raft library that need to be applied (rc.entriesToApply(rd.CommittedEntries)) are applied to the state machine (kvstore) or the server shuts down.

// wait until all committed entries are applied (or server is closed)
if applyDoneC != nil {
    select {
    case <-applyDoneC:
    case <-rc.stopc:
        return
    }
}

Then the actual snapshot creation logic follows:

getSnapshot: Retrieves the JSON serialized data of all key-value pairs stored in the current kvstore state machine;
CreateSnapshot: Creates a snapshot. CreateSnapshot calculates the last included index and last included term based on the committed log index (appliedIndex). The snapshot also includes the latest cluster configuration information (confState) and the state of the state machine (data).

This strictly follows the requirements mentioned in the paper that a snapshot must include all necessary information.

saveSnap: Writes the created snapshot to disk and records the snapshot metadata in the WAL to enable state recovery from the WAL.

log.Printf("start snapshot [applied index: %d | last snapshot index: %d]", rc.appliedIndex, rc.snapshotIndex)
data, err := rc.getSnapshot()
if err != nil {
    log.Panic(err)
}
snap, err := rc.raftStorage.CreateSnapshot(rc.appliedIndex, &rc.confState, data)
if err != nil {
    panic(err)
}
if err := rc.saveSnap(snap); err != nil {
    panic(err)
}

In the implementation of MemoryStorage, since CreateSnapshot does not actually compress the Raft Log, we need to manually call the Compact method to delete all entries before compactIndex. Otherwise, creating snapshots without deleting the Raft Log would render the snapshot creation meaningless. Here, we retain snapshotCatchUpEntriesN log entries while deleting the entries to allow some slow followers to catch up with the leader.

// keep some in memory log entries for slow followers.
compactIndex := uint64(1)
// snapshotCatchUpEntriesN represents the number of log entries retained after a snapshot is triggered.
if rc.appliedIndex > snapshotCatchUpEntriesN {
    compactIndex = rc.appliedIndex - snapshotCatchUpEntriesN
}
if err := rc.raftStorage.Compact(compactIndex); err != nil {
    if err != raft.ErrCompacted {
        panic(err)
    }
} else {
    log.Printf("compacted log at index %d", compactIndex)
}

Finally, update the snapshot progress to the current last committed log entry.

rc.snapshotIndex = rc.appliedIndex

2. In addition to nodes creating snapshots periodically based on their snapshot creation strategy, followers may also receive snapshots from the leader to help with log synchronization in cases such as new nodes joining the cluster or log entries lagging too far behind.

When the Snapshot field of Ready is not empty, persist the snapshot, then apply the snapshot (ApplySnapshot), and notify the kvstore module to load the snapshot by sending a nil signal to commitC.

if !raft.IsEmptySnap(rd.Snapshot) {
    rc.saveSnap(rd.Snapshot)
}
// rd.HardState + rd.Entries = persistent state on all servers
rc.wal.Save(rd.HardState, rd.Entries)
if !raft.IsEmptySnap(rd.Snapshot) {
    rc.raftStorage.ApplySnapshot(rd.Snapshot)
    // Send a signal to load the snapshot. 
    // The kvstore will restore the state machine from the snapshot.
    rc.publishSnapshot(rd.Snapshot)
}

Upon receiving the nil signal, kvstore loads the previously saved snapshot from the disk through saveSnap, and recoverFromSnapshot deserializes the JSON data of all key-value pairs saved in the snapshot to overwrite the state machine's (map[string]string) storage.

for commit := range commitC {
    // signaled by raftNode.publicSnapshot rc.commitC <- nil
    if commit == nil {
        snapshot, err := s.loadSnapshot()
        if err != nil {
            log.Panic(err)
        }
        if snapshot != nil {
            log.Printf("loading snapshot at term %d and index %d", snapshot.Metadata.Term, snapshot.Metadata.Index)
            if err := s.recoverFromSnapshot(snapshot.Data); err != nil {
                log.Panic(err)
            }
        }
        continue
    }
    ...
}

Recovering from Snapshots

Through the maybeTriggerSnapshot method, raftexample creates a snapshot and persists it to disk when the log entries reach a set threshold. Next, let's look at how raftexample uses these snapshots on disk for recovery.

1. During the startup of the raft module, the Raft Log is reconstructed using the replayWAL method.

The loadSnapshot method loads the previously saved snapshot from disk using saveSnap.
openWAL reconstructs the WAL based on the loaded snapshot's Index and Term.
ApplySnapshot, SetHardState, and Append are used to restore MemoryStorage, which is the Raft Log (MemoryStorage is in-memory, so it needs the WAL for recovery).

The HardState and Entries saved in the WAL were persisted after receiving data in the Ready state.

rc.wal.Save(rd.HardState, rd.Entries)

func (rc *raftNode) replayWAL() *wal.WAL {
    log.Printf("replaying WAL of member %d", rc.id)
    snapshot := rc.loadSnapshot()
    w := rc.openWAL(snapshot)
    _, st, ents, err := w.ReadAll()
    if err != nil {
        log.Fatalf("raftexample: failed to read WAL (%v)", err)
    }
    rc.raftStorage = raft.NewMemoryStorage()
    if snapshot != nil {
        rc.raftStorage.ApplySnapshot(*snapshot)
    }
    rc.raftStorage.SetHardState(st)

    // append to storage so raft starts at the right place in log
    rc.raftStorage.Append(ents)

    return w
}

After starting the Raft module, in the serveChannels method of raftexample, which handles interactions with the raft library, we can use the Snapshot method to retrieve the snapshot applied to MemoryStorage in replayWAL and reconstruct the current node's cluster configuration (confState), snapshot index (snapshotIndex), and committed log index (appliedIndex).

snap, err := rc.raftStorage.Snapshot()
if err != nil {
    panic(err)
}

rc.confState = snap.Metadata.ConfState
rc.snapshotIndex = snap.Metadata.Index
rc.appliedIndex = snap.Metadata.Index

2. Besides the raft module reconstructing the Raft Log from snapshots, the kvstore module also recovers the state machine using snapshots.

Similarly, it uses loadSnapshot to load the snapshot and then recoverSnapshot to deserialize the JSON data to recover the state machine.

func newKVStore(snapshotter *snap.Snapshotter, proposeC chan<- string, commitC <-chan *commit, errorC <-chan error) *kvstore {
    s := &kvstore{proposeC: proposeC, kvStore: make(map[string]string), snapshotter: snapshotter}
    snapshot, err := s.loadSnapshot()
    if err != nil {
        log.Panic(err)
    }
    if snapshot != nil {
        log.Printf("loading snapshot at term %d and index %d", snapshot.Metadata.Term, snapshot.Metadata.Index)
        if err := s.recoverFromSnapshot(snapshot.Data); err != nil {
            log.Panic(err)
        }
    }

    go s.readCommits(commitC, errorC)
    return s
}

Summary

That's all for this article. We have analyzed the log compaction and snapshot handling logic in raftexample from two perspectives: creating snapshots and recovering from snapshots. I hope this helps you better understand how to use the etcd raft library to build your own distributed KV storage service.

If there are any mistakes or issues, please feel free to comment or message me directly. Thank you.

References

How to Build Dynamic Grafana Dashboards and Visualize Open-Source Community Data

Lorain — Sat, 13 Jul 2024 16:17:29 +0000

Introduction

In “How to Visualize Open Source Community Data”, we introduced how to fetch data through the GitHub GraphQL API and visualize and display the data using MySQL and Grafana Dashboards.

This article will continue this topic, focusing on how to build a dynamic Grafana Dashboard using Variables.

Static Panels and Dynamic Panels

Static Panels

In this context, static panels refer to panels where the content of the queries is "hard-coded."

Imagine you want to monitor the load of your backend server backend_server_1 using Grafana. You hard-code backend_server_1 in the query, and it works fine. However, when one server is not enough to support your application, you might need to add backend_server_2, backend_server_3, etc. In this case, the initial query will become problematic, and you will need to modify the query every time you add or remove a server. This approach is cumbersome and not scalable.

Take the panel showing the star count changes of various repositories from the previous article as an example:

In the corresponding SQL query fetching data, the repository names are hard-coded. Such static panels are not advisable. Do not create such panels.

Dynamic Panels

By utilizing the Variables feature provided by Grafana Dashboards, we can easily create a series of panels that dynamically change based on the set variables.

Compared to static panels, dynamic panels are more flexible and natural by writing queries that adapt to different types of variables.

Creating Variables

Grafana Dashboard supports the creation of various types of variables (as shown in the table below). The methods of creation and usage are quite similar across different types. Here, we will mainly discuss Query type variables. If you want to learn about other types of variables, you can refer to the official documentation.

Variable type	Description
Query	Query-generated list of values such as metric names, server names, sensor IDs, data centers, and so on.
Custom	Define the variable options manually using a comma-separated list.
Text box	Display a free text input field with an optional default value.
Constant	Define a hidden constant.
Data source	Quickly change the data source for an entire dashboard.
Interval	Interval variables represent time spans.
Ad hoc filters	Key/value filters that are automatically added to all metric queries for a data source (Prometheus, Loki, InfluxDB, and Elasticsearch only).
Global variables	Built-in variables that can be used in expressions in the query editor.
Chained variables	Variable queries can contain other variables.

To create a variable, go to the Variables tab in the Dashboard Settings and click New variable.

After setting the variable type to Query, we can write a query to set the actual value of this variable.

Here, we create a simple login variable to query the names of all GitHub organizations from the database. Since we use MySQL as the data source, we only need to write a simple SQL query.

The effect of the login variable after creation is as follows: all organizations are queried and displayed in a dropdown list, and we can select an entry as the actual value of the login variable.

Variables can also reference each other. For example, if we want to create a repos variable that shows the names of all repositories under an organization, we can use the previously created login variable in the query for the repos variable using the $varname syntax. For more syntax for using variables, refer to the official documentation.

Through the Show dependencies option in the Variables tab, you can clearly see the dependencies between variables.

We can also choose to set multiple values as the actual value of a variable.

Now, with the Multi-value option enabled, we can select multiple repository names under a specific organization as the value of the repos variable by referencing the login variable.

Using Variables

To use variables, embed them in specific queries or expressions using the $varname or ${var_name} syntax, as we did when creating the repos variable.

To illustrate the flexibility and advantages of dynamic panels over static panels, let's take the initial panel showing the star count changes of various repositories as an example. Now, we have the repos variable that can select multiple repository names under the organization chosen by the login variable and use them as the value of the repos variable. Thus, we can write our SQL query as follows:

As shown in the figure:

We selected cloudwego as the value of the login variable and chose the netpoll, kitex, and hertz repositories in the repos variable.
In the SQL query, we used the repos variable with the $varname syntax.
Finally, our chart shows the star count change trends for the three selected repositories.

This approach is much more elegant than hard-coding the repository names in the query.

Another important point is that this usage requires adding an extra Transform to process the queried data. The Multi-frame time series Transform can use the returned string values as labels, enabling separate display of time series for each label.

Summary

That concludes this article. We have explored the use of Variables in Grafana Dashboard through practical examples, allowing us to easily create flexible dynamic panels.

By utilizing features like Grafana Dashboard Variables, the OPENALYSIS project can more flexibly perform visual analysis of the configured open-source community data. I believe this will help you better build and develop your open-source community.

References

How to Build Your Own Distributed KV Storage System Using the etcd Raft Library

Lorain — Fri, 05 Jul 2024 06:55:45 +0000

This article is the first in the series "How to Build Your Own Distributed KV Storage System Using the etcd Raft Library" - raftexample Architecture and Write Request Handling Process.

Introduction

raftexample is an example provided by etcd that demonstrates the use of the etcd raft consensus algorithm library. raftexample ultimately implements a distributed key-value storage service that provides a REST API.

This article will read and analyze the code of raftexample, hoping to help readers better understand how to use the etcd raft library and the implementation logic of the raft library.

Architecture

The architecture of raftexample is very simple, with the main files as follows:

main.go: Responsible for organizing the interaction between the raft module, the httpapi module, and the kvstore module;
raft.go: Responsible for interacting with the raft library, including submitting proposals, receiving RPC messages that need to be sent, and performing network transmission, etc.;
httpapi.go: Responsible for providing the REST API, serving as the entry point for user requests;
kvstore.go: Responsible for persistently storing committed log entries, equivalent to the state machine in the raft protocol.

The Processing Flow of a Write Request

A write request arrives in the ServeHTTP method of the httpapi module via an HTTP PUT request.

curl -L http://127.0.0.1:12380/key -XPUT -d value

After matching the HTTP request method via switch, it enters the PUT method processing flow:

Read the content from the HTTP request body (i.e., the value);
Construct a proposal through the Propose method of the kvstore module (adding a key-value pair with key as key and value as value);
Since there is no data to return, respond to the client with 204 StatusNoContent;

The proposal is submitted to the raft algorithm library through the Propose method provided by the raft algorithm library.

The content of a proposal can be adding a new key-value pair, updating an existing key-value pair, etc.

// httpapi.go
v, err := io.ReadAll(r.Body)
if err != nil {
    log.Printf("Failed to read on PUT (%v)\n", err)
    http.Error(w, "Failed on PUT", http.StatusBadRequest)
    return
}
h.store.Propose(key, string(v))
w.WriteHeader(http.StatusNoContent)

Next, let's look into the Propose method of the kvstore module to see how a proposal is constructed and processed.

In the Propose method, we first encode the key-value pair to be written using gob, and then pass the encoded content to proposeC, a channel responsible for transmitting proposals constructed by the kvstore module to the raft module.

// kvstore.go
func (s *kvstore) Propose(k string, v string) {
    var buf strings.Builder
    if err := gob.NewEncoder(&buf).Encode(kv{k, v}); err != nil {
        log.Fatal(err)
    }
    s.proposeC <- buf.String()
}

The proposal constructed by kvstore and passed to proposeC is received and processed by the serveChannels method in the raft module.

After confirming that proposeC has not been closed, the raft module submits the proposal to the raft algorithm library for processing using the Propose method provided by the raft algorithm library.

// raft.go
select {
    case prop, ok := <-rc.proposeC:
    if !ok {
        rc.proposeC = nil
    } else {
        rc.node.Propose(context.TODO(), []byte(prop))
    }

After a proposal is submitted, it follows the raft algorithm process. The proposal will eventually be forwarded to the leader node (if the current node is not the leader and you allow followers to forward proposals, controlled by the DisableProposalForwarding configuration). The leader will add the proposal as a log entry to its raft log and synchronize it with other follower nodes. After being deemed committed, it will be applied to the state machine and the result will be returned to the user.

However, since the etcd raft library itself does not handle communication between nodes, appending to the raft log, applying to the state machine, etc., the raft library only prepares the data required for these operations. The actual operations must be performed by us.

Therefore, we need to receive this data from the raft library and process it accordingly based on its type. The Ready method returns a read-only channel through which we can receive the data that needs to be processed.

It should be noted that the received data includes multiple fields, such as snapshots to be applied, log entries to be appended to the raft log, messages to be transmitted over the network, etc.

Continuing with our write request example (leader node), after receiving the corresponding data, we need to persistently save snapshots, HardState, and Entries to handle issues caused by server crashes (e.g., a follower voting for multiple candidates). HardState and Entries together comprise the Persistent state on all servers as mentioned in the paper. After persistently saving them, we can apply the snapshot and append to the raft log.

Since we are currently the leader node, the raft library will return MsgApp type messages to us (corresponding to AppendEntries RPC in the paper). We need to send these messages to the follower nodes. Here, we use the rafthttp provided by etcd for node communication and send the messages to follower nodes using the Send method.

// raft.go
case rd := <-rc.node.Ready():
    if !raft.IsEmptySnap(rd.Snapshot) {
        rc.saveSnap(rd.Snapshot)
    }
    rc.wal.Save(rd.HardState, rd.Entries)
    if !raft.IsEmptySnap(rd.Snapshot) {
        rc.raftStorage.ApplySnapshot(rd.Snapshot)
        rc.publishSnapshot(rd.Snapshot)
    }
    rc.raftStorage.Append(rd.Entries)
    rc.transport.Send(rc.processMessages(rd.Messages))
    applyDoneC, ok := rc.publishEntries(rc.entriesToApply(rd.CommittedEntries))
    if !ok {
        rc.stop()
        return
    }
    rc.maybeTriggerSnapshot(applyDoneC)
    rc.node.Advance()

Next, we use the publishEntries method to apply the committed raft log entries to the state machine. As mentioned earlier, in raftexample, the kvstore module acts as the state machine. In the publishEntries method, we pass the log entries that need to be applied to the state machine to commitC. Similar to the earlier proposeC, commitC is responsible for transmitting the log entries that the raft module has deemed committed to the kvstore module for application to the state machine.

// raft.go
rc.commitC <- &commit{data, applyDoneC}

In the readCommits method of the kvstore module, messages read from commitC are gob-decoded to retrieve the original key-value pairs, which are then stored in a map structure within the kvstore module.

// kvstore.go
for commit := range commitC {
    ...
    for _, data := range commit.data {
        var dataKv kv
        dec := gob.NewDecoder(bytes.NewBufferString(data))
        if err := dec.Decode(&dataKv); err != nil {
            log.Fatalf("raftexample: could not decode message (%v)", err)
        }
        s.mu.Lock()
        s.kvStore[dataKv.Key] = dataKv.Val
        s.mu.Unlock()
    }
    close(commit.applyDoneC)
}

Returning to the raft module, we use the Advance method to notify the raft library that we have finished processing the data read from the Ready channel and are ready to process the next batch of data.

Earlier, on the leader node, we sent MsgApp type messages to the follower nodes using the Send method. The follower node's rafthttp listens on the corresponding port to receive requests and return responses. Whether it's a request received by a follower node or a response received by a leader node, it will be submitted to the raft library for processing through the Step method.

raftNode implements the Raft interface in rafthttp, and the Process method of the Raft interface is called to handle the received request content (such as MsgApp messages).

// raft.go
func (rc *raftNode) Process(ctx context.Context, m raftpb.Message) error {
    return rc.node.Step(ctx, m)
}

The above describes the complete processing flow of a write request in raftexample.

Summary

This concludes the content of this article. By outlining the structure of raftexample and detailing the processing flow of a write request, I hope to help you better understand how to use the etcd raft library to build your own distributed KV storage service.

If there are any mistakes or issues, please feel free to comment or message me directly. Thank you.

References

How to Visualize and Analyze Data in Open Source Communities

Lorain — Sun, 21 Apr 2024 08:49:41 +0000

Introduction

This article will introduce the development approach and implementation of OPENALYSIS, an open-source community data analysis service. We will first preview the effects of the service after deployment, and then delve into the entire project's development process from basic ideas to concrete implementation.

Demonstration of Results

After successful deployment, the data display panel looks as follows. Here, we present statistics and displays of the open-source community CloudWeGo, a project by ByteDance. The panels include:

Key data statistics, including: total number of Issues, total number of Pull Requests (PRs), total number of Forks, total number of Stars, and total number of Contributors (deduplicated).
Ranking of all contributors based on their contributions.
Distribution of contributors by region and company.
Number of Issues and PRs initiated by contributors.
Number of days since contributors' first PR.
List and quantity of projects contributors have participated in.
Assignees of Issues and PRs across all repositories (Open Issues, Open PRs).
Trends in Stars, Forks, Issues, PRs, and Contributors for major repositories.

Basic Approach

The basic approach of this project is to retrieve corresponding data through the API provided by GitHub, persist the retrieved data into a database, and finally display the data stored in the database through Grafana Dashboard. Additionally, it requires using scheduled tasks to periodically fetch the latest data and update the persisted data.

Data Acquisition: GitHub provides two different types of APIs, REST (v3) and GraphQL (v4). We primarily utilize the GraphQL API for data retrieval, resorting to the REST API when fetching data not supported by v4.

GraphQL API offers more flexibility in obtaining the data we need compared to REST API. This example vividly illustrates the advantages of GraphQL over REST.

Data Storage: We use the most common MySQL database to persistently store our data.
Data Analysis: We employ Grafana Dashboard to query the MySQL database and display the data by configuring different types of panels.

Implementation Approach

Concept of Groups

Given that the repositories within the CloudWeGo community span multiple GitHub organizations and include separate repositories, such as:

https://github.com/cloudwego (org)
https://github.com/kitex-contrib (org)
https://github.com/hertz-contrib (org)
https://github.com/volo-rs (org)
https://github.com/bytedance/sonic (repo)
https://github.com/bytedance/monoio (repo)

If we aim to gather data for the entire community, we need to establish a new level of granularity to encompass these organizations and repositories.

In our project, we introduce the concept of Groups. A group can consist of multiple organizations or repositories. This way, we can consider the entire CloudWeGo community as a group and perform data retrieval, storage, analysis, etc., at the group level.

Data Acquisition

As we primarily utilize the GitHub GraphQL API (v4) for data retrieval, we can craft the corresponding GraphQL query based on the data we wish to obtain, leveraging the Public schema provided by GitHub. Subsequently, we send a request to GitHub's GraphQL endpoint at https://api.github.com/graphql.

For instance, if we aim to retrieve the number of issues, pull requests (PRs), stars, and forks for a repository, the corresponding GraphQL query would be as follows:

query RepoInfo($owner: String!, $name: String!) {
    repository(owner: $owner, name: $name) {
        id
        owner {
            id
        }
        issues {
            totalCount
        }
        pullRequests {
            totalCount
        }
        stargazers {
            totalCount
        }
        forks {
            totalCount
        }
    }
}

The $owner and $name are parameters required for this query, which can be passed in the form of Variables:

{
    "owner": "cloudwego",
    "name": "hertz"
}

However, this simple single query is not sufficient to fulfill all data retrieval needs.

GitHub limits the number of items that can be obtained through a single query via the GraphQL API to 100, in order to prevent users from making excessive or abusive requests to GitHub servers.

For example, if we want to retrieve a list of names of all repositories under an organization, but the total number of repositories owned by this organization is 150, then in a single GraphQL query, we can only obtain the names of up to 100 repositories, leaving the names of the remaining 50 repositories to be obtained in the next query. (This might not be a very good example because there are rarely organizations with more than 100 repositories, but you can imagine a query to retrieve all issues of repositories, and most large projects have more than 100 issues.)

To handle cases where a single query cannot retrieve all the data, GitHub GraphQL API provides Pagination. By using Pagination, we can make a series of consecutive requests to obtain the complete data.

Continuing with the example above, a GraphQL query to obtain a list of names of all repositories under an organization using Pagination would be:

query QueryReposByOrg($login: String!, $first: Int!, $after: String) {
    organization(login: $login) {
        repositories(first: $first, after: $after) {
            totalCount
            pageInfo {
                hasNextPage
                endCursor
            }
            nodes {
                nameWithOwner
            }
        }
    }
}

The $login, $first, and $after are parameters required for this query. $first represents the number of entries to retrieve in a single query, while $after serves as a cursor. By setting the cursor, entries can be retrieved starting from a specific position. Here, it retrieves $first number of entries starting from the position indicated by $after.

The Variables for the first query are configured as follows. Since we don't know the value of the cursor when initiating the first query, it is not set:

{
    "login": "cloudwego",
    "first": 100,
    "after": null
}

After the first query is completed, we can use the values of hasNextPage and endCursor from the returned pageInfo to initiate subsequent requests. For instance, when we determine that the value of hasNextPage is true, it indicates that there are still data entries to be retrieved. In this case, we only need to pass the value of endCursor as a parameter to the $after field of the next query. This way, the next query will start retrieving data entries from the last one obtained in the current query.

In terms of code implementation, we can use a for loop to carry out this series of requests using pagination. Below is the Go language implementation of the example mentioned above:

type RepoName struct {
    Organization struct {
        Repositories struct {
            PageInfo struct {
                HasNextPage bool
                EndCursor   string
            }
            Nodes []struct {
                NameWithOwner string
            }
        } `graphql:"repositories(first: $first, after: $after)"`
    } `graphql:"organization(login: $login)"`
}

// QueryRepoNameByOrg return repos of the provided org in `org/repo` format
func QueryRepoNameByOrg(ctx context.Context, login string) ([]string, error) {
    query := &RepoName{}
    variables := map[string]interface{}{
        "login": githubv4.String(login),
        "first": githubv4.Int(100),
        "after": (*githubv4.String)(nil),
    }
    var (
        repos []struct {
            NameWithOwner string
        }
        names []string
    )
    for {
        if err := GlobalV4Client.Query(ctx, query, variables); err != nil {
            return nil, err
        }
        repos = append(repos, query.Organization.Repositories.Nodes...)
        if !query.Organization.Repositories.PageInfo.HasNextPage {
            break
        }
        variables["after"] = githubv4.NewString(githubv4.String(query.Organization.Repositories.PageInfo.EndCursor))
    }
    for _, repo := range repos {
        names = append(names, repo.NameWithOwner)
    }
    return names, nil
}

Through pagination, we can handle most of the data retrieval needs.

Here are some pitfalls to watch out for:

issues have a since field, but pullrequests do not. Therefore, it's easy to retrieve all issues updated after a certain timestamp by using the since field from the last retrieval. However, for pullrequests, you can only retrieve those updated after the last queried cursor is saved.

When you initiate a query using a cursor, but there are no data updates, the returned cursor is empty instead of the cursor value you used for the query.

Some data can only be retrieved through the REST API.

Data Storage and Scheduled Tasks

All tasks needing execution within the project are divided into InitTask and UpdateTask. The InitTask is used to fetch and store the complete data of orgs and repos included in the configured groups upon project startup, while the UpdateTask is used for scheduled tasks after project initiation to fetch and store data updated since the last retrieval.

For instance, within InitTask, it's necessary to retrieve all issues from a repository, whereas within UpdateTask, only new issues or those updated since the last retrieval need to be fetched from a repository.

In UpdateTask, besides updating a portion of old data in the database, there is also a portion of data that doesn't require updating. This is because we need to retain historical data to form a time series, which enables the construction of graphs depicting the trend of data changes in subsequent data analyses.

Below is a simple example of a one-dimensional time series, illustrating temperature variations at two locations, LGA and BOS:

StartTime	Temp	Location
09:00	24	LGA
09:00	20	BOS
10:00	26	LGA
10:00	22	BOS

In our specific project, we need to store the data of each repository as time series. Therefore, in each UpdateTask, we need to retrieve and store data such as the number of issues, stars, etc., for all repositories.

By storing the time series, we can easily generate trend graphs like the one below:

Another important point to note is that when storing data into MySQL, it's necessary to encapsulate a complete operation within a transaction. This ensures that if an error occurs during data retrieval due to network issues or other reasons, we can roll back the entire transaction and retry the operation. Alternatively, if you're conducting a larger operation, you can roll back a portion of the transaction and retry.

Data Analysis

Once we've fetched data through the GitHub GraphQL API and stored it in MySQL, we can then utilize Grafana for data analysis and visualization.

Grafana offers a variety of visualization options, making it convenient to select based on the type and format of the stored data. For instance, data stored in a time series format, as mentioned earlier for various repositories, can be visualized using Grafana's Time series visualization. On the other hand, for displaying community contributors' companies and geographical distribution, we can utilize the Pie chart visualization.

After selecting the appropriate visualization method, we can proceed with querying the data and displaying it. Since we use MySQL as our data persistence mechanism, our primary method of data querying is SQL. By writing different SQL queries to retrieve the corresponding data in various ways, coupled with the multiple visualization options provided by Grafana, we can easily achieve the desired effects showcased at the beginning of the article.

For instance, the following is a visualization panel of the community contribution leaderboard:

The corresponding SQL is shown below. We arrange it in descending order based on the contributions statistics of each contributor. By utilizing the DENSE_RANK() function, we ensure that rankings are assigned consecutively when dealing with contributors who have the same contributions:

SELECT
    DENSE_RANK() OVER (ORDER BY SUM(contributions) DESC) AS 'Rank',
    login AS 'Name',
    SUM(contributions) AS 'Contributions'
FROM
    openalysis.contributors
GROUP BY
    login
ORDER BY
    SUM(contributions) DESC;

Summary

That concludes all the content of this article. We started from showcasing the final results and then delved into the specific processes of transforming the basic ideas into implementations, gaining an understanding of the entire project development.

OPENALYSIS still has many shortcomings, such as not providing more scalable Grafana Dashboards, which will be addressed in future development efforts.

We hope this article is helpful to readers. If there are any mistakes or questions, feel free to comment or reach out via private message.

References

How to reverse proxy the WebSocket protocol

Lorain — Mon, 04 Dec 2023 13:42:18 +0000

Introduction

The article will introduce how to reverse proxy the WebSocket protocol.

We'll start with the basics, understanding reverse proxying and the WebSocket protocol. Additionally, we'll delve into learning how to implement and explore relevant details by reading the source code of Hertz's open-source websocket reverseproxy extension.

Hertz: ByteDance's open-source high-performance Golang HTTP framework;
reverseproxy: A WebSocket reverse proxy extension for the Hertz framework, inspired by fasthttp-reverse-proxy for WebSocket reverse proxying.

Basic knowledge

What is a reverse proxy?

A reverse proxy is a type of proxy server positioned between internal servers and an external network, used to handle requests to internal servers. When a client sends a request, it doesn't directly access the target server but does so through the reverse proxy server. This proxy server is responsible for forwarding the request to one or more target servers and returning the obtained response to the client.

The typical functions of a reverse proxy are as follows:

Hide Backend Servers: Clients communicate only with the reverse proxy, not directly with the backend servers, thereby concealing information about the backend servers.
Load Balancing: The reverse proxy can distribute requests among multiple backend servers based on load, balancing the server load.
Cache Static Resources: It can cache static content to reduce server load and enhance response speed.
Security: It can act as a firewall, filtering malicious requests to improve security.

A schematic representation of a reverse proxy is as follows: NGINX is a commonly used reverse proxy server (often referred to as a gateway), where user requests are directed to the reverse proxy server, which then forwards them to a cluster of backend servers.

What is WebSocket?

WebSocket is a protocol that enables full-duplex communication over a single TCP connection. Unlike the traditional HTTP request-response model, WebSocket allows the establishment of persistent connections between servers and clients, enabling bidirectional communication for real-time data transmission. It permits servers to actively push data to clients without requiring client-initiated requests.

Full-Duplex Communication: Allows bidirectional communication between servers and clients, enabling real-time sending and receiving of data.
Low Latency: Established over a single TCP connection, reducing connection setup overhead and lowering communication latency.
Reduced Data Transfer Overhead: Compared to traditional HTTP polling, WebSocket minimizes data transfer overhead, making data transmission more efficient.

Implementation Approach

After grasping the fundamental knowledge, we can now start considering the specific implementation approach.

Terminology Agreement

Let's first establish a few terms that will be used to facilitate our understanding of the entire process:

Client: User;
Proxy Server: Reverse proxy server, for instance, NGINX mentioned earlier and the Hertz server used here;
Backend Server: The actual server that receives and handles client requests, not directly communicating with the client;

Basic Concept

As we're implementing a reverse proxy service based on the Hertz HTTP framework, the reverse proxy server here is Hertz itself. To enable websocket reverse proxying, we can achieve this by providing an http.Handler. This handler can forward the request for establishing a websocket connection from the user to the backend server. Subsequently, a websocket connection is established between the proxy server and the backend server, and another between the client and the proxy server. The proxy server manages message transmission between these two connections.

The process of establishing a websocket reverse proxy from connection setup to completion is outlined below:

1. The client initiates a handshake request to establish a websocket connection with the proxy server.
2. The proxy server forwards the request to the backend server.
3. The proxy server establishes a websocket connection with the backend server.
4. The client establishes a websocket connection with the proxy server.

Once all connections are established, the websocket reverse proxy is set up. Below is an example of a client sending information through the websocket reverse proxy:

5. The client writes a message to the websocket connection established with the proxy server.
6. The proxy server reads the message from the websocket connection with the client.
7. The proxy server writes the read message to the websocket connection established with the backend server.

I've also provided a sequence diagram where the numbering corresponds to the steps outlined above. Readers can refer to the diagram to better understand the entire process of reverse proxying websocket connections.

Specific Implementation

With the basic concept of implementation in place, we can now delve into the specific implementation details. Here, we will comprehend the concrete implementation process by reviewing the code in the Hertz framework websocket reverse proxy extension.

The code for websocket reverse proxy in this extension resides in two main files:

ws_reverse_proxy.go: Contains the primary business logic for websocket reverse proxying.
ws_reverse_proxy_option.go: Provides customizable configuration options for users.

Readers can either clone this repository and review the code alongside or directly examine the source code analysis provided below.

Main Struct (WSReverseProxy)

type WSReverseProxy struct {
    target  string
    options *Options
}

The main structure of the websocket reverse proxy appears to be quite simple, consisting of only two fields:

target: The target address for reverse proxying, which is the path to the backend server.
options: Configuration options. WSReverseProxy offers three customizable configuration options to users in the form of Functional Options.

Constructor (NewWSReverseProxy)

func NewWSReverseProxy(target string, opts ...Option) *WSReverseProxy {
    if target == "" {
        panic("target string must not be empty")
    }
    options := newOptions(opts...)
    wsrp := &WSReverseProxy{
        target:  target,
        options: options,
    }
    return wsrp
}

The logic of the constructor method is as follows:

It begins by checking whether the backend server path provided in the method parameter is empty. If it's empty, it directly triggers a panic.
Initialization of configuration options occurs next. If the user has configured any options, it uses those values; otherwise, it resorts to default values.
Creation of the main structure takes place, followed by assigning the values.
Finally, the populated main structure is returned to the user.

Core Method ServeHTTP

func (w *WSReverseProxy) ServeHTTP(ctx context.Context, c *app.RequestContext)

The ServeHTTP method is the core function for implementing websocket reverse proxying. As mentioned earlier, it serves as the Handler. Users utilize an instance of the main structure returned by the constructor method to invoke ServeHTTP and register the corresponding routes to facilitate the process of websocket reverse proxying.

Given that ServeHTTP is quite extensive, I'll break down the method into four parts according to the process of implementing websocket reverse proxying. We'll analyze these four parts sequentially.

Part 1: Prepare Forwarding Header

forwardHeader := prepareForwardHeader(ctx, c)
if w.options.Director != nil {
    w.options.Director(ctx, c, forwardHeader)
}

In this section, the Handler processes the request header of the client's handshake request using the prepareForwardHeader method and returns a forwardHeader to enable the proxy server to initiate a request to establish a websocket connection with the backend server.

Additionally, if the user has customized the Director option, further processing of the forwardHeader can be performed accordingly.

type Director func(ctx context.Context, c *app.RequestContext, forwardHeader http.Header)

Next, let's take a look at the prepareForwardHeader method:

func prepareForwardHeader(_ context.Context, c *app.RequestContext) http.Header {
    forwardHeader := make(http.Header, 4)
    if origin := string(c.Request.Header.Peek("Origin")); origin != "" {
        forwardHeader.Add("Origin", origin)
    }
    if proto := string(c.Request.Header.Peek("Sec-Websocket-Protocol")); proto != "" {
        forwardHeader.Add("Sec-WebSocket-Protocol", proto)
    }
    if cookie := string(c.Request.Header.Peek("Cookie")); cookie != "" {
        forwardHeader.Add("Cookie", cookie)
    }
    if host := string(c.Request.Host()); host != "" {
        forwardHeader.Set("Host", host)
    }
    clientIP := c.ClientIP()
    if prior := c.Request.Header.Peek("X-Forwarded-For"); prior != nil {
        clientIP = string(prior) + ", " + clientIP
    }
    forwardHeader.Set("X-Forwarded-For", clientIP)
    forwardHeader.Set("X-Forwarded-Proto", "http")
    if string(c.Request.URI().Scheme()) == "https" {
        forwardHeader.Set("X-Forwarded-Proto", "https")
    }
    return forwardHeader
}

The method logic is as follows:

1. First, initialize a http.Header with a size of 4 (type Header map[string][]string);
2. Check the client's request header for fields such as Origin, Sec-Websocket-Protocol, Cookie, and Host (HTTP Header). If any are present, set them in the forwardHeader;

The Sec-Websocket-Protocol header is used to specify the subprotocol that the client and server will use when establishing a WebSocket connection. The WebSocket protocol allows defining one or more subprotocols during connection establishment, which can describe the types of data or message formats to be sent and received on that connection.

3. Check if the client's request header contains the X-Forwarded-For field. If present, append the current client's IP to the existing X-Forwarded-For. If not present, set the X-Forwarded-For field in forwardHeader to the current client's IP;

The X-Forwarded-For header is typically added by a proxy server when forwarding requests and is used to identify the original client's IP address.

In network communication, when a request passes through multiple proxy servers (like load balancers, reverse proxies, etc.), the actual IP address of the original client that initiated the request might be hidden. To trace the true origin of the request, proxy servers usually add the X-Forwarded-For field in the HTTP request header, which contains the original client's IP address.

An example might look like this:

   Note: client1, proxy1, proxy2 here are actual IP addresses
   X-Forwarded-For: client1, proxy1, proxy2

4. Set the X-Forwarded-Proto field in forwardHeader and return it;

The X-Forwarded-Proto header is typically added by a proxy server when forwarding requests and indicates the protocol (HTTP or HTTPS) used in the original request.

Points to Note:

Difference between header.Add and header.Set methods;

The Add method checks if the key already exists. If it doesn't, it sets the corresponding key and value. If it does exist, it appends the current value to the existing value array. On the other hand, the Set method doesn't perform any checks. It sets the key and value regardless of whether it already exists or not.

Combining the explanation with the following code might make it easier for you to understand:

header := make(http.Header)
header.Add("Key1", "Value1")
fmt.Println(header)

header.Add("Key1", "Value2")
fmt.Println(header)

header.Set("Key1", "Value3")
fmt.Println(header)

// output:
// map[Key1:[Value1]]
// map[Key1:[Value1 Value2]]
// map[Key1:[Value3]]

Why aren't fields like Connection, Upgrade, Sec-WebSocket-Key, etc., set for forwardHeader?

Readers familiar with the WebSocket protocol might know that these fields are all essential for a WebSocket handshake request. They indicate that the client initiating the handshake intends to upgrade to the WebSocket protocol. If you add the following code within the prepareForwardHeader method, you'll find that indeed these fields are present in the client's request.

fmt.Println("Upgrade: " + string(c.Request.Header.Peek("Upgrade")))
fmt.Println("Connection: " + string(c.Request.Header.Peek("Connection")))
fmt.Println("Sec-WebSocket-Key: " + string(c.Request.Header.Peek("Sec-Websocket-Key")))

However, the reason these fields aren't included in forwardHeader is because, as mentioned earlier, the client doesn't establish the WebSocket connection directly with the backend server but with the proxy server.

Now, some readers might wonder how the WebSocket connection is established with the backend server if forwardHeader doesn't contain these necessary fields. Please refer to the upcoming second part for further clarification.

Part 2: Proxy Server Establishes WebSocket Connection with Backend Server

connBackend, respBackend, err := w.options.Dialer.Dial(w.target, forwardHeader)
if err != nil {
    hlog.CtxErrorf(ctx, "can not dial to remote backend(%v): %v", w.target, err)
    if respBackend != nil {
        if err = wsCopyResponse(&c.Response, respBackend); err != nil {
            hlog.CtxErrorf(ctx, "can not copy response: %v", err)
        }
    } else {
        c.AbortWithMsg(err.Error(), consts.StatusServiceUnavailable)
    }
    return
}

In the first part, we've prepared the forwardHeader. Now, the next step involves passing the backend server's path (target) along with the forwardHeader to the Dial method. The Dial method initiates a handshake request to the backend server, allowing the proxy server to establish a WebSocket connection with the backend server.

Within the Dial method, the necessary fields mentioned in the first part are also added to the initiated request:

req.Header["Upgrade"] = []string{"websocket"}
req.Header["Connection"] = []string{"Upgrade"}
req.Header["Sec-WebSocket-Key"] = []string{challengeKey}
req.Header["Sec-WebSocket-Version"] = []string{"13"}

The connBackend returned by the Dial method is the instance of the WebSocket connection established between the proxy server and the backend server.

Of course, if the Dial method encounters an error, indicating a failure to establish a WebSocket connection between the proxy server and the backend server, the corresponding response needs to be returned to the client. However, as this isn't the primary logic, I won't delve into further details here.

Part 3: Establishing WebSocket Connection between Client and Proxy Server

if err := w.options.Upgrader.Upgrade(c, func(connClient *hzws.Conn) {
    defer connClient.Close()
    ...
}); err != nil {
    hlog.CtxErrorf(ctx, "can not upgrade to websocket: %v", err)
}

In the second part, we saw that the proxy server had successfully established a WebSocket connection with the backend server using the Dial method. In this third part, we'll use the Upgrade method to enable the client to establish a WebSocket connection with the proxy server.

Upgrade will finalize the established WebSocket connection with the client's handshake and pass it into connClient, signifying that connClient is the instance of the WebSocket connection established between the client and the proxy server.

Of course, if the Upgrade method encounters an error, indicating a failed connection establishment, it will log the error, and the entire ServeHTTP method will consequently terminate.

Part 4: Connection Communication

var (
    errClientC  = make(chan error, 1)
    errBackendC = make(chan error, 1)
    errMsg      string
)

hlog.CtxDebugf(ctx, "upgrade handler working...")

gopool.CtxGo(ctx, func() {
    replicateWSRespConn(ctx, connClient, connBackend, errClientC)
})
gopool.CtxGo(ctx, func() {
    replicateWSReqConn(ctx, connBackend, connClient, errBackendC)
})

for {
    select {
    case err = <-errClientC:
        errMsg = "copy websocket response err: %v"
    case err = <-errBackendC:
        errMsg = "copy websocket request err: %v"
    }

    var ce *websocket.CloseError
    var hzce *hzws.CloseError
    if !errors.As(err, &ce) || !errors.As(err, &hzce) {
        hlog.CtxErrorf(ctx, errMsg, err)
    }
}

In the third part, the WebSocket connection between the client and the proxy server was established, and we obtained the connection instance connClient. Next is to enable the client to communicate with the backend server in a reverse proxy manner using the following two connections:

connClient: WebSocket connection instance between the client and the proxy server
connBackend: WebSocket connection instance between the proxy server and the backend server

As seen, we first prepare two channels to receive errors during communication:

errClientC: For receiving errors when the backend server sends messages to the client
errBackendC: For receiving errors when the client sends messages to the backend server

Then, we retrieve two goroutines from the coroutine pool to concurrently execute the replicateWSRespConn and replicateWSReqConn methods. The naming of these methods might seem peculiar because WebSocket is a full-duplex communication protocol, where requests and responses are relative.

However, here, we uniformly consider messages sent from the backend server to the client as responses and messages sent from the client to the backend server as requests, in terms of the client's perspective.

Since this can be a bit convoluted, I've created a schematic diagram to aid in understanding.

Let's continue examining these two concurrently executed communication methods. Since the logic of both methods is essentially similar, let's take a look at the logic of the replicateWSRespConn method:

func replicateWSRespConn(ctx context.Context, dst *hzws.Conn, src *websocket.Conn, errC chan error) {
    for {
        msgType, msg, err := src.ReadMessage()
        if err != nil {
            ...
            errC <- err

            if err = dst.WriteMessage(hzws.CloseMessage, msg); err != nil {
                hlog.CtxErrorf(ctx, "write message failed when replicate websocket conn: err=%v", err)
            }
            break
        }

        err = dst.WriteMessage(msgType, msg)
        if err != nil {
            hlog.CtxErrorf(ctx, "write message failed when replicating websocket conn: msgType=%v msg=%v err=%v", msgType, msg, err)
            errC <- err
            break
        }
    }
}

The logic of the method is quite simple. It involves reading messages sent from the backend server to the proxy server through the ReadMessage method of connBackend and then writing the read messages into the connection between the client and the proxy server using the WriteMessage method of connClient.

Any errors encountered are passed to errClientC for unified handling outside the method.

Returning to the outer method, errors are received from errClientC and errBackendC using a for-select structure. If the error is not a CloseError, it is logged.

With this, we have completed the understanding of the core logic within the ServeHTTP method. The logic of the ServeHTTP method aligns entirely with the websocket reverse proxy process outlined in the basic approach. Readers can compare the basic approach with the specific implementation to achieve a better understanding.

Example Usage (Echo Server)

Just now, we've finished reading through the core code of the Hertz framework's WebSocket reverse proxy extension. Here, we'll demonstrate the usage of this extension by creating an example of an echo server. This example aims to assist readers in better understanding how to utilize this extension.

We'll break down this example into three parts, and the complete code will be provided at the end.

Firstly, let's globally declare the addresses and paths for the proxy server and the backend server:

var (
    proxyURL    = "ws://127.0.0.1:8080/ws"
    backendURL  = "ws://127.0.0.1:9090/backend"
    proxyAddr   = "127.0.0.1:8080"
    backendAddr = "127.0.0.1:9090"
)

Proxy Server

// proxy server
wsrp := reverseproxy.NewWSReverseProxy(backendURL)
ps := server.Default(server.WithHostPorts(proxyAddr))
ps.GET("/ws", wsrp.ServeHTTP)
go ps.Spin()

Using the constructor method NewWSReverseProxy that we learned in the specific implementation section, create a WebSocket reverse proxy instance with the backendURL as the target parameter. Next, register the ServeHTTP method under the /ws route, and start the proxy server via a goroutine. It's important to note that the address of the proxy server and the registered route should correspond to the proxyURL.

Backend Server

go func() {
    // backend server
    bs := server.Default(server.WithHostPorts(backendAddr))
    bs.GET("/backend", func(ctx context.Context, c *app.RequestContext) {
        upgrader := &websocket.HertzUpgrader{}
        if err := upgrader.Upgrade(c, func(conn *websocket.Conn) {
            for {
                msgType, msg, err := conn.ReadMessage()
                if err != nil {
                    hlog.Errorf("backend read message err: %v", err)
                }
                err = conn.WriteMessage(msgType, msg)
                if err != nil {
                    hlog.Errorf("backend write message err: %v", err)
                }
            }
        }); err != nil {
            hlog.Errorf("upgrade error: %v", err)
            return
        }
    })
    bs.Spin()
}()

Start the backend server via a goroutine and register the /backend route. Similarly, ensure that the address of the backend server and the registered route correspond to the backendURL. Then, handle incoming WebSocket connections within the handler.

Begin by using the Upgrade method to upgrade the HTTP protocol to the WebSocket protocol. Subsequently, read messages sent by the client (in this context, the client refers to the proxy server) from the established WebSocket connection and write the messages back to the WebSocket connection. This completes the echo logic, which continuously repeats this process within a for loop.

Client

// client
conn, _, err := reverseproxy.DefaultOptions.Dialer.Dial(proxyURL, make(http.Header))
if err != nil {
    hlog.Errorf("client dial err: %v", err)
    return
}

time.Sleep(time.Second)

var echoInput string
for {
    fmt.Print("send: ")
    _, _ = fmt.Scanln(&echoInput)
    err = conn.WriteMessage(websocket.TextMessage, []byte(echoInput))
    if err != nil {
        hlog.Errorf("client write message err: %v", err)
    }
    _, echoOutput, err := conn.ReadMessage()
    if err != nil {
        hlog.Errorf("client read message err: %v", err)
    }
    fmt.Println("receive: " + string(echoOutput))
}

Using the Dial method, send a handshake request to the proxy server to upgrade to the WebSocket protocol. Once you obtain the returned connection instance, utilize the Scanln method to read user-input messages and write them to the connection. Simultaneously, receive the returned messages from the connection and print them. Continue this process within a for loop.

With this, we've completed an example of a WebSocket reverse proxy echo server.

Complete Code

The complete code for the echo server example is as follows:

package main

import (
    "context"
    "fmt"
    "net/http"
    "time"

    "github.com/cloudwego/hertz/pkg/app"
    "github.com/cloudwego/hertz/pkg/app/server"
    "github.com/cloudwego/hertz/pkg/common/hlog"
    "github.com/hertz-contrib/reverseproxy"
    "github.com/hertz-contrib/websocket"
)

var (
    proxyURL    = "ws://127.0.0.1:8080/ws"
    backendURL  = "ws://127.0.0.1:9090/backend"
    proxyAddr   = "127.0.0.1:8080"
    backendAddr = "127.0.0.1:9090"
)

func main() {
    // proxy server
    wsrp := reverseproxy.NewWSReverseProxy(backendURL)
    ps := server.Default(server.WithHostPorts(proxyAddr))
    ps.GET("/ws", wsrp.ServeHTTP)
    go ps.Spin()

    time.Sleep(time.Second)

    go func() {
        // backend server
        bs := server.Default(server.WithHostPorts(backendAddr))
        bs.GET("/backend", func(ctx context.Context, c *app.RequestContext) {
            upgrader := &websocket.HertzUpgrader{}
            if err := upgrader.Upgrade(c, func(conn *websocket.Conn) {
                for {
                    msgType, msg, err := conn.ReadMessage()
                    if err != nil {
                        hlog.Errorf("backend read message err: %v", err)
                    }
                    err = conn.WriteMessage(msgType, msg)
                    if err != nil {
                        hlog.Errorf("backend write message err: %v", err)
                    }
                }
            }); err != nil {
                hlog.Errorf("upgrade error: %v", err)
                return
            }
        })
        bs.Spin()
    }()

    time.Sleep(time.Second)

    // client
    conn, _, err := reverseproxy.DefaultOptions.Dialer.Dial(proxyURL, make(http.Header))
    if err != nil {
        hlog.Errorf("client dial err: %v", err)
        return
    }

    time.Sleep(time.Second)

    var echoInput string
    for {
        fmt.Print("send: ")
        _, _ = fmt.Scanln(&echoInput)
        err = conn.WriteMessage(websocket.TextMessage, []byte(echoInput))
        if err != nil {
            hlog.Errorf("client write message err: %v", err)
        }
        _, echoOutput, err := conn.ReadMessage()
        if err != nil {
            hlog.Errorf("client read message err: %v", err)
        }
        fmt.Println("receive: " + string(echoOutput))
    }
}

Summary

That concludes all the content of this article. We started from the basics of WebSocket reverse proxy, determined the basic approach to implementation, and delved deeper into understanding how to reverse proxy WebSocket by reading the code of the WebSocket reverse proxy extension in the Hertz framework and using an echo server as an example.

Hopefully, this article has been helpful for readers in understanding WebSocket reverse proxy. If there are any mistakes or questions, please feel free to comment or message me :).

Reference List

How to Build Your Own Chrome Extension Using ChatGPT

Lorain — Sat, 04 Nov 2023 13:11:28 +0000

Introduction

In my previous article, I shared how I developed a Chrome extension using ChatGPT within 15 minutes, despite having no prior knowledge of frontend development. Recently, I completed another Chrome extension project with the help of ChatGPT. In this article, I want to summarize and share the entire development process and insights, hoping to provide some inspiration and assistance to you.

In this article, I will walk you through the process of developing the TABSNAPSHOT extension using ChatGPT. We will start from the basic requirements and move on to some key points to consider when developing with ChatGPT.

Requirements

The idea for this extension came from a real-life scenario. I spend most of my time browsing web pages and PDFs. Chrome provides an excellent reading experience, but I often find myself opening specific pages related to a particular topic. For example, during my midterm exam preparation, I needed to open three pages (a lecture PDF and two article links) every time I opened Chrome. Using Chrome's built-in features, I had two options:

Create a folder and save these three pages as bookmarks inside the folder. I could open all the pages at once using the "Open all bookmarks" option in the folder.
Add these three pages to Chrome's "Reading List" and open them one by one from the Reading List.

However, I rejected both of these methods because:

The process of creating a folder and adding pages to it is too tedious: creating the folder, adding a page to the folder, and saving it require too many steps. Besides, I usually use Chrome folders to collect web pages rather than storing these temporary pages I need to read.
The Reading List doesn't support adding PDFs, and dealing with PDF pages separately would be a very cumbersome process.

So, I clearly identified the need for a tool that could temporarily save one or multiple tab pages and open these pages with minimal actions, similar to the Open All Bookmarks option.

Development Approach

Unlike my previous GitHub Searcher project, I had no specific idea of how to implement this extension. I wasn't even sure if Chrome provided APIs to achieve these functionalities. After giving it some thought, I came up with a rough plan:

Implement a button in the extension popup to save all currently open tabs as a "snapshot."
Use the extension's popup window as the main control panel for the extension.
Display all saved snapshots in the popup window. Clicking on a snapshot should open all the tabs saved in that snapshot.

With this plan in mind, I named the extension TABSNAPSHOT and proceeded to write the code with ChatGPT.

Development Process

Basic Functionality

Since I relied entirely on GPT to write the code, I communicated my requirements and approach clearly to GPT. However, due to GPT's nature, there were some challenges and issues that arose.

My initial prompt was as follows:

I want to develop a Chrome extension called tabsnapshot. This extension should:

Save the URLs of all open tabs in the browser when the user clicks the "Create Snapshot" button in the extension's popup window (i.e., create a snapshot).

Display the saved snapshots as items in the popup window, with the snapshot's creation time as the item's name.

When the user clicks on a saved snapshot in the popup window, open the URLs saved when the snapshot was created.

Please develop this extension and provide all necessary files.

However, the code generated based on this prompt had several issues:

The manifest_version was set to 2.
Only the URL of the first open tab was saved in each snapshot, not all open tabs.
Saved snapshots were not persisted. When I closed and reopened Chrome, the saved snapshots disappeared.

To address these issues, I provided additional instructions to GPT:

I want to develop a Chrome extension called tabsnapshot. This extension should:

Save the URLs of all open tabs in the browser when the user clicks the "Create Snapshot" button in the extension's popup window (i.e., create a snapshot).

Display the saved snapshots as items in the popup window, with the snapshot's creation time as the item's name.

When the user clicks on a saved snapshot in the popup window, open the URLs saved when the snapshot was created.

Please develop this extension and provide all necessary files.

Additional instructions:

The manifest_version value should be set to 3.

Each snapshot item should save all open URLs, not just one URL. You can consider using an array or map for storage.

All snapshot items must be persisted. When I close and reopen the browser, I should see all previously saved snapshot items.

With these additional instructions, GPT generated code that met my requirements. I had the basic functionality of TABSNAPSHOT, allowing me to create snapshots, save them, and open them with a single click.

The initial UI for this basic version was quite simple:

Once the basic version was implemented, I had a foundation to build upon. I continued to enrich and optimize the features of TABSNAPSHOT.

Delete Functionality and UI Enhancement

In the initial version, I only had the functionality to create snapshots but lacked the ability to delete them. I asked GPT to add the delete functionality:

I need you to add snapshot deletion functionality to this extension. Without changing the existing functionality, add an "x" button next to each snapshot item in the popup window. Users can click this button to delete the corresponding saved snapshot. Please provide the updated code after adding the delete functionality.

With the code provided by GPT, the UI was updated as follows:

Although the "x" buttons were functional, the UI was not aesthetically pleasing. I asked GPT to improve the style while keeping the delete functionality intact:

Great, but the style of the delete button is not appealing. Can you make it similar to the "Create Snapshot" button and maintain the delete functionality?

The improved style of the delete button, along with other UI enhancements, looked like this:

We can see that the optimized delete button looks much better, even richer in style than the Create Snapshot button mentioned in the prompt, so we continue to let GPT optimize the UI, and the final UI looks like this:

At this point, TABSNAPSHOT is fully operational, and all the current features are sufficient to address the pain points I mentioned in the requirements scenario.

But because of my OCD, we continue to add features and optimizations to TABSNAPSHOT.

Rename and Open Snapshot

From the above UI, it can be seen that each snapshot entry is named after the time it was created. When there are many entries, it becomes difficult to distinguish which content each snapshot contains. Therefore, here we added the renaming functionality to TABSNAPSHOT:

The first feature we are going to add is the renaming functionality. Please add a rename button to the left of the delete button with a style consistent with the delete button. When the user clicks the rename button, the original text of the snapshot entry will become editable. Users can rename the snapshot by modifying the text and confirming with the Enter key.

However, GPT did not provide a perfect solution in this case. When clicking the Rename button and modifying the text, the Enter key did not save the changes. Users had to click somewhere else in the popup window to save the changes. We had to use a few more prompts to guide GPT and make the necessary modifications to finally complete the development of the renaming functionality:

Here, we also changed the way snapshots are opened to a specific button:

Great! Now I would like you to modify the logic for opening saved snapshots. Currently, the logic is to click on the snapshot entry to open it. I want you to change the way snapshots are opened to clicking an open button. This open button should be located to the right of each snapshot entry. The style of a snapshot entry should be: Snapshot Name, Open button, Rename button, Delete button.

The final result looks like this:

Open All and Delete All

To further enhance the functionality of TABSNAPSHOT, I asked GPT to add "Open All" and "Delete All" buttons:

Excellent. Now I want you to add two buttons to the right of the "Create Snapshot" button:

"Open All": Opens all saved snapshots.

"Delete All": Deletes all saved snapshots.

The updated UI with these features was as follows:

Now that we have completed all the major feature points, we will fine-tune some of the details of TABSNAPSHOT.

Detail Optimizations

Optimizable details are as follows:

If the tab contains a local PDF for browsing, it should automatically refresh after opening; otherwise, manual refresh might be necessary.
Add a tab count for each snapshot entry.
Simplify the default snapshot naming format (retain only month, day, hour, and minute).
If multiple snapshots are created within the same minute, automatically add numbering to avoid duplicates.
Snapshot preview.

When communicating with GPT through prompts, it's essential to describe your requirements clearly. You can make your prompts more vivid by providing examples:

Next, we are going to add a tab count feature to the snapshots. When creating a snapshot entry, the number of tabs included in that snapshot will be displayed after the snapshot name. For example, a name for a snapshot containing three tabs would be sample [3]. Please note that this [3] should not be editable by the user through the rename button. You can place the snapshot entry name and tab count in separate elements but display them on the same line.

Please add a logic check for snapshot creation. If multiple snapshots are created within the same minute, start numbering from the second snapshot created within that minute, following the order of creation. For example, the name of the first snapshot created at 15:53 on 11/1 would be 11/1 15:53, the second snapshot created at 15:53 on 11/1 would be 11/1 15:53 (2), and the third one would be 11/1 15:53 (3).

One thing worth mentioning is the snapshot preview feature. I have found it challenging to convey the exact effect I want to GPT, which might be why the implemented feature did not meet my expectations. Perhaps I haven't clearly defined what the preview feature should look like.

From a hover-based implementation to a click-based popup window:

Now I want to add a preview feature to this plugin. Leave a space at the bottom of the popup window as the preview area. When the user hovers over a snapshot entry, the preview window will list all the links from the tabs included in that snapshot in the form of a list. Please implement this feature based on the above code.

Now I want to add a preview feature to this plugin. When the user clicks on a snapshot entry, the browser will pop up a preview window (please note that this preview window is not the plugin's popup window). The preview window will list all the links from the tabs included in that snapshot in the form of a list. Please implement this feature based on the above code.

The final version, with all optimizations completed, is as follows. This is the v0.1.0 version released after open-sourcing:

Plugin UI

Preview window UI

Key Takeaways from Developing with ChatGPT

Here are some key points and lessons I learned during the development process with ChatGPT:

Clearly define your development goals and expectations. Ensure you can articulate your requirements logically; otherwise, the responses from ChatGPT might not meet your needs.
Break down your project into small functional points. Develop one feature at a time, starting with the basic functionality and then refining and optimizing it.
Long prompts might cause ChatGPT to lose context. Consider using previous prompts to edit and submit or start a new chat to maintain context.
Use consistent terminology and agreements with ChatGPT during the development process.

Logo

You can also design an attractive logo for TABSNAPSHOT:

Conclusion

This article has covered my entire journey of developing the TABSNAPSHOT extension with the help of ChatGPT. It includes the iterative thought process and the key points summarized at the end. I hope this experience can assist you in your projects.

As you can see, TABSNAPSHOT is still a very basic and simple extension with plenty of room for improvement. However, if you have a similar use case to mine, feel free to use TABSNAPSHOT to simplify your browsing experience.

If you find TABSNAPSHOT helpful or if you have suggestions for improvements, please feel free to Star, Fork, and submit Pull Requests !!!

References

I Created a Chrome Extension in 15 Minutes with Zero Front-End Knowledge Using GPT

Lorain — Sun, 10 Sep 2023 16:42:03 +0000

Preface

When reading, authors often mention various projects or related materials, and sometimes it's just plain text without corresponding links. If I want to learn more about these projects, I have to search for them myself, either through Google or other means. One common thing I often do is:

Copy the name of a project.
Open a new tab.
Visit GitHub.
Paste and search.

Perhaps because I've been repeating this process too frequently recently, I came up with the idea to develop a plugin to simplify this process.

So, a few minutes later, I created my first Chrome extension, GitHub Searcher (GHS).

Expected Outcome

The desired outcome for the plugin is very simple, or one could say rudimentary: search for the text I've selected on GitHub, and be able to choose whether to search in the current tab or open a new tab. With this feature, I can simplify the four steps mentioned earlier into just two:

Select the content I want to search for.
Right-click and choose whether to search in the current tab or open a new tab.

Development Approach

After trying to search for several repositories on GitHub, I found that the URL for searching repositories on GitHub is:

github.com/search?q=test&type=repositories

In this URL, the q parameter corresponds to the search query content, and the default type is repositories. Therefore, to achieve the desired outcome, it becomes very simple. I just need to find a way to get the selected text, then concatenate it and visit the URL.

Development Process

With the basic idea in mind, it's time to start development. Since I primarily use Chrome, I decided to implement it as a Chrome extension.

I quickly went through the Development basics provided by the official Chrome documentation to understand the project structure and necessary files for a Chrome extension. However, my knowledge of front-end development is limited to a few common HTML tags. This is where I relied on my trusty friend GPT.

I organized my earlier thoughts into language that GPT could understand and fed them to it, and then... GPT generated all the code for me.

Initially, I didn't have very high expectations. I thought it would generate some code samples using Chrome API, which I could then modify to make it work. But when I copied the code generated by GPT into my project and loaded the extension in Chrome, the desired functionality was fully implemented!

My prompts to GPT were quite simple, as follows:

Me: What's the operation called when you select a portion of text in a web page by pressing and dragging the mouse?

GPT: In a web browser, the operation of selecting a portion of text by pressing and dragging the left mouse button is typically referred to as "text selection" or "text dragging." This operation allows users to highlight text on a web page for purposes such as copying, cutting, or performing other actions like searching or translating. It's a common interaction when reading web pages, copying information, or quoting text.

Me: What's the operation called when you right-click with the mouse in a web browser to open a menu?

GPT: In a web browser, the operation of opening a menu by right-clicking with the mouse is usually called "context menu" operation, sometimes referred to as the "right-click menu." This menu typically contains options related to the element or area you right-clicked on, allowing you to perform various actions like opening links, saving images, copying text, and more. The content of this context menu can vary depending on what you right-clicked and your browser's settings. It provides a convenient way to access common functions quickly.

Me: In some Chrome extensions, the right-click menu often has a submenu, such as "Image Helper," which contains various supported actions like "Extract Images from this page" and "Download Images from this page." Is there an official term for these?

GPT: In Chrome extensions, these submenus within the right-click menu, which contain multiple related actions, are typically referred to as "context menu submenus" or "right-click submenus." These submenus allow extension developers to organize different functionalities supported by the extension into a larger group of options, providing more functionality choices and an improved user experience. In this submenu, each option usually represents a specific operation or feature supported by the extension. In the example you mentioned, the "Image Helper" submenu includes actions like "Extract Images from this page" and "Download Images from this page."

It's important to note that there isn't an official standard term for this, and different extension developers may use different terminology to describe this functionality. However, in general, the purpose of such submenus is to organize and present multiple related action options.

Me: I want to develop a Chrome extension called "ghs" (GitHub Searcher). The usage of this extension is as follows:

The user selects some words or sentences on a web page using the mouse, which is the "text selection" operation.

The user right-clicks with the mouse to open a context menu and selects a submenu named "GitHub Searcher." This submenu contains two options: "Current Tab" and "New Tab."

After selecting text, clicking on these two options will open the URL github.com/search?q={{ sample }}&type=repositories in either the current tab or a new tab, where {{ }} represents the selected text.

Here's an actual use case: While browsing a web page, I select the word "helloworld," then right-click and choose the "New Tab" option from the "GitHub Searcher" submenu. The browser should then open a new tab and visit the URL github.com/search?q=helloworld&type=repositories.

Now, I need your help to develop this extension. Please list each step and add necessary comments to the code to help me understand it.

GPT: Developing a Chrome browser extension involves several steps. I'll list each step and add comments to the code to help you understand it.

Step 1: Create the Extension Directory and Manifest File

First, you need to create a local directory for your extension and create a manifest file (manifest.json) within that directory. The manifest file is used to define the extension's basic information, permissions, and functionality.
// manifest.json

{
  "manifest_version": 3,
  "name": "GitHub Searcher",
  "version": "1.0",
  "description": "Search GitHub repositories from selected text.",
  "permissions": ["contextMenus"],
  "icons": {
    "48": "icon.png"
  },
  "background": {
    "service_worker": "background.js"
  },
  "permissions": ["activeTab", "contextMenus"],
  "action": {
    "default_popup": "popup.html",
    "default_icon": {
      "16": "icon.png",
      "48": "icon.png",
      "128": "icon.png"
    }
  }
}
Step 2: Create the Extension Icon

Add the extension icon (icon.png) to the extension directory. This icon represents your extension.

Step 3: Create the Context Menu

In the background.js file, create the context menu so that users can right-click selected text to open the extension's submenu. Here's an example background.js file:
// background.js

chrome.contextMenus.create({
  id: "githubSearcherContextMenu",
  title: "GitHub Searcher",
  contexts: ["selection"]
});

chrome.contextMenus.create({
  id: "githubSearcherCurrentTab",
  title: "Current Tab",
  parentId: "githubSearcherContextMenu",
  contexts: ["selection"]
});

chrome.contextMenus.create({
  id: "githubSearcherNewTab",
  title: "New Tab",
  parentId: "githubSearcherContextMenu",
  contexts: ["selection"]
});

// Add click event listeners
chrome.contextMenus.onClicked.addListener((info, tab) => {
  if (info.menuItemId === "githubSearcherCurrentTab") {
    openGitHubSearchPage(info.selectionText, false);
  } else if (info.menuItemId === "githubSearcherNewTab") {
    openGitHubSearchPage(info.selectionText, true);
  }
});

// Function to open the GitHub search page
function openGitHubSearchPage(selectedText, newTab) {
  const searchUrl = `https://github.com/search?q=${encodeURIComponent(selectedText)}&type=repositories`;
    if (newTab) {
      chrome.tabs.create({ url: searchUrl });
  } else {
      chrome.tabs.update({ url: searchUrl });
  }
}
Step 4: Create the Extension Popup Page

Create a popup page (popup.html) that will display information or settings when the user clicks the extension icon. You can customize this page as needed.

Step 5: Load the Extension

Finally, load your extension in the Chrome browser:

Open the Chrome browser and go to the extensions management page (chrome://extensions/).

Enable "Developer mode."

Click the "Load unpacked" button and select your extension directory.

Once you've completed these steps, your extension should be able to display the "GitHub Searcher" submenu when the user selects text and right-clicks, and it should open the corresponding GitHub search page when "Current Tab" or "New Tab" is selected.

Please note that this is a basic example, and you can further expand and customize the extension's interface according to your needs. Also, ensure that you follow the Chrome Web Store's publishing guidelines and best practices. Once successfully published, users can install and use your extension from the Chrome Web Store.

You can see that the first three steps were primarily about aligning terminology and concepts with GPT. Only in the fourth step did I start combining these terms and my own ideas to have GPT generate the actual code.

As I mentioned earlier, the code provided by GPT was essentially correct and achieved the desired functionality when installed, but there were some flaws that needed to be addressed, such as the absence of popup.html and a reminder to set the icon. However, these were minor issues, and after designing a nice-looking icon and adding supplementary files like popup.html (optional), README, LICENSE, etc., our extension was complete :)

Conclusion

The above is the complete process of developing a Chrome extension from scratch with the help of GPT. A significant reason for the smooth development was that the functionality of this extension was quite simple, hhhh, but it certainly saved me some time.

Due to the complexity of publishing extensions in the Chrome Web Store, I didn't go through that process. If you're interested in this extension, you can download the source code and manually load it into your Chrome browser. Of course, if you find this extension useful, feel free to give the project a Star!

References

Add License Headers to Your Code Files

Lorain — Mon, 28 Aug 2023 06:10:11 +0000

Introduction

As developers, we often need to ensure that our code complies with the appropriate licenses to protect our intellectual property.

This article introduces a more powerful license statement management tool called NWA. It helps you effortlessly add license headers to your code files and also check, update, and remove existing license statements, ensuring the legality and compliance of your code.

What Is a License Statement?

A license statement (license header) is a comment section at the top of a source code file that declares the licensing information for the code. It typically includes copyright information, license type, and other relevant legal statements. License statements help protect the rights of the code's author and also help other developers understand how they can use the code.

If you've ever looked at code files from open-source projects, you've probably noticed that they clearly mark their license statements within the code files. For example:

kubernetes

spring-boot

Additionally, some open-source projects use tools like GitHub Actions to check if your code has the correct license header when you submit a pull request:

hertz

License Header Adding Tools

Usually, we need to display license statements in the form of comments at the beginning of each code file, similar to what 'kubernetes' and 'spring-boot' did in the previous section. However, when you are working on a large project, the number of code files can become extensive, making manually adding license headers a tedious and painful task.

This is where license header adding tools come in handy. One commonly used tool is the addlicense project under the 'google' organization. 'addlicense' allows you to add license statements to specified files via command-line interaction. However, 'addlicense' has limited functionality; it only adds license headers to files. Some issues raised for 'addlicense' include:

Request for support for line comments (//) instead of only block comments (/**/) #130
Request to add a feature for updating license statements #58
Request for customizable license statement checking logic #56

Unfortunately, issue #58 is not supported due to concerns about adding complexity to 'addlicense', issue #130 is marked as unsupported, and issue #56 is currently awaiting review.

NWA's development took these issues into consideration and provided solutions. It also supports more operations related to license statements, such as removal. You can see how NWA addresses these issues and get started quickly in the Usage section.

Installation

Installation via Go (if you have Go installed)

go install github.com/B1NARY-GR0UP/nwa@latest

Execute the following command to verify a successful installation:

nwa --version

Installation via Docker (if you don't have Go installed)

Installation

Get NWA's Docker image directly:

docker pull ghcr.io/b1nary-gr0up/nwa:main

Alternatively, you can build the image from source, for example:

docker build -t ghcr.io/b1nary-gr0up/nwa:main .

Verify Installation

docker run -it ghcr.io/b1nary-gr0up/nwa:main --version

Mount the directory you want NWA to operate on to /src. Here's an example, but you can learn more about NWA's usage in the Usage section:

docker run -it -v ${PWD}:/src ghcr.io/b1nary-gr0up/nwa:main add -c "RHINE LAB.LLC." -y 2077 .

Usage

To help you get started with NWA's functionality, developers have provided nwa-examples to help you learn how to use NWA in a practical way. You can clone this project and follow the tutorial or simply refer to this guide and use nwa-examples for more usage examples.

NWA is a command-line tool built on cobra. Here's an overview of NWA's commands:

Usage:         
  nwa [command]

Common Mode Commands:
  add         add license headers to files
  check       check license headers of files
  remove      remove license headers of files
  update      update license headers of files

Config Mode Commands:
  config      edit the files according to the configuration file

Additional Commands:
  help        Help about any command

Flags:
  -h, --help      help for nwa
  -v, --version   version for nwa

Use "nwa [command] --help" for more information about a command.

Command List:

Add: Add license headers to files.
Remove: Remove license headers from files.
Update: Update license headers in files.
Check: Check license headers in files.
Config: Edit license headers in files using a configuration file.

Add - Add License Headers to Files

Usage

nwa add [flags] path...

Use the add command after nwa to add license headers. [flags] allows you to specify optional flags, and path... lets you specify one or more file paths to add license headers to.

Example

nwa add -l apache -c "RHINE LAB.LLC." -y 2077 ./server ./utils/bufferpool

In the above example, the command adds the following to all files in the relative paths ./server and ./utils/bufferpool:

License type: Apache 2.0
Copyright holder: RHINE LAB.LLC.
Copyright year: 2077

NWA generates the corresponding license statement for each file based on its type, e.g., .py files use # comments, and .go files use // comments. If your file type is not supported by NWA, you can:

Specify a template file using the -t (--tmpl) flag.
Contribute to NWA by creating an issue or pull request.

NWA will also provide log

outputs indicating files that already have license headers or are not allowed for editing (such as some generated code files).

Flags

The add command supports the following flags:

Short Flag	Long Flag	Default	Description
-c	--copyright	`<COPYRIGHT HOLDER>`	Copyright holder
-l	--license	`apache`	License type
-m	--mute	`false` (unspecified)	Mute mode
-s	--skip	`[]`	Skipped file paths
-t	--tmpl	`""`	Template file path
-y	--year	`time.Now().Year()` (current year)	Copyright year
-h	--help	None	Help

Most flags are self-explanatory. Notable flags are -s (-skip) and -t (-tmpl):

-s's default value is an empty array, so you can use zero or more -s flags to specify file paths to skip. This path supports doublestar syntax, making it very flexible. For example:

nwa add -s **.py -s /example/**/*.txt -c Lorain .

-t allows you to specify a template file path. NWA reads the content of this template file and adds its content to the files that require license headers.

Note: If you specify a template, NWA won't generate license headers based on file types, and it will ignore -c, -l, and -y configurations.

Here's an example of a template file (example-tmpl.txt):

// Copyright 2077 RHINE LAB.LLC.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

For more usage examples, refer to nwa-examples.

Remove - Remove License Headers from Files

Usage

nwa remove [flags] path...

Use the remove command after nwa to remove license headers. [flags] allows you to specify optional flags, and path... lets you specify one or more file paths to remove license headers from.

Example

nwa remove -l mit -c "RHINE LAB.LLC." -s **.py pkg

In the above example, the command removes the following from all non-Python files in the relative path pkg:

License type: MIT
Copyright holder: RHINE LAB.LLC.

NWA provides log outputs indicating files without license headers or files that are not editable.

Flags

The remove command supports the following flags:

Short Flag	Long Flag	Default	Description
-c	--copyright	`<COPYRIGHT HOLDER>`	Copyright holder
-l	--license	`apache`	License type
-m	--mute	`false` (unspecified)	Mute mode
-s	--skip	`[]`	Skipped file paths
-t	--tmpl	`""`	Template file path
-y	--year	`time.Now().Year()` (current year)	Copyright year
-h	--help	None	Help

Note: If you specify a template, NWA won't generate license headers based on file types, and it will ignore -c, -l, and -y configurations.

For more usage examples, refer to nwa-examples.

Update - Update License Headers in Files

Usage

nwa update [flags] path...

Use the update command after nwa to update license headers. [flags] allows you to specify optional flags, and path... lets you specify one or more file paths to update license headers in.

Example

nwa update -l apache -c "BINARY Members" .

In the above example, the command updates the license headers in all files in the current path with the following:

License type: Apache 2.0
Copyright holder: BINARY Members

The previous copyright statement is replaced, regardless of its content.

Note: Update is essentially a combination of Remove and Add operations.

The update command recognizes the content before the first empty line in a file as the license header (with the exception of shebang lines). NWA generates a new license statement based on the specified flags and replaces the existing one.

If the content before the first empty line in your file includes something other than the license statement, it's recommended to use the remove and add operations separately to achieve the same effect. This approach, along with the template file flag, can lead to better removal results in the remove operation.

Flags

The update command supports the following flags:

Short Flag	Long Flag	Default	Description
-c	--copyright	`<COPYRIGHT HOLDER>`	Copyright holder
-l	--license	`apache`	License type
-m	--mute	`false` (unspecified)	Mute mode
-s	--skip	`[]`	Skipped file paths
-t	--tmpl	`""`	Template file path
-y	--year	`time.Now().Year()` (current year)	Copyright year
-h	--help	None	Help

Note: If you specify a template, NWA won't generate license headers based on file types, and it will ignore -c, -l, and -y configurations.

For more usage examples, refer to nwa-examples.

Check - Check License Headers in Files

Usage

nwa check [flags] path...

Use the check command after nwa to check license headers. [flags] allows you to specify optional flags, and path... lets you specify one or more file paths to check license headers in.

Example

nwa check --tmpl tmpl.txt ./client

In the above example, the command checks if license headers in all files within the ./client folder match the content specified in the tmpl.txt template file.

After checking, NWA provides log outputs indicating the result of the check. Here's a sample output:

time="2023-08-25T23:01:49+08:00" level=info msg="skip file" path=README.md
time="2023-08-25T23:01:49+08:00" level=info msg="file has a matched header" path="dirA\\fileA.go"                
time="2023-08-25T23:01:49+08:00" level=info msg="file does not have a matched header" path="dirB\\dirC\\fileC.go"
time="2023-08-25T23:01:49+08:00" level=info msg="file has a matched header" path="dirB\\fileB.go"                
time="2023-08-25T23:01:49+08:00" level=info msg="file does not have a matched header" path=main.go

Flags

The check command supports the following flags:

Short Flag	Long Flag	Default	Description
-c	--copyright	`<COPYRIGHT HOLDER>`	Copyright holder
-l	--license	`apache`	License type
-m	--mute	`false` (unspecified)	Mute mode
-s	--skip	`[]`	Skipped file paths
-t	--tmpl	`""`	Template file path
-y	--year	`time.Now().Year()` (current year)	Copyright year
-h	--help	None	Help

Note: Avoid using the -m flag with the check command, as it will prevent NWA from outputting the check results.

For more usage examples, refer to nwa-examples.

Config - Edit License Headers via Configuration File

Usage

nwa config [flags] path

Use the config command after nwa to edit license headers based on a configuration file. [flags] allows you to specify optional flags, and path is required to specify the path to the configuration file.

Example

nwa config config.yaml

In the above example, the command reads the config.yaml configuration file and edits license headers in specified files according to its content. The structure of the configuration file is provided below.

Flags

Since all configuration is in the configuration file, there's only one help flag.

Short Flag	Long Flag	Default	Description
-h	--help	None	Help

Configuration File

Here's an example of a complete configuration file (config.yaml):

nwa:
  cmd: "add"                        # Default: "add". Options: "add", "check", "remove", "update"
  holder: "RHINE LAB.LLC."          # Default: "<COPYRIGHT HOLDER>"
  year: "2077"                      # Default: Current Year
  license: "apache"                 # Default: "apache"
  mute: false                       # Default: false (unspecified)
  path: ["server", "client", "pkg"] # Default: []
  skip: ["**.py"]                   # Default: []
  tmpl: "nwa.txt"                   # Default: ""

If you don't specify certain fields in the configuration file, NWA will use default values. For example, if you don't specify the license type, Apache 2.0 will be used by default.

Note: If you set the tmpl field, NWA will ignore the holder, year, and license fields.

For more usage examples, refer to nwa-examples.

Conclusion

The above content introduces NWA — A Powerful License Header Management Tool.

If you find this tool helpful, please consider giving our project a star!

If you notice any errors or have questions, feel free to leave a comment or send a message.