动手实现一个短链接服务

最近在学习开发面经时，遇到了一个经典的系统设计面试题：如何设计和实现一个短链接系统。这个题目从浅入深，涵盖了高并发、安全等我之前背过的"八股文"知识。既然心动不如行动，决定亲自动手实现一个简单的短链接服务，并将其部署到我的博客系统中—权当是自娱自乐了。

简单实现

第一眼看到这个问题，首先想到的就是想到直接使用mysql了。当输入一个长链接时候，就加入数据库，并返回一个自增id作为短链接给用户。当用户输入短链接id之后，则在数据库中查询获取原始长链接，并通过302来零时重定向。

那么，在生产环境下面，就需要考虑更加周全一些，如果短链接的数量特别多怎么？自增id总会有上限，数据库的存储空间也有上限。高并发的时候，如何确保最好的性能。如何确保安全，防止盗刷接口？

存储优化

首先考虑 ID 问题。如果第 999999999999 个存储的长 URL 进入系统时，得到的短 URL 的 ID 就是 999999999999。这其实是一个比较长的值，不够"短"。同时，这个值已远超 MySQL 单表 500 万行的推荐上限，需要分表。最后，这个值可能已经超过了 MySQL 自增 ID 的极限（极限取决于自增 ID 的类型）。

为了更好地存储，我们希望 ID 满足以下条件：

1. 尽可能短，以减少占用空间

2. 能表示的数量非常大，满足海量长 URL 转短 URL 的需求

有人可能会问：为应对 MySQL 自增 ID 数量有限的问题，能否使用 UUID？不建议。这是 MySQL 中的一个常见问题，因为 UUID 的生成不是递增的。每次生成的 UUID 插入到 B+ 树中可能导致页分裂，降低查询效率和空间利用率。

更好的方式是采用 Base62 编码。这种方法将自增 ID 的数值通过 62 进制转换得到 Base62 字符串。由于 62^5 = 916,132,832，仅 5 位 Base62 编码的字符串就能表示 9 亿多个长链接，足以满足需求。

Base62 编码不仅解决了 ID 长度问题，还保证了 ID 的唯一性和顺序性。它使用所有大小写字母和数字，既能生成简短的 URL，又能保证足够大的地址空间。此外，Base62 编码比纯数字 ID 更易读、易记和易输入。

性能优化

在高并发场景下，我们需要考虑如何最大化系统的吞吐量和响应速度。首先，我们可以通过减少数据库操作来提升性能。其次，引入缓存机制可以大幅降低数据库负载。最后，采用异步处理和队列机制可以进一步提高系统的并发处理能力。

引入分布式ID生成器

这种方法可以有效减少数据库操作，提高系统性能。分布式ID生成器可以使用诸如雪花算法（Snowflake）等技术，这不仅能保证ID的唯一性，还能支持高并发的ID生成需求。此外，通过将生成的ID存入队列，我们可以进一步优化性能，实现ID的批量预生成和快速获取。

具体过程，可以分为以下几个步骤：首先，使用雪花算法生成唯一的分布式ID。然后，将这些ID存入一个队列中，以便快速获取。当需要生成短链接时，从队列中取出一个ID，将其转换为Base62编码。最后，将长URL与Base62编码的短链接一起存储到数据库中。这种方法不仅能够高效地生成唯一ID，还能减少数据库操作，大大提高了系统的性能和并发处理能力。

• 分布式ID生成方案

  除了雪花算法，还包括Redis和分布式MySQL等实现方式。不过，雪花算法因其简洁性而成为最常用的选择。

引入缓存

引入缓存是提高短链接服务性能的另一个重要策略。对于频繁访问的短链接，我们可以将其对应的长URL存储在内存缓存中，如Redis。这样，当用户请求一个热门的短链接时，系统可以直接从缓存中获取长URL，而不需要查询数据库，大大减少了响应时间。为了保持缓存的有效性，我们可以设置合适的过期时间，并使用LRU（最近最少使用）等缓存淘汰策略来管理缓存内容。

引入布隆过滤器

布隆过滤器尝尝和redis一同使用，作为一个快速检查机制。当收到一个短链接请求时，首先通过布隆过滤器进行检查。如果布隆过滤器表明该短链接可能不存在，系统就可以直接返回错误，而不需要查询Redis或数据库。这样可以有效地过滤掉大量无效请求，减轻后端系统的压力。然而，由于布隆过滤器可能存在假阳性，所以仍需要在Redis或数据库中进行最终的验证。

设计实现

这里实现了一个简单的版本，并且部署应用到本博客系统中，权当是自娱自乐了。

仔细分析这个过程：当用户输入一个长URL时，首先通过雪花获取ID，然后将ID从10进制转换为Base62编码，最后在MySQL中设置Base62编码并返回给用户。

当用户请求一个短链接时，系统首先检查布隆过滤器。如果布隆过滤器显示该短链接可能存在，系统会查询Redis缓存。如果缓存中没有找到，才会去查询MySQL数据库。这种多层次的查询策略能够有效地提高系统的响应速度和处理能力。

代码

实现如下：

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 结构体定义

type URL struct {

	ID        uint   `gorm:"primaryKey"`

	LongURL   string `gorm:"type:varchar(2048);not null"`

	ShortCode string `gorm:"type:varchar(10);uniqueIndex;not null"`

}



// 全局变量

var (

	db          *gorm.DB

	redisClient *redis.Client

	node        *snowflake.Node

)



func main() {

	// 初始化数据库连接

	initDB()



	// 初始化Redis客户端

	initRedis()



	// 初始化雪花算法节点

	initSnowflake()



	// 设置Fiber应用

	app := fiber.New()



	// 路由设置

	app.Post("/shorten", shortenURL)

	app.Get("/:shortCode", redirectToLongURL)



	// 启动服务器

	app.Listen(":3000")

}



// 初始化数据库连接

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")

	}

	

	// 自动迁移

	db.AutoMigrate(&URL{})

}



// 初始化Redis客户端

func initRedis() {

	redisClient = redis.NewClient(&redis.Options{

		Addr: "localhost:6379",

	})

}



// 初始化雪花算法节点

func initSnowflake() {

	var err error

	node, err = snowflake.NewNode(1)

	if err != nil {

		panic(err)

	}

}



// 缩短URL的处理函数

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"})

	}



	// 生成短码

	id := node.Generate()

	shortCode := base62Encode(id.Int64())



	// 创建URL记录

	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"})

	}



	// 将短码和长URL存入Redis缓存

	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)})

}



// 重定向到长URL的处理函数

func redirectToLongURL(c *fiber.Ctx) error {

	shortCode := c.Params("shortCode")



	// 首先尝试从Redis缓存中获取长URL

	longURL, err := redisClient.Get(c.Context(), shortCode).Result()

	if err == nil {

		return c.Redirect(longURL, 302)

	}



	// 如果Redis中没有，则从数据库中查询

	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")

	}



	// 将查询到的长URL存入Redis缓存

	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编码函数

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

}

这段代码实现了一个基本的短链接服务，包括URL缩短和重定向功能。它使用了雪花算法生成唯一ID，Base62编码生成短码，MySQL存储数据，以及Redis缓存来优化性能。