순차 탐색 중 이미 지나친 정보를 알고 싶다면? 자료구조를 활용한 메모리 캐싱 직접 구현해보기 (feat. 알고리즘 vs 자료구조)

0. 목차

1. 개요
2. 문제 상황
3. 가장 쉬운 접근
4. 캐싱
5. 결론

1. 개요

본 글에서는 로그 파일을 파싱하고 구조화 할때 사용한 메모리 캐싱에 대해 다룹니다. 파일을 순차적으로 탐색하며 진행할 때 이미 지나친 파일에 대한 정보가 필요했습니다. 이를 해결하는 방식으로 한 차례 더 순차 탐색을 진행할 수도 있었지만 내부적으로 캐싱 방식을 구현하여 해결한 케이스입니다. 스프링 캐시나 별도의 캐시 라이브러리를 사용하지 않고 직접 구현한 경험을 소개합니다.

 

• 예시 코드는 실제 코드가 아닌 컨셉 코드로 대체하였습니다.

 

2. 문제 상황

아래와 같은 SimpleLogEventReader는 LogData를 String으로 받아 이를 읽고 LogEvent로 변환하는 작업을 수행합니다. 이때 LogEvent는 내부에 Message를 비롯한 복잡한 메시지 타입의 객체를 갖고 있어 이들은 LogEvent를 Root로 하는 LogAggregate로 분류됩니다.

 

@Component
@RequiredArgsConstructor
public class SimpleLogEventReader implements LogEventReader {

    private static final String LOG_EVENT_PATTERN = "정규식 패턴";

    private final EventActionFactory eventActionFactory;
    private final MessageFactory messageFactory;

    @Override
    public List<LogEvent> read(String logData) {
        return Arrays.stream(logData.split("\n"))
           		// ...
                .collect(Collectors.toList());
    }

    public LogEvent createLogEvent(Matcher matcher) {
        EventAction eventAction = eventActionFactory.fromString(matcher.group(5));
        Message<?> Message = messageFactory.createMessage(matcher.group(7), recentLogEvents.get(extractUUIDFromMessage(matcher.group(7))));

        LogEvent logEvent = LogEvent.builder()
                .파라미터1(LocalTime.parse(matcher.group(1)))
                .파라미터2(matcher.group(2))
                .파라미터3(matcher.group(3))
                .파라미터4(matcher.group(4))
                .파라미터5(eventAction)
                //... 
                .build();

        return logEvent;
    }
}

 

LogEvent는 그 속성에 따라 Request와 Response로 분류될 수 있습니다. 즉, 어떤 LogEvent는 Request 타입이며, 어떤 LogEvent는 Response 타입입니다. 즉, LogEvent 각자는 고유한 개별 객체이지만 도메인 백그라운드가 적용된 논리적인 존재로서 pair 형태로 존재함을 의미합니다.

 

여기서 Request와 Response는 UUID를 공유하며 이를 통해 연결됩니다. 따라서 Request 속성의 LogEvent는 스스로의 pair로서 response를 인지할 필요가 있으며, 반대도 마찬가지입니다.

 

이때, Request와 Response 타입은 Message를 통해 판단되어지기 때문에 LogEventReader는 Message 생성을 다음과 같은 MessageFactory에 위임합니다.

 

@Component
@RequiredArgsConstructor
public class MessageFactoryImpl implements MessageFactory {

    private final PayloadActionFactory payloadActionFactory;

    @Override
    public <P> Message<P> createChannelMessage(String rawData, LogEvent pairLogEvent) {
        JsonArray jsonArray = new JsonParser().parse(rawData).getAsJsonArray();
        String uniqueId = jsonArray.get(1).getAsString();

        return Arrays.stream(MessageFormat.values())
                .filter(format -> format.getMessageCode() == jsonArray.get(0).getAsInt())
                .findFirst()
                .map(format -> (Message<P>) format.createCMessage(uniqueId, payloadActionFactory, jsonArray, pairLogEvent))
                .orElse(Message.nullObject());
    }
}

 

MessageFactory는 MessageFormat의 타입을 판단해주고, 각각의 타입 포맷에게 다시 스스로의 생성 책임을 맡깁니다. 이때 과거의 LogEvent에 대한 정보를 알아야 하는 필요성이 생기는데 앞서 살펴보았듯 LogEvent는 UUID를 통해 Request와 Response가 연결되어 있는 상황입니다. Response 타입은 스스로 Payload를 인지하지 못하며 Request에 대응되는 Payload여야 하기 때문에 Request를 알아야 자기 자신의 Payload를 규정할 수 있기 때문입니다.

 

