Sử dụng Redis để dựng một Nosql Autocomplete Search Index

Autocomplete search?

Với mỗi một chức năng tìm kiếm, việc tự động gợi ý các từ khóa ngay khi người dùng gõ vào ô tìm kiếm có hai mục đích chính:

- Giúp người dùng lựa chọn được từ khóa tìm kiếm thích hợp một cách nhanh chóng, tăng trải nghiệm người dùng

- Một phần nào đó giúp cho từ khóa được chuẩn hóa từ đó góp phần tối ưu được kết quả tìm kiếm cho người dùng

Why?

Nếu bạn đang sử dụng một search engine bất kì nào đó như ApacheSolr hay Elasticsearch thì quên luôn cái này đi, hoặc xem để biết. Vì ApacheSolr hay Elasticsearch đều hỗ trợ bạn làm điều này rất đơn giản với hiệu năng cao mà không cần phải lăn tăn gì cả.
Còn nếu bạn không có thời gian tìm hiểu về search engine, trong khi lượng người dùng tìm kiếm trên hệ thống của bạn đang tăng lên rất nhanh, việc autocomplete search lúc này chắc chắn đã bắt đầu làm cho hệ thống của bạn trở nên ì ạch thì bài viết này có thể hữu ích.
Redis là gì? và tại sao lại dùng Redis?
Trả lời: Redis là cái thằng nosql nổi tiếng, muốn biết tiếp thì vào đây
Nếu bạn dùng sql để thực hiện việc autocomplete search chẳng hạn, nhiều khả năng bạn phải truy vấn như thế này

SELECT name FROM product WHERE LOWER(name) LIKE "quần%"

Truy vấn này sẽ duyệt qua tất cả các bản ghi trong bảng "product" để lấy ra các bản ghi có tiền tố là "quần", tuy nhiên khi lượng dữ liệu của bạn lớn đến một mức độ nào đó, cùng với việc lượng truy cập vào hệ thống của bạn cùng lúc là rất nhiều, thì câu truy vấn sql này sẽ trở nên rất chậm.

Indexing

Ý tưởng: Chặt một từ ra thành Ngram, lưu các gram này vào một Redis Sortedset. Ở kết thúc của mỗi từ ta thêm một kí tự đặc biệt để đánh dấu từ hoàn chỉnh
Ví dụ:
Từ "quan ao bao ho" và từ "quan ao" sẽ được index vào sorted set có dạng:

1. q
2. qu
3. qua
4. quan
5. quan|_|
6. quan a
7. quan ao
8. quan ao*
9. quan ao|_|
10. quan ao b
11. quan ao ba
12. quan ao bao
13. quan ao bao|_|
14. quan ao bao h
15. quan ao bao ho
16. quan ao bao ho*

Ghi chú: kí tự (|_| là của người viết tự thêm vào để hiểu đó là một khoảng trắng cho dễ hình dung)

Khi truy vấn, người dùng gõ "qua" ta tìm đến vị trí của "qua" trong redis (trong ví dụ trên là thứ 3), ta sẽ tìm tất cả các từ có dấu kết thúc (*) từ vị trí thứ 3 trở đi, kiểm tra các kí tự bắt đầu để loại bỏ và dừng việc tìm kiếm ngay sau khi xuất hiện gram khác từ "qua".


Ngoài ra còn có một số cách khác để thực hiện index với Redis sorted set không phải dùng Ngram và cũng sẽ cho ra kết quả khác, dựa trên ý tưởng inverted index. Sẽ đề cập trong bài viết khác

Mã nguồn demo viết bằng python

 import redis  
   
 r = redis.StrictRedis(host='localhost', port=6379, db=0)  
   
 # Create the completion sorted set  
 if r.exists('compl') == False:  
     print "Loading entries in the Redis DB\n"  
     # file-names.txt contants product name for each line  
     f = open('file-names.txt',"r")  
     for line in f:  
         n = line.strip()  
         for l in range(1,len(n)):  
             prefix = n[0:l]  
             r.zadd('compl',0,prefix)  
         r.zadd('compl',0,n+"*")  
 else:  
     print "NOT loading entries, there is already a 'compl' key\n"  
   
 def complete(r,prefix,count):  
     results = []  
     rangelen = 50 # This is not random, try to get replies < MTU size  
     start = r.zrank('compl',prefix)  
     if not start:  
         return []  
     while (len(results) != count):  
         range = r.zrange('compl',start,start+rangelen-1)  
         start += rangelen  
         if not range or len(range) == 0:  
             break  
         for entry in range:  
             minlen = min(len(entry),len(prefix))  
             if entry[0:minlen] != prefix[0:minlen]:  
                 count = len(results)  
                 break  
             if entry[-1] == "*" and len(results) != count:  
                 results.append(entry[0:-1])  
     return results  
   
 def autoComplete():  
     print complete(r,"quan",50)  
   
 if __name__ == "__main__":  
     autoComplete()