# 版本 1 - 数据结构和前端界面

第 1 个版本的代码 goto_v1goto_v1

# 19.3 数据结构

(本节代码见 goto_v1/store.go。)

当程序运行在生产环境时,会收到很多短网址的请求,同时会有一些将长 URL 转换成短 URL 的请求。我们的程序要以什么样的结构存储这些数据呢?19.2 节 中 (A) 和 (B) 两种 URL 都是字符串,此外,它们相互关联:给定键 (B) 能获取到值 (A),他们互相映射(map)。要将数据存储在内存中,我们需要这种结构,它们几乎存在于所有的编程语言中,只是名称有所不同,例如“哈希表”或“字典”等。

Go 语言就有这种内建的映射(map):map[string]string

键的类型写在 [] 之间,紧接着是值的类型。有关映射的所有知识详见 8 章。为特定类型指定一个别名在严谨的程序中非常实用。Go 语言中通过关键字 type 来定义,因此有定义:

type URLStore map[string]string
1

它从短 URL 映射到长 URL,两者都是字符串。

要创建那种类型的变量,并命名为 m,使用:

m := make(URLStore)
1

假设 http://goto/a 映射到 http://google.com/ ,我们要把它们存储到 m 中,可以用如下语句:

m["a"] = "http://google.com/"
1