다음과 같이 Response Format은 UUID가 일치하여 pair로 판명난 LogEvent를 받아와 해당 LogEvent의 Request Payload가 무엇인지를 이해해야 해당 Payload에 맞는 Response로 스스로를 생성할 수 있습니다.

 

public class SomethingResultFormat implements MessageFormatter {
    @Override
    public <P> Message<P> create(int messageTypeId, String uniqueId, PayloadActionFactory payloadActionFactory, JsonArray jsonArray, LogEvent pairLogEvent) {

        if (pairLogEvent == null) {
            // 처리 후 리턴 로직 
        }

       // 처리 후 리턴 로직
    }
}

 

이러한 플로우가 진행된다고 할 때, Response 타입에 해당하는 LogEvent는 pair로서 Request 타입의 LogEvent를 인지해야 합니다.

 

이때 Response가 존재한다면 Request도 반드시 존재할 것이라는 전제는 가정하며, 만약 이것이 성립하지 않는다면 예외 상황으로 판단합니다.

 

바로 이 지점에서 로그 파일은 순차적으로 읽히기 때문에 이미 지나간 정보를 다시 어떻게 알 것이냐에 대한 문제가 생깁니다.

 

고려해야 할 점은 응답과 요청은 바로 앞뒤 선후관계로 나오지 않고 몇 로그씩 건너뛰고 등장할 수도 있다는 점입니다.

 

3. 가장 쉬운 접근

만약 앞뒤로 로그가 발생한다면, 이전 LogEvent와 현재 LogEvent와 다음 LogEvent를 Node 형태로 참조하게 하여 현재를 기준으로 응답인지 요청인지를 판단할 수 있을 것입니다. 그러나 응답이 얼마나 뒤에 발생할지 모른다면, 이 방식으로는 결국 전체를 두 번 순회하는 것이 필요하게 될 것 같습니다. 1차에서 LogEvent 전체 탐색을 마치고, 해당 로그를 한 번 더 전체 탐색을 하여 UUID를 통해 매핑되는 LogEvent를 찾는 것이죠.

 

이 과정은 전체 로그를 두 번 순회해야 하므로 시간 복잡도가 O(n^2)이 되므로 효율성에서 좋은 점수를 얻기 힘들 것 같습니다.

 

4. 캐싱 

LogEvent를 생성할 때 UUID를 키로 가지는 Map을 사용해 LogEvent를 저장하는 것입니다. 이렇게 하면 응답과 요청을 매칭하는데 O(1)의 시간 복잡도로 해결되고, 1차례 전체 탐색만 이루어지므로 결과적인 시간 복잡도는 O(n)로 해결할 수 있습니다. 이를 구현하면 다음과 같습니다.

 

@Component
@RequiredArgsConstructor
public class SimpleLogEventReader implements LogEventReader {

    // ... 

    private Map<String, LogEvent> recentLogEvents = new LinkedHashMap<>();

    // ... 

