使用Redis构建自动补全程序

Published on 2017 - 06 - 13

在Web领域里面,自动补全(autocomplete)是一种能够让用户在不进行搜索的情况下,快速找到所需东西的技术。自动补全一般会根据用户已输入的字母来查找所有以已输入字母为开头的单词,有些自动补全甚至可以在用户输入句子开头的时候自动补充完整个句子。比如说,Google搜索的自动补全就向我们展示了,Betty White在《周六夜现场》上现身一事在发生数年之后的今天仍然热度不减(因为Betty White是一个话题人物,所以这并不奇怪)。Web浏览器在用户向地址栏中输入信息的时候,也会通过自动补全来展示用户最近访问过的网址,以此来帮助用户快速地再次访问某个网站,另外Web浏览器内置的自动补全还会帮助用户记忆各个网站的登录名。以上提到的各种自动补全功能都旨在帮助用户更快地访问信息。类似Google搜索栏这样的自动补全是由很多TB的远程数据驱动的,而类似浏览器历史记录和网站登录框这样的自动补全则是由体积小得多的本地数据库驱动的。但所有的这些自动补全功能都可以让我们在更短的时间内找到想要的东西。

本节将构建两种不同类型的自动补全,它们使用的结构、选择的自动补全算法以及完成操作所需的时间都不相同。第一个自动补全通过使用联系人列表来记录用户最近联系过的100个人,并尝试尽可能地减少实现自动补全所需的内存。而第二个自动补全则为更大的联系人列表提供了更好的性能和可扩展性,但实现这些列表所花费的内存也会更多一些。下面就让我们来了解一下,实现联系人自动补全的具体方法。

自动补全最近联系人

本节将实现一个用于记录最近联系人的自动补全程序。为了增加游戏的社交元素,并让用户快速地查找和记忆亲密的玩家,Fake Game公司正考虑为他们的客户端创建一个联系人列表,并使用这个列表来记录每个用户最近联系过的100个玩家。当用户打算在客户端发起一次聊天并开始输入聊天对象的名字时,自动补全就会根据用户已经输入的文字,列出那些昵称以已输入文字为开头的人。图1展示了一个这样的自动补全示例。

因为服务器上的数百万用户都需要有一个属于自己的联系人列表来存储最近联系过的100个人,所以我们需要在能够快速向列表里面添加用户或者删除用户的前提下,尽量减少存储这些联系人列表带来的内存消耗。因为Redis的列表会以有序的方式来存储元素,并且和Redis提供的其他结构相比,列表占用的内存是最少的,所以我们选择使用列表来存储用户的联系人信息。可惜的是,Redis列表提供的功能并不足以让我们在Redis内部完成自动补全操作,因此实际的自动补全操作将会放到Redis之外的Python里面执行,这种做法使得程序可以尽量减少Redis存储和更新用户最近联系人列表所需的内存数量,并将较为简单的过滤工作交给Python来执行。

构建最近联系人自动补全列表通常需要对Redis执行3个操作。第一个操作就是添加或者更新一个联系人,让他成为最新的被联系用户,这个操作包含以下3个步骤。

  1. 如果指定的联系人已经存在于最近联系人列表里面,那么从列表里面移除他。
  2. 将指定的联系人添加到最近联系人列表的最前面。
  3. 如果在添加操作完成之后,最近联系人列表包含的联系人数量超过了100个,那么对列表进行修剪,只保留位于列表前面的100个联系人。

以上描述的3个操作可以通过依次执行LREM命令、LPUSH命令和LTRIM命令来实现,并且为了确保操作不会带有任何竞争条件,我们会使用由MULTI命令和EXEC命令构成的事务包裹起LREM、LPUSH和LTRIM这3个命令。代码清单1展示了这个操作的具体实现代码。

def add_update_contact(conn, user, contact):
    ac_list = 'recent:' + user
    pipeline = conn.pipeline(True)     #A
    pipeline.lrem(ac_list, contact)    #B
    pipeline.lpush(ac_list, contact)   #C
    pipeline.ltrim(ac_list, 0, 99)     #D
    pipeline.execute()                 #E