(键只是 http://goto/ 的后缀,其前缀总是不变的。)

要获得给定 "a" 对应的长 URL,可以这么写:

url := m["a"]
1

此时 url 的值等于 http://google.com/

注意,使用了 := 就不需要指明 url 的类型为 string,编译器会从右侧的值中推断出来。

# 使程序线程安全

这里,变量 URLStore 是中心化的内存存储。当收到网络流量时,会有很多 Redirect 服务的请求。这些请求其实只涉及读操作:以给定的短 URL 作为键,返回对应的长 URL 的值。然而,对 Add 服务的请求则大不相同,它们会更改 URLStore,添加新的键值对。当在瞬间收到大量更新请求时,可能会产生如下问题:添加操作可能被另一个同类请求打断,写入的长 URL 值可能会丢失;另外,读取和更改同时进行,导致可能读到脏数据。代码中的 map 并不保证当开始更新数据时,会彻底阻止另一个更新操作的启动。也就是说,map 不是线程安全的,goto 会并发地为很多请求提供服务。因此必须使 URLStore 是线程安全的,以便可以从不同的线程访问它。最简单和经典的方法是为其增加一个锁,它是 Go 标准库 sync 包中的 Mutex 类型,必须导入到我们的代码中(关于锁详见 9.3 节)。

现在,我们把 URLStore 类型的定义更改为一个结构体(就是字段的集合,类似 C 或 Java ,10 章 介绍了结构体),它含有两个字段:mapsync 包的 RWMutex

import "sync"
type URLStore struct {
	urls map[string]string		// map from short to long URLs
	mu sync.RWMutex
}
1
2
3
4
5

RWMutex 有两种锁:分别对应读和写。多个客户端可以同时设置读锁,但只有一个客户端可以设置写锁(以排除所有的读锁),有效地串行化变更,使他们按顺序生效。

我们将在 Get 函数中实现 Redirect 服务的读请求,在 Set 函数中实现 Add 服务的写请求。Get 函数类似下面这样:

func (s *URLStore) Get(key string) string {
	s.mu.RLock()
	url := s.urls[key]
	s.mu.RUnlock()
	return url
}
1
2
3
4
5
6

函数按照键(短 URL)返回对应映射后的 URL。它所处理的变量是指针类型(见 4.9 节),指向 URLStore。但在读取值之前,先用 s.mu.RLock() 放置一个读锁,这样就不会有更新操作妨碍读取。数据读取后撤销锁定,以便挂起的更新操作可以开始。如果键不存在于 map 中会怎样?会返回字符串的零值(空字符串)。注意点号(.)类似面向对象的语言:在 smu 字段上调用方法 RLock()

Set 函数同时需要 URL 的键值对,且必须放置写锁 Lock() 来排除同一时刻任何其他更新操作。函数返回布尔值 truefalse 来表示 Set 操作是否成功:

func (s *URLStore) Set(key, url string) bool {
	s.mu.Lock()
	_, present := s.urls[key]
	if present {
		s.mu.Unlock()
		return false
	}
	s.urls[key] = url
	s.mu.Unlock()
	return true
}
1
2
3
4
5
6
7
8
9
10
11

形式 _, present := s.urls[key] 可以测试 map 中是否已经包含该键,包含则 presenttrue,否则为 false。这种形式称为“逗号 ok 模式”,在 Go 代码中会频繁出现。如果键已存在,Set 函数直接返回布尔值 false,map 不会被更新(这样可以保证短 URL 不会重复)。如果键不存在,把它加入 map 中并返回 true。左侧 _ 是一个值的占位符,赋值给 _ 来表明我们不会使用它。注意在更新后尽早调用 Unlock() 来释放对 URLStore 的锁定。

# 使用 defer 简化代码

目前代码还比较简单,容易记得操作完成后调用 Unlock() 解锁。然而在代码更复杂时很容易忘记解锁,或者放置在错误的位置,往往导致问题很难追踪。对于这种情况 Go 提供了一个特殊关键字 defer(见 6.4 节)。在本例中,可以在 Lock 之后立即示意 Unlock,不过其效果是 Unlock() 只会在函数返回之前被调用。

Get 可以简化成以下代码(我们消除了本地变量 url):

func (s *URLStore) Get(key string) string {
	s.mu.RLock()
	defer s.mu.RUnlock()
	return s.urls[key]
}
1
2
3
4
5

Set 的逻辑在某种程度上也变得清晰了(我们不用再考虑解锁的事了):

func (s *URLStore) Set(key, url string) bool {
	s.mu.Lock()
	defer s.mu.Unlock()
	_, present := s.urls[key]
	if present {
		return false
	}
	s.urls[key] = url
	return true
}
1
2
3
4
5
6
7
8
9
10

# URLStore 工厂函数

URLStore 结构体中包含 map 类型的字段,使用前必须先用 make 初始化。在 Go 中创建一个结构体实例,一般是通过定义一个前缀为 New,能返回该类型已初始化实例的函数(通常是指向实例的指针)。

func NewURLStore() *URLStore {
	return &URLStore{ urls: make(map[string]string) }
}
1
2
3

return 语句中,创建了 URLStore 字面量实例,其中包含初始化了的 map 映射。锁无需特别指明初始化,这是 Go 创建结构体实例的惯例。& 是取址运算符,它将我们要返回的内容变成指针,因为 NewURLStore 返回类型是 *URLStore。然后调用该函数来创建 URLStore 变量:

var store = NewURLStore()
1

# 使用 URLStore

要新增一对短/长 URL 到 map 中,我们只需调用 s 上的 Set 方法,由于返回布尔值,可以把它包裹在 if 语句中:

if s.Set("a", "http://google.com") {
	// 成功
}
1
2
3

要获取给定短 URL 对应的长 URL,调用 s 上的 Get 方法,将返回值放入变量 url

if url := s.Get("a"); url != "" {
	// 重定向到 url
} else {
	// 键未找到
}
1
2
3
4
5

这里我们利用 Go 语言 if 语句的特性,可以在起始部分、条件判断前放置初始化语句。另外还需要一个 Count 方法以获取 map 中键值对的数量,可以使用内建的 len 函数:

func (s *URLStore) Count() int {
	s.mu.RLock()
	defer s.mu.RUnlock()
	return len(s.urls)
}
1
2
3
4
5

如何根据给定的长 URL 计算出短 URL 呢?为此我们创建一个函数 genKey(n int) string {…},将 s.Count() 的当前值作为其整型参数传入。(具体算法并不重要,示例代码可以在 key.go 找到。)

现在,我们可以创建一个 Put 方法,接收一个长 URL,用 genKey 生成其短 URL 键,调用 Set 方法在此键下存储长 URL 数据,然后返回这个键:

func (s *URLStore) Put(url string) string {
	for {
		key := genKey(s.Count())
		if s.Set(key, url) {
			return key
		}
	}
	// shouldn’t get here
	return ""
}
1
2
3
4
5
6
7
8
9
10

for 循环会一直尝试调用 Set 直到成功为止(意味着生成了一个尚未存在的短网址)。现在我们定义好了数据存储,以及配套的可工作的函数(见代码 store.go)。但这本身并不能完成任务,我们还需要开发 web 服务器以交付 AddRedirect 服务。