    public LogEvent createLogEvent(Matcher matcher) {

        // ... 

        recentLogEvents.put(channelMessage.getUniqueId(), logEvent);
        return logEvent;
    }

 

여기서 UUID를 키로 사용하는 recentLogEvents Map은 사실상 캐시와 유사한 역할을 합니다. 이 캐시는 시간 복잡도를 크게 줄여주므로, 로그 데이터의 크기가 크더라도 효과적으로 요청과 응답을 매핑할 수 있게 할 것입니다.

 

그런데 이런 생각이 듭니다. 해당 클래스는 Reader의 역할을 수행하는 클래스이기 때문에 저장에 대한 책임은 없다는 것입니다. 그렇기 때문에 캐싱을 위한 자료 구조 네이밍도 recentLogEvents이죠. 말 그대로 임시적 필요에 따라 구현된 자료구조인 것이라면, Reader 클래스가 인스턴스 필드로서 해당 자료구조를 가질 필요가 있겠느냐에 대한 의문이 드는 것입니다.

 

설계 측면에서 recentLogEvents를 필드로 가지고 있는 것은 이 클래스가 상태를 가지게 만들고, 따라서 이 클래스의 인스턴스를 재사용하는 것을 어렵게 만듭니다. SimpleLogEventReader 클래스가 로그 이벤트를 읽는 동시에 일부 상태를 유지하고 있기 때문에 이로 인해 SimpleLogEventReader는 재사용하기 어렵게 만들어집니다.

 

이를 해결하고자 상태를 로컬로 유지하면 어떨까요? 즉, recentLogEvents를 메서드 로컬 변수로 만드는 것입니다.

 

@Override
public List<LogEvent> read(String logData) {
    Map<String, LogEvent> recentLogEvents = new LinkedHashMap<>();
    return Arrays.stream(logData.split("\n"))
            .map(Pattern.compile(LOG_EVENT_PATTERN)::matcher)
            .filter(Matcher::matches)
            .map(matcher -> this.createLogEvent(matcher, recentLogEvents))
            .collect(Collectors.toList());
}

public LogEvent createLogEvent(Matcher matcher, Map<String, LogEvent> recentLogEvents) {
    //...
}

 

그러나 이렇게 하면 createLogEvent 메서드가 상태를 변경하므로, 이 메서드는 순수 함수가 아니게 되는데, 개념적으로 클래스 차원의 문제를 메서드 차원으로 축소했을 뿐인 거죠.

 

따라서 리팩토링의 방법으로 recentLogEvents에 대한 관리를 SimpleLogEventReader에서 분리하는 새로운 클래스를 만들어보는 방식을 선택했습니다. 간단한 방법이죠. 이 클래스는 UUID를 추출하고, recentLogEvents를 관리하는 책임을 갖습니다. 이렇게 함으로써 기존 Reader 클래스는 캐싱에 대한 책임을 갖지 않아도 됩니다.

@Component
public class LogEventCache {
    private Map<String, LogEvent> recentLogEvents = new LinkedHashMap<>();

    public LogEvent findLogEventByUUID(String uuid) {
        return recentLogEvents.get(uuid);
    }

    public void put(String uuid, LogEvent event) {
        recentLogEvents.put(uuid, event);
    }

    public void clear() {
        recentLogEvents.clear();
    }
}

 

그런데 여기서 이 클래스의 적절한 패키지 구조상의 위치는 어디일까요? 막상 개발을 하면 이런 고민을 참 많이 하게 되는 것 같은데 그 주제는 다음 기회에...

 

아무튼,

 

이제 SimpleLogEventReader는 LogEventCache의 상태를 걱정할 필요가 없어졌습니다.

 

여기서 해당 클래스의 상태는 상시적으로 초기화 되어야 하기 때문에 원칙적으로 빈으로 등록하면 안될 것입니다. 하지만 어차피 별도의 초기화 로직이 필요하므로 명시적인 초기화 로직을 둔다면 문제가 없을 것으로 판단했습니다.

 

캐시를 초기화 하는 로직을 호출하는 시점은 파일을 읽기 시작하는 read 메서드의 시작점이 적절할 것입니다.

 

@Override
    public List<LogEvent> read(String logData) {
        logEventCache.clear();
        return Arrays.stream(logData.split("\n"))
              // ... 
                .collect(Collectors.toList());
    }

 

이렇게 하여 캐시를 초기화하는 로직이 LogEventReader의 read 메소드에 명시적으로 들어가므로, read 메소드가 호출될 때마다 캐시가 초기화되어 이전에 읽은 로그 이벤트가 캐시에 남아있지 않게 되므로 요구사항을 만족합니다.

5. 결론

로그 파일을 순차적으로 파싱하며 LogEvent로 구조화하는 과정에서 응답 타입의 LogEvent가 요청 타입의 LogEvent를 인지해야 하는 문제를 다뤘습니다. 이 문제를 해결하기 위해 가장 직관적인 방법은 아마도 (?) 전체 로그 파일을 두 번 순회하는 방법일 것 같은데요. 시간 복잡도의 비효율성 문제로 선택하기 어려웠습니다.

 

저는 이 케이스를 생각하면서 '알고리즘으로 풀기 vs. 자료구조로 풀기'라는 대결 구도가 떠올랐습니다. 어떤 문제를 해결할 때 다양한 방식이 있지만 먼저 자료구조를 잘 생각해보면 의외로 쉽게 풀리는 경우가 있는 것 같습니다. 물론, 막상 해놓고 보면 이걸 왜 몰랐지 싶기도 하구요.

 

순차 탐색 중간 과정에서 뒤로 돌아갈 필요가 있을 때 어떻게 할까? UUID를 키로 가지는 Map을 활용해 캐싱 로직을 간단히 구현하여 해결한 경험을 소개해보았습니다.