您好,匿名用户
随意问技术百科期待您的加入

怎样设计一个轻量的用户autocomplete系统

0 投票

我最近在设计一个系统时需要有一个用户下拉选择的功能,设计成输入首字母自动联想的autocomplete模式。现在在设计后端数据结构上遇到了些麻烦。目前是我直接用mysql的LIKE来做的这一功能,但如果随着用户和访问量的增长,这样肯定很慢。

我使用的是redis缓存,用redis的朋友都应该读过那篇用redis实现autocomplete的文章。不过我要说的是,这篇文章并不解决我的问题。因为它只能完成关键词的联想功能,但它的关键词是无状态的,没有任何索引标记它的id。也就是说它除了能完成自动联想以外,无法完成关键词与用户的关联过程。

另一个缺点是,这玩意索引的代价太高了,要对每个字都做分词,然后存入cache中做索引。而用户名是可以修改的,我觉得每次修改再重建索引的成本太大。

我想了另一个方案,利用redis的交集功能来做搜索,这也是比较流行的方法。比如一个用户名叫Hello,用php代码来展示如何处理这个用户名,为了展示方便,我只处理英文字母

$user_name = strtolower('Hello');
$user_id = 1001;
$len = strlen($user_name);

for ($pos = 0; $pos < $len; $pos ++) {
    $key = md5($user_name[$pos]);
    $redis->sAdd('user_name:' . $key . ':' . $pos, $user_id);
}

在上面的代码中,我把每个字母用md5哈希一下然后和他的位置值$pos共同组成一个redis索引。这样如果在所有用户名都用这种办法做索引后,我们就可以使用redis的交集功能来做搜索了

$keyword = strtolower('he');    // 测试的关键词
$indexes = array();             // 索引集合
$len = strlen($keyword);

for ($pos = 0; $pos < $len; $pos ++) {
    $key = md5($keyword[$pos]);
    $indexes[] = 'user_name:' . $key . ':' . $pos;
}

// 得出结果仅需一步, 求它们的交集
$result = $redis->sInter($indexes);

但这个办法有几个缺陷

  1. 我觉得还是偏重,因为我只想实现一个用户名自动联想的功能而不是搜索。这样的系统还要维护一套庞大的索引,每次更新用户名还得一个一个删掉然后再塞入新的。
  2. 无法做LIMITOFFSET啊,翻页怎么半,万一一个交集非常大,岂不是要把系统撑死
  3. 模糊查询的功能偏弱,只能处理以关键词开头的情况。不过这个不是重点,能把上面两点解决就很好了。

不知道各位有什么好的方案?

用户头像 提问 2012年 12月1日 @ Emiya Shirou 上等兵 (438 威望)
分享到:

1个回答

0 投票
 
最佳答案

antirez的方法和你的还是不一样的,他是自动完成,所以只需要提示一个值就行了,而你需要的是多个值,用他的方法,提示多个值在效率上没法保证。而且还需要能修改,用他那个肯定不行。

而你自己这个做法复杂度太高了。sInter的复杂度是O(N*M),N表示最小的集合长度,M表示集合数。当用户输入比较短时,比如He,你M=2,N而N应该会随着数据量越来越大。当用户输入长一些的时候,M和N都会变得非常大。所以我个人觉得不可取。

我的建议是使用类似trie树的结构,使用Redis的话做法也很简单。将所有usename切成多个前缀。比如“foo”切成

f
fo
foo

几个前缀,每一个前缀维护一个set,后面跟着uname:uid的形式,这样你反查uid的需求也能满足。
这样如果有两个用户:

100001:foo
100002:fou

你的存储就是

f => foo:100001,fou:100002
fo => foo:100001,fou:100002
foo => foo:100001
fou => fou:100001

这样查询的时候一次查询就可以了。修改的时候在所有前缀里把对应的uname:uid删除掉即可。比如foo这个用户名修改为bar了,就把foo这个删除,再对新名字的前缀对应的集合进行维护即可。

srem f foo:100001
srem fo foo:100001
srem foo foo:100001

另外,如果你把set换成zset,score可以用到存热度,比如上面的fou和foo,如果有用户输入f选择了foo,那么就对foo在f对应的集合里的score加1。

zincrby f 1 foo

这样排在前面的就是用户经常选择的了。

用户头像 回复 2012年 12月1日 @ Cho'Gath 上等兵 (267 威望)
选中 2012年 12月1日 @Emiya Shirou
提一个问题:

相关问题

0 投票
1 回复 38 阅读
0 投票
1 回复 55 阅读
用户头像 提问 2012年 12月1日 @ Hades 上等兵 (152 威望)
0 投票
1 回复 48 阅读
用户头像 提问 2012年 12月1日 @ Renekton 上等兵 (260 威望)
0 投票
1 回复 41 阅读

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...