DEV Community: huizhou92

Big Tech Is Killing Their Customers

huizhou92 — Mon, 20 Jan 2025 06:20:58 +0000

Recently, Dennis Schubert posted a fiery update about a crisis in the “diaspora*” project. The platform's network infrastructure was collapsing due to heavy traffic. But what caused this overload? Shockingly, 70% of the requests came from LLM (Large Language Model) bots operated by major tech companies. These bots ignored robots.txt directives, relentlessly scraping every data they could access.

Dennis discovered that ChatGPT and Amazon bots even went as far as to scrape the entire edit history of Wiki pages—every single revision. He couldn’t help but ask:

“What are they trying to achieve? Are they analyzing how text evolves?”

This data hoarding significantly strained diaspora*’s servers, slowing the platform for legitimate users. Dennis tried several countermeasures:

Updating robots.txt: Useless, as the bots ignored it.
Rate-limiting: Failed because the bots rotated their IP addresses.
Blocking User Agents: Ineffective, as the bots disguised themselves as regular browsers.

Frustrated, Dennis likened the situation to a DDoS attack on the entire internet.

Why Does Big Tech Need Our Data?

The answer lies in AI’s insatiable hunger for training data.

High-quality datasets are the backbone of AI models, and the industry is running out of fresh material to train on. As OpenAI engineer James Betker once wrote:

As I’ve spent these hours observing the effects of tweaking various model configurations and hyperparameters, one thing that has struck me is the similarities between all the training runs.

It’s becoming clear to me that these models are truly approximating their datasets to an incredible degree

To stay ahead in the AI arms race, tech giants are aggressively scraping data from every corner of the web—personal blogs, independent wikis, and small projects. They don’t just scrape; they strip the internet bare.

Can We Fight Back?

Big Tech has teams of experts balancing web scraping and user experience, but small websites and independent projects lack these resources. For individuals, it’s an uphill battle.

Dennis suggested two unconventional methods to fend off bots:

Tarpit Strategy: Generate meaningless random text to trick bots into wasting resources on irrelevant data.
JavaScript Traps: Serve bot-detected requests with JavaScript-heavy content, embedding scripts that only bots would execute, such as crypto mining code.

While these approaches might work, they’re expensive and technically demanding.

The Zero-Click Internet

What’s Big Tech’s ultimate goal?

To trap users within their ecosystems. By leveraging AI to generate “the best content,” they eliminate the need for users to visit other websites. No more outbound links, no more exploring—their AI serves everything directly, with ads seamlessly integrated.

For individual creators, this means:

SEO doesn’t matter anymore.
High-quality content won’t reach users.
Revenue dries up.

Your work is more than fuel for Big Tech’s data engines in this new reality.

The Inevitable Decline of the Open Web

Big Tech is reshaping the internet, exploiting data while squeezing value out of independent creators. Fighting back is nearly impossible for small websites. The shift is already happening, and it’s irreversible. Ironically, the open web is dying, and the companies that built it are killing it.

References

This version maintains the original tone while aligning with Medium’s concise, conversational style. It’s structured for readability and flows logically to keep readers engaged.

Long Time Link
If you find my blog helpful, please subscribe to me via RSS
Or follow me on X
If you have a Medium account, follow me there. My articles will be published there as soon as possible.

Software Engineering: Hyrum's Law

huizhou92 — Wed, 08 Jan 2025 11:37:45 +0000

/dev
In software development, have you ever encountered a situation where you are developing a shopping cart feature that requires storing product information in a database when a user adds an item? You might have designed a straightforward function as follows:

func addToCart(item Item) {
    // add to db
    ....
}

In this method, you assume that the database storage operation will always succeed without considering potential errors such as connection failures, write errors, or incorrect data formats.

If you assume that the operation will always succeed and do not account for error conditions, you may encounter issues highlighted by Hyrum's Law.

What is Hyrum's Law?

Hyrum's Law is a principle in software development that states:

“When you depend on an API, you also depend on its implementation details.”

In other words, even if an API is defined and documented, the various ways it can be implemented should be considered when using that API. You must consider the implementation details, not just the declared functionality.

Hyrum's Law is named after Google engineer Hyrum Wright, who introduced the concept in a presentation.

Hyrum Wright emphasized that developers should pay more attention to API implementation details, as these aspects can affect their code's future maintainability and stability.

Importance of Hyrum's Law

Hyrum's Law serves several significant purposes:

Awareness of Implementation Details: This reminds developers that it is crucial to understand an API's functionalities, implementation details, and limitations when using it. APIs are commonplace in software development, helping us quickly implement features and improve productivity.
Implications for Code Behavior: How APIs are implemented can significantly affect code behavior and may lead to unforeseen issues. Hyrum’s Law emphasizes the need to evaluate implementation details and stability carefully to prevent potential problems and enhance code maintainability and reliability.
Adaptation to Changes: The law also underscores software development's iterative and evolving nature. As software requirements and technical environments change, API implementations may also grow. Thus, staying abreast of these changes is vital for maintaining software quality and stability.

A Case Study

In Go's source code, there are echoes of Hyrum's Law.

For instance, in ./src/net/http/request.go:1199:

func (e *MaxBytesError) Error() string {  
    // Due to Hyrum's law, this text cannot be changed.  
    return "http: request body too large"  
}

This raises the question: why is it a concern? Changing an error message might affect other users relying on that message.

I have encountered similar issues where upstream database changes in ErrCode affected my business logic.

Practical Recommendations for Hyrum's Law

Here are some suggestions to effectively implement Hyrum’s Law in practice:

Understand API Documentation: Before using an API, carefully read its documentation and specifications to understand its features, uses, limitations, and potential issues.
Write Robust Code: When utilizing APIs, ensure robust error handling and consider various error and exception scenarios to bolster code reliability and stability.
Use Stable API Versions: When multiple API versions are available, opt for stable versions and avoid deprecated or obsolete ones whenever possible.
Conduct Integration and Unit Tests: Write integration and unit tests to validate the API's correctness and stability and promptly address any emerging issues.
Be Aware of API Dependencies: Pay attention to API dependencies, avoiding unnecessary dependencies while ensuring that those you do use are reliable and stable.
Promptly Address API Changes: Stay informed about and adapt to changes in API implementations to maintain software quality and stability amidst evolving requirements.

In summary, adhering to these best practices can help you better apply Hyrum's Law, enhance the maintainability and stability of your code, and adapt to changes and innovations in the software development process.

Anti-Patterns Related to Hyrum's Law

In addition to standard practices, here are some prevalent anti-patterns that detract from the principles of Hyrum’s Law:

Direct Dependency on Implementation: Some developers may ignore API specifications and directly rely on its concrete implementations, leading to tight coupling and increased fragility and maintenance challenges.
Neglecting API Limitations: Failing to consider API limitations and exceptions can result in code uncertainty and unreliability, as developers might assume the API will always function correctly.
Direct Use of Low-Level Libraries: Bypassing API encapsulation by using low-level libraries or components can complicate code and hinder maintainability.
Ignoring API Version Changes: Developers who overlook API version changes may face compatibility issues and maintenance difficulties, risking disconnection from technological advancements.
Unreasonable Additions or Removals of Dependencies: Improperly managed dependencies can create confusion and complexity, hindering maintainability.

Avoiding these anti-patterns can ensure better alignment with Hyrum’s Law, ultimately leading to more maintainable and stable code.

Conclusion

Hyrum's Law is a vital principle that underscores the importance of focusing on a system's core functionalities and considering various dependencies and side effects present within complex systems.

Assuming everything is functioning correctly without accounting for dependencies and side effects can result in unexpected issues that might lead to system failures or other significant problems.

As developers, we must be mindful of the traps posed by Hyrum's Law and consider best practices to ensure the stability and reliability of our code.

In conclusion, Hyrum's Law is of paramount importance. For developers, understanding this principle and applying it in practice will enhance code quality and reliability, subsequently providing users with better experiences.

Long Time Link
If you find my blog helpful, please subscribe to me via RSS
Or follow me on X
If you have a Medium account, follow me there. My articles will be published there as soon as possible.

Debunking the Misconception: Maximum Number of TCP Connections on a Server

huizhou92 — Wed, 04 Dec 2024 07:06:43 +0000

Introduction

There's a widespread misconception:

Since TCP port numbers are 16-bit unsigned integers with a maximum value of 65535, a single server can support at most 65536 TCP socket connections.

Even experienced network programmers may believe this conclusion to be proper. Let's debunk this myth using both theoretical and practical perspectives.

Theoretical Analysis

In *nix systems, each TCP connection is uniquely identified by a 4-tuple structure: {local_ip, local_port, remote_ip, remote_port}.

For IPv4, the system can theoretically manage up to 2^(32 + 16 + 32 + 16) connections—equivalent to 2^96.

IPv4 can be viewed as a 32-bit unsigned number.

Breaking Down the 4-Tuple Limits