#A Set up the atomic operation
#B Remove the contact from the list if it exists
#C Push the item onto the front of the list
#D Remove anything beyond the 100th item
#E Actually execute everything

跟之前提到过的一样,如果指定的联系人已经存在,那么add_update_contact()函数将从列表里面移除该联系人,然后将他重新推入列表的最左端,最后对列表进行修剪以防止联系人人数超过限制。

构建最近联系人自动补全列表要做的第二个操作,就是在用户不想再看见某个联系人的时候,将指定的联系人从联系人列表里面移除掉,这个操作可以通过以下这个LREM调用来完成:

def remove_contact(conn, user, contact):
    conn.lrem('recent:' + user, contact)

构建最近联系人自动补全列表需要执行的最后一个操作,就是获取自动补全列表并查找匹配的用户。因为实际的自动补全处理是在Python里面完成的,所以操作需要首先获取整个列表结构,然后再在Python里面处理它,正如代码清单2所示。

def fetch_autocomplete_list(conn, user, prefix):
    candidates = conn.lrange('recent:' + user, 0, -1) #A
    matches = []
    for candidate in candidates:                      #B
        if candidate.lower().startswith(prefix.lower()):      #B
            matches.append(candidate)                 #C
    return matches                                    #D
#A Fetch the autocomplete list
#B Check each candidate
#C We found a match
#D Return all of the matches

fetch_autocomplete_list()函数首先获取整个自动补全列表,然后根据联系人的名字是否带有指定的前缀来判断是否对联系人进行过滤,最后返回过滤后的结果。因为这个操作非常简单,所以如果我们发现服务器在计算自动补全列表方面花费了太多时间,那么可以考虑把这个功能交给客户端来实现,客户端只需要在联系人列表被更新之后重新获取一次整个列表就可以了。

因为我们已经预先考虑到了“从列表里面移除一个元素所需的时间与列表长度成正比”这个问题,并明确地限制最近联系人列表最多只能存储100个联系人,所以本节给出的自动补全实现可以运行得非常好,并且速度也足够快,但它并不适合用来处理非常大的列表。如果你需要一个能够存储更多元素的最常使用列表(most-recently-used list)或者最少使用列表(least-recently-used list),那么可以考虑使用带有时间戳的有序集合来代替本节介绍的最近联系人列表。

通讯录自动补全

在前面的自动补全例子里面,Redis主要用于记录联系人列表,而非实际地执行自动补全操作。对于比较短的列表来说,这种做法还算可行,但对于非常长的列表来说,仅仅为了找到几个元素而获取成千上万个元素,是一种非常浪费资源的做法。因此,为了对包含非常多元素的列表进行自动补全,我们必须直接在Redis内部完成查找匹配元素的工作。

对于Fake Game公司来说,带有自动补全特性的最近联系人聊天功能是游戏里面最常用的社交功能,而游戏中第二常用的社交功能——邮件功能正在变得越来越受欢迎,为了让邮件功能的发展势头继续保持下去,我们将为邮件功能添加自动补全特性。但是为了防止邮件功能被滥用,并避免用户接收到不请自来的邮件,我们决定只允许用户向属于同一“公会”(公会就是游戏里面的社交群组)的其他玩家发送邮件。

因为一个公会可能会有好几千个成员,所以我们没办法在这里使用之前介绍的基于列表实现的自动补全程序,但是由于每个公会只需要一个自动补全列表,所以在实现这个列表的时候可以稍微多花费一些内存。为了在客户端进行自动补全的时候,尽量减少服务器需要传输给客户端的数据量,我们将使用有序集合来直接在Redis内部完成自动补全的前缀计算工作。

为了存储公会自动补全列表,我们将以一种之前未曾介绍过的方式来使用有序集合。在大多数情况下,我们使用有序集合是为了快速地判断某个元素是否存在于有序集合里面、查看某个成员在有序集合中的位置或索引,以及从有序集合的某个地方快速地按范围取出多个元素。然而这一次,我们将把有序集合里面的所有分值都设置为0——这种做法使得我们可以使用有序集合的另一个特性:当所有成员的分值都相同时,有序集合将根据成员的名字来进行排序;而当所有成员的分值都是0的时候,成员将按照字符串的二进制顺序进行排序。为了执行自动补全操作,程序会以小写字母的方式插入联系人的名字,并且为了方便起见,程序规定用户的名字只能包含英文字母,这样的话就不需要考虑如何处理数字或者符号了。

