요구사항

  • 대량의 채팅 로그 스트림을 받아 글자수가 아닌 토큰 수 기준으로 간이 인코더 구현
  • 메모리 오버 헤드 없이 실시간 큐를 관리하는 O(N) 의 시간복잡도의 최적화 슬라이딩 윈도우 알고리즘 구현

문제 정의

  • AI 채팅 기록이 계속 쌓이는데, LLM에는 모든 대화를 다 보낼 수 없으니까,토큰 수 제한 안에서 최근 대화만 남기는 큐를 만드는 것
  • 우리 앱 -> LLM 을 사용할때 LLM API는 이전 대화를 자동으로 기억하지 않는다고 한다, 그렇기 때문에 우리 앱에서 최근 대화
    내용까지 포함해서 요청을 보내야 한다.
  • Chat GPT나 Claude 같은건 생각해 보면 채팅방을 구성하고 대화내용을 기반으로 답변을 주는것 그 대화 내용을 어디에 저장하고 운영할지 

LLM은 콘텍스트 윈도우 한계가 있기 때문에 대화방 하나를 기준으로 토큰 계산기를 사용해 각각의 대화 토큰 개수를 도출 하고, 정의한 제한 토큰 개수로 이전 대화를 포함 해 LLM애 요청하기 위함.

 

LLM 모델에서 사용하는 토큰이랑 햇갈렸는데 이건 LLM 내부에서 처리 하는거고, 지금 하는건 더 큰 맥락에서의 분류라고 생각 하자.

 

1차 고민사항

  • 토큰 기준을 어떤 단위로 구분할까
    • 공백 단위로 구분 ?
    • 글자 수 단위로 구분 ?
    • 영어, 한글 기준으로 고민해 보자
  • 채팅 메시지를 어디에 저장할까
    • 최근 대화 기반으로 메모리에만 올리고 별도의 저장은 일단 제외
    • 추후 DB 사용으로 대화 관리
  • 어떤 자료구조로 실시간 큐를 관리 할까
    • 사용자가 입력한 메시지를 앞 뒤에서 추가 삭제하기 때문에 Deque 사용하는걸로
    • Deque 사용하면 앞 뒤 추가 제거에 대한 불필요한 오버헤드 없다고 생각
  • 토큰 수 계산 방법
    • 매번 순회 하면서 토큰 수를 계산하면 대화가 길어질 수록 순회 시간이 증가 하고, 불필요한 계산 발생
  • 많은 사용자 기준으로 영어와 한글이 같이 들어오는 상황이 빈번한데 이걸 어떤 방식으로 토큰화 할까 ?

 

ChatMessage 객체 1차 구현사항

LLM 요청에 포함될 하나의 대화 메시지를 표현하는 객체

  • 역할
    • 사용자 요청, AI 모델 응답, 시스템 메시지를 구분하기 위한 Role 정보 저장
    • 실제 대화 내용인 content 저장
    • 해당 메시지의 토큰 개수인 tokenCount 저장
    • 생성 시 role, content, tokenCount에 대한 기본 검증 수행

값 변경이 필요없는 객체이기 때문에 record 사용

토큰 분리기능 1차 구현사항

토큰 계산기는 문자열을 입력받아 간이 규칙에 따라 토큰 수를 계산하는 역할.

  • Tokenizer 인터페이스를 작성하여 토큰 계산 기능을 추상화
  • SimpleTokenizer 구현체를 통해 간이 토큰 계산 로직 구현
  • 추후 모델별 토큰 계산 방식이 달라질 수 있으므로 구현체를 교체할 수 있는 구조로 설계
  • 한글, 영어/숫자, 공백, 특수문자를 기준으로 토큰 수 계산
  • 한글은 1글자당 1토큰으로 계산
  • 영어와 숫자는 4글자당 1토큰으로 계산
  • 공백은 토큰 수에 포함하지 않음
  • 특수문자는 1개당 1토큰으로 계산

추후 개선 가능 사항

현재 countTokens() 메서드 안에 한글, 영어/숫자, 공백, 특수문자 처리 로직이 함께 존재한다.

문자 유형을 CharacterType enum으로 분리하고, 문자 분류 책임을 별도 클래스로 분리한다 

  • KOREAN
  • ALPHA
  • NUMBER
  • WHITESPACE
  • SPECIAL

이를 통해 SimpleTokenizer는 전체 순회 흐름만 담당하고, 문자 구분 로직은 별도의 분류 객체가 담당하도록 책임을 분리할 수 있다.

 

문제 발생 가능성

 

 

