이번 어플에 추천단어 검색기능이 들어갑니다...


그렇습니다 만만치 않군요 


Mysql 을 쓸까? 라는 생각은 일찌감치 접어뒀습니다. 


대신에 redis 를 사용하기로 하면서 재밌는 포스팅을 발견했습니다.


http://oldblog.antirez.com/post/autocomplete-with-redis.html


해당 포스팅에서 힌트를 얻어 작성을 해보기로 합니다.



< Precondition >

1. 한글 및 영어 및 숫자 자동완성이 가능해야 함. (그 외 문자는 생각안하기로 함)

2. 사용자가 검색한 검색어가 저장되어야 함

3. 한글 자음 자동완성은 제외(e.g ㄱ 을 입력하면  가 , 가족, 가수.... 등등)

4. 혹시 모르니 페이징도 가능해야함 (현 버전에서는 불가능 ㅠㅠ)

5. 우선수위 처리가 되어야함...(사용자들이 많이 검색한 단어가 우선순위로 노출)

6. 단어만 노출되는게 아니라 얼마나 조회되었는지 카운트도 표시되어야 함.... ㅎㄷㄷ


뭐 기획팀에서 나온게 이 정도 입니다... 


가장 문제는 역시 사용자가 검색한 것도 저장되어야 하니 얼마나 많은 단어가 저장될지는 모르는거고 


1억건이 될 수도 있는거고.... 성능이슈가 있으면 안된다는건데.... 



일단 레디스를 사용하기로 했으니 믿고 작성해 봅니다.



# 단어 자르기


가장 우선적으로 한 것은 단어 자르기 입니다. 


예를들어서 사람, 사랑, 사과 등등이 있다고 했을때 


사용자가 "사" 를 입력하게되면 사과 , 사람, 사랑 이 자동완성으로 표시되어야 하죠 


그래서 단어를 자르기 시작합니다. 


코드부터 볼까요??


	public void addWord(final String word) {
		stringRedisTemplate.opsForZSet().add(AUTO_COMPLETE_NAMESPACE, word + "*", 0);
		for (int index = 1; index < word.length(); index++) {
		   stringRedisTemplate.opsForZSet().add(AUTO_COMPLETE_NAMESPACE, word.substring(0, index - 1), 0);
		}
	}

먼저 사용자가 입력한 단어를 저장합니다. 있는 그대로 저장하면서, Wild card 를 하나 넣어줍니다. (*)
그 이유는 실제로 사용자가 입력한 단어를 찾아내기 위함입니다.
두번째로 각 글자를 한글자씩 잘라내어 저장합니다. 
또한, 그냥 입력이 아닙니다. zadd 라는방식을 사용했습니다.(정렬된 셋 방식)

참조 : http://redis.io/commands/zadd




왜 이렇게 하냐면 코드를 쓰기 전 설명처럼 해당 단어의 첫 글자만 입력해도 자동완성 되기 위해서입니다.



# 추천단어 검색


두번째로 할 일은 추천단어 검색입니다.


레디스에 적절하게 값을 입력을 했으니 적절하게 값을 가져오기만 하면 끝나는거죠~


코드를 볼까요??


public List complete(final String prefix, final int count) {
	List results = new ArrayList();
	int prefixLength = prefix.length();
	if (null == prefix || prefixLength == 0) return results;
	
	long start = stringRedisTemplate.opsForZSet().rank(AUTO_COMPLETE_NAMESPACE, prefix);
	if (start < 0) return results;
	

	
	Set> rangeResultsWithScore = stringRedisTemplate.opsForZSet().rangeWithScores(AUTO_COMPLETE_NAMESPACE, start, -1);
	if (rangeResultsWithScore.isEmpty()) return results;

	for (TypedTuple typedTuple : rangeResultsWithScore) {
		String value = typedTuple.getValue();		
		int minLength = Math.min(value.length(), prefixLength);
		if (value.endsWith("*") && value.startsWith(prefix.substring(0, minLength))) {
			results.add(new HashVO(value.replace("*", ""), typedTuple.getScore().intValue()));
		} 
	}
	return results;
}

뭐 나쁘지 않습니다.


HashVO 는 value 와 score 로 이루어진 VO 객체니까 신경안쓰셔도 됩니다~


실제 잘 나오는지 볼까요??




a 로 시작하는걸로 검색을 해봤더니 잘 나옵니다. 


대략 잘라진 단어까지 2만단어가 좀 안되게 있을텐데 속도가 그럭저럭 잘 나오는것 같습니다.



그러나 위 코드에는 심각한 문제가 하나 있습니다. 바로 시간복잡도입니다. 


그렇습니다 사실 평범한 개발자들은 시간복잡도?? 저도 잘 생각 안하고 짭니다... 