A single server typically uses only one local_ip, meaning the server could theoretically manage 2^(16 + 32 + 16) connections.
A single service (e.g., an Nginx process) usually listens on one local_port, which reduces the capacity further to 2^(32 + 16).
If one remote machine (client) connects to a server, fixing local_ip, local_port, and remote_ip leaves only the remote_port variable. Since the remote_port range is 16-bit, there are only 2^16 = 65536 possible connections from a single client to a specific server endpoint.

This limitation is the root of the classic misunderstanding.

For protocols beyond TCP (like UDP), the tuple expands to include the protocol type, making it a 5-tuple, adding even more possibilities.

The actual limits for a server depend on factors beyond the tuple structure.

Practical Limitations

File Descriptors

In Linux, everything is treated as a file, and sockets are no exception. The number of file descriptors determines the maximum number of simultaneous TCP connections.

Maximum file descriptors supported by the system:

   [root@test1 ~]# cat /proc/sys/fs/file-max
   1616352

Maximum file descriptors per process:

   [root@test1 ~]# ulimit -n
   1024

Both values can be modified. For instance, during stress testing, these limits are often increased manually.

ip_local_port_range

When a client connects to the same TCP endpoint (ip:port), each connection requires a unique local TCP endpoint. For clients with a single IP, the available local ports determine the connection limit.

On *nix systems, the default local port range is typically from 32768 to 61000. Check this range using:

[root@test1 ~]# cat /proc/sys/net/ipv4/ip_local_port_range
32768    60999

This means a single client can establish around 30,000 connections to the same server endpoint during stress tests.

Operating systems automatically reuse local ports if multiple distinct remote endpoints (ip:port) are involved.

Memory & CPU

Each TCP socket in the ESTABLISHED state consumes approximately 3.3 KB of memory. While CPU usage for idle connections is minimal, the server's memory capacity significantly impacts the total number of connections.

In practice, hardware resources like memory and CPU limit the maximum number of TCP connections a server can handle, long before reaching the theoretical 4-tuple limit.

Summary

The maximum number of TCP connections a server can support is an astronomical 2^96. However, practical constraints like memory, CPU, file descriptors, and port availability impose far lower limits.

There's no universal number; the limit depends on hardware, configuration, and workload.

The background Photo by Alina Grubnyak on Unsplash

Using JOSE To Protect your APIs 1：JOSE Basics

huizhou92 — Mon, 11 Nov 2024 02:31:16 +0000

With the development of internet technology, data security has become a top priority. Data security covers a broad spectrum, including technical, service, storage, and transmission security. This article focuses on transmission security, specifically how to develop secure APIs.

This article series will include several topics:

Basic Knowledge
Introduction to JOSE, JWT, and JWE
Certificates
How HTTPS Secures Web Applications
OAuth 2.0

The primary content of this article reviews several encryption and verification algorithms, laying a foundation for later practical discussions. Let’s go！

Information Security Algorithms

Encryption Algorithms

Modern cryptography classifies encryption techniques into:

Single-key algorithms
Dual-key algorithms
Keyless algorithms

Single-key algorithms, known as symmetric encryption, use the same key for encryption and decryption.

Dual-key algorithms, or asymmetric encryption, use different keys for encryption and decryption.

Keyless algorithms, also called random key algorithms, generate a unique key for each use, making them an ideal but less common method due to design challenges.

Symmetric Encryption Algorithms

Symmetric encryption, also known as private-key encryption, involves using the same key for encryption and decryption. Standard symmetric encryption algorithms include DES, IDEA (based on DES), 3DES, RC4, RC5, RC6, and AES.

Critical characteristics of symmetric encryption:

Fast, suitable for encrypting extensive data.
The security of the algorithm depends on the key's confidentiality.

Asymmetric Encryption Algorithms

Asymmetric encryption uses a public key for encryption and a private key for decryption. Standard algorithms include RSA, ECC, and DSA.

Critical characteristics of asymmetric encryption:

Slower speed, mainly used for small data encryption.
Higher security.

Data Verification Algorithms

Data verification algorithms fall into three categories: message digests, message authentication, and digital signatures.

Message Digest (MD)

Message digests, or digital digests, use a one-way hash function to "digest" plaintext into a fixed-length encrypted string, also known as a digital fingerprint. Popular hash algorithms include MD2, MD4, MD5, HAVAL, SHA-1, and SHA256.

Key characteristics:

The process is irreversible.
The output length is fixed.
It ensures data integrity.

Message Authentication (MA)

Message authentication ensures that messages have not been altered during transmission or storage. It often uses hash algorithms combined with encryption to verify the integrity of the message.

