엘리베이터는 왜 아직도 어려운 문제인가 — 부하가 높아지면 단순한 LOOK이 정교한 RSR을 이긴다

정교한 최적화는 늘 이기는가, 아니면 부하가 높아질수록 단순함이 이기는가 — 매일 타는 엘리베이터가 그 경계선을 눈앞에서 보여준다.

도입 — 매일 타는 시스템이 실은 풀리지 않은 스케줄링 문제다

john.fun/elevators라는 인터랙티브 에세이가 그날 해커뉴스에서 AI를 제외한 이야기 중 1위에 올랐다(855포인트). 주제는 뜻밖에도 엘리베이터였다. 화면 안에서 직접 조작 가능한 시뮬레이션으로, 여러 대의 승강기가 층을 오르내리며 호출을 처리하는 모습을 보여주고, 어떤 배차 알고리즘이 사람을 더 빨리 나르는지를 실측한다. 그리고 그 결과는 대부분의 독자가 예상하지 못한 방향으로 흐른다.

우리는 엘리베이터를 해결된 문제로 여긴다. 100년 넘게 존재했고, 버튼을 누르면 오고, 대개는 그럭저럭 빠르다. 그러나 조금만 파고들면 이것은 전형적인 미해결 최적화 문제다. 호출은 미래를 모른 채 하나씩 도착하고, 각 승강기는 지금 이 순간 어디로 갈지를 되돌릴 수 없이 결정해야 하며, 잘못 배차하면 되돌릴 방법이 없다. 이것은 정확히 “불확실성 속 온라인 스케줄링(online scheduling under uncertainty)“의 교과서적 사례다 — 디스크 헤드 스케줄링, 작업 큐 배분, 배차 앱의 차량 할당과 한 가족인 문제다.

에세이의 핵심 발견은 이렇게 요약된다. 오티스가 실제로 쓰는 정교한 독점 알고리즘 RSR이, 부하가 높아질수록 교과서에나 나올 법한 단순한 LOOK에게 진다. 정교함이 늘 이기는 것이 아니라, 부하라는 조건 앞에서 뒤집힌다는 것이다. 이 글은 그 뒤집힘이 왜 일어나는지, 그리고 그 교훈이 엘리베이터 밖 어디까지 옮겨 붙는지를 따라간다.

현상 — 두 알고리즘, 그리고 뒤집힌 승부

먼저 무대에 오르는 알고리즘들을 정리하자. 이들은 모두 “여러 층에서 도착하는 호출을, 제한된 대수의 승강기로, 되돌릴 수 없이 처리한다”는 같은 문제를 서로 다른 철학으로 푼다.

SCAN과 LOOK. 이 둘은 운영체제 수업에서 디스크 암(disk arm) 스케줄링으로 배우는 바로 그 알고리즘이다. 실제로 SCAN은 별명이 “엘리베이터 알고리즘”일 만큼 승강기와 뿌리가 같다. SCAN은 한 방향으로 끝층까지 쭉 훑으며 도중의 호출을 모두 처리하고, 끝에 닿으면 방향을 뒤집는다. LOOK은 그 개선판으로, 진행 방향에 더 이상 호출이 없으면 굳이 끝층까지 가지 않고 그 자리에서 방향을 되돌린다. 에세이의 표현을 빌리면 LOOK은 “대부분의 사람이 알고 기대하는 그 알고리즘”이다 — 위로 갈 사람은 위로 모아 태우고, 방향이 없을 때 뒤집는, 직관 그대로의 규칙.

RSR(Relative System Response). 오티스의 독점 알고리즘이다. LOOK이 규칙 하나로 움직인다면 RSR은 점수로 움직인다. 호출이 들어오면 각 승강기에 대해 점수를 매기고, 가장 좋은 점수의 차를 보낸다. 점수는 대략 “도착 예상 시간(ETA) + 탑승 하중 페널티 + 같은 방향 밀집(anti-bunching) 페널티” 같은 항들로 구성되고, 근처에서 놀고 있는 차나 방향이 맞는 차, 짐이 적은 차에는 보너스가 붙는다. 결정적으로, RSR은 5초마다 전체를 재계산한다 — 상황이 바뀌면 배차를 다시 최적화해 승강기 사이에서 승객을 재할당할 수 있다. 겉보기에 RSR은 LOOK보다 명백히 똑똑하다. 더 많은 정보를, 더 자주 반영한다.

