Redis實作自動補全

本文可作為redis in action第六章的讀書筆記

首先,資料庫裡有 abc,abks,pskm,aspqbmc,而自動補全,至少有兩種:

1 字首補全

  例如我輸入'ab',給我傳回abc與abks

2 随機補全

  例如我輸入'm p'給我傳回pskm,aspqbmc

字首補全

ok,咱們先說這個字首補全

如果資料量不大的話,java的String類型有startWith方法,直接周遊調用startWith方法即可

如果資料量大的話,怎麼辦?

使用redis,zset

具體怎麼辦呢?

首先我們知道zset裡面存放的是member-score的值對,預設score從小到大排序,如果score相等,那麼安裝member排序。

然後我們把abc,abks,pskm,aspqbmc放入zset,score都是0

那麼zset裡的排序情況如下:

abc------0

abks-----0

aspqbmc--0

pskm-----0

我們要比對abk,如果我們能知道所有能比對abk的member在zset裡的起始位置,那就好辦了。

下面的問題就是我怎麼知道能比對abk的字元都有什麼,都在zset的什麼位置呢?

我們知道在ascii碼裡小寫字母a的前面是',z的後面是{

那麼能比對abk的字元串肯定就在abj{和abk{之間

能比對abka的字元就肯定在abk`{和abka{之間

那剩下的就簡單了,我們吧起始字元串都插入zset,然後獲得startIndex和endIndex,再從startIndex和endIndex中取出所有的member,這不就是最後的答案麼?當然,最後還得再從庫裡删除插入的那兩個字元串

具體代碼

public String[] findPrefixRange(String prefix) {
        int posn = VALID_CHARACTERS.indexOf(prefix.charAt(prefix.length() - 1));
        char suffix = VALID_CHARACTERS.charAt(posn > 0 ? posn - 1 : 0);
        String start = prefix.substring(0, prefix.length() - 1) + suffix + '{';
        String end = prefix + '{';
        System.out.println(prefix+"  "+start+"---"+end);
        return new String[]{start, end};
    }      

如果prefix給定abka,那麼上面的方法就列印出abka  abk`{---abka{

    然後開始查找

 @SuppressWarnings("unchecked")

public Set<String> autocompleteOnPrefix(Jedis conn, String guild, String prefix) {
        String[] range = findPrefixRange(prefix);
        String start = range[0];
        String end = range[1];
        
        String identifier = UUID.randomUUID().toString();
        start += identifier; //1加這個東西 幹什麼?
        end += identifier;
        String zsetName = "members:" + guild;


        conn.zadd(zsetName, 0, start);
        conn.zadd(zsetName, 0, end);
        


        Set<String> items = null;
        while (true){   //2為什麼要循環?
            conn.watch(zsetName);   //3為什麼要watch
            int sindex = conn.zrank(zsetName, start).intValue();
            int eindex = conn.zrank(zsetName, end).intValue();
            int erange = Math.min(sindex + 9, eindex - 2);//一次隻找出10個


            Transaction trans = conn.multi();
            trans.zrem(zsetName, start);
            trans.zrem(zsetName, end);
            trans.zrange(zsetName, sindex, erange);
            List<Object> results = trans.exec();
            
            if (results != null){
                items = (Set<String>)results.get(results.size() - 1);
                break; //4為什麼要退出?
            }
        }


    //剔除開始加入的那兩個标記
        for (Iterator<String> iterator = items.iterator(); iterator.hasNext(); ){
            if (iterator.next().indexOf('{') != -1){
                iterator.remove();
            }
        }
        return items;
    }      

讀到上面的代碼,肯定會有幾個問題

咱們一個一個說

辨別1的前面,就是獲得那兩個起始與結尾的字元串,很容易了解

那為什麼要給後面加一個uuid呢?

如果得到的一個起始字元串是abk{,但是我們的資料庫裡本身就有一個abk{,最後怎麼删除呀?

表示3 那邊為什麼要加watch呀

這個還用說麼,我看的時候,你就别看了

關于redis的事務問題,大家看

辨別2 while循環,你明白表示3就明白辨別2了,如果我查的時候,有别的用戶端也在查,那我就退出重來麼

表示4 退出 好了解

在負載很大的情況下,watch那邊就會經常重試,下一節,我們試着用鎖來替換watch

另外如果我要支援漢字怎麼辦?用空代替',用編碼支援的最大值來代替{就OK了。

随機補全