Standard message authentication algorithms use hash functions with keys, known as [HMAC](http://www.ietf.org/rfc/rfc2104.txt, and combine MD and SHA algorithms with added vital protection.

Key characteristics:

Ensures data integrity and accuracy.
The process is irreversible.
The output length is fixed. ### Digital Signatures (DS)

A digital signature encrypts the message digest using the sender’s private key and sends it with the original message. The receiver decrypts the digest using the sender's public key and compares it to the original message digest.

Key characteristics:

Ensures data integrity, sender authentication, and non-repudiation.
The process is irreversible.

sub summary

Characteristics and examples of each algorithm

Algorithm Type	Features	Example
Symmetric Encryption	Fast, suitable for large data/files	DES, 3DES, AES
Asymmetric Encryption	Slower, suitable for small data	RSA, ECC
Message Digest (MD)	Integrity	MD2, MD4, MD5, SHA1, SHA256
Message Authentication (MA)	Integrity, authenticity	HMAC-MD5, HMAC-SHA1, HMAC-SHA256, HMAC-SHA384
Digital Signature (DS)	Integrity, authenticity, non-repudiation	RSA, DSA, ECDSA

Evolution of Security Solutions

1. Symmetric Encryption

After the development of the Internet, some enterprises began to focus on security, based on symmetric encryption algorithms, designed this program.

The whole process involves only the AES (symmetric) algorithm, only and encrypts the data in transit. As shown in the figure:

Security

Security Item	Description
Data Security	Achieved through AES
Data Integrity	Not ensured
Data Authenticity	Not ensured, vulnerable to key exposure

There are many drawbacks to this program.

single key can not realize dynamic key management
Unable to verify data integrity
After the key is exposed, the security of the whole program will not be broken.

2. Symmetric Encryption + Message Digest

This solution adds a message digest to ensure data integrity, but the other issues remain.

Security

Security Item	Description
Data Security	Achieved through AES
Data Integrity	Realized through information summaries
Data Authenticity	Not ensured, vulnerable to key exposure

drawback

single key can not realize dynamic key management
After the key is exposed, the security of the whole program will not be broken.

3. Symmetric Encryption + Message Authentication

Symmetric encryption + message digest is used when the security requirements are not exceptionally high. However, there is room for improvement for industries with particularly high-security requirements, such as finance, education, and other sectors. Therefore, people have improved the digest mechanism, the message digest with message authentication code to replace the formation of HTTP + symmetric encryption + message authentication scheme; this scheme is characterized by message authentication code to replace the digest, based on the ordinary digest to increase the two-way checksum, to ensure the authenticity of the data.

The security and disadvantages are similar to the second scheme.

4. Asymmetric Encryption

Asymmetric encryption solves the issue of key exposure by using a public-private key pair, providing higher security but at the cost of performance.

Security

Security Item	Description
Data Security	Achieved via RSA
Data Integrity (Tamper-proof)	Achieved via RSA
Data Authenticity (Anti-forgery)	Achieved through RSA public and private key pairing

drawback

Poor performance, slow speed
Not suitable for extensive data or file encryption/decryption ### 5. Symmetric Encryption + Message Authentication + Asymmetric Encryption

All of the above schemes have flaws, which stem from the encryption algorithms, so is there a way to combine symmetric and asymmetric encryption to complement each other's weaknesses? The answer is yes; human wisdom is infinite, so this scheme comes to mind:

The message is encrypted with symmetric encryption, and the key of the symmetric algorithm is encrypted with asymmetric encryption so that efficiency and security are considered. As shown in the figure below, using AES + authentication + RSA as an example:

Security:

Security Item	Description
Data Security	Achieved through AES and RSA
Data Integrity	Ensured via HMAC
Data Authenticity	Ensured with RSA public-private key pair

The solution is secure enough to meet the vast majority of security requirements. Many companies use this type of program now.

AES encryption of the original message, fast
HMAC on the AES result authentication code to ensure the authenticity of the data
each time the keys of AES and HMAC are randomly generated, to achieve the effect of dynamic keys
the RSA algorithm guarantees the security of the key, and the data is small, to play the advantages of RSA
the key of RSA is two groups, realizing two-way authentication.

Conclusion

This article outlines the basics of encryption algorithms, including symmetric and asymmetric encryption, message authentication, and digital signatures. It also explores the evolution of security solutions, illustrating how modern transmission security balances performance and security. These concepts provide the groundwork for developing secure APIs in future discussions.

SwissTable: A High-Performance Hash Table Implementation

huizhou92 — Thu, 03 Oct 2024 02:59:20 +0000

Introduction

In 2022, ByteDance proposed an issue recommending that Golang adopt SwissTable for its map implementation. In 2023, Dolt published a blog post titled SwissMap: A Smaller, Faster Golang Hash Table, detailing their design of a swisstable, which garnered widespread attention. The Go core team is reevaluating the swisstable design and has added some related code in the runtime. With some free time during the holidays, let's delve deeper into the principles, compare it to the runtime map, and understand why it might become the standard for map implementation.

This article was first published in the Medium MPP plan. If you are a Medium user, please follow me on Medium. Thank you very much.

This article will not fully explain the principles of hashtable or swisstable. A basic understanding of hashtable is required.

A hashtable provides a mapping from a key to a corresponding value by converting the key to some "position" using a hash function. From this position, we can directly retrieve the desired value.

Traditional `Hashtable`

A hashtable provides a mapping from a key to a corresponding value by converting the key to some "position" using a hash function. However, even if the hash function is perfect, conflicts are still inevitable when mapping an infinite number of keys into a finite memory space: two different keys will be mapped to the same position. To solve this, traditional hashtables have several conflict resolution strategies, most commonly chaining and linear probing.

Chaining

Chaining is the most common method where if multiple keys map to the same position, these keys and values are stored in a linked list. During lookups, the hash function is used to find the position, and then the linked list at that position is traversed to find the matching key. Its structure is similar to this:

Figure 1: Chaining implementation of hashtable

Chaining is straightforward to implement, with fewer boundary conditions to consider. Data insertion and deletion are quick, using head insertion to add new entries and adjusting the next pointer for deletion. Chaining can also prevent performance degradation by converting overly long chains into search trees. However, chaining is not cache-friendly, and performance can be affected if there are many conflicts. Different slots can be widely spread in memory, leading to poor spatial locality of the data structure overall.

Linear Probing

Linear probing is another standard hash table conflict resolution method. Unlike chaining, when a hash conflict occurs, it searches sequentially from the conflict position until it finds an empty slot or loops back to the conflict position. At this point, it resizes and rehashes the entries.

Figure 2: Linear probing animation

Lookups work similarly: calculate the hash position for the key and then compare each key starting from that position, skipping any deleted entries until an empty slot is reached, indicating the key is not in the table. Deletion uses a tombstone marker.

Figure 3: Linear probing lookup animation

Linear probing has comparable time complexity to chaining. Its advantages include being cache-friendly and implementable with tight data structures like arrays. However, its drawbacks are:

Complex implementation with three states for a slot: occupied, empty, and deleted.
Chain reaction of conflicts, leading to more frequent resizing than chaining and potentially more significant memory usage.
Higher likelihood of lookup process degradation to O(n) without the ability to convert heavily conflicted areas into search trees.

Many libraries use chaining due to the difficulties with element deletion and conflict chain reactions in linear probing. Despite its drawbacks, linear probing's cache friendliness and memory efficiency provide significant performance advantages on modern computers, leading to its use in languages like golang and Python.

Go Map Data Storage

Let's recap how Go Map stores data:

*Figure 4: Go map *

Quick summary:

Go map uses a hash function to map keys to multiple buckets, each with a fixed number of key-value slots for storage.
Each bucket stores up to 8 key-value pairs. The conflicting keys and values are stored within the same bucket when conflicts occur.
The map uses a hash function to compute the key's hash value and locate the corresponding bucket.
If a bucket is complete (all 8 slots used), an overflow bucket is generated to continue storing new key-value pairs.
For lookups, the key's hash value is calculated, the corresponding bucket is determined, and each slot within the bucket is checked. If there is an overflow bucket, its keys are also checked sequentially.

SwissTable: An Efficient Hashtable Implementation

SwissTable is a hashtable implementation based on an improved linear probing method. Its core idea is to optimize performance and memory usage by enhancing the hashtable structure and metadata storsage. SwissTable uses a new metadata control mechanism to significantly reduce unnecessary key comparisons and leverages SIMD instructions to boost throughput.

Reviewing the two standard hashtable implementations shows they either waste memory, need to be cache-friendly or suffer performance drops in lookup, insertion, and deletion operations after conflicts. These issues persist even with a "perfect hash function." Using a suboptimal hash function dramatically increases the probability of key conflicts and worsens performance, possibly even falling short of linear searches in an array.

The industry sought a hash table algorithm that was friendly to cache and resistant to lookup performance degradation. Many focused on developing better hash functions close to "perfect hash function" quality while optimizing calculation performance; others worked on improving the hash table's structure to balance cache friendliness, performance, and memory usage. swisstable belongs to the latter.

SwissTable's time complexity is similar to linear probing, while its space complexity is between chaining and linear probing. The implementation I've referenced is primarily based on dolthub/swiss.

Basic Structure of SwissTable

Although the name has changed, swisstable is still a hashtable utilizing an improved linear probing method for hash collisions. Its underlying structure resembles an array. Now, let's delve into the structure of swisstable:

type Map[K comparable, V any] struct {  
    ctrl     []metadata  
    groups   []group[K, V]  
    hash     maphash.Hasher[K]  
    resident uint32   
    dead     uint32   
    limit    uint32   
} 

type metadata [groupSize]int8  

type group[K comparable, V any] struct {  
    keys   [groupSize]K  
    values [groupSize]V  
}

In swisstable, ctrl is an array of metadata, corresponding to the group[K, V] array. Each group has 8 slots.

The hash is divided into 57 bits for H1 to determine the starting groups, and the remaining 7 bits called H2, stored in metadata as the hash signature of the current key for subsequent search and filtering.

The key advantage of swisstable over traditional hash tables lies in the metadata called ctrl. Control information includes:

Whether a slot is empty: 0b10000000
Whether a slot has been deleted: 0b11111110
The key's hash signature (H2) in a slot: 0bh2

The unique values of these states allow the use of SIMD instructions, maximizing performance.

Adding Data

The process of adding data in swisstable involves several steps:

Calculate the hash value and split it into h1 and h2. Using h1, determine the starting groups.
Use metaMatchH2 to check the current group's metadata for a matching h2. If found, further check for the matching key and update the value if they match.
If no matching key is found, use metaMatchEmpty to check for empty slots in the current group. Insert the new key-value pair if an empty slot is found and update the metadata and resident count.
If no empty slots are available in the current group, perform linear probing to check the next groups.

func (m *Map[K, V]) Put(key K, value V) {  
    if m.resident >= m.limit {  
        m.rehash(m.nextSize())  
    }  
    hi, lo := splitHash(m.hash.Hash(key))  
    g := probeStart(hi, len(m.groups))  
    for { // inlined find loop  
        matches := metaMatchH2(&m.ctrl[g], lo)  
        for matches != 0 {  
            s := nextMatch(&matches)  
            if key == m.groups[g].keys[s] { // update  
                m.groups[g].keys[s] = key  
                m.groups[g].values[s] = value  
                return  
            }  
        }  
        matches = metaMatchEmpty(&m.ctrl[g])  
        if matches != 0 { // insert  
            s := nextMatch(&matches)  
            m.groups[g].keys[s] = key  
            m.groups[g].values[s] = value  
            m.ctrl[g][s] = int8(lo)  
            m.resident++  
            return  
        }  
        g += 1 // linear probing  
        if g >= uint32(len(m.groups)) {  
            g = 0  
        }  
    }  
}
func metaMatchH2(m *metadata, h h2) bitset {  
    return hasZeroByte(castUint64(m) ^ (loBits * uint64(h)))  
}

func nextMatch(b *bitset) uint32 {  
    s := uint32(bits.TrailingZeros64(uint64(*b)))  
    *b &= ^(1 << s)  
    return s >> 3   
}

Although the steps are few, they involve complex bit operations. Normally, h2 needs to be compared with all keys sequentially until the target is found. swisstable cleverly achieves this by:

Multiplying h2 by 0x0101010101010101 to get a uint64, allowing simultaneous comparison with 8 ctrl values.
Performing xor with meta. If h2 exists in metadata, the corresponding bit will be zero. The metaMatchH2 function helps us understand this process.

func TestMetaMatchH2(t *testing.T) {
    metaData := make([]metadata, 2)
    metaData[0] = [8]int8{0x7f, 0, 0, 0x7f, 0, 0, 0, 0x7f}
    m := &metaData[0]
    h := 0x7f
    metaUint64 := castUint64(m)
    h2Pattern := loBits * uint64(h)
    xorResult := metaUint64 ^ h2Pattern
    fmt.Printf("metaUint64: %b\n", xorResult)
    r := hasZeroByte(xorResult)
    fmt.Printf("r: %b\n", r)
    for r != 0 {  
        fmt.Println(nextMatch(&r))  
    }
}
----
output
// metaUint64: 00000000 11111110 11111110 11111110 0000000 01111111 01111111 00000000
// r: 10000000 00000000 00000000 00000000 10000000 00000000 00000000 10000000
// 0
// 3
// 7

Advantages of SwissTable

Reviewing SwissTable implementation reveals several key benefits:

Operations are shifted from slots to ctrl, which are smaller and easily placed in the CPU cache, speeding up operations despite the additional step of locating slots.
Records hash signatures, reducing meaningless key comparisons—the main cause of linear probing performance drops.
Batch operations on ctrl for slots increase throughput significantly.
Metadata and memory layout are optimized for SIMD instructions, maximizing performance.
Slot optimizations, such as compressing large data, increase cache hit rates.

swisstable solves spatial locality issues and exploits modern CPU features for batch element operations, significantly boosting performance.

Finally, running a benchmark on a local MacBook M1 (without SIMD support) shows significant performance improvements in large map scenarios.

Figure 5: Official swisstable benchmark

Conclusion

Currently, the official implementation of swisstable in Go is still under discussion, and there are a few community implementations like concurrent-swiss-map and swiss. However, they are not perfect; in small map scenarios, swisstable may even underperform compared to runtime_map. Nonetheless, the potential demonstrated by swisstable in other languages indicates that it is worth anticipation.

References

Dolthub: SwissMap
SwissTable principles: Abseil SwissTables
Original SwissTable proposal at cppcon: cppcon talk
Improvements to SwissTable algorithm: YouTube link
Bit manipulation primer: Stanford Bit Hacks
Hash function comparisons: Hash function tests
An additional bit manipulation article: Fast Modulo Reduction

Decrypt Go: varint

huizhou92 — Fri, 20 Sep 2024 09:51:21 +0000

Recently, I discovered that the Go standard library includes a built-in implementation of varint, found in encoding/binary/varint.go. This implementation is similar to the varint used in protobuf. Using the Golang standard library's varint source code, we will systematically learn and review the concept of varint.

If you're familiar with protobuf, you probably already know that all integer types (except fixed types like fixed32 and fixed64) are encoded using varint.

varint mainly solves two issues:

Space Efficiency: Take uint64 as an example, representing values as large as 18,446,744,073,709,551,615. In most real-world scenarios, however, our integer values are much smaller. If your system needs to process values as low as 1, you'd still use 8 bytes to represent this value in transmission, wasting space since most bytes store no useful data. varint encoding uses a variable-length byte sequence to represent integers, reducing the space required for smaller values.
Compatibility: varint allows us to handle integers of different sizes without altering the encoding/decoding logic. This means fields can be upgraded from smaller types (like uint32) to larger ones (like uint64) without breaking backward compatibility.

This article will dive into Golang varint implementation, exploring its design principles and how it addresses the challenges of encoding negative numbers.

This article was first published under the Medium MPP plan. Follow me on Medium if you're a Medium user.

The Design Principles of varint

varint is designed based on simple principles:

7-bit Grouping: The binary representation of an integer is divided into 7-bit groups. From the least significant bit to the most significant bit, every 7-bit group becomes a unit.
Continuation Bit: A flag bit is added before each 7-bit group, forming an 8-bit byte. If more bytes follow, the flag bit is set to 1; otherwise, it’s set to 0. For example, the integer uint64(300) has a binary representation of 100101100. Dividing this into two groups—10 and 0101100—and adding flag bits results in two bytes: 00000010 and 10101100, which is the varint encoding of 300. Compared to uint64, which uses 4 bytes, varint reduces the storage by 75%. list1: uint64 to varint

func main() {  
    v := uint64(300)  
    bytes := make([]byte, 0)  
    bytes = binary.AppendUvarint(bytes, v)  
    fmt.Println(len(bytes))  
    for i := len(bytes); i > 0; i-- {  
       fmt.Printf("%08b ", bytes[i-1])  
    }  
}

`varint` for Unsigned Integers

The Go standard library provides two sets of varint functions: one for unsigned integers (PutUvarint, Uvarint) and another for signed integers (varint, Putvarint).

Let's first look at the unsigned integer varint implementation:

list2: go src PutUvarint

func PutUvarint(buf []byte, x uint64) int {
    i := 0
    for x >= 0x80 {
        buf[i] = byte(x) | 0x80
        x >>= 7
        i++
    }
    buf[i] = byte(x)
    return i + 1
}

There is a very important constant in the code: 0x80, which corresponds to the binary code 1000 0000. This constant is very important for the logic that follows:

x >= 0x80: This checks if x requires more than 7 bits for representation. If it does, x needs to be split.
byte(x) | 0x80: This applies a bitwise OR with 0x80 (1000 0000), ensuring the highest bit is set to 1 and extracting the lowest 7 bits of x.
x >>= 7: Shift x right by 7 bits to process the next group.
buf[i] = byte(x): When the loop ends, the highest bits are all zeros, so no further action is needed.

Uvarint is the reverse of PutUvarint.

It should be noted that: varint splits integers into 7-bit groups, meaning large integers may face inefficiencies. For example, uint64's maximum value requires 10 bytes instead of the usual 8 (64/7 ≈ 10).

Encoding Negative Numbers: Zigzag Encoding

Though varint is efficient, it doesn’t account for negative numbers. In computing, numbers are stored as two’s complement, which means a small negative number might have a sizeable binary representation.

For example, -5 in 32-bit form is represented as 11111111111111111111111111111011, requiring 5 bytes in varint encoding

Go uses zigzag encoding to solve this problem:

For positive numbers n, map them to 2n.
For negative numbers -n, map them to 2n-1. This way, positive and negative numbers alternate without conflict, hence the name zigzag encoding. For example, after zigzag encoding int32(-5), the value becomes 9 (00000000000000000000000000001001), which varint can represent with just 1 byte.

Here’s the Golang implementation:

list3: go src Putvarint

func Putvarint(buf []byte, x int64) int {
    ux := uint64(x) << 1
    if x < 0 {
        ux = ^ux
    }
    return PutUvarint(buf, ux)
}

From the code, we can see that for the implementation of varint for signed integers, the Go standard library breaks it down into two steps:

First, the integer is converted using ZigZag encoding.
Then, the converted value is encoded using varint.

For negative numbers, there is an extra step: ux = ^ux. This part might be confusing—why does this transformation result in 2n - 1?

We can roughly deduce the process, assuming we have an integer -n:

First, the original value is shifted left, then inverted. This can be viewed as: first invert the value, then shift left, and finally add 1. This results in 2*(~(-n)) + 1.
the two’s complement of a negative number is the bitwise inversion of its absolute value plus 1. So, how do we derive the absolute value from the two’s complement? There is a formula: |A| = ~A + 1.
Substituting this formula into the first step: 2*(n - 1) + 1 = 2n - 1. This perfectly matches the ZigZag encoding for negative numbers (mathematics is indeed excellent).

In the Go standard library, calling PutUvarint only applies varint encoding, while calling PutVarint first applies ZigZag encoding and then varint encoding.

In protobuf, if the type is int32, int64, uint32, or uint64, only varint encoding is used. However, for sint32 and sint64, ZigZag encoding is applied first, followed by varint encoding.

When `varint` Is Not Suitable

Despite its benefits, varint isn't ideal for all scenarios:

Large integers: varint can be less efficient than fixed-length encoding for huge numbers.
Random data access: Since varint uses variable lengths, indexing specific integers directly is challenging.
Frequent mathematical operations: varint-encoding data requires decoding before operations, potentially affecting performance.
Security-sensitive applications: varint encoding may leak information about the original integer's size, which could be unacceptable in secure environments.

Decrypt Go: empty struct

huizhou92 — Wed, 11 Sep 2024 02:45:16 +0000

In Go, a normal struct typically occupies a block of memory. However, there's a special case: if it's an empty struct, its size is zero. How is this possible, and what is the use of an empty struct?

This article is first published in the medium MPP plan. If you are a medium user, please follow me in medium. Thank you very much.

type Test struct {
    A int
    B string
}

func main() {
    fmt.Println(unsafe.Sizeof(new(Test)))
    fmt.Println(unsafe.Sizeof(struct{}{}))
}

/*
8
0
*/

The Secret of the Empty Struct

Special Variable: zerobase

An empty struct is a struct with no memory size. This statement is correct, but to be more precise, it actually has a special starting point: the zerobase variable. This is a uintptr global variable that occupies 8 bytes. Whenever countless struct {} variables are defined, the compiler assigns the address of this zerobase variable. In other words, in Go, any memory allocation with a size of 0 uses the same address, &zerobase.

Example

package main

import "fmt"

type emptyStruct struct {}

func main() {
    a := struct{}{}
    b := struct{}{}
    c := emptyStruct{}

    fmt.Printf("%p\n", &a)
    fmt.Printf("%p\n", &b)
    fmt.Printf("%p\n", &c)
}

// 0x58e360
// 0x58e360
// 0x58e360

The memory addresses of variables of an empty struct are all the same. This is because the compiler assigns &zerobase during compilation when encountering this special type of memory allocation. This logic is in the mallocgc function:

//go:linkname mallocgc  
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {  
    ...
    if size == 0 {  
       return unsafe.Pointer(&zerobase)  
    }
    ...

This is the secret of the Empty struct. With this special variable, we can accomplish many functionalities.

Empty Struct and Memory Alignment

Typically, if an empty struct is part of a larger struct, it doesn't occupy memory. However, there's a special case when the empty struct is the last field; it triggers memory alignment.

Example

type A struct {
    x int
    y string
    z struct{}
}
type B struct {
    x int
    z struct{}
    y string
}

func main() {
    println(unsafe.Alignof(A{}))
    println(unsafe.Alignof(B{}))
    println(unsafe.Sizeof(A{}))
    println(unsafe.Sizeof(B{}))
}

/**
8
8
32
24
**/

When a pointer to a field is present, the returned address may be outside the struct, potentially leading to memory leaks if the memory is not freed when the struct is released. Therefore, when an empty struct is the last field of another struct, additional memory is allocated for safety. If the empty struct is at the beginning or middle, its address is the same as the next variable.

type A struct {  
    x int  
    y string  
    z struct{}  
}  
type B struct {  
    x int  
    z struct{}  
    y string  
}  

func main() {  
    a := A{}  
    b := B{}  
    fmt.Printf("%p\n", &a.y)  
    fmt.Printf("%p\n", &a.z)  
    fmt.Printf("%p\n", &b.y)  
    fmt.Printf("%p\n", &b.z)  
}

/**
0x1400012c008
0x1400012c018
0x1400012e008
0x1400012e008
**/

Use Cases of the Empty Struct

The core reason for the existence of the empty struct struct{} is to save memory. When you need a struct but don't care about its contents, consider using an empty struct. Go's core composite structures such as map, chan, and slice can all use struct{}.

`map` & `struct{}`

// Create map
m := make(map[int]struct{})
// Assign value
m[1] = struct{}{}
// Check if key exists
_, ok := m[1]

`chan` & `struct{}`

A classic scenario combines channel and struct{}, where struct{} is often used as a signal without caring about its content. As analyzed in previous articles, the essential data structure of a channel is a management structure plus a ring buffer. The ring buffer is zero-allocated if struct{} is used as an element.

The only use of chan and struct{} together is for signal transmission since the empty struct itself cannot carry any value. Generally, it's used with no buffer channels.

// Create a signal channel
waitc := make(chan struct{})

// ...
goroutine 1:
    // Send signal: push element
    waitc <- struct{}{}
    // Send signal: close
    close(waitc)

goroutine 2:
    select {
    // Receive signal and perform corresponding actions
    case <-waitc:
    }

In this scenario, is struct{} absolutely necessary? Not really, and the memory saved is negligible. The key point is that the element value of chan is not cared about, hence struct{} is used.

Summary

An empty struct is still a struct, just with a size of 0.
All empty structs share the same address: the address of zerobase.
We can leverage the empty struct's non-memory-occupying feature to optimize code, such as using maps to implement sets and channels.

References

RPC Action EP2: Using Protobuf and Creating a Custom Plugin

huizhou92 — Mon, 09 Sep 2024 10:25:23 +0000

In the previous article, I implemented a simple RPC interface using the net/rpc package and tried out the Gob encoding that comes with net/rpc and JSON encoding to learn some basics of Golang RPC. In this post, I'll combine net/rpc with protobuf and create my protobuf plugin to help us generate code, so let's get started.

This article was first published in the Medium MPP plan. If you are a Medium user, please follow me on Medium. Thank you very much.

We must have used gRPC and protobuf during our work, but they are not bound. gRPC can be encoded using JSON, and protobuf can be implemented in other languages.

Protocol Buffers (Protobuf) is a free and open-source cross-platform data format used to serialize structured data. It is useful in developing programs that communicate with each other over a network or for storing data. The method involves an interface description language that describes the structure of some data and a program that generates source code from that description for generating or parsing a stream of bytes that represents the structured data.

An example of using protobuf

First we write a proto file hello-service.proto that defines a message "String"

syntax = "proto3";
package api;
option  go_package="api";

message String {
  string value = 1;
}

Then use the protoc utility to generate the Go code for the message String

protoc --go_out=. hello-service.proto

Then we modify the Hello function's arguments to use the String generated by the protobuf file.

type HelloServiceInterface = interface {  
    Hello(request api.String, reply *api.String) error  
}

Using it is no different from before, even, it is not as convenient as using string directly. So why should we use protobuf? As I said earlier, using Protobuf to define language-independent RPC service interfaces and messages, and then using the protoc tool to generate code in different languages, is where its real value lies. For example, use the official plugin protoc-gen-go to generate gRPC code.

protoc --go_out=plugins=grpc. hello-service.proto

Plugin system for protoc

To generate code from protobuf files, we must install the protoc , but the protoc doesn't know what our target language is, so we need plugins to help us generate code. how does protoc's plugin system work? Take the above grpc as an example.

There is a --go_out parameter here. Since the plugin we're calling is protoc-gen-go, the parameter is called go_out; if the name was XXX, the parameter would be called XXX_out.

When protoc is running, it will first parse the protobuf file and generate a set of Protocol Buffers-encoded descriptive data. It will first determine whether or not the go plugin is included in protoc, and then it will try to look for protoc-gen-go in $PATH, and if it can't find it, it will report an error, and then it will run protoc-gen-go. protoc-gen-go command and sends the description data to the plugin command via stdin. After the plugin generates the file contents, it then inputs Protocol Buffers encoded data to stdout to tell protoc to generate the specific file.

plugins=grpc is a plugin that comes with protoc-gen-go in order to invoke it. If you don't use it, it will only generate a message in Go, but you can use this plugin to generate grpc-related code.

Customize a protoc plugin

If we add Hello interface timing to protobuf, can we customize a protoc plugin to generate code directly?

syntax = "proto3";  
package api;  
option  go_package="./api";  
service HelloService {  
  rpc Hello (String) returns (String) {}  
}  
message String {  
  string value = 1;
}

Objective

For this article, my goal was to create a plugin that would then be used to generate RPC server-side and client-side code that would look something like this.

// HelloService_rpc.pb.go
type HelloServiceInterface interface {  
    Hello(String, *String) error  
}  

func RegisterHelloService(  
    srv *rpc.Server, x HelloServiceInterface,  
) error {  
    if err := srv.RegisterName("HelloService", x); err != nil {  
       return err  
    }  
    return nil  
}  

type HelloServiceClient struct {  
    *rpc.Client  
}  

var _ HelloServiceInterface = (*HelloServiceClient)(nil)  

func DialHelloService(network, address string) (  
    *HelloServiceClient, error,  
) {  
    c, err := rpc.Dial(network, address)  
    if err != nil {  
       return nil, err  
    }  
    return &HelloServiceClient{Client: c}, nil  
}  

func (p *HelloServiceClient) Hello(  
    in String, out *String,  
) error {  
    return p.Client.Call("HelloService.Hello", in, out)  
}

This would change our business code to look like the following

// service
func main() {  
    listener, err := net.Listen("tcp", ":1234")  
    if err != nil {  
       log.Fatal("ListenTCP error:", err)  
    }  
    _ = api.RegisterHelloService(rpc.DefaultServer, new(HelloService))  
    for {  
       conn, err := listener.Accept()  
       if err != nil {  
          log.Fatal("Accept error:", err)  
       }  
       go rpc.ServeConn(conn)  
    }  
}  

type HelloService struct{}  

func (p *HelloService) Hello(request api.String, reply *api.String) error {  
    log.Println("HelloService.proto Hello")  
    *reply = api.String{Value: "Hello:" + request.Value}  
    return nil  
}
// client.go
func main() {  
    client, err := api.DialHelloService("tcp", "localhost:1234")  
    if err != nil {  
       log.Fatal("net.Dial:", err)  
    }  
    reply := &api.String{}  
    err = client.Hello(api.String{Value: "Hello"}, reply)  
    if err != nil {  
       log.Fatal(err)  
    }  
    log.Println(reply)  
}

Based on the generated code, our workload is already much smaller and the chances of error are already very small. A good start.

Based on the api code above, we can pull out a template file:

const tmplService = `  
import (  
    "net/rpc")  
type {{.ServiceName}}Interface interface {  
func Register{{.ServiceName}}(  
    if err := srv.RegisterName("{{.ServiceName}}", x); err != nil {        return err    }    return nil}  
    *rpc.Client}  
func Dial{{.ServiceName}}(network, address string) (  
{{range $_, $m := .MethodList}}  
    return p.Client.Call("{{$root.ServiceName}}.{{$m.MethodName}}", in, out)}  
`

The whole template is clear, and there are some placeholders in it, such as MethodName, ServiceName, etc., which we'll cover later.

How to develop a plug-in?

Google released the Go language API 1, which introduces a new package google.golang.org/protobuf/compile R/protogen, which greatly reduces the difficulty of plugins development:

First of all, we create a go language project, such as protoc-gen-go-spprpc
Then we need to define a protogen.Options, then call its Run method, and pass in a func(*protogen.Plugin) error callback. This is the end of the main process code.
We can also set the ParamFunc parameter of protogen.Options, so that protogen will automatically parse the parameters passed by the command line for us. Operations such as reading and decoding protobuf information from standard input, encoding input information into protobuf and writing stdout are all handled by protogen. What we need to do is to interact with protogen.Plugin to implement code generation logic.

The most important thing for each service is the name of the service, and then each service has a set of methods. For the method defined by the service, the most important thing is the name of the method, as well as the name of the input parameter and the output parameter type. Let's first define a ServiceData to describe the meta information of the service:

// ServiceData 
type ServiceData struct {  
    PackageName string  
    ServiceName string  
    MethodList  []Method  
}
// Method 
type Method struct {  
    MethodName     string  
    InputTypeName  string  
    OutputTypeName string  
}

Then comes the main logic, and the code generation logic, and finally the call to tmpl to generate the code.

func main() {  
    protogen.Options{}.Run(func(gen *protogen.Plugin) error {  
       for _, file := range gen.Files {  
          if !file.Generate {  
             continue  
          }  
          generateFile(gen, file)  
       }  
       return nil  
    })  
}  

// generateFile function definition
func generateFile(gen *protogen.Plugin, file *protogen.File) {  
    filename := file.GeneratedFilenamePrefix + "_rpc.pb.go"  
    g := gen.NewGeneratedFile(filename, file.GoImportPath)  
    tmpl, err := template.New("service").Parse(tmplService)  
    if err != nil {  
       log.Fatalf("Error parsing template: %v", err)  
    }  
    packageName := string(file.GoPackageName)  
// Iterate over each service to generate code
    for _, service := range file.Services {  
       serviceData := ServiceData{  
          ServiceName: service.GoName,  
          PackageName: packageName,  
       }  
       for _, method := range service.Methods {  
          inputType := method.Input.GoIdent.GoName  
          outputType := method.Output.GoIdent.GoName  

          serviceData.MethodList = append(serviceData.MethodList, Method{  
             MethodName:     method.GoName,  
             InputTypeName:  inputType,  
             OutputTypeName: outputType,  
          })  
       }  
// Perform template rendering
       err = tmpl.Execute(g, serviceData)  
       if err != nil {  
          log.Fatalf("Error executing template: %v", err)  
       }  
    }  
}

Debug plugin

Finally, we put the compiled binary execution file protoc-gen-go-spprpc in $PATH, and then run protoc to generate the code we want.

protoc --go_out=.. --go-spprpc_out=.. HelloService.proto

Because protoc-gen-go-spprpc has to depend on protoc to run, it's a bit tricky to debug. We can use

fmt.Fprintf(os.Stderr, "Fprintln: %v\n", err)

To print the error log to debug.

Summary

That's all there is to this article. We first implemented an RPC call using protobuf and then created a protobuf plugin to help us generate the code. This opens the door for us to learn protobuf + RPC, and is our path to a thorough understanding of gRPC. I hope everyone can master this technology.

Reference

RPC Action EP1: Implement a simple RPC interface in Go

huizhou92 — Mon, 09 Sep 2024 08:25:49 +0000

RPC(Remote Procedure Call)is a widely used communication method between different nodes in distributed systems and a foundational technology of the Internet era. Go's standard library provides a simple implementation of RPC under the net/rpc package. This article aims to help you understand RPC by walking you through implementing a simple RPC interface using the net/rpc package.

This article was first published in the Medium MPP plan. If you are a Medium user, please follow me on Medium. Thank you very much.

To enable a function to be remotely called in net/rpc, it must meet the following five conditions:

The method’s type is exported.

The method is exported.

The method has two arguments, both of which are exported (or built-in) types.

The method’s second argument is a pointer.

The method has a return type of error.

In other words, the function signature must be:

func (t *T) MethodName(argType T1, replyType *T2) error

Creating a Simple RPC Request

Based on these five conditions, we can construct a simple RPC interface:

type HelloService struct{}  
func (p *HelloService) Hello(request string, reply *string) error {  
    log.Println("HelloService Hello")  
    *reply = "hello:" + request  
    return nil  
}

Next, you can register an object of the HelloService type as an RPC service:

func main() {
    _ = rpc.RegisterName("HelloService", new(HelloService))  
    listener, err := net.Listen("tcp", ":1234")  
    if err != nil {  
        log.Fatal("ListenTCP error:", err)  
    }  
    for {  
        conn, err := listener.Accept()  
        if err != nil {  
           log.Fatal("Accept error:", err)  
        }  
        go rpc.ServeConn(conn)  
    }
}

The client-side implementation is as follows:

func main() {
    conn, err := net.Dial("tcp", ":1234")
    if err != nil {
        log.Fatal("net.Dial:", err)
    }
    client := rpc.NewClient(conn)
    var reply string
    err = client.Call("HelloService.Hello", "hello", &reply)
    if err != nil {
        log.Fatal(err)
    }
    fmt.Println(reply)
}

First, the client dials the RPC service using rpc.Dial, then invokes a specific RPC method via client.Call(). The first parameter is the RPC service name and method name combined with a dot, the second is the input, and the third is the return value, which is a pointer. This example demonstrates how easy it is to use RPC.

In both the server and client code, we need to remember the RPC service name HelloService and the method name Hello. This can easily lead to errors during development, so we can wrap the code slightly by abstracting the common parts. The complete code is as follows:

// server.go
const ServerName = "HelloService"  

type HelloServiceInterface = interface {  
    Hello(request string, reply *string) error  
}  

func RegisterHelloService(srv HelloServiceInterface) error {  
    return rpc.RegisterName(ServerName, srv)  
}  

type HelloService struct{}  

func (p *HelloService) Hello(request string, reply *string) error {  
    log.Println("HelloService Hello")  
    *reply = "hello:" + request  
    return nil  
}

func main() {  
    _ = RegisterHelloService(new(HelloService))  
    listener, err := net.Listen("tcp", ":1234")  
    if err != nil {  
       log.Fatal("ListenTCP error:", err)  
    }  
    for {  
       conn, err := listener.Accept()  
       if err != nil {  
          log.Fatal("Accept error:", err)  
       }  
       go rpc.ServeConn(conn)  
    }  
}

// client.go

type HelloServiceClient struct {  
    *rpc.Client  
}  

var _ HelloServiceInterface = (*HelloServiceClient)(nil)  

const ServerName = "HelloService" 

func DialHelloService(network, address string) (*HelloServiceClient, error) {  
    conn, err := net.Dial(network, address)  
    client := rpc.NewClient(conn)  
    if err != nil {  
       return nil, err  
    }  
    return &HelloServiceClient{Client: client}, nil  
}

func (p *HelloServiceClient) Hello(request string, reply *string) error {  
    return p.Client.Call(ServerName+".Hello", request, reply)  
}
func main() {
    client, err := DialHelloService("tcp", "localhost:1234")  
    if err != nil {  
        log.Fatal("net.Dial:", err)  
    }  
    var reply string  
    err = client.Hello("hello", &reply)  
    if err != nil {  
        log.Fatal(err)  
    }  
    fmt.Println(reply)
}

Does it look familiar?

Implementing JSON Codec with Go's `net/rpc` Package

By default, Go's standard RPC library uses Go's proprietary Gob encoding. However, it's straightforward to implement other encodings, such as Protobuf or JSON, on top of it. The standard library already supports jsonrpc encoding, and we can implement JSON encoding by making minor changes to the server and client code.

// server.go
func main() {  
    _ = rpc.RegisterName("HelloService", new(HelloService))  
    listener, err := net.Listen("tcp", ":1234")  
    if err != nil {  
       log.Fatal("ListenTCP error:", err)  
    }  
    for {  
       conn, err := listener.Accept()  
       if err != nil {  
          log.Fatal("Accept error:", err)  
       }  
       go rpc.ServeCodec(jsonrpc.NewServerCodec(conn))  
       //go rpc.ServeConn(conn)  
    }  
}

//client.go
func DialHelloService(network, address string) (*HelloServiceClient, error) {  
    conn, err := net.Dial(network, address)  
    //client := rpc.NewClient(conn)  
    client := rpc.NewClientWithCodec(jsonrpc.NewClientCodec(conn))  
    if err != nil {  
       return nil, err  
    }  
    return &HelloServiceClient{Client: client}, nil  
}

The JSON request data object internally corresponds to two structures: on the client side, it's clientRequest, and on the server side, it's serverRequest. The content of clientRequest and serverRequest structures is essentially the same:

type clientRequest struct {  
    Method string `json:"method"`  
    Params [1]any `json:"params"`  
    Id     uint64 `json:"id"`  
}
type serverRequest struct {  
    Method string           `json:"method"`  
    Params *json.RawMessage `json:"params"`  
    Id     *json.RawMessage `json:"id"`  
}

Here, Method represents the service name composed of serviceName and Method. The first element of Params is the parameter, and Id is a unique call number maintained by the caller, used to distinguish requests in concurrent scenarios.

We can use nc to simulate the server and then run the client code to see what information the JSON-encoded client sends to the server:

 nc -l 1234

The nc command receives the following data:

 {"method":"HelloService.Hello","params":["hello"],"id":0}

This is consistent with serverRequest.

We can also run the server code and use nc to send a request:

echo -e '{"method":"HelloService.Hello","params":["Hello"],"Id":1}' | nc localhost 1234 
--- 
{"id":1,"result":"hello:Hello","error":null}

Conclusion

This article introduced the rpc package from Go's standard library, highlighting its simplicity and powerful performance. Many third-party rpc libraries are built on top of the rpc package. This article serves as the first installment in a series on RPC research. In the next article, we will combine protobuf with RPC and eventually implement our own RPC framework.

A Deep Dive into CNCF’s Cloud-Native AI Whitepaper

huizhou92 — Sat, 29 Jun 2024 22:03:00 +0000

During KubeCon EU 2024, CNCF launched its first Cloud-Native AI Whitepaper. This article provides an in-depth analysis of the content of this whitepaper.

In March 2024, during KubeCon EU, the Cloud-Native Computing Foundation (CNCF) released its first detailed whitepaper on Cloud-Native Artificial Intelligence (CNAI) ¹. This report extensively explores the current state, challenges, and future development directions of integrating cloud-native technologies with artificial intelligence. This article will delve into the core content of this whitepaper.

This article is first published in the medium MPP plan. If you are a medium user, please follow me in medium. Thank you very much.

What is Cloud-Native AI?

Cloud-Native AI refers to building and deploying artificial intelligence applications and workloads using cloud-native technology principles. This includes leveraging microservices, containerization, declarative APIs, and continuous integration/continuous deployment (CI/CD) among other cloud-native technologies to enhance AI applications’ scalability, reusability, and operability.

The following diagram illustrates the architecture of Cloud-Native AI, redrawn based on the whitepaper.

Relationship between Cloud-Native AI and Cloud-Native Technologies

Cloud-native technologies provide a flexible, scalable platform that makes the development and operation of AI applications more efficient. Through containerization and microservices architecture, developers can iterate and deploy AI models quickly while ensuring high availability and scalability of the system. Kuuch as resource scheduling, automatic scaling, and service discovery.

The whitepaper provides two examples to illustrate the relationship between Cloud-Native AI and cloud-native technologies, namely running AI on cloud-native infrastructure:

Hugging Face Collaborates with Microsoft to launch Hugging Face Model Catalog on Azure²
OpenAI Scaling Kubernetes to 7,500 nodes³

Challenges of Cloud-Native AI

Despite providing a solid foundation for AI applications, there are still challenges when integrating AI workloads with cloud-native platforms. These challenges include data preparation complexity, model training resource requirements, and maintaining model security and isolation in multi-tenant environments. Additionally, resource management and scheduling in cloud-native environments are crucial for large-scale AI applications and need further optimization to support efficient model training and inference.

Development Path of Cloud-Native AI

The whitepaper proposes several development paths for Cloud-Native AI, including improving resource scheduling algorithms to better support AI workloads, developing new service mesh technologies to enhance the performance and security of AI applications, and promoting innovation and standardization of Cloud-Native AI technology through open-source projects and community collaboration.

Cloud-Native AI Technology Landscape

Cloud-Native AI involves various technologies, ranging from containers and microservices to service mesh and serverless computing. Kubernetes plays a central role in deploying and managing AI applications, while service mesh technologies such as Istio and Envoy provide robust traffic management and security features. Additionally, monitoring tools like Prometheus and Grafana are crucial for maintaining the performance and reliability of AI applications.

Below is the Cloud-Native AI landscape diagram provided in the whitepaper.

Kubernetes
Volcano
Armada
Kuberay
Nvidia NeMo
Yunikorn
Kueue
Flame

Distributed Training

Kubeflow Training Operator
Pytorch DDP
TensorFlow Distributed
Open MPI
DeepSpeed
Megatron
Horovod
Apla
…

ML Serving

Kserve
Seldon
VLLM
TGT
Skypilot
…

CI/CD — Delivery

Kubeflow Pipelines
Mlflow
TFX
BentoML
MLRun
…

Data Science

Jupyter
Kubeflow Notebooks
PyTorch
TensorFlow
Apache Zeppelin

Workload Observability

Prometheus
Influxdb
Grafana
Weights and Biases (wandb)
OpenTelemetry
…

AutoML

Hyperopt
Optuna
Kubeflow Katib
NNI
…

Governance & Policy

Kyverno
Kyverno-JSON
OPA/Gatekeeper
StackRox Minder
…

Data Architecture

ClickHouse
Apache Pinot
Apache Druid
Cassandra
ScyllaDB
Hadoop HDFS
Apache HBase
Presto
Trino
Apache Spark
Apache Flink
Kafka
Pulsar
Fluid
Memcached
Redis
Alluxio
Apache Superset
…

Vector Databases

Chroma
Weaviate
Quadrant
Pinecone
Extensions
Redis
Postgres SQL
ElasticSearch
…

Model/LLM Observability

• Trulens
Langfuse
Deepchecks
OpenLLMetry
…

Conclusion

Finally, the following key points are summarized:

Role of Open Source Community : The whitepaper indicates the role of the open-source community in advancing Cloud-Native AI, including accelerating innovation and reducing costs through open-source projects and extensive collaboration.
Importance of Cloud-Native Technologies : Cloud-Native AI, built according to cloud-native principles, emphasizes the importance of repeatability and scalability. Cloud-native technologies provide an efficient development and operation environment for AI applications, especially in resource scheduling and service scalability.
Existing Challenges : Despite bringing many advantages, Cloud-Native AI still faces challenges in data preparation, model training resource requirements, and model security and isolation.
Future Development Directions : The whitepaper proposes development paths including optimizing resource scheduling algorithms to support AI workloads, developing new service mesh technologies to enhance performance and security, and promoting technology innovation and standardization through open-source projects and community collaboration.
Key Technological Components : Key technologies involved in Cloud-Native AI include containers, microservices, service mesh, and serverless computing, among others. Kubernetes plays a central role in deploying and managing AI applications, while service mesh technologies like Istio and Envoy provide necessary traffic management and security.

For more details, please download the Cloud-Native AI whitepaper ⁴.

Reference Links

Whitepaper: ↩︎
Hugging Face Collaborates with Microsoft to launch Hugging Face Model Catalog on Azure ↩︎
OpenAI Scaling Kubernetes to 7,500 nodes: ↩︎
Cloud-Native AI Whitepaper: ↩︎

If Google No Longer supports Golang

huizhou92 — Sat, 29 Jun 2024 22:01:00 +0000

Last month’s hot topic in IT circles was Google laying off many developers from its Python core team and flutter/dart team, purportedly for a city-wide reorganization.

https://news.ycombinator.com/item?id=40171125

Reportedly, those laid off were mostly core members responsible for important Python maintenance.

As a gopher, I pondered: will Google abandon Go? And if so, what would become of Go?

What does Google offer to Go?

Based on our past understanding clarified by @lance Taylor and descriptions from various sources, we can estimate what Go has likely received from Google.

Job Positions : Details regarding job positions of members of the Go core team, including compensation, benefits, and other remuneration.
Software and Hardware Resources : Information on Go-related resources such as intellectual property, servers, domain names, and module management mirrors required by the community.
Offline Activities : Possibility of reduced or scaled-down Go conferences worldwide in terms of funding and endorsement.
Internal Resources of Big Corporations : Gradual loss of exposure to advanced projects and opportunities for Go’s adoption due to the absence of resources within Google.
Promotion and Feedback Channels : Slower discovery and response to significant issues and features in Go as Google’s internal demands historically take precedence.

Potential Scenarios

What might happen if Google dissolves the Go core team and ceases all infrastructure support?

Dissolution of the Go core team, leading members may retire or seek employment elsewhere.
If Google decides to cease all investment in Go, maintenance of Go could become more complex as it relies heavily on infrastructure. In such a scenario, Go might transition from Google to an external foundation, resulting in noticeable maintenance fluctuations.
If Google chooses to continue investing in Go through other internal teams, the worst-case scenario could involve Google flexing its ownership of intellectual property, possibly leading to Go being rebranded.
CNCF might take over Google’s mantle, organizing the future development of Go. Among CNCF projects, the Go language enjoys the widest adoption.

Probability of Occurrence

Currently, Go belongs to Google Cloud. Considering Go’s current trend focusing on customer success, the likelihood of Google Cloud shutting down Go is low. But who knows? I consulted gemini on this question.

generated by Gemini

Conclusion

Drawing from the example of Rust, which transitioned from Mozilla’s core to an independent foundation, Go could potentially thrive even more. A nonprofit organization will probably form around Go (or it may directly join CNCF), with enough support from major companies, at least for a period.

References

Why Did Google Choose To Implement gRPC Using HTTP/2?

huizhou92 — Thu, 23 May 2024 09:35:13 +0000

Background

gRPC is an open-source high-performance RPC framework developed by Google. The design goal of gRPC is to run in any environment, supporting pluggable load balancing, tracing, health checking, and authentication. It not only supports service calls within and across data centers but is also suitable for the last mile of distributed computing, connecting devices, mobile applications, and browsers to backend services. For more on the motivation and principles behind gRPC's design, refer to this article: gRPC Motivation and Design Principles.

This article is first published in the medium MPP plan. If you are a medium user, please follow me in medium. Thank you very much.

Key points from the official article:

Internally, there is a framework called Stubby, but it is not based on any standard.
Supports use in any environment, including IoT, mobile, and browsers.
Supports streaming and flow control.

In reality, performance is not the primary goal of gRPC design. So why choose HTTP/2?

What is HTTP/2

Before discussing why gRPC chose HTTP/2, let's briefly understand HTTP/2.

HTTP/2 can be simply introduced with an image:

From: https://hpbn.co/

The header in HTTP/1 corresponds to the HEADERS frame in HTTP/2.
The payload in HTTP/1 corresponds to the DATA frame in HTTP/2. In the Chrome browser, open chrome://net-internals/#http2 to see information about HTTP/2 connections.

Many websites are already running on HTTP/2.

gRPC Over HTTP/2

Strictly speaking, gRPC is designed in layers, with the underlying layer supporting different protocols. Currently, gRPC supports:

However, most discussions are based on gRPC over HTTP2. Let's look at a real gRPC SayHello request and see how it is implemented over HTTP/2 using Wireshark:

You can see the following headers:

Header: :authority: localhost:50051
Header: :path: /helloworld.Greeter/SayHello
Header: :method: POST
Header: :scheme: http
Header: content-type: application/grpc
Header: user-agent: grpc-java-netty/1.11.0

Then the request parameters are in the DATA frame:

GRPC Message: /helloworld.Greeter/SayHello, Request

In short, gRPC puts metadata in HTTP/2 Headers and serialized request parameters in the DATA frame.

Advantages of HTTP/2 Protocol

HTTP/2 is an Open Standard

Google thought this through and chose not to open-source its internal Stubby but to create something new. As technology becomes more open, the space for proprietary protocols is shrinking.

HTTP/2 is a Proven Standard

HTTP/2 was developed based on practical experience, which is crucial. Many unsuccessful standards were created by a group of vendors before implementation, leading to chaos and unusability, such as CORBA. HTTP/2's predecessor was Google's SPDY. Without Google's practice and promotion, HTTP/2 might not exist.

HTTP/2 Naturally Supports IoT, Mobile, and Browsers

In fact, mobile phones and mobile browsers were the first to adopt HTTP/2. The mobile internet has driven the development and adoption of HTTP/2.

Multi-language Implementation of HTTP/2 is Easy

Discussing only the implementation of the protocol itself, without considering serialization:

Every popular programming language has a mature HTTP/2 Client.
HTTP/2 Clients are well-tested and reliable.
Sending HTTP/2 requests with a Client is much easier than sending/receiving packets with sockets.

HTTP/2 Supports Stream and Flow Control

There are many streaming solutions in the industry, such as those based on WebSocket or rsocket. However, these solutions are not universal.

Streams in HTTP/2 can also be prioritized, which might be used in complex scenarios, although less frequently in RPC.

Easy Support for HTTP/2 in Gateway/Proxy

Nginx support for gRPC: https://www.nginx.com/blog/nginx-1-13-10-grpc/
Envoy support for gRPC: https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/grpc#

HTTP/2 Ensures Security

HTTP/2 naturally supports SSL, although gRPC can run on a clear text protocol (i.e., unencrypted).
Many proprietary RPC protocols might wrap a layer of TLS support, making it very complex to use. Do developers have enough security knowledge? Are users configuring it correctly? Can operators understand it correctly?
HTTP/2 ensures secure transmission over public networks. For example, the CRIME attack is hard to prevent in proprietary protocols.

Mature Authentication in HTTP/2

Authentication systems developed from HTTP/1 are mature and can be seamlessly used in HTTP/2.
End-to-end authentication from front-end to back-end without any conversion or adaptation. For example, traditional RPC like Dubbo requires writing a Dubbo filter and considering how to pass authentication-related information through thread local. The RPC protocol itself also needs to support it. In short, it's very complex. In fact, most RPCs in companies do not have authentication and can be called freely.

Disadvantages of HTTP/2 Protocol

Inefficient Transmission of RPC Metadata

Although HPAC can compress HTTP Headers, for RPC, determining a function call can be simplified to an int. Once negotiated between both ends, it can be directly looked up in a table, without the need for HPAC encoding and decoding.

Consider optimizing an HTTP/2 parser specifically for gRPC to reduce some general processing and improve performance.

gRPC Calls in HTTP/2 Require Two Decodings

One for the HEADERS frame and one for the DATA frame.

The HTTP/2 standard itself only allows one TCP connection, but in practice, gRPC may have multiple TCP connections, which needs attention during use.

Choosing HTTP/2 for gRPC means its performance won't be top-notch. But for RPC, moderate QPS is acceptable, and generality and compatibility are the most important. Refer to the official benchmark: https://grpc.io/docs/guides/benchmarking.html

https://github.com/hank-whu/rpc-benchmark If your scenario is to...

Google's Standard-Setting Ability

In the past decade, Google's ability to set standards has grown stronger. Here are some standards:

HTTP/2
WebP image format
WebRTC for real-time communication
VP9/AV1 video encoding standards
Service Worker/PWA
QUIC/HTTP/3 Of course, Google doesn't always succeed. Many initiatives it tried to push failed, such as Chrome's Native Client.

gRPC is currently the de facto standard in the Kubernetes ecosystem. Will gRPC become the RPC standard in more areas and larger fields?

Why gRPC Emerged

Why did an HTTP/2-based RPC emerge?

I believe an important reason is that in the trend of Cloud Native, the need for open interoperability inevitably leads to HTTP/2-based RPC. Even without gRPC, there would be other HTTP/2-based RPCs.

gRPC was first used internally at Google on Google Cloud Platform and public APIs: https://opensource.google.com/projects/grpc

Summary

Although gRPC may not replace internal RPC implementations, in an era of open interoperability, not just on Kubernetes, gRPC will have more and more stages to showcase its capabilities.

DEV Community: huizhou92

Big Tech Is Killing Their Customers

Why Does Big Tech Need Our Data?

Can We Fight Back?

The Zero-Click Internet

The Inevitable Decline of the Open Web

References

Software Engineering: Hyrum's Law

What is Hyrum's Law?

Importance of Hyrum's Law

A Case Study

Practical Recommendations for Hyrum's Law

Anti-Patterns Related to Hyrum's Law

Conclusion

Debunking the Misconception: Maximum Number of TCP Connections on a Server

Introduction

Theoretical Analysis

Breaking Down the 4-Tuple Limits

Practical Limitations

File Descriptors

ip_local_port_range

Memory & CPU

Summary

Using JOSE To Protect your APIs 1：JOSE Basics

Information Security Algorithms

Encryption Algorithms

Symmetric Encryption Algorithms

Asymmetric Encryption Algorithms

Data Verification Algorithms

Message Digest (MD)

Message Authentication (MA)

sub summary

Evolution of Security Solutions

1. Symmetric Encryption

2. Symmetric Encryption + Message Digest

3. Symmetric Encryption + Message Authentication

4. Asymmetric Encryption

Conclusion

SwissTable: A High-Performance Hash Table Implementation

Introduction

Traditional Hashtable

Chaining

Linear Probing

Go Map Data Storage

SwissTable: An Efficient Hashtable Implementation

Basic Structure of SwissTable

Adding Data

Advantages of SwissTable

Conclusion

References

Decrypt Go: varint

The Design Principles of varint

varint for Unsigned Integers

Encoding Negative Numbers: Zigzag Encoding

When varint Is Not Suitable

Decrypt Go: empty struct

The Secret of the Empty Struct

Special Variable: zerobase

Empty Struct and Memory Alignment

Use Cases of the Empty Struct

map & struct{}

chan & struct{}

Summary

References

RPC Action EP2: Using Protobuf and Creating a Custom Plugin

An example of using protobuf

Plugin system for protoc

Customize a protoc plugin

Objective

How to develop a plug-in?

Debug plugin

Summary

Reference

RPC Action EP1: Implement a simple RPC interface in Go

Creating a Simple RPC Request

Implementing JSON Codec with Go's net/rpc Package

Conclusion

A Deep Dive into CNCF’s Cloud-Native AI Whitepaper

What is Cloud-Native AI?

Relationship between Cloud-Native AI and Cloud-Native Technologies

Traditional `Hashtable`

`varint` for Unsigned Integers

When `varint` Is Not Suitable

`map` & `struct{}`

`chan` & `struct{}`

Implementing JSON Codec with Go's `net/rpc` Package