[Trouble Shooting] 추천 경로 계산 시간이 너무 느린 문제

1. 문제상황

이 글에서의 방식으로 DB에 데이터를 쌓았고 해당 데이터를 바탕으로 길찾기 기능을 제공해야 한다.

데이터베이스에 시작점, 끝점, 거리를 모두 잘 정리되어 있는 상태이다.

길찾기 기능은 최단경로/추천경로 두 가지를 제공하고 

예상은 했지만 생각보다 경로 계산이 더 느린 이슈가 발생했다.

(10초 정도 소요)

---

2. 고민해본 내용

경로 추천 기능의 코드를 대략적으로 설명하면 아래와 같다.

* 경로 추천 방법
* 1. 입력된 시작점, 끝 점으로 부터 가장 가까운 DB에서 관리하는 시작점과 끝 점을 DB에서 검색
* 2. DB에서 도로에 사용하는 모든 정점의 개수 가져오기 select count(*) from pointHash
* 3. RoadInfo DB에서 정점(도로의 시작점 & 끝점)과 길이(최단경로) 가져오고, 가중치(추천경로)도 계산
* 4. 해당 점을 가지고 다익스트라 알고리즘 진행 => 결과값은 시작 점으로부터 모든 점 까지의 최단거리
* 5. 다익스트라로 나온 최단 거리를 바탕으로 역방향 BFS를 진행해서 최단 경로를 계산
* 5-1. 3번의 결과값으로 나온 도로의 결과는 tamp이 관리하는 도로 번호
* 6. 5번의 결과값을 MongoDB에서 tmapid를 이용해 검색해 실제 경로(List<Point>)를 가져옴
* 7. 가져온 도로들의 List를 Point<List>로 변환하고, 앞 뒤에 시작점 끝점을 붙여줌
* 8. 7번의 결과값을 최단/추천 경로 DB(recommendproject)에 insert
* 8-1. DB에 저장된 경로은 프로젝트 생성시 해당 프로젝트 id를 넣어는 작업 필요
* 9. 8번의 결과값을 return

참고로 추천 경로에서 사용하는 도로의 가중치 계산 식은 아래와 같다

n : 도로의 신고 횟수(플로깅되었다면 0으로 초기화)

d : 도로의 총 길이

m : 도로의 누적 신고 횟수 (0이라면 +1)

b : 최근에 플로깅 된 도로인지(redis에서 확인, 존재한다면 +25, 아니라면 0)

 

말도 안되는 식을 만든건 아니고, DB 내에 있는 도로의 길이는 대략 3 ~ 293 사이의 값이므로

길이를 어느정도 고려하지만 적당히 비슷한 값으로 만들어줘야 할 필요성을 느껴 ln(d)를,

m은 도로의 누적 신고 횟수로 신고가 많이되었다면 우선순위에 더 뽑히도록 하기 위해 넣었다.

n 역시도 m과 비슷한 이유로 넣게 되었고 마지막으로 b는 최근에 플로깅되었다면 추천 경로에 최대한 포함하지 않기 위해 위와같은 식을 작성하게 되었다.

---

로그를 찍어보며 확인해본 결과 도로 데이터를 넣는데 시간이 오래 걸림을 확인했고

그 이유는 3번 작업에서 도로 관련 데이터를 넣는 과정에

가중치 계산에서 필요한 최근에 플로깅 된 도로를 redis에서 가져오는 연산이 도로의 수 마다 이루어졌음을 깨달았다.

(도로가 약 500개라고 가정한다면, redis에 500번 쿼리를 보내는 것이나 마찬가지이므로)

---

3. 해결 방안

그럼 그냥 redis에 도로 관련 컬럼들을 한번만 연산하게 된다면(select all) 속도 개선이 이루어지리라 확신했고

최근에 플로깅된 도로들을 redis에 저장할 때 prefix를 붙여서 해당 컬럼들만 한번에 가져오도록 했다.

이후 이 도로들을 HashSet에 저장해서 디비에 가지 않고 HashSet에서 검색 연산을 하도록 코드를 수정했다.

 

redis에서 road_ 라는 이름이 붙은 모든 컬럼을 가져오는 코드

Set<String> cleanRoadSet = new HashSet<>(Objects.requireNonNull(redisTemplate.keys(("road_*"))));

 

이후 가중치를 넣을 때 Set을 이용해 비교하는 코드

if (cleanRoadSet.contains("road_"+roadInfos))weight += 25; // b

---

위와같이 코드를 최적화하였더니 12초가량 걸리던 요청 시간이 3초 이내로 나오는 것을 확인했고,

예상됬던 문제를 개선했더니 실제로 성능 향상이 이루어져서 상당히 기뻤다.

---

4. 느낀점

DB에 쿼리를 요청하는 코드가 반복문에 들어가는 경우 한번 더 고민해야 할 필요성을 느꼈다.