궁금한 점

  • 추후 개선 가능 사항에 있는 문자 구분할 때 한글이면 KOREAN 영어면 ALPHA 이런식으로 구분해서 처리 하는 방식은 어떤지 ?

문자 분리 기준

  • 처음에는 공백 기준이나, 여러 방법을 찾아봤지만 각 언어의 특성에 맞게 구성 하기에는 어려움이 있다고 생각
  • 영어와 한글 숫자 등등 어려 문자가 혼합 되어서 올 수도 있고 여러 예외 상황이 발생 할 수 있다고 생각 해 일단 구현을 단순화 하기 위해서 기준을 잡음.

인터페이스 분리 기준

  • 다른 기능을 구현하면 쉽게 구현체를 변경 할 수 있도록 구성
  • 구현체는 countTokens 메서드를 구현한다, 지금은 하나의 메서드 안에 한글, 영어, 특수문자 등등 여러 기능이 있기 때문에 이 부분도 변경 예정

슬라이딩 윈도우 기능 1차 구현사항

LLM의 Context Window 제한을 넘지 않도록 최근 대화 메시지를 토큰 수 기준으로 관리하는 기능.

 

상태

  • maxTokens: 윈도우가 허용하는 최대 토큰 수
  • messages: 현재 유지 중인 ChatMessage 목록
  • currentTokens: 현재 윈도우에 포함된 메시지들의 총 토큰 수

 기능

  • 새로운 메시지가 추가될 때마다 현재 누적 토큰 수를 관리
  • 새 메시지를 추가했을 때 최대 토큰 수를 초과할 경우 오래된 메시지부터 제거
  • ArrayDeque를 사용하여 뒤에는 새 메시지를 추가하고, 앞에서는 오래된 메시지를 제거
  • 매번 전체 메시지의 토큰 수를 다시 계산하지 않고 currentTokens를 누적 관리
  • 대화방 또는 세션마다 서로 다른 maxTokens 값을 설정할 수 있도록 생성 시 외부에서 값을 주입

예외 처리 정책

  • 최대 토큰을 한번에 넘어가는 컨텍스트가 들어온다  -> 예외 발생

ArrayDeque 선택 이유

ArrayList를사용하게 되었을 때 맨 뒤에 데이터를 추가 하는건 O(1) 에 가능하다 하지만 맨 앞 데이터를 지우는 경우에 문제가 발생 한다. 

 

맨 앞 데이터를 지운다고 했을 때는 O(1)로 지울 수 있지만 빈 공간을 채우기 위해서, 맨 앞 데이터 + 1 위치에 있는 데이터를 모두 앞으로 한칸씩 이동 시켜야 한다. 

 

그렇기 때문에 ArrayList 는 슬라이딩 윈도우 알고리즘에는 적합하지 않다 슬라이딩 윈도우 특성 상 맨 뒤에 데이터를 추가 하고, 맨 앞에있는 데이터를 지우는 방식이기 때문에 ArrayDeque, LinkedList 같은 자료구조를 선택해야 한다

 

LinkedList 문제점 

이 중에서 ArrayDeque를 선택 했는데 그 이유는 LinkedList는 내부적으로 Node라는 독립된 객체를 매번 새로 생성한다

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;
   
...

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    
...

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
 
...

 

LinkedList 내부에 위치해 있는 Node 구조인데 자신, 앞, 뒤의 구조를 가지고 있고 제네릭 타입을 가지고 있다, 이 부분은 얼핏 보면 객체의 주소만 들고있기 때문에 문제가 없을것 같지만 큰 문제는 Node 구조 자체에 문제가 있다 Node 객체의 메모리 무게를 4바이트로 가정했을 때 내부 12바이트 + 객체의 메타데이터를 담고있는 객체 헤더까지 대략 24바이트를 차지할 수 있다.

 

내가 저장할 것은 item 한개인데 그 뒤에 부가적으로 붙는 next, prev + 객체 헤더 포함 20바이트의 오버헤드가 나타나게 된다.

 

또한 int = 4바이트, double = 8바이트 각 타입마다 고정되어있는 방이 있는것 처럼 JVM의 메모리 관리 기법중 하나인 8바이트 정렬로 인해서 예시는 8의 배수이기 때문에 패딩을 추가하지 않겠지만 만약 25바이트라면 여기에 페딩 7바이트가 추가되기 때문에 7바이트의 오버헤드가 발생할수 있다.

 

