문제 인식

프로젝트 기능 중 "지도 화면에 나오는 상권 조회" 기능에서,
화면 이동 시 현재 화면의 좌표 범위(min, max)를 서버로 보내 상권 데이터를 조회해야 했다.

이 과정에서 카카오 지도 API의 bounds_changed 이벤트를 사용했는데, 해당 이벤트는 화면이 조금만 이동해도 콜백을 실행하므로, API 요청이 과도하게 발생하는 문제가 있었다.

처음에는 디바운싱을 적용해 최적화하려 했지만, 적합하지 않은 점들이 있었다.

디바운싱의 문제점

디바운싱을 사용해 보니, 다음과 같은 문제점들이 발견되었다.

1. 이미 호출했던 범위의 API 재호출
2. 빠른 화면 이동 시 상권 데이터를 놓칠 가능성
3. bounds_changed마다 setState를 실행해 불필요한 렌더링 발생

이미 호출했던 범위의 API 재호출

넓은 범위에서 이미 데이터를 조회했음에도
해당 부분을 확대하게 되면 다시 한 번 조회를 할 수 밖에 없었다.

데이터 요청 누락 및 불필요한 렌더링 존재

• 유저가 화면을 빠르게 넘긴다면 데이터가 있음에도, 상권 데이터를 확인하지 못할 가능성 존재
• bounds_changed가 실행될 때마다 setState를 해줘야 하기 때문에, 불필요한 렌더링 발생

문제 해결 과정

1. 사각형을 합쳐 Cache된 다각형 영역 생성하기

처음에는 위 문제를 해결하기 위해 각각의 조회 영역을 캐시해두고, 캐시된 영역을 넓혀가며 최적화 하는 방법을 생각해 보았다.

• Cache Hit가 발생하지 않으면 기존 Cache되어 있는 사각형과 합쳐 다각형 생성
• Cache Hit가 발생한다면 API 요청을 보내지 않음

하지만 위 방법으로 진행했을 경우, 아래와 같이 가운데가 비어있는 도넛형태에서는 어떤 방식으로 비교를 해야 할지 감이 잡히지 않았다. 😢

추가적으로 다른 이슈도 존재했다.

• 기존 조회된 영역에서 약간만 벗어나는 경우,
  다시 한 번 조회를 진행했어야 했기에 Cache의 효과도 그렇게 크지 않을 것이라 판단
• 기존 문제를 해결하지 못함
  • 2. 유저가 화면을 빠르게 넘긴다면 데이터가 있음에도, 상권 데이터를 확인하지 못할 가능성 존재
  • 3. bounds_changed가 실행될 때마다 setState를 해줘야 하기 때문에, 불필요한 렌더링 발생

2. Viewport 기준으로 캐시 영역 생성

두번째로 생각해본 방식은 Viewport 기준으로 캐시 영역을 생성하는 방식이다.

화면을 이동할 경우,
조금이라도 Cache되지 않은 영역이 존재할 경우 API 요청을 보내고,
해당 영역을 다시 Cache 해두는 방식이었다.

이 방법이라면 기존 문제를 전부 해결할 수 있을 것 같았는데 문제가 또 존재했다.

Viewport를 확대했을 경우에는
또 다른 크기의 사각형이 생성되어 첫번째 시도한 방법처럼 도넛형태의 공간이 생기게 된다..

또 다각형으로 생성하여 비교하는 방법보다 조금 더 효율적인 방법을 찾고싶었다.

3. 타일링(Tiling) 기법을 이용한 캐시

방법을 찾아보던 중, 정말 가까운 곳에서 힌트를 얻었다.
카카오 지도 API는 위치를 변경할 때마다, 해당 위치에 대한 지도 이미지를 불러오는데,
이를 타일링(Tiling) 기법이라고 한다.

타일링 기법은 일반적으로 큰 데이터셋이나 이미지를 작은 조각(타일)으로 나누어 효율적으로 처리하거나 저장하는 방법을 말합니다. 주로 그래픽 프로그래밍이나 게임 개발에서 사용되지만, 메모리 사용을 최적화하거나 데이터 처리를 개선하는 데도 활용될 수 있습니다.

타일링 기법의 주요 장점은 다음과 같습니다:

• 메모리 최적화: 큰 데이터를 작은 타일로 나누어 필요한 부분만 메모리에 로드하므로 메모리 사용량을 줄일 수 있습니다. 예를 들어, 큰 이미지에서 특정 부분만 필요할 때 전체 이미지를 로드하지 않고 해당 부분만 로드할 수 있습니다.

- 병렬 처리: 타일 단위로 작업을 나누어 여러 개의 CPU 코어에서 병렬로 처리할 수 있어 성능을 개선할 수 있습니다. 이는 GPU 렌더링에서도 유용하게 활용됩니다.

• 캐시 효율성: 타일을 사용하면 자주 사용하는 데이터가 더 작은 범위로 집중되기 때문에 캐시 효율이 높아질 수 있습니다. 이는 특히 메모리 접근 속도가 중요한 상황에서 유리합니다.

자료를 찾아보며 고민하던 중,
굳이 viewport에 맞춰 조회할 필요가 있을까?란 생각이 들었고,
이 생각에서 해결 방법을 찾았다.

해결 방법

뷰포트에 맞춰 데이터를 조회할 필요가 없었다.
뷰포트는 확대, 축소되며 동적으로 변하므로, 작은 데이터셋을 반복적으로 요청하는 것은 여러 면에서 비효율적이었다.
이를 개선하기 위해, 전체 지도를 여러 개의 타일로 나누고 캐시 관리를 통해 조회를 최적화하는 방식을 선택했다.

해결 방법은 다음과 같다.