바빠 죽겠는데 일정맞추려면 구현이 우선이다... (아주 잘못된 선택이죠... 시스템이 바뀌어야 되는데 ㅠㅠ)


시간복잡도로 말할것 같으면... 빅오표기법으로 나타내며... 그 뭐랄까...





먼저, 해당 함수 내에 있는 반복문의 경우 O(n) 으로 처리되는데, 이 경우는 어쩔 수 없는경우이므로 생략하고요


일단 다른건 생각하지 말고 레디스 쪽만 생각해 봅시다 


위에서 사용한 명령어는 2가지로 나타나는데요, 


먼저 ZRANK 를 볼까요? (참조 : http://redis.io/commands/zrank)


ZRANK 의 경우 시간복잡도는 O(log(N)) 입니다. 제가 알기론... redis 는 정렬된 set 방식의 경우 이진탐색을 합니다

(직접 찾아보세요 ㅎㄷㄷㄷ )


O(log(N)) 의 경우 전체를 뒤지지 않습니다. 그러므로 데이터 양이 늘어나는 만큼 검색 시간도 소요되지만 일정 수준이 되면 

평행한 곡선을 이룹니다. 


자세한 내용은 이쪽을 보세요 (참조 : http://bigocheatsheet.com/)


일단 ZRANK 의 경우 뭐 별로 볼게 없네요 코드상에 문제가 전혀 없습니다. 검색 시간도 짧습니다. 왜냐면 index 번호만 갖고오기 때문이죠~


두번째로 ZRANGEBYSCORE 를 볼까요?? (참조 : http://redis.io/commands/zrangebyscore)


ZRANGEBYSCORE 의 경우 시간복잡도는 O(log(N)+M) 입니다. 뭐여 M 은.. 일단 딱 봐도 M 이 늘어나는 만큼 수행시간이 길어질게 뻔해보입니다.


그렇다면 M 이 무엇이냐?? 


reference 문서에서 보여주듯 M the number of elements being returned 입니다. 


기본적으로 redis 는 정렬된 셋을 돌려줄때 Limit 이 걸립니다. 그래서 항상 최초 indexing 부터 10개를 보여줍니다. 


그러나 위의 코드상에서 보면 a 로 시작하는 모든걸 반환하므로 시간이 곱절로 늘어날 겁니다.. 


a 로 시작하는 단어가 만약에 천만개라면?? 수행시간은 상상할 수도 없겠죠 


그래서 레디스는 M 값을 최소한으로 줄일 것을 권장합니다. 



여러분들은 초고수이기 때문에 아이디어가 샘솟으시겠지만 저는 아니므로 ㅋㅋ 


첫번째 시도는 시작점과 끝지점을 정하도록 합니다. 


예를들어서 인덱싱이 이렇게 있다고 생각해 봅시당



 INDEX

VALUE 

 0

 사람

 1

 사랑해

 2

 사귀자

 3

 사장나오셈


사용자가 "사" 라는 글자를 입력했습니다. 그러면 위의 모든 글자가 나타나야 정상이지요~


그런데 예를들어서 시작지점과 끝 지점을 0 ~ 2 라고 정하면 "사장나오셈" 글자는 사용자에게 반환되지 않습니다.


일단 최대반환갯수는 알아낼 수 있습니다. 그러나 나타나야 될 글자가 반환안되는 문제가 있네요??


좋은아이디어 일 줄 알았는데 역시 저는 초보입니다... 사수한테 혼나야 정신차리지?? 



두번째 시도는 score 를 최대로 활용해 봅니다. 


앞서 설명한 적은 없지만 지금 코드는 스프링 부트에서 사용되고 있습니다. 


stringRedisTemplate 라는 것을 이용해서 작업을 하고 있는데 여기에는 여러가지의 명령어들이 있습니다.


먼저 우리는 정렬된 셋 명령어를 사용할 예정이니 opsForZSet 기능을 사용합니다.


range 명령어에는 크게 4가지의 명령어가 있습니다. 


첫번째로 range(key, start, end) 기능을 살펴볼까요??


별거 없습니다. 첫번째 아이디어인 index 의 범위를 정하는 것 입니다. 


두번째로 rangeWithScores(key, start, end) 입니다. 


첫번째 소개드린 것과 같은 기능이지만 score 정보가 담긴 Tuple 을 제공해 줍니다.


세번째로 rangeByScore(key, min, max) , rangeByScoreWithScores(key, min, max) 기능을 살펴볼까요?


여기서 min , max 는 score 의 점수를 나타냅니다. 예를들어서 min = 0 , max = 5 라고 한다면


score 가 0 ~ 5 범위의 값들만 추출됩니다. 


두개의 다른점은 rangeByScore 는 value 만 반환되고, rangeByScoreWithScores 는 Tuple 이라고 해서 해당 value 의 score 까지 알 수 있습니다.


네번째로 rangeByScore(key, min, max, offset, count) , rangeByScoreWithScores(key, min, max, offset, count) 입니다.


아주 흥미롭게도 offset 과 count 가 존재합니다. 저게 과연 무엇일까요?? 


맞습니다 여러분이 생각하시는 Limit 입니다. 저것을 이용해서 paging 기능을 이용할 수 있습니다. 


첫번째와 두번째 방법에는 한계가 존재합니다 그러니 제외하고 세번째와 네번째 방법중에 선택을 해야 합니다.


일단 저는 3번째 방법을 선택하기로 합니다. 사실 4번째 기능을 이용해 페이징을 할 수 도 있지만 전제조건이 좀 필요합니다. 



** 반드시 기억하세요

rangeByScore 로 시작하는 명령어들은 해당 score 범위안의 모든 값을 전달합니다. 


다시 그 표를 볼까요?? 


 INDEX

VALUE 

Score 

 0

 사람

 1

 1

 사랑해

 1

 2

 사귀자

 3

 3

 사장나오셈

 2


이번에는 Score 까지 표현해봤습니다. 


예를들어서 rangeByScore(key, 1, 2, 0, 2) 를 사용했다고 한다면 Score 가 1 ~ 2 사이의 모든 값을 갖고오되 


2개만 갖고오길 원합니다. 그러면 사용자가 "사" 를 입력했을 경우 


사람, 사랑해만 나타나게 될겁니다. 사장나오셈은 안나온다는 얘깁니다. 


이게 무엇이 문제냐면 사용자가 "사장" 이라고 검색을 할 경우 갖고오는 게시물이 사람, 사랑해 이므로 


사장나오셈은 절대로 첫 페이지에 못가져옵니다. offset 과 count 를 2, 4로 설정해 줘야 갖고온다는 말이 됩니다. 


그러니 페이징은 신중하게 사용하세요~


------------------------------------------------------------------------------------------------



다시 돌아가서 3번째 방법에 대한 이야기를 해볼까요?


우리는 정해야 하는 규칙이 생깁니다. 바로 Score 에 대한 이야기죠~


검색 범위를 정하는 매우 중요한 요소입니다. 


서비스 초반에는 사용자들이 많이 없을테지만 사용자가 늘어난다면 기준이 되는 Score 값이 변화해야 겠죠 


일단 우리는 3이라고 기준범위를 정해놓아볼까요? 


3 미만의 정렬된 셋 데이터는 갖고오지 않습니다. 일단 범위를 줄였다는 얘기는 성능이 좋아짐을 뜻합니다. 


해당 값은 기획팀 및 운영에서 수시로 값을 변경할 수 있으니 객체지향적으로 변화에 유연하게 코드를 짜야합니다.


자꾸 이야기가 새어나가네요 


바로 코드를 볼까요? 이렇게 score 범위를 3으로 지정해 버렸으므로 3이하의 모든 정렬된 셋은 검색에서 제외됩니다.

stringRedisTemplate.opsForZSet().rangeByScoreWithScores(AUTO_COMPLETE_NAMESPACE, 3, 3);



스코어가 3인 값만 딱 나왔네요 ㅎㅎ 흐뭇


범위를 높게 잡으면 높게잡을수록 성능은 좋아질겁니다. 하지만 트레이드 오프로 사용자에게 보여질 자동완성 문자는 줄어들 수 있겠죠 ~ 이것은 실제로 개발자 및 기획자가 정해야 하는 값이니 꼭 참고하시기 바랍니다.



글이 굉장히 길어지고 있습니다. 


저도 당황스럽습니다 이게 아닌데요 


일단 참고 주소를 몇개 드립니다.


http://redis.io/topics/indexes

http://autocomplete.redis.io/


다음번에는 샘플소스인 github 페이지를 공개하도록 하겠습니다. 


또한, 이번에 다루지 않았던 것들을 다룰겁니다. 예를들어서 score 값을 늘리고 줄이는 법등요 


그리고 쓸모없는 값들이 생기지 않을까? 라는 것에 대한 고민도 좀 해볼생각입니다.


어떤거냐구요?? 예를들어서 score 가 1~2개 정도인 값들이 넘쳐날 경우에 기준이 3이게 되면 


이런 값들은 절대 사용자에게 나타나지 않을겁니다, 그리고 기준값이 더 높아지게 되면 노출빈도가 더 낮아지겠지요 


어쩌면 그런생각을 할 지도 모릅니다.. 이거 쓰레기값이자나...?? 메모리만 차지하는데 없애버려?


뭐 어쨋듯 여러가지 생각이 나올 수 있겠지요 또한, 여러가지 아이디어도 반영될 수 있을거고요



개인적인 바램은 해당 구현체를 github 에서 가꿔나가볼까 합니다. 


많은사람들이 참여해서 좀 더 깔끔하게 소스를 다듬고 한다면 어쩌면 새로운 API 가 탄생할 수도 있겠네요












  1. 몽구스 2018.02.07 09:26 신고

    안녕하세요! 레디스로 자동완성을 만들어 보려는 학생입니다! 포스팅 덕분에 큰 도움이 되었어요 감사합니다 ^_^
    하나 여쭤볼 것이 있는데, 레디스를 보니 중복되는 값의 score를 올리는 명령어는 없더라고요, 혹시 일단 레디스에 멤버가 있는지 조회하여 있으면 score를 +1 하고 아니면 score와 멤버를 추가하는 식으로 하신건가요?

    • 몽구스 2018.02.07 09:30 신고

      아, 방금 확인해 봤는데 입력시
      ZADD가 아닌
      ZINCRBY를 이용하면 upsert(update+insert) 같은 기능을 할 수 있네요 !! 혹시 이렇게 하셨나요? 제가 스프링을 해보지 않아서 여쭤봅니다 !! ^-^

    • OKIHOUSE 2018.02.07 10:15 신고

      넵 현재 코드에서는 opsForZSet().incrementScore(value) 함수를 사용하고 있습니다~ (ZINCRBY)

      https://github.com/okihouse/spring-boot-redis-auto-complete

    • 몽구스 2018.02.07 13:11 신고

      답변 정말 감사드려요!!!! 날이 많이 추운데 따뜻하고 행복한 하루 보내셔요 ^-^!



    • 몽구스 2018.02.07 13:24 신고

      질문 하나만 더 드리겠습니다 !!

      먼저 사용자가 입력한 단어를 저장합니다. 있는 그대로 저장하면서, Wild card 를 하나 넣어줍니다. (*)
      그 이유는 실제로 사용자가 입력한 단어를 찾아내기 위함입니다.

      이 부분에서 와일드카드를 넣는 이유가 실제로 사용자가 입력한 단어를 찾아내기 위함이라고 하셨는데, 왜 실제로 사용자가 입력한 단어를 구분해서 저장해야 하는지 이유를 알 수 있을까요?

    • OKIHOUSE 2018.02.07 13:47 신고

      레디스에 직접 해당 구문을 이용하여 값을 넣어보시면 아시겠지만 다음과 같이 값이 들어갈겁니다.

      입력 단어 : 선생님
      레디스 저장 단어:
      선생님*

      선생
      선생님

      이렇게 총 4개의 단어로 저장됩니다.(스코어는 이해를 위해 제외되었습니다)

      사용자에게 보여지는 자동완성 단어는
      선생님* 로 보여지고, 마지막 *는
      view 에서는 삭제되어 보여집니다.

      위와같이 하는 가장 큰 이유는 바로 prefix 검색 기능때문입니다.
      "선" 이라는 단어만 입력해도 "선생님"을 찾기 위함이죠,
      사실 단어 형태소 검색을 구현하기 힘든 구조라 위와 같은 형태만 지원하게 되었고,
      그렇기 때문에 위와 같이 값이 들어갑니다.

      저는 일부 설명만 드린 것이고 핵심내용은 다음 사이트를 참조해보세요~
      http://oldblog.antirez.com/post/autocomplete-with-redis.html

    • 몽구스 2018.02.07 14:51 신고

      정말정말 감사합니다 !! 예까지 들어주시고!!! 감사드려요 ^-^

    • OKIHOUSE 2018.02.07 16:18 신고

      질문글에 중요한 점을 말씀을 안드렸네요~

      왜 실제로 사용자가 입력한 단어를 구분해서 저장해야 하는지 이유를 알 수 있을까요?

      해당 질문에 대한 답변에서 제가 빼먹은 부분이 있네요

      입력 단어 : 선생님
      레디스 저장 단어:
      선생님*

      선생
      선생님

      이 부분에서
      "선생님*" 과 "선생님" 이렇게 2개를 굳이 입력해야 하는 이유를 말씀 안드렸어요~

      그 이유는
      "선생님*" 부분에만 스코어 점수가 입력됩니다
      다른 부분들은 단순히 검색을 위한 부분입니다.

      와일드카드가 포함된 단어가 입력되는 이유입니다.

      이해가 되셨으면 좋겠네요~

      참고로 모든 글을 보시면 더 이해가 쉬우실거에요~

      http://okihouse.tistory.com/search/auto%20complete

    • 몽구스 2018.02.08 12:47 신고

      아.. 글이 더 있었군요 ㅠ.ㅠ 몰랐습니다 감사드려요 !! ^^

+ Recent posts