다음 문제로 메모리의 연속성이 없기 때문에 탐색에도 문제가 된다. new Node로 생성되기 때문에 메모리에 렌덤한 위치에 객체가 생성되게 된다, 이 문제는 CPU 캐시 미스 문제를 유발한다 

 

배열 공간을 new로 생성 한다고 하면 렌덤한 위치에 연속적인 메모리 공간을 차지하게 된다, 여기서의 탐색은 하드웨어 관점에서 CPU가
1번 데이터를 읽는 순간, 미리 2번 데이터, 3번 데이터를 읽는구나 하고 연속된 공간에 있는 다음 주소들을 CPU 캐시 메모리에 통째로 미리 올려버려 다음 데이터를 탐색할 때 메인 메모리를 방문 할 필요 없이 더 빠르게 데이터를 탐색할 수 있지만

 

LinkedList의 경우 렌덤한 위치에 Node가 생성되기 때문에 CPU 캐시 미스로 인해 메모리를 한번 더 들려야 하고, 이때 제네릭을 사용하기 때문에 한번더 그 객체의 주소로 이동하는 이중 랜덤 점프가 반복되기 때문에 탐색에 2중으로 오버헤드가 발생한다.

 

ArrayDeque는 LinkedList, ArrayList 에서 나타났던 문제를 효과적으로 해결하고 있다.

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
   
    transient Object[] elements;

    transient int head;

    transient int tail;
    
...

public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        final Object[] es = elements;
        es[head = dec(head, es.length)] = e;
        if (head == tail)
            grow(1);
    }
    
...

 

LinkedList와 다르게 Object 배열로 연속된 공간을 미리 할당하고 원형 큐의 구조를 띄고있다.

 

이것이 어떤 이점이 있냐면 연속된 배열 공간을 사용하고 있기 때문에 LinkedList의 문제점을 최적화 한다
다음 데이터에 접근하기 위해 Node 객체를 거쳐 진짜 데이터 주소로 넘어가는 이중 랜덤 점프 하는 문제를 ArrayDeque는 연속된 배열 내에 진짜 데이터의 참조 주소가 일렬로 저장되어 있기 때문에, 단 한 번의 점프로 데이터에 접근하게 되고.

 

메모리가 물리적으로 연속되어 존재하기 때문에 하드웨어 단의 최적화로 인해 다음 객체를 방문할때 메인 메모리까지 갈 필요 없이 캐시에서 바로 주소를 읽어 CPU 캐시 미스를 줄일수 있다.

 

ArrayDeque는 LinkedList처럼 데이터마다 Node 객체를 매번 생성하지 않기 때문에, 불필요한 객체 생성 비용이 전혀 발생하지 않는다. 처음에 할당받은 단 하나의 연속된 내부 배열 공간에 순수 참조 주소만 채워 넣는 구조를 가지고 있어 메모리 낭비를 최소화합니다

 

ArrayList에서 발생한 데이터를 앞으로 이동시키는 문제는 원형큐의 특성인 앞, 뒤를 가리키는 포인터만 이동시키는 구조로 해결한다. 코드의 head, tail가 이 역할을 한다.

 

불필요한 메모리 오버헤드를 줄이기 위해 Deque 기반 슬라이딩 윈도우를 사용했고, 캡슐화를 통해 현재 윈도우 상태를 객체 내부에서 관리하도록 구현했다. Deque는 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이기 때문에, 최신 메시지는 뒤에 추가하고 오래된 메시지는 앞에서 제거하는 슬라이딩 윈도우 구조에 적합하다고 생각한다.

 

사용자와, 답변에 대한 많은 질문이 오고 갔을때 이전 대화를 LLM은 기억하지 못한다, 평소 사용하는 Chat GPT, Claude 등등 이런 방식을 사용한다, 요약 방식으로 하나의 세션의 콘텍스트가 전부 할당되면 이것을 2, 3줄 정도로 요약하여 다시 Queue에 저장 하고 대화를 이어 나가는 방식.

 

또 다른 방식은 벡터 검색 방식으로 아주 예전 대화는 데이터베이스에 실수형 벡터 데이터(임베딩)로 저장해 두고, 그러다가 사용자가 과거 질문과 관련된 말을 하면, 슬라이딩 윈도우 밖에 있던 옛날 대화 중 필요한 부분만 싹 긁어와서 윈도우 안에 잠깐 끼워 넣는 방식이 있다.

 

실제 운영 환경 외부 라이브러리

OpenAI : tiktoken

 

'ai' 카테고리의 다른 글

고동시성 환경에서의 AI 요청 비동기 스케줄링 큐  (0) 2026.06.24

티스토리툴바