• 위경도 범위 설정: 우리나라 전체를 커버하는 위경도 범위 설정
• 타일 분할: 설정된 범위를 일정한 단위(unit)로 나눠 정사각형 타일을 생성
• 캐싱 방식: 타일마다 조회 여부를 boolean[][] 배열에 기록하여 Cache Hit을 효율적으로 확인
• 타일 기준 API 요청: bound_change 이벤트가 발생할 때마다 현재 뷰포트의 네 꼭짓점을 검사하여, 캐시되지 않은 타일에 대해서만 API 요청을 진행하고 데이터를 캐시에 저장

코드

우리나라의 위경도는 아래와 같다.

• 위도 (Latitude): 약 33.1°N (제주도 남쪽 끝) ~ 38.6°N (강원도 북쪽 끝)
• 경도 (Longitude): 약 124.6°E (서해안) ~ 131.9°E (동해안)

대략적으로 1° = 111km 정도이다.

결론적으로 (current.lat - minLat) / (unit / 111) 식을 이용하면 위도에 대한 index를 얻을 수 있고,
unit = 10(km)로 가정했을 때(우리나라 기준)
62 × 82 크기의 이중 배열을 활용하여O(1)의 시간 복잡도로 Cache Hit을 확인할 수 있다.

// 1°당 거리 = 111km
// unit = 정사각형 타일 변의 길이
const distancePerDegree = 111;

const cachedTileList = useRef<boolean[][]>(
  (() => {
    const { minLat, minLng, maxLat, maxLng } = boundingCoords;

    const latTileLength = ((maxLat - minLat) / unit) * distancePerDegree;
    const lngTileLength = ((maxLng - minLng) / unit) * distancePerDegree;

    return Array.from({ length: latTileLength }, () =>
                      Array.from({ length: lngTileLength }, () => false)
                     );
  })()
)

// viewport 4개의 꼭지점
const boundingCoords = {
  minLat,
  minLng,
  maxLat,
  maxLng,
};

const findCoordsListByBoundingCoords = (
  boundingCoords: BoundingCoords
): Coords[] => {
  const { minLat, minLng, maxLng, maxLat } = boundingCoords;
  return [
    { lat: minLat, lng: minLng },
    { lat: minLat, lng: maxLng },
    { lat: maxLat, lng: minLng },
    { lat: maxLat, lng: maxLng },
  ];
};

//좌표에 해당하는 타일의 index를 반환함
const findTileByCoords = (currentCoords: Coords) => {
  const latTileIndex = Math.floor(
    (currentCoords.lat - boundingCoords.minLat) / (unit / distancePerDegree)
  );
  const lngTileIndex = Math.floor(
    (currentCoords.lng - boundingCoords.minLng) / (unit / distancePerDegree)
  );

  return { latTileIndex, lngTileIndex };
};

//타일 로드 여부를 반환함
const isLoaded = (currentCoords: Coords) => {
  const { latTileIndex, lngTileIndex } = findTileByCoords(currentCoords);

  return cachedTileList.current[latTileIndex][lngTileIndex];
};


const getBoundingCoordsByCoords = (coords: Coords): BoundingCoords => {
  const { latTileIndex, lngTileIndex } = findTileByCoords(coords);
  return {
    minLat: boundingCoords.minLat + latTileIndex * (unit / distancePerDegree),
    maxLat:
    boundingCoords.minLat + (latTileIndex + 1) * (unit / distancePerDegree),
    minLng: boundingCoords.minLng + lngTileIndex * (unit / distancePerDegree),
    maxLng:
    boundingCoords.minLng + (lngTileIndex + 1) * (unit / distancePerDegree),
  };
};

// bound_change 내부에서 실행

// viewport 4개의 꼭짓점에 해당하는 타일을 반환함
const requestBoundingCoordsList = findCoordsListByBoundingCoords(
  boundingCoords
).map((coords) => getBoundingCoordsByCoords(coords));

requestBoundingCoordsList.forEach((coords) => {
  // 해당 
  if (isLoaded({ lat: coords.minLat, lng: coords.minLng })) return;
  // API가 반환되기 이 전 다시 요청보내는 것을 막기 위해 함수 호출
  onLoadComplete();

  // API 요청
  api.simulation.getTradeBounding(coords)
    .then((trades) => {
      trades?.forEach((trade) => {
        addPolygon(
          map.current,
          parseMultipolygon(trade.coordinates)
        );
      });
  })
    .catch(() => {
    //실패했을 경우, 되돌리기
    onLoadFail();
  });
});

결과물

최종적으로, 타일링 기법을 통해 효율적인 캐싱이 가능해졌으며, 성능 및 비용 문제를 모두 해결했다. 😊

1. 이미 호출했던 범위의 API 재호출
   -> Cache Hit을 확인해 새로운 영역에 대해서만 API 호출
2. 유저가 화면을 빠르게 넘긴다면 데이터가 있음에도, 상권 데이터를 확인하지 못할 가능성 존재
   -> 영역이 변경됨과 동시에 api 호출을 하여 해결
3. bounds_changed가 실행될 때마다 setState를 해줘야 하기 때문에, 불필요한 렌더링 발생
   -> setState가 아닌 api가 응답함과 동시에 polygon 추가

백엔드는 여기!

https://velog.io/@tjdwjs23/%EC%A7%80%EC%97%AD-%EA%B2%80%EC%83%89%EC%9D%84-%EC%9C%84%ED%95%9C-%ED%8F%B4%EB%A6%AC%EA%B3%A4-%EA%B8%B0%EB%B0%98-%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4-%EC%84%A4%EA%B3%84-%EB%B0%8F-%EA%B5%AC%ED%98%84