Implement a short link service by hand
"TLDR: This article introduces how to design and implement a short link service, covering key technologies such as high concurrency and security."
Recently, when I was studying development interviews, I encountered a classic system design interview question: how to design and implement a short link system. This topic goes from the shallower to the deeper, covering high concurrency, security and other "eight-legged essay" knowledge that I have memorized before. Since my heart is not as good as action, I decided to implement a simple short link service myself and deploy it to my blog system - just for my own entertainment.
Simple implementation
When I first saw this question, the first thing that came to my mind was to use mysql directly. When a long link is entered, it is added to the database and an auto-incrementing ID is returned to the user as a short link. When the user enters the short link ID, the original long link is queried in the database and redirected in time via 302.
Then, in a production environment, you need to think more carefully. What if the number of short links is particularly large? There is always an upper limit for self-increasing IDs, and there is also an upper limit for database storage space. How to ensure the best performance when there is high concurrency. How to ensure security and prevent interface theft?
Storage Optimization
Consider the ID issue first. If the 999999999999th stored long URL enters the system, the ID of the short URL obtained is 999999999999. This is actually a relatively long value, not "short" enough. At the same time, this value has far exceeded the recommended upper limit of 5 million rows for a single MySQL table, and it needs to be divided into tables. Finally, this value may have exceeded MySQL's auto-increment ID limit (the limit depends on the type of auto-increment ID).
For better storage, we want the ID to meet the following conditions:
-
Be as short as possible to reduce space usage
-
The number that can be represented is very large, meeting the needs of converting massive long URLs to short URLs.
Someone may ask: To deal with the limited number of self-increasing IDs in MySQL, can UUID be used? Not recommended. This is a common problem in MySQL because UUID generation is not incremental. Each time the generated UUID is inserted into the B+ tree, it may cause page splits, reducing query efficiency and space utilization.
A better way is to use Base62 encoding. This method converts the value of the auto-incremented ID into a Base62 string through hexadecimal conversion. Since 62^5 = 916,132,832, just a 5-bit Base62-encoded string can represent over 900 million long links, which is more than enough.
Base62 encoding not only solves the ID length problem, but also ensures the uniqueness and sequence of the ID. It uses all uppercase and lowercase letters and numbers to generate short URLs while ensuring a large enough address space. Additionally, Base62 encoding is easier to read, remember, and type than purely numeric IDs.
Performance Optimization
In high-concurrency scenarios, we need to consider how to maximize the throughput and response speed of the system. First, we can improve performance by reducing database operations. Secondly, the introduction of caching mechanism can significantly reduce database load. Finally, the use of asynchronous processing and queuing mechanisms can further improve the system's concurrent processing capabilities.
Introducing distributed ID generator
This method can effectively reduce database operations and improve system performance. Distributed ID generators can use technologies such as Snowflake, which not only ensures the uniqueness of IDs, but also supports high-concurrency ID generation requirements. In addition, by storing the generated IDs in the queue, we can further optimize performance and achieve batch pre-generation and rapid acquisition of IDs.
The specific process can be divided into the following steps: First, use the snowflake algorithm to generate a unique distributed ID. These IDs are then stored in a queue for quick retrieval. When you need to generate a short link, take an ID from the queue and convert it to Base62 encoding. Finally, the long URL is stored into the database along with the Base62-encoded short link. This method can not only efficiently generate unique IDs, but also reduce database operations, greatly improving the system's performance and concurrent processing capabilities.
-
Distributed ID generation solution
In addition to the snowflake algorithm, it also includes implementation methods such as Redis and distributed MySQL. However, the snowflake algorithm is the most commonly used choice due to its simplicity.
Introduce cache
Introducing caching is another important strategy to improve the performance of short link services. For frequently accessed short links, we can store their corresponding long URLs in a memory cache, such as Redis. In this way, when a user requests a popular short link, the system can directly obtain the long URL from the cache without querying the database, greatly reducing the response time. In order to maintain the effectiveness of the cache, we can set an appropriate expiration time and use cache elimination strategies such as LRU (Least Recently Used) to manage cache content.
Introduce Bloom filter
Bloom filters try to be used with redis as a quick checking mechanism. When a short link request is received, it is first checked through a bloom filter. If the bloom filter indicates that the short link may not exist, the system can directly return an error without querying Redis or the database. This can effectively filter out a large number of invalid requests and reduce the pressure on the back-end system. However, since Bloom filters may have false positives, final validation still needs to be done in Redis or the database.
Design Implementation
A simple version is implemented here and is deployed and applied to this blog system for your own entertainment.
Analyze this process carefully: when the user enters a long URL, the ID is first obtained through Snowflake, then the ID is converted from decimal to Base62 encoding, and finally the Base62 encoding is set in MySQL and returned to the user.
When a user requests a short link, the system first checks the bloom filter. If the Bloom filter shows that the short link may exist, the system will query the Redis cache. If it is not found in the cache, the MySQL database will be queried. This multi-level query strategy can effectively improve the system's response speed and processing capabilities.
code
The implementation is as follows:
package main
import (
"fmt"
"github.com/bwmarrin/snowflake"
"github.com/go-redis/redis/v8"
"github.com/gofiber/fiber/v2"
"gorm.io/driver/mysql"
"gorm.io/gorm"
)
// URL structure definition
type URL struct {
ID uint `gorm:"primaryKey"`
LongURL string `gorm:"type:varchar(2048);not null"`
ShortCode string `gorm:"type:varchar(10);uniqueIndex;not null"`
}
//global variables
var (
db *gorm.DB
redisClient *redis.Client
node *snowflake.Node
)
func main() {
//Initialize database connection
initDB()
//Initialize Redis client
initRedis()
//Initialize the snowflake algorithm node
initSnowflake()
// Set up Fiber application
app := fiber.New()
//Route settings
app.Post("/shorten", shortenURL)
app.Get("/:shortCode", redirectToLongURL)
// Start the server
app.Listen(":3000")
}
//Initialize database connection
func initDB() {
var err error
dsn := "user:password@tcp(127.0.0.1:3306)/shorturl?charset=utf8mb4&parseTime=True&loc=Local"
db, err = gorm.Open(mysql.Open(dsn), &gorm.Config{})
if err != nil {
panic("failed to connect database")
}
// automatic migration
db.AutoMigrate(&URL{})
}
//Initialize Redis client
func initRedis() {
redisClient = redis.NewClient(&redis.Options{
Addr: "localhost:6379",
})
}
//Initialize the snowflake algorithm node
func initSnowflake() {
var err error
node, err = snowflake.NewNode(1)
if err != nil {
panic(err)
}
}
// Shorten URL processing function
func shortenURL(c *fiber.Ctx) error {
var input struct {
LongURL string `json:"long_url"`
}
if err := c.BodyParser(&input); err != nil {
return c.Status(fiber.StatusBadRequest).JSON(fiber.Map{"error": "Invalid input"})
}
// Generate shortcode
id := node.Generate()
shortCode := base62Encode(id.Int64())
//Create URL record
url := URL{
LongURL: input.LongURL,
ShortCode: shortCode,
}
if result := db.Create(&url); result.Error != nil {
return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": "Could not create short URL"})
}
// Store short codes and long URLs in the Redis cache
err := redisClient.Set(c.Context(), shortCode, input.LongURL, 0).Err()
if err != nil {
fmt.Printf("Error setting Redis cache: %v\n", err)
}
return c.JSON(fiber.Map{"short_url": fmt.Sprintf("http://localhost:3000/%s", shortCode)})
}
//Redirect to long URL processing function
func redirectToLongURL(c *fiber.Ctx) error {
shortCode := c.Params("shortCode")
// First try to get the long URL from the Redis cache
longURL, err := redisClient.Get(c.Context(), shortCode).Result()
if err == nil {
return c.Redirect(longURL, 302)
}
// If it is not found in Redis, query it from the database
var url URL
if result := db.Where("short_code = ?", shortCode).First(&url); result.Error != nil {
return c.Status(fiber.StatusNotFound).SendString("Short URL not found")
}
// Store the queried long URL in the Redis cache
err = redisClient.Set(c.Context(), shortCode, url.LongURL, 0).Err()
if err != nil {
fmt.Printf("Error setting Redis cache: %v\n", err)
}
return c.Redirect(url.LongURL, 302)
}
// Base62 encoding function
func base62Encode(number int64) string {
const base62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
if number == 0 {
return string(base62[0])
}
var encoded string
for number > 0 {
encoded = string(base62[number%62]) + encoded
number = number / 62
}
return encoded
}
This code implements a basic short link service, including URL shortening and redirection functions. It uses the Snowflake algorithm to generate unique IDs, Base62 encoding to generate short codes, MySQL to store data, and Redis caching to optimize performance.