那么我们该如何实现这个自动补全功能呢?首先,如果我们将用户的名字看作是类似abc,abca,abcd,…,abd这样的有序字符串序列,那么查找带有abc前缀的单词实际上就是查找介于abbz...之后和abd之前的字符串。如果我们知道第一个排在abbz之前的元素的排名以及第一个排在abd之后的元素的排名,那么就可以用一个ZRANGE调用来取得所有介于abbz...和abd之间的元素,而问题就在于我们并不知道那两个元素的具体排名。为了解决这个问题,我们需要向有序集合分别插入两个元素,一个元素排在abbz...的后面,而另一个元素则排在abd的前面,接着根据这两个元素的排名来调用ZRANGE命令,最后移除被插入的两个元素。

因为在ASCII编码里面,排在z后面的第一个字符就是左花括号{,所以我们只要将{拼接到abc前缀的末尾,就可以得出元素abc{,这个元素既位于abd之前,又位于所有带有abc前缀的合法名字之后。同样的,只要将{追加到abb的末尾,就可以得出元素abb{,这个元素位于所有带有abc前缀的合法名字之前,可以在按范围查找所有带有abc前缀的名字时,将其用作起始元素。另一方面,因为在ASCII编码里面,第一个排在a前面的字符就是反引号`,所以如果我们要查找的是带有aba前缀的名字,而不是带有abc前缀的名字,那么可以使用`ab作为范围查找的起始元素,并将aba{用作范围查找的结束元素。

综上所述,通过将给定前缀的最后一个字符替换为第一个排在该字符前面的字符,可以得到前缀的前驱(predecessor),而通过给前缀的末尾拼接上左花括号,可以得到前缀的后继(successor)。为了防止多个前缀搜索同时进行时出现任何问题,程序还会给前缀拼接一个左花括号,以便在有需要的时候,根据这个左花括号来过滤掉被插入有序集合里面的起始元素和结束元素。代码清单3展示了这个根据给定前缀生成查找范围的函数。

valid_characters = '`abcdefghijklmnopqrstuvwxyz{'             #A

def find_prefix_range(prefix):
    posn = bisect.bisect_left(valid_characters, prefix[-1:])  #B
    suffix = valid_characters[(posn or 1) - 1]                #C
    return prefix[:-1] + suffix + '{', prefix + '{'           #D
#A Set up our list of characters that we know about
#B Find the position of prefix character in our list of characters
#C Find the predecessor character
#D Return the range

因为前面花了那么多篇幅来描述如何根据给定的前缀来生成查找范围,所以可能会有读者对这个功能只需要寥寥数行就能实现而感到惊讶。find_prefix_range()函数要做的就是使用bisect模块在预先排好序的字符序列里面找到前缀的最后一个字符,并据此来查找第一个排在该字符前面的字符。

字符集与国际化对于只使用a~z字符的语言来说,这个在ASCII编码里面查找前一个字符和后一个字符的方法可以运作得非常好,但如果你要处理的字符并不仅仅限于a~z范围,那么你还需要解决其他几个问题。

首先,你需要想办法把所有字符都转换为字节,常见的做法是使用UTF-8、UTF-16或者UTF-32字符编码(UTF-16和UTF-32有大端版本和小端版本可用,但只有大端版本可以在我们所处的情况下运作)。其次,你需要找出自己想要支持的字符范围,并确保你的字符编码在你所选范围的前面和后面都至少留有一个字符。最后,你需要使用位于范围前面和后面的字符来分别代替前面例子中的反引号`和左花括号{。

好在我们的算法只关心编码而不是字符在底层的排列顺序,所以无论你使用的是UTF-8,还是大端或者小端的UTF-16、UTF-32,你都可以使用空字节(null)来代替反引号,并使用你的编码和语言支持的最大值来代替左花括号。(某些语言的绑定数量是比较有限的,它们在UTF-16上面最大只能支持Unicode码点U+ffff,在UTF-32上面最大只能支持Unicode码点U+2ffff。)

在确认了需要查找的范围之后,程序会将起始元素和结束元素插入有序集合里面,然后查看两个被插入元素的排名,并从它们之间取出一些元素,最后再从有序集合里面移除这两个元素(为了避免滋扰用户,程序最多只会取出10个元素)。为了防止自动补全程序在多个公会成员同时向同一个公会成员发送消息的时候,将多个相同的起始元素和结束元素重复地添加到有序集合里面,或者错误地从有序集合里面移除了由其他自动补全程序添加的起始元素和结束元素,自动补全程序会将一个随机生成的128位全局唯一标识符(UUID)添加到起始元素和结束元素的后面。另外自动补全程序还会在插入起始元素和结束元素之后,通过使用WATCH、MULTI和EXEC来确保有序集合不会在进行范围查找和范围取值期间发生变化。代码清单4展示了自动补全函数的完整代码。

def autocomplete_on_prefix(conn, guild, prefix):
    start, end = find_prefix_range(prefix)                 #A
    identifier = str(uuid.uuid4())                         #A
    start += identifier                                    #A
    end += identifier                                      #A
    zset_name = 'members:' + guild

    conn.zadd(zset_name, start, 0, end, 0)                 #B
    pipeline = conn.pipeline(True)
    while 1:
        try:
            pipeline.watch(zset_name)
            sindex = pipeline.zrank(zset_name, start)      #C
            eindex = pipeline.zrank(zset_name, end)        #C
            erange = min(sindex + 9, eindex - 2)           #C
            pipeline.multi()
            pipeline.zrem(zset_name, start, end)           #D
            pipeline.zrange(zset_name, sindex, erange)     #D
            items = pipeline.execute()[-1]                 #D
            break
        except redis.exceptions.WatchError:                #E
            continue                                       #E

    return [item for item in items if '{' not in item]     #F
#A Find the start/end range for the prefix
#B Add the start/end range items to the ZSET
#C Find the ranks of our end points
#D Get the values inside our range, and clean up
#E Retry if someone modified our autocomplete zset
#F Remove start/end entries if an autocomplete was in progress

autocomplete_on_prefix()函数的大部分代码都用于簿记和设置工作。函数首先获取起始元素和结束元素,并将它们添加到公会的自动补全有序集合里面,在添加操作完成之后,函数会使用WATCH命令来监视有序集合,并根据起始元素和结束元素在有序集合中的排名,从它们之间取出一些元素,最后执行相应的清理操作。

加入公会和离开公会这两个操作的实现都非常简单直接:前者只需要使用ZADD命令将用户添加到公会的有序集合里面就可以了,而后者只需要使用ZREM命令将用户从公会的有序集合里面移除掉就可以了。代码清单6-5展示了这两个操作的实现代码。

def join_guild(conn, guild, user):
    conn.zadd('members:' + guild, user, 0)

def leave_guild(conn, guild, user):
    conn.zrem('members:' + guild, user)

对于自动补全来说,加入公会或者离开公会都是非常简单的——只要将用户的名字加入有序集合里面,或者从有序集合里面移除用户的名字就可以了。

通过向有序集合添加元素来创建查找范围,并在取得范围内的元素之后移除之前添加的元素,这是一种非常有用的技术。这种技术同样可以应用在任何已排序索引(sorted index)上面。这种技术能够应用于几种不同类型的范围查询,并且不需要通过添加元素来创建范围。

在自动补全程序向有序集合里面添加起始元素和结束元素的时候,我们需要谨慎地处理其他正在执行的自动补全操作,这也是程序里面用到了WATCH命令的原因。但是随着负载的增加,程序进行重试的次数可能会越来越多,导致资源被白白浪费。接下来的一节将介绍如何通过使用锁来减少对WATCH命令的使用,甚至使用锁来代替WATCH命令,从而达到避免重试、提升性能并在某些情况下简化代码的效果。

参考文档

  • Redis实战 第6章 使用Redis构建应用程序组件