목적지 선택 방식(Destination Dispatch). 세 번째 후보는 아예 인터페이스를 바꾼다. 로비의 키오스크에서 승객이 타기 전에 목적지 층을 먼저 입력하면, 시스템이 같은 목적지끼리 묶어 특정 승강기를 배정한다. 정보가 가장 많다 — 각 승객이 어디로 갈지를 출발 전부터 안다. 그러니 이론적으로는 가장 똑똑해야 한다.

에세이의 실험 무대는 이 셋을 같은 조건에서 돌리는 시뮬레이션이다. 측정 지표가 특히 정교하다. 단순 평균 대기시간이 아니라 대기시간의 분포를 본다 — 중앙값 p50과, 상위 10%의 꼬리 지연을 나타내는 p90. 여기에 “30초 안에 승강기가 오는 비율은?”, “90초 안에는?” 같은 고정 창(window) 지표를 더한다. 이 설계에는 관찰이 하나 깔려 있다. 사람은 평균을 기억하지 않는다. 승강기가 하염없이 오지 않던 그 최악의 순간, 즉 p90의 경험을 기억한다. 그래서 좋은 배차란 평균을 조금 줄이는 것이 아니라 꼬리를 잘라내는 것이다.

그리고 승부가 뒤집힌다. 트래픽이 한산할 때는 RSR의 정교함이 값을 한다 — 놀고 있는 차를 미리 배치하고, 방향을 맞춰 보내고, 밀집을 피하는 그 모든 규칙이 대기시간을 다듬는다. 그런데 유입률이 올라갈수록, 즉 승강기가 늘 만원이고 거의 모든 층에 서게 되는 고부하 영역으로 갈수록, LOOK이 RSR을 따라잡고 마침내 앞선다. 에세이의 문장을 옮기면, “유량이 높아질수록 LOOK이 실제로 RSR을 앞지르기 시작한다.” 목적지 선택 방식은 더 놀랍다. 가장 많은 정보를 가지고도, 여러 조건에서 오히려 더 나쁜 성적을 낸다. 정보량과 성능이 비례하지 않는다는 것 — 이것이 이 에세이가 던지는 첫 번째 균열이다.

심층 — 불확실성 속 온라인 스케줄링, 그리고 조기 확정의 함정

왜 이런 뒤집힘이 일어나는가. 답은 이 문제가 “온라인(online)“이라는 데 있다. 오프라인 최적화는 모든 호출을 미리 알고 최적해를 계산한다. 그러나 실제 엘리베이터는 다음 1초에 누가 어느 층에서 버튼을 누를지 모른 채 지금 결정을 내려야 한다. 이 조건에서 알고리즘의 가치는 “지금 최적으로 보이는 배차”가 아니라 “미래가 어떻게 흘러도 크게 손해 보지 않는 배차”로 판정된다. 알고리즘 이론이 경쟁분석(competitive analysis)으로 재는 바로 그 성질이다 — 미래를 다 아는 신탁 대비 얼마나 덜 나쁜가.

이 렌즈로 보면 정교함이 부하 앞에서 무너지는 이유가 드러난다. RSR의 강점은 상황에 맞춰 미리 자원을 배치하는 데 있다. 그런데 고부하에서는 배치할 여유 자원이 없다. 모든 승강기가 만원이고 거의 모든 층에 선다. 이 영역에서 최적해는 사실상 “가던 방향으로 계속 훑으며 실을 수 있는 만큼 싣는 것”으로 수렴하는데, 그것이 정확히 LOOK이 하는 일이다. RSR이 5초마다 정교하게 계산하는 점수는, 선택지가 사라진 상황에서는 계산 비용만 남고 이득은 사라진다. 정교한 최적화는 여유가 있을 때 여유를 잘 쓰는 기술이지, 여유가 없을 때 없는 여유를 만들어내는 마법이 아니다.

조기 확정(early lock-in)의 함정. 목적지 선택 방식의 역설은 더 깊은 교훈을 담는다. 이 방식은 승객을 호출 시점에 특정 승강기에 확정 배정한다 — “당신은 3호기에 타세요.” 문제는 그 확정이 미래를 닫아버린다는 데 있다. 30초 뒤 세상이 바뀌어 다른 승강기가 훨씬 유리해져도, 이미 배정된 승객은 재배치할 수 없다. 반면 전통적인 위/아래 버튼 방식은 승객을 “위로 갈 사람”이라는 느슨한 상태로만 묶어두기에, 시스템이 마지막 순간까지 어느 차에 태울지를 미룰 수 있다. 결정을 늦게 확정할수록 더 많은 정보를 반영할 수 있다. 목적지 선택 방식은 정보를 일찍 얻는 대신 유연성을 일찍 버렸고, 고부하에서는 그 유연성이 정보보다 값지다.

