翻译进度
9
分块数量
2
参与人数

19.3. 数据结构分析

这是一篇社区协同翻译的文章,你可以点击右边区块信息里的『改进』按钮向译者提交改进建议。

[ 这个章节的代码,可以在 goto_v1\store.go 中找到 ]

当我们的应用在生产环境中运行的时候,它将接收到很多短网址的请求,并且还会收到很多将一个长网址变短的请求。我们的程序会用哪些数据结构存储这些数据?如在 章节 19.2 中的 url 类型 (A)和(B)都是一个字符串,并且它们彼此相关: 我们可以将(B)作为键,通过它去获取(A)的值,它们相互映射。为了将数据存储在内存中,我们需要这样一种结构,几乎所有编程语言都存在的,用不同的名字作下标的 hash 表、字典等。

BroQiang 翻译于 6个月前

Go 有一个这样的内置的 map :一个 map[string]strng

键的类型写在 [ ] 里面,后面跟的是值的类型;可以去 章节 8 学习所有和 map 有关的知识。 在任何一个不平凡的程序中,给特定的类型使用一个名称是很有用的。在 Go 中,我们使用关键字 type 可以做到,所以我们定义一个: type URLStore map[string]string

它将短网址映射到长网址,并且都是字符串。

要创建一个该类型命名的变量 m,只需使用:

m := make(URLStore)

假设我们想要存储 http://goto/ahttp://google.com/ 的映射到 m , 我们可以使用这样的语句: m["a"] = "http://google.com/"

(在键始终保持不变的前提下,我们只需要存储 http://goto/ 的后缀来作为一个键)。要检索指定的 a 对应的长网址,我们写: url := m["a"]

然后 url 的值等于 「http://google.com/」 。

注意: 使用 := 我们不需要说明 urlstring 类型: 编译器会从右侧的值中推导出类型。

BroQiang 翻译于 6个月前

使它线程安全:我们的 URLStore 变量是一个重要的内存数据存储,在这里: 一旦我们获得一些流量,将会有许多重定向类型的请求。这些实际上只是读的操作:使用短网址作为键读取,并且将长网址作为值返回。但是 Add 类型的请求是不同的,他们改变了我们的 URLStore,添加了新的键值对。当我们的服务一次性获得需要更新类型的请求时,可能会出现以下问题: 添加操作可能被另一个相同类型的请求打断,并且长网址的值可能不会被写入。也可能会将读取的内容一起修改,导致读取到一个错误的结果。我们的 map 不能保证在开始一个更新操作的时候,一个新的更新开始之前,它会完全终止。换句话说: 一个 map 不是线程安全的,它将会并发处理许多的请求,所以我们必须使我们的 URLStore 类型安全的从一个单独的线程去访问。最简单和经典的方法就是为它添加一个锁。在 Go 中,这是一个标准库中 sync 包中的 Mutex 类型,我们必须将它导入到我们的代码中(详细的锁定参见: 章节 9.3 )。

我们将我们的 URLStore 的类型更改成一个 struct 类型(就这像在 C 或者 Java 中一个字段的集合,我们在 第 10 章 解释了 struct ), 它有两个字段: map 和 一个 sync 包中的 RWMutex

import “sync”

type URLStore struct {

    urls map[string]string  // map 是从短网址到长网址

    mu  sync.RWMutex

}
BroQiang 翻译于 6个月前

一个 RWMutex 有两个锁: 一个用于读取,一个用于写入。多个客户端可以同时获得读取锁,但是只能有一个客户端能够获得写入锁(禁用所有读取器),从而有效的序列化更新,使他们连续的工作。

我们将在一个 Get 方法中实现重定向我们读类型的请求,并且我们添加一个 Set 方法来处理写的请求。Get 方法看起来就像这样:

func (s *URLStore) Get(key string) string {

    s.mu.RLock()

    url := s.urls[key]

    s.mu.RUnlock()

    return url

}
BroQiang 翻译于 6个月前

它传入一个 key (短网址),并将相应的 map 中的值作为 url 返回。这个方法用在一个变量 s 上,它是一个指向我们的 URLStore 的指针(参见: 章节 4.9 )。但是在读取值之前,我们使用 s.mu.RLock() 设置了一个读锁,所以没有更新能够打断读取。读取之后我们解锁,所以等待的更新可以开始执行。如果在 map 中不存在 key 怎么办? 一个字符串类型的零值(空字符串)将被返回。注意面向对象语言中熟悉的 . 符号: 方法 RLock()smu 字段上被调用。

Set 方法需要同时传入一个 key 和 一个 url ,并且必须使用一个写锁 Lock() 来阻止在同一时间的任何其他的更新。它返回一个布尔类型的 true 或者 false 值来表示 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

}
BroQiang 翻译于 6个月前

