[open-webui] Open WebUI 스트리밍 성능 190배 개선: O(N^2)에서 O(N)으로의 최적화

PR 링크: open-webui/open-webui#28861 상태: Merged | 변경: +25 / -5

들어가며

LLM 기반의 애플리케이션에서 스트리밍 응답은 사용자 경험의 핵심입니다. 하지만 스트리밍 데이터를 처리하는 과정에서 사소한 알고리즘 실수가 전체 시스템 성능을 저하시키는 경우가 많습니다. 최근 open-webui 레포지토리에 올라온 PR은 스트리밍 응답 내의 특정 태그(reasoning, code interpreter 등)를 탐색하는 로직에서 발생하던 심각한 성능 병목을 해결했습니다. 기존 로직은 매 청크(chunk)가 들어올 때마다 전체 응답 텍스트를 처음부터 다시 스캔하는 방식을 취하고 있었는데, 이는 데이터가 커질수록 연산량이 제곱으로 증가하는 O(N^2) 복잡도를 가졌습니다. 이번 글에서는 이 문제를 어떻게 해결했는지 코드 레벨에서 분석합니다.

코드 분석

기존 방식의 문제점

기존 코드에서는 매번 item_text.rfind()를 사용하여 전체 텍스트의 시작점(0)부터 현재까지의 길이를 매번 다시 스캔했습니다.

# Before
last_tag_boundary = max(
    item_text.rfind('>', 0, scanned_length),
    item_text.rfind('\n', 0, scanned_length),
)
open_tag_start = item_text.rfind('<', 0, scanned_length)

이 방식은 텍스트에 <와 같은 기호가 없을 경우, rfind 함수가 문자열 전체를 훑어야 하므로 응답이 길어질수록 성능이 급격히 저하되었습니다.

개선된 방식: 상태 유지(Stateful Scanning)

이번 PR의 핵심은 마지막으로 스캔한 위치를 기억하고, 새로 추가된 청크만큼만 스캔 범위를 좁히는 것입니다.

# After
def get_tag_boundaries(item, text, scanned_length):
    key = (item.get('id'), content_type)
    scanned, last_open, last_boundary = tag_boundary_positions.get(key, (0, -1, -1))
    
    if scanned < scanned_length:
        # 새로 추가된 부분만 스캔
        open_tag = text.rfind('<', scanned, scanned_length)
        # ... (중략) ...
        tag_boundary_positions[key] = (scanned_length, last_open, last_boundary)
    return last_open, last_boundary

tag_boundary_positions라는 딕셔너리를 도입하여, 이전에 스캔했던 위치(scanned)를 저장합니다. 이후 호출 시에는 scanned부터 scanned_length까지만 rfind를 수행하여 불필요한 중복 연산을 완전히 제거했습니다.

왜 이게 좋은가

성능 수치

제공된 벤치마크 결과에 따르면, 270KB의 응답을 27,000개의 청크로 처리할 때 다음과 같은 극적인 성능 향상이 있었습니다.

• Before: 약 5,695ms ~ 7,690ms
• After: 약 40.6ms ~ 41.7ms

약 190배의 성능 향상을 보여줍니다. 이는 스트리밍 데이터 처리 시 '전체 데이터 재스캔'이 얼마나 위험한 패턴인지 잘 보여줍니다.

교훈

1. 스트리밍 데이터 처리 시 상태 유지(Stateful Processing): 스트리밍은 데이터가 점진적으로 들어옵니다. 이전 상태를 캐싱하여 새로 들어온 데이터(delta)에 대해서만 연산을 수행하는 것이 성능 최적화의 기본입니다.
2. 알고리즘 복잡도 인지: rfind와 같은 문자열 검색 함수는 O(N) 연산입니다. 이를 루프 안에서 매번 처음부터 호출하면 O(N^2)이 됩니다. 데이터의 크기가 커질 것을 대비해 항상 연산 범위를 제한해야 합니다.
3. 리뷰의 중요성: 이번 PR은 단순히 기능을 구현하는 것을 넘어, 시스템의 확장성을 고려한 좋은 예시입니다. 리뷰어 Classic298이 지적했듯, 일반적인 텍스트(prose)에서는 태그가 거의 없기 때문에 기존 로직은 매번 최악의 경우(전체 스캔)를 수행하고 있었습니다.

이번 최적화는 복잡한 라이브러리 도입 없이도, 알고리즘의 효율적인 설계만으로 시스템의 처리량을 획기적으로 늘릴 수 있음을 증명합니다.

참고 자료

• https://docs.python.org/3/library/stdtypes.html#str.rfind

⚠️ 알림: 이 분석은 AI가 실제 코드 diff를 기반으로 작성했습니다.