短链接在互联网中已经十分常见了，如B站的 b23.tv 平台能够把一个很长的视频链接转化为一个仅由几个数字和字母组成的短链接。用户提交一个原始的长链接（URL），平台会为其生成一个唯一的短链接，通常包含一个域名和一段短路径，如 abc.com/xyz123。

短链接在社交媒体传播和数据分析等场景中被广泛使用。尤其是一些限制字数或者增加阅读体验的场景，短链接能够有效压缩内容。而由于访问短链接时需要经过服务器重定向到原始 URL，统计其访问数据也变得很容易。

接下来我们将使用 Go 语言实现一个短链接生成平台。思路比较简单：用户输入原始 URL 后，通过某种哈希算法得到摘要字符串并将其作为短路径，将映射关系存入数据库；当用户访问短链接时从路径中提取摘要字符串，访问数据库拿到原始 URL，并将用户重定向即可。在这个过程中我们需要选择合适的哈希算法，处理哈希碰撞问题，高效地检查 URL 是否已经注册过，以及如何利用 Redis 缓存加速链接的转换。

这个项目从 Eddy WM 的博客文章 Let's build a URL shortener in Go 中得到灵感。

完整的项目代码在 Github 上

实现存储（store）模块

store 模块是项目的核心模块。创建文件夹 store 并新建文件 store.go 和 gen.go，其中 store.go 文件实现数据库交互，包括 数据库初始化、Redis 和 SQLite3 数据库中链接的存取等功能，而 gen.go 文件通过 Murmur3 哈希算法和 62 进制转换生成短链接，两者属于同一个 package.

初始化数据库

首先在 store.go 中定义一个 storage 结构体储存数据库对象方便操作。

type Storage struct {
    RedisClient  *redis.Client
    SqliteClient *sql.DB
}

然后我们在函数 InitDB 中初始化数据库，这个函数将由 main 函数调用。如果服务器连接失败，需要返回错误：

func (s *Storage) InitDB(redisHost string, redisPort string, redisPass string, redisDB int, sqliteFile string) error

连接数据库

使用 go-redis 库连接 Redis 服务器，使用官方库 database/sql 提供的接口和第三方库 go-sqlite3 打开 SQLite3 数据库文件。参数都比较好理解，其中的 redisDB 指的是 Redis 的数据库编号，一般情况下 Redis 有编号 0-15 共 16 个数据库。