여기서 해커뉴스 스레드의 논의를 하나 인용한다. 다만 직접 인용이 아니라 코멘트의 정서 요약이다. 스레드에서 가장 많이 곱씹힌 지적은, 목적지 선택 방식이 “당신이 호출한 30초 뒤의 세상”에 적응하지 못한다는 것이었다. 조기 확정이 재최적화의 문을 닫는다는 통찰을, 실제 건물을 타 본 사람들의 경험담이 뒷받침했다.

평균 대 꼬리의 트레이드오프. 또 하나의 축은 무엇을 최적화하느냐다. 평균 대기시간(p50)을 줄이는 배차와 최악 대기시간(p90/p99)을 줄이는 배차는 종종 다른 방향을 가리킨다. 어떤 규칙은 다수의 대기를 조금씩 줄이는 대신 소수를 아주 오래 기다리게 만든다. 사람의 불만은 평균이 아니라 꼬리에서 터지므로, 체감 품질을 지배하는 것은 p90이다. 좋은 스케줄러는 평균을 자랑하지 않고 꼬리를 관리한다 — 이것은 엘리베이터만의 이야기가 아니라 지연시간을 다루는 모든 시스템의 공통 계율이다.

트래픽 레짐 의존성. 결정적으로, 정답은 건물이 아니라 시간대와 용도에 따라 바뀐다. 엘리베이터 교통공학은 하루를 세 국면으로 나눈다 — 아침의 상승 피크(up-peak, 로비에서 위층으로), 저녁의 하강 피크(down-peak, 위층에서 로비로), 그리고 층간 이동이 뒤섞인 오프피크(interfloor). 오티스 계열 문헌이 말하는 상승 피크란 로비에서 들어온 승객이 특정 층들로만 향하고 층간 호출은 거의 없는 시간대를 뜻하며, 하강 피크에서는 놀고 있는 차를 미리 위층에 올려 대기시킨다. 최적 전략이 국면마다 다르다는 것은, 하나의 고정된 정교한 규칙이 항상 이기기 어렵다는 뜻이다.

건물 용도도 판을 뒤집는다. 사무실은 아침 상승 피크와 점심의 양방향 러시가 지배하고, 트래픽의 대부분이 로비와 개별 층 사이를 오간다. 호텔은 식사 시간대에 양방향으로 흐른다. 주거 건물은 또 다른 리듬을 탄다. 여기서 해커뉴스 스레드의 또 다른 지적이 아프다 — 역시 직접 인용이 아니라 코멘트의 정서 요약이다. 무작위 목적지로 돌리는 시뮬레이션은 현실을 닮지 않았다는 것이다. 사무실 트래픽은 로비와 개별 층 사이가 대부분이고, 점심시간에는 같은 층 사람들이 함께 내려갔다 함께 올라오는 배칭(batching)이 일어나 오히려 처리를 돕는다. 무작위 균등 분포는 알고리즘을 공정하게 비교하기엔 좋지만, 어느 알고리즘이 실제 건물에서 이길지는 말해주지 못한다.

마지막으로, 실무의 제약이 이론을 압도한다는 지적도 무겁다. 건물주는 승강기를 “딱 필요한 만큼만” 설치한다 — 한 대의 자본비용이 다른 모든 비용을 압도하기 때문이다. 그 결과 진짜 제약은 승객의 쾌적함이 아니라 처리량(throughput)이다. 실제 승강기는 무게 센서로 탑승 하중을 읽어 만원 여부를 판단하고, 잦은 급출발·급정지는 마모와 에너지를 늘리므로 처리량과 마모 사이에도 트레이드오프가 있다. 이 모든 제약을 얹으면, 그리고 더블데크 승강기나 특정 층만 서는 급행 샤프트까지 더하면, “최적 알고리즘”이 무엇인지는 급격히 불투명해진다. 정교한 규칙 하나가 모든 조건을 지배한다는 그림은 현실에서 성립하지 않는다.

전망 — 엘리베이터에서 로드밸런서로, 옮겨 붙는 교훈

엘리베이터 이야기가 흥미로운 진짜 이유는, 그 교훈이 승강기 밖으로 곧장 걸어 나오기 때문이다. “여러 요청이 미래를 모른 채 하나씩 도착하고, 제한된 서버가 되돌릴 수 없이 처리하며, 조기 확정이 재최적화를 막는다”는 구조는 소프트웨어 도처에 있다.