通过 _, present := s.urls[key] 这种形式,我们可以测试看看我们的 map 是否已经包含了这个 key,存在 present 变成 true,否则为 false。这个就是我们在 Go 代码中经常遇到的所谓的 逗号 ok 模式。如果 key 已经存在, Set 返回一个布尔型的值 false ,并且因为我们从方法返回, map 不会更新(所以我们不允许短网址被重用)。如果这个 key 不存在,我们添加它到 map,并且返回 true。左侧的 _ 是一个值的占位符,并且我们表明了不会使用它,因为我们将它分配给了 _ 。请注意,要尽可能快的(更新之后)解锁我们的 URLStore

使用 defer 来简化代码:

在这种情况下,因为代码简单,它可以很容易的记住去执行 Unlock 。然而,在非常复杂的代码中,就可能会被忘记了或者放在错误的地方,导致的问题难以追踪。对于这种情况,Go 有一个特殊的关键字 defer (参见: 章节 6.4 ),在这种情况下,它允许在执行完锁定后立即发出解锁信号,但其效果是 Unlock() 只会在函数返回之前才会被执行。

Get 可以被简化为 (我们已经去除了局部变量 url):

func (s *URLStore) Get(key string) string {

    s.mu.RLock()

    defer s.mu.RUnlock()

    return s.urls[key]

}

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

}
BroQiang 翻译于 6个月前

URLStore 工厂函数:

URLStore 结构体包含一个 map 字段,在使用它之前,必须要使用 make 初始化。在 Go 中通过定义个 New 前缀的函数来完成创建一个结构体的实例,该函数返回一个被初始化的类型的实例(在这里,大多数情况下,它是一个指向它的指针):

func NewURLStore() *URLStore {

    return &URLStore{ urls: make(map[string]string) }

}

在返回中,我们制造了一个 URLStore 字面,并且初始化 map ,锁不需要特意初始化;这是在 Go 中制造结构体对象的标准方法。 & 是一个地址运算符,将我们返回的内容转换为指针,因为 NewURLStore 需要返回一个指针 *URLStore 。我们只是调用这个函数来制造一个 URLStore 变量 svar s = NewURLStore()

BroQiang 翻译于 6个月前

使用我们的 URLStore:

向我们的 map 添加一对新的 短/长 URL ,我们需要做的是调用 s 上的 Set 方法,并且由于这是一个布尔值,我们能立即包装它到一个 if 语句中:

if s.Set("a", "http://google.com") {

    // success

}

要取回指定短网址 a 的长网址,我们将调用 s 上的 Get 方法,并将结果放到一个 url 变量中:

if url := s.Get(“a”); url != “” {

    // redirect to url

} else {

    // key not found

}

在 Go 中,我们可以使用它的一个特性, if 可以在条件之前,使用一个初始化语句。我们还需要一个 Count() 方法,来为我们计算 map 中的键值对的数量,这是由一个内置的 len 函数实现的。

func (s *URLStore) Count() int {

    s.mu.RLock()

    defer s.mu.RUnlock()

    return len(s.urls)

}

我们如何计算指定的长网址的短网址?我们使用一个函数 genKey(n int) string {…} 并且它的整形参数我们赋予它 s.Count() 当前的值。

BroQiang 翻译于 6个月前

[ 确切的算法并不重要,可以在 key.go 中找到示例代码 ]

我们现在可以做一个 Put 方法,它需要一个长网址,使用 genKey 生成他的短网址 key ,使用 Set 方法,将长网址使用这个(短网址) key 作为下标储存,并返回它的 key:

func (s *URLStore) Put(url string) string {

    for {

        key := genKey(s.Count())

        if s.Set(key, url) {

            return key

        }

    }

    // 不应该到这里

    return ""

}

for 循环一直重试 Set , 直到它成功(表示我们生成了一个尚未存在的短网址)。到现在为止,我们已经定义了我们的数据存储和处理它的函数(可以在 store.go 中找到代码)。但是这本身并没有做任何事,我们还必须去定义一个 web 服务器去提供添加与重定向服务。

BroQiang 翻译于 6个月前

本文章首发在 GolangCaff
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。

参与译者:2
讨论数量: 0
发起讨论


暂无话题~