s.RedisClient = redis.NewClient(&redis.Options{
    Addr:     net.JoinHostPort(redisHost, redisPort),
    Password: redisPass,
    DB:       redisDB,
}
// Ping the server

s.SqliteClient, err = sql.Open("sqlite3", sqliteFile)
// Ping the server

这两个操作只会初始化数据库连接对象，并不会真正连接数据库，因此我们需要 Ping 一下数据库检查连通性。这里我们使用 retry-go 库在连接失败时重试，以去除网络波动的影响。retry-go 中的 retry.Do 函数第一个参数为可能需要重试的执行函数，它将在这个函数返回 error 时启动重试，其它参数为最大重试次数、重试间隔算法（这里为指数退避算法）和重试回调函数（这里为生成一条日志）。另外，这里首次出现了 context.Context 类型的参数，这个是在 go routine 中用于传递上下文信息的结构体，我们可以利用这个参数传递超时、错误等信息，以便在如网络出现错误时及时停止后续操作，减少资源的浪费。

func checkRedisReachable(ctx context.Context, client *redis.Client) error {
    err := retry.Do(
        func() error {
            return client.Ping(ctx).Err()
        },
        retry.Attempts(8),
        retry.DelayType(retry.BackOffDelay),
        retry.OnRetry(func(n uint, err error) {
            slog.Warn(fmt.Sprintf("Cannot connect to Redis. Retry: %d Error: %v", n, err))
        }),
    )
    return err
}

创建表和索引

接下来就是在 SQLite3 中使用 SQL 语句 CREATE TABLE IF NOT EXISTS 建表。数据表的列因需求而异，这个项目中只包含 4 个字段: (url, digest, date, collide)，其中 url 为原始长链接，digest 为生成的短路径，date 为生成日期，collide 指示这个 digest 是否是因为哈希碰撞而再次生成的。关于如何处理哈希碰撞的问题在后面会介绍。

这里 url 为主键，SQLite3 将默认为其创建索引，而为了加速原始 URL 的获取，再加上 digest 也必定是唯一的，我们使用 CREATE UNIQUE INDEX IF NOT EXISTS idx_digest ON table_name (digest) 给 digest 也创建一个索引。使用数据库连接的 ExecContext 方法执行 SQL 语句，记得处理错误。

到这里 SQLite3 数据库的初始化就完成了，接下来看看 Redis 数据库。

Redis 中的 Bloom Filter（布隆过滤器）

在我们的短链接生成平台中需要快速检查某个 URL 是否已经在数据库中，或者某个短路径已经被生成（哈希碰撞），这时我们需要一种高效的数据结构。

Bloom Filter（布隆过滤器）是一个基于概率的数据结构，能够在 O(1) 时间内和常量空间中查询元素是否在集合内，但有一定的误判概率。不过这种误判不会出现 false negative，即如果 Bloom Filter 说该元素不在集合内，则它一定不在集合内；反之，如果 Bloom Filter 说该元素在集合内，则它有可能不在集合内。

Bloom Filter 的原理比较简单，它根据用户预设的错误率和容量构建一个固定大小的数组（或位图）并确定一个数字 n，用户将元素加入其中时，用 n 个不同的哈希函数计算元素的哈希值，并将这 n 个哈希值作为数组下标，将对应的数组元素置 1，注意某个下标可能会被多次置 1. 检查元素是否存在时，用同样这 n 个哈希函数计算下标，当所有下标元素均为 1 时返回“元素存在”，否则返回“元素不存在”。算法的正确性可以通过反证法轻松证明。

Redis 官方实现了布隆过滤器，但需要安装插件或使用 Redis Stack. 我们通过 go-redis 中的 BFReserve 方法创建一个布隆过滤器，其中可以设置名称、错误率、容量等参数，Redis 中的布隆过滤器名称将作为一个 key 存储在数据库中，随后我们可以通过 BFAdd 和 BFExists 方法添加元素和检查元素是否存在。默认情况下 Redis 中的布隆过滤器不会过期，且当元素数量超过容量参数时会自动扩容。当然也可以使用 BFReserveExpansion 方法指定扩容因子（默认为两倍）。

接下来我们为原始 URL 和短路径创建两个布隆过滤器。注意创建之前要先检查它们两个是否已经存在。

var ErrDBFails = errors.New("database connection error")
const redisNamespace = "urlshortener:"

func reserveRedisBF(ctx context.Context, client *redis.Client, errRate float64, capacity int64) error {
    exist, err := client.Exists(ctx, redisNamespace+"url_filter").Result()
    if err != nil {
        return fmt.Errorf("%w: %v", ErrDBFails, err)
    }
    if exist != 1 {
        err = client.BFReserve(ctx, redisNamespace+"url_filter", errRate, capacity).Err()
        if err != nil {
            return fmt.Errorf("%w: %v", ErrDBFails, err)
        }
    }

其中 ErrDBFails 为一个简单的自定义错误类型，而 fmt.Errorf 和其中的 %w 占位符可以将某种错误 wrap 起来，方便展示错误信息，调用者可以使用 errors.Is(err, ErrDBFails) 检查 err 参数是否为该类型的错误。

而这里的 redisNamespace 常量（<应用名称>: <key>）是一种在 Redis 数据库中区分不同应用数据的最佳实践。

到此为止数据库的初始化就完成了。下面我们来实现链接的生成、存储和查询。

短链接的生成、存储和查询

生成短链接

首先我们在 gen.go 中实现一个根据 URL 生成短路径（摘要）的函数。这里我们采用主流的 Murmur3 哈希算法。Murmur3 有高效的性能，其生成的哈希值分布均匀，已经被广泛应用。我们使用第三方库 murmur3 中的 murmur3.StringSum64 函数根据 URL 生成一个 64 位的 Murmur3 哈希值（类型为 uint64）。我们当然可以直接使用这个生成的哈希值作为短路径，但为了进一步缩短链接，我们将进行一个 base-62 encoding，即把哈希值通过 62 进制转化，生成一个仅由数字或大小写字母组成的字符串。其算法和二进制转十进制等算法并无二致。

// gen.go

const chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const RADIX = 62

func GenerateDigest(url string) string {
    hash := murmur3.StringSum64(url)
    return encodeToString(hash)
}

func encodeToString(num uint64) string {
    var bytes []byte
    for num > 0 {
        bytes = append(bytes, chars[num%RADIX])
        num /= RADIX
    }
    slices.Reverse(bytes)
    return string(bytes)
}

实现短路径的生成后，我们就可以开始处理存储了。

存储短链接映射

在 store.go 中暴露一个函数 StoreURL 负责调用短链接生成函数和存储映射关系。在这个函数中，我们需要：

  1. 先确认 URL 是否已经在平台中注册过，若已经注册过就返回 ErrURLExists 错误。

  2. 再根据 URL 生成短路径（摘要），此时要确认摘要是否发生哈希碰撞。

    1. 如果发生了哈希碰撞，就将 URL 字符串合并上当前时间字符串送去哈希函数再次计算；
    2. 如果再次发生哈希碰撞就说明这个用户太幸运了，放弃治疗，返回 ErrTooLucky 错误。（此时可以把对应 URL 和对应的时间裱起来做纪念🤣）
  3. 最后将 URL、生成的短路径、生成时间和是否发生碰撞存入 SQLite3 数据库，同时将 <短路径> -> <URL> 作为键值对使用 Set 方法存入 Redis（可以设置过期时间）.

判断 URL 或者短路径是否存在就用到了我们先前创建的布隆过滤器，如果返回不存在就可以放心进行下一步，但如果返回存在就要去 SQLite3 数据库再次确认了。

// checkURLExist check if a URL is in Sqlite3 database, return a boolean and an error.
// Error occurs only when database connection goes wrong.
// The value of the boolean should be omitted if error occurs.
func (s *Storage) checkURLExist(ctx context.Context, url string) (bool, error) {
    urlBFExist, err := s.RedisClient.BFExists(ctx, "url_filter", url).Result()
    if err != nil {
        return true, fmt.Errorf(“%w: %v”, ErrDBFails, err)
    }

    if urlBFExist {
        err = s.SqliteClient.QueryRowContext(ctx, "SELECT url FROM shortener WHERE url = ?", url).Scan()
        if err != nil {
            if errors.Is(err, sql.ErrNoRows) {
                return false, nil
            }
            return true, fmt.Errorf(“%w: %v”, ErrDBFails, err)
        } else {
            return true, nil
        }
    } else {
        return false, nil
    }
}

而在重新生成哈希值后，为了判断是否再次发生哈希碰撞，可以直接将短路径存入数据库看它是否返回约束错误（我们在建立数据表和索引时标注了 UNIQUE 属性），我们需要先尝试将错误转化为 sqlite3.Error 类型看看是否为数据库内部的错误（而非连接错误）。

err = s.storeToSqlite(ctx, url, digest, now, digestExist)
        if err != nil {
            var sqliteErr sqlite3.Error
            if errors.As(err, &sqliteErr) {
                // Break unique key constrain
                if sqliteErr.Code == sqlite3.ErrConstraint && sqliteErr.ExtendedCode == sqlite3.ErrConstraintUnique {
                    return "", fmt.Errorf("%w, url: %v, time: %v", ErrTooLucky, url, now)
                }
            }
            return "", fmt.Errorf("%w: %v", ErrDBFails, err)
        }

另外若在 StoreURL 中发生数据库的连接问题，应该返回 ErrDBFails 错误给上一级处理（可以是重试或者向用户返回“服务暂时不可用”）。

完整的 StoreURL 函数比较长，就不在这里展示了。

短链接的查询

短链接的查询非常直接，先使用 Redis 数据库连接的 Get 方法，将短路径 digest 作为键查询是否有对应记录，若没有就在 SQLite3 数据库中执行 SELECT 语句查询。最后返回 URL 字符串或者 ErrNotExists 错误。

至此存储模块的功能就全部实现了，接下来我们将在 Web 服务器处理请求时调用其中的功能。

开启 Web 服务器处理请求

我们将使用 gin Web 框架提供 API 的处理。首先我们创建一个 router 目录来把 Web 框架相关的内容放在一个 package 里面。在 router 目录中新建文件 router.go 用于提供 gin router（或者说是 engine）的初始化，以及另一个文件 endpoints.go 用于实现 API 的处理函数，这样能够分离 API 的注册和实现，使代码更具可读性。然后在创一个 templates 目录用于存放 HTML templates

初始化 router

首先我们定义一个 storageModel struct 对前面实现的存储模块进行一个包装，后续可能有更多的拓展字段。储存模块应该在 main 函数调用 SetupRouter 初始化函数之前调用，并传入 SetupRouter 函数中，从而后续 API 注册时我们能够传入存储模块供处理函数使用。

使用 gin.New() 生成一个 gin engine，然后我们可以对这个 engine 进行一些配置，比如指定使用的 logger 等等。注意这里的 engine.LoadHTMLGlob(“router/templates/*”) 是用于载入 HTML 模版的，必须在初始化时就告诉 gin 模版的位置，否则后续渲染 HTML 时会找不到对应的文件。registerRoute 函数用于注册 API 接口，用 GET 方法注册一个 GET 请求的处理函数，用 POST 方法注册一个 POST 请求的处理函数，如有其它请求可以参考 gin 的官方文档调用对应的方法完成注册。其中传入的回调函数位于同一个 package 下的 endpoints.go 文件中。

// router.go

type storageModel struct {
    storage *store.Storage
}

func SetupRouter(logger *slog.Logger, storage *store.Storage) *gin.Engine {
    engine := gin.New()
    engine.Use(sloggin.New(logger))
    model := storageModel{storage}
    engine.LoadHTMLGlob("router/templates/*")
    registerRoutes(engine, model)
    return engine
}

func registerRoutes(engine *gin.Engine, model storageModel) {
    engine.GET("/", getIndex)
    engine.GET("/:digest", model.getURL)
    engine.GET("/admin/login", getLogin)
    engine.POST("/admin/login", postLogin)
    engine.GET("/admin/register", getRegisterURL)
    engine.POST("/admin/register", model.postRegisterURL)
    engine.NoRoute(notFound)
}

API 接口设计与注册

我们需要用到的 API 接口并不多。为了最大限度压缩短链接的长度，我们应该把存储模块生成的 digest 直接拼接在网站根目录后面。这里我们可以使用 “/:digest” 即一个冒号加上参数名称的格式指定一个路由参数，这个变量可以在后续的处理函数中通过检查 gin.Context 参数获取。“/:digest” 会匹配根目录下的任意路径，如 “/abc123” 但如果后面还有目录，则不会匹配：如 “/abc123/def567” 就不会被匹配。

因此我们可以把管理短链接平台的接口放在后面的 admin 目录下。这里的 register 指的是注册一个 URL，即生成一个短链接的接口，进入注册界面之前需要在 login 页面下完成系统的登陆（当然这步可以省略，但把平台部署到公网上时省略鉴权可能导致安全问题）。

需要注意的是，访问短链接接口的处理函数 getURL 和注册（生成）短链接接口的处理函数postRegisterURL 需要传入前面定义的 storageModel 以使用存储模块中的功能。

实现处理函数

处理函数的实现位于 endpoints.go 中。处理函数需要接收一个类型为 *gin.Context 的参数，其所指的结构体中保存了对应请求的相关信息如 header 和请求参数。

func handler(c *gin.Context) {
    key := c.Param(“key”)    // 获取名称为 “key” 的参数
    // 处理函数的实现
}

接下来我们来看看 getURL 处理函数的实现，其包含了大部分 gin 的响应生成方法。

func (m storageModel) getURL(c *gin.Context) {
    digest := c.Param("digest")
    url, err := m.storage.GetOriginalURL(c.Request.Context(), digest)
    if err != nil {
        if errors.Is(err, store.ErrNotFound) {
            c.HTML(http.StatusNotFound, "404.html", nil)
        } else if errors.Is(err, store.ErrDBFails) {
            c.HTML(http.StatusServiceUnavailable, "DBFails.html", nil)
            slog.Error("Database fails: %v", err)
        } else {
            c.HTML(http.StatusInternalServerError, "500.html", nil)
            slog.Error(err.Error())
        }
        return
    }
    c.Redirect(http.StatusFound, "https://"+url)
}

获取路径参数与错误处理

getURL 函数从请求参数（这里为路径参数）中获取 digest 的值，并将其传入存储模块的 GetOriginalURL 方法来获取原始 URL，最后根据返回的内容进行错误处理或将链接重定向至对应的 URL. 还记得我们之前在 store.go 中定义的自定义错误类型吗？这里就派上用场了，由于在存储模块中对底层操作的错误进行了包装，在这里我们只需要处理两种错误：ErrNotFound（未找到对应的 URL，即用户提供的参数有误）和 ErrDBFails（数据库相关错误，即服务端出错）。我们使用 errors.Is 函数来判断错误变量 err 是否为某个类型的错误，这个函数可以处理多层包装的情况。

渲染 HTML

接下来就是返回响应了，我们使用 c.HTML 向客户端渲染一个 HTML 页面，第一个参数为响应状态码（200、301、302、500 等），第二个参数为 HTML template 的路径，即以前面 gin 初始化时指定的 HTML template 存放位置为根目录的路径。第三个参数为 options，可忽略。

重定向

使用 c.Redirect 方法将链接重定向，第一个参数同样为状态码，这里使用 302 临时重定向（http.StatusFound），因为这个短链接到原始 URL 的映射在后面可能更改或删除。第二个参数为重定向后的链接，注意这里要加上 https:// 前缀，否则将重定向当前网站的根目录下。比如说短链接部署的网站为 origin.com，使用 https 协议访问短链接 https://origin.com/abc123，其对应的 URL 为 example.com，加与不加前缀将有以下的现象：

是否加前缀现象
加 https:// 前缀重定向至 https://example.com
不加 https:// 前缀重定向至 https://origin.com/example.com