로드 밸런서와 작업 스케줄러. 요청을 서버에 배분하는 로드 밸런서는 엘리베이터에 승객을 배차하는 문제와 동형이다. 가장 정교해 보이는 정책 — 매 요청마다 모든 서버의 부하를 재서 최적 서버를 고르는 것 — 은 저부하에서는 빛나지만 고부하에서는 재는 비용만 남기 쉽다. 실제로 분산 시스템에서 널리 쓰이는 “두 개 무작위 선택(power of two choices)“이 순진한 최소부하 선택보다 안정적인 것도 같은 결이다. 조기 확정 함정도 그대로 옮겨온다. 요청을 큐 앞에서 특정 워커에 못박아 두는(스티키) 설계는, 그 워커가 느려져도 재배치할 수 없다. 늦게 확정하는 워크 스틸링(work stealing) 스케줄러가 유연한 이유가 여기 있다.

배차 앱과 물류. 라이드헤일링의 차량-승객 매칭은 목적지 선택 방식의 딜레마를 실시간으로 겪는다. 승객을 특정 차량에 너무 일찍 확정하면, 3분 뒤 훨씬 가까운 차가 비어도 재매칭하지 못한다. 배달·물류의 실시간 배차도 같은 축 위에 있다 — 일찍 확정해 예측 가능성을 얻을 것인가, 늦게 확정해 유연성을 남길 것인가.

그렇다면 엔지니어가 가져갈 실천적 교훈은 무엇인가. 첫째, 부하 구간을 나눠서 판단하라. 저부하에서 이기는 알고리즘과 고부하에서 이기는 알고리즘은 다를 수 있다. 단일 부하에서 벤치마크한 뒤 “이게 최고”라고 결론짓는 것은 위험하다. 둘째, 복잡한 최적화기를 의심하라. 정교함이 값을 하는 것은 대개 여유가 있을 때다. 최적화기의 계산·유지보수 비용이 이득을 넘어서는 부하 구간이 반드시 있고, 그 구간에서는 단순한 규칙이 낫다. 셋째, 결정을 최대한 늦게 확정하라. 조기 확정은 정보를 얻는 대신 유연성을 판다. 재최적화가 값진 환경일수록 확정을 미루는 설계가 강하다. 넷째, 평균이 아니라 꼬리를 최적화하라. 체감 품질은 p90/p99가 지배한다.

전망을 세 갈래로 정리한다. 낙관적으로 보면, 이런 인터랙티브 시뮬레이션은 “정교함=우월”이라는 맹신을 걷어내고, 부하 조건을 명시적으로 따지는 설계 문화를 확산시킨다. 비관적으로 보면, 벤더의 독점 알고리즘은 여전히 블랙박스이고 실측 벤치마크는 공개되지 않으므로, 어느 방식이 실제로 나은지는 건물별 트래픽 데이터 없이는 알 수 없다 — 무작위 시뮬레이션의 승부를 현실로 오독할 위험이 남는다. 현실적 중간값은, 정교한 최적화와 단순한 규칙을 부하에 따라 전환하는 하이브리드다. 저부하에서는 RSR류의 정교함을 쓰고, 고부하가 감지되면 LOOK류의 단순 훑기로 전환하는 것 — 실제 엘리베이터 컨트롤러가 상승 피크·하강 피크·오프피크 모드를 전환하는 것도 정확히 이 발상의 구현이다.

결론 — 정교함은 여유의 기술이지, 부하의 해법이 아니다

리드 질문에 답하자면, 정교한 최적화는 늘 이기지 않는다. 여유가 있을 때 이기고, 부하가 여유를 지우면 진다. LOOK이 RSR을 앞지르는 그 지점은 알고리즘의 결함이 아니라 문제의 성질이다 — 고부하에서는 좋은 배차가 하나로 수렴하고, 그 수렴점에 단순한 규칙이 계산 비용 없이 이미 서 있기 때문이다.

엘리베이터가 100년 된 문제인데도 여전히 열려 있는 이유가 여기 있다. 정답이 하나가 아니라 조건의 함수이기 때문이다. 부하, 트래픽 레짐, 건물 용도, 확정 시점, 무엇을 최적화하는가 — 이 축들이 만드는 공간 위에서 승자가 자리를 바꾼다. 매일 무심코 타는 그 상자가, 사실은 우리가 짓는 모든 온라인 시스템의 축소판이다. 다음에 복잡한 최적화기를 도입하려 할 때, 한 가지만 먼저 묻자 — 이 정교함은 여유가 있을 때의 기술인가, 아니면 정말 부하 앞에서도 버티는가.

출처: