엘리베이터 버튼 하나에도 알고리즘 전쟁이 숨어 있음

• 엘리베이터는 그냥 가까운 칸이 오는 게 아니라, 꽤 진지한 스케줄링 문제임

  • 가장 단순한 방식은 1961년에 특허가 나온 스캔 알고리즘임
  • 로비에서 출발해 꼭대기층까지 올라갔다가 다시 내려오면서 중간 요청을 처리하는 방식임
  • 실제로는 꼭대기층까지 갈 필요가 없으니, 요청된 가장 높은 층까지만 갔다가 돌아오는 룩 알고리즘이 더 직관적임

• 엘리베이터가 여러 대가 되면 문제는 바로 복잡해짐

  • 기본형은 중앙 스케줄러가 새 요청을 가장 가까운 엘리베이터에 배정하는 방식임
  • 그런데 가까운 엘리베이터가 이미 꽉 찼거나, 같은 방향으로 다른 칸이 가고 있다면 단순 거리만으로는 별로임
  • 그래서 배차 알고리즘은 위치뿐 아니라 방향, 혼잡도, 주변 유휴 차량까지 같이 봐야 함

• 엘리베이터 품질은 평균 대기시간보다 대기시간 분포가 더 중요함

  • 예를 들어 90번째 백분위가 2분이면, 승객 90%는 2분 이하로 기다렸다는 뜻임
  • 50번째 백분위가 1분이면 절반은 1분 안에 엘리베이터를 탔다는 뜻임
  • 사람들은 평균 47초 기다린 걸 기억하지 않고, 3분 동안 멍하니 서 있던 순간을 기억함. 아, 이거 진짜임

• 출근 시간대에는 트래픽 패턴이 완전히 달라짐

  • 사무실 건물 아침에는 거의 모든 요청이 로비에서 위층으로 향함
  • 저녁에는 반대로 위층에서 로비로 내려오는 흐름이 지배적임
  • 점심시간은 양방향과 층간 이동이 섞여서 또 다른 분포가 나옴
  • 그래서 같은 알고리즘도 시간대별로 대기시간 통계가 확 달라짐

• 오티스의 상대 시스템 응답 방식은 각 엘리베이터에 점수를 매김

  • 점수가 낮을수록 특정 호출을 처리하기 좋은 엘리베이터라는 뜻임
  • 이미 다른 엘리베이터가 같은 층과 같은 방향으로 가고 있으면 벌점을 줌
  • 호출 층 근처 두 층 안에 놀고 있는 엘리베이터가 있으면 보상을 줌
  • 핵심은 5초마다 재최적화해서, 엘리베이터 A가 맡던 승객을 상황에 따라 B로 다시 배정할 수 있다는 점임

• 똑똑한 알고리즘이 항상 이기는 건 아님

  • 흐름이 너무 많아 엘리베이터가 항상 꽉 차고 거의 모든 층에 서는 상황에서는 룩이 상대 시스템 응답보다 나을 수 있음
  • 작은 건물이나 엘리베이터 대수가 적은 뱅크에서도 단순한 방식이 더 좋은 경우가 있음
  • 최적화 규칙이 많다고 무조건 승리하는 건 아니라는 게 재밌는 포인트임

• 목적지 배차 키오스크는 직관과 달리 대기시간을 악화시킬 수 있음

  • 층마다 키오스크가 있고, 승객이 목적층을 먼저 입력하면 시스템은 누가 어디로 가는지 미리 알 수 있음
  • 얼핏 보면 최적화에 필요한 정보가 늘어나니 당연히 좋아 보여야 함
  • 하지만 키오스크는 ‘당신은 이 엘리베이터를 타라’고 고정 배정해버림
  • 30초 뒤 상황이 바뀌어도 승객을 다른 엘리베이터로 유연하게 옮기기 어려움
  • 아주 높은 건물이나 엘리베이터가 8대 이상인 특수한 경우를 빼면, 전통적인 위아래 버튼이 더 나은 경우가 많다고 함

---

기술 맥락

• 이 글의 핵심 선택은 ‘더 많은 정보를 받을 것인가, 더 자주 재최적화할 것인가’예요. 목적지 배차는 승객의 목적층을 미리 알아서 좋아 보이지만, 그 대신 배정을 고정해버려요.

• 상대 시스템 응답 방식이 강한 이유는 5초마다 상태를 다시 본다는 점이에요. 엘리베이터 위치, 방향, 혼잡도, 근처 유휴 차량 같은 조건은 계속 바뀌니까, 처음 내린 결정이 금방 낡아버리거든요.

• 대기시간 평가에서 평균보다 90번째 백분위를 보는 것도 실무적으로 익숙한 얘기예요. 웹 서비스에서 평균 응답시간이 괜찮아도 일부 요청이 5초씩 걸리면 사용자는 그걸 장애처럼 느끼는 것과 비슷해요.

• 그래서 엘리베이터 알고리즘은 건물 규모와 시간대에 따라 답이 달라져요. 작은 건물에서는 단순한 룩이 낫고, 복잡한 트래픽에서는 재최적화가 이길 수 있는 식이에요.