(326)

[MySQL] Lost Update와 Write Skew

서론트랜잭션의 격리 수준 포스팅에서 다루지 않았던 이상현상 중 Lost Update와 Write Skew같은 일관되지 않은 쓰기 결과를 반환하는 데이터 부정합 문제가 있다. PostegraSQL에서는 격리 수준을 REPEATABLE READ로 설정하는 것만으로도 쓰기 결과를 올바르게 보장할 수 있다. 하지만 MySQL의 MVCC(Multi Version Concurrency Control)은 일관된 읽기(Consistence Read)를 지원하지만 위와 같은 데이터 업데이트의 부정합 문제를 REPEATABLE READ의 격리 수준 만으로는 해결할 수 없다.  아래 그림은 MySQL에서 REPEATABLE READ 격리 수준을 사용했을 때 Lost Update가 발생하는 상황이다. 고객 A가 10,000원..

[데이터베이스] MVCC(다중 버전 동시성 제어 - Multi Version Concurrency Control)

동시성 제어(Concurrency Control)DBMS에서 동시성 제어는 동시에 데이터에 접근하는 여러 사용자, 즉 여러 트랜잭션의 상호작용에서 트랜잭션의 isolation을 보장하고 일관성과 무결성을 유지할 수 있도록 하는 목적으로 사용되는 기술이다.  이러한 동시성 제어를 하는 대표적인 방식 중 가장 대표적인 Lock을 간단하게 알아보자.  공유 잠금(읽기 잠금, shared lock)이나 배타적 잠금(쓰기 잠금, exclusive lock)을 통해 Lock을 획득한 후 트랜잭션 내부의 작업을 수행하는 방식이다. (read로도 쓰기 잠금을 획득할 수 있다)  다른 트랜잭션은 이전 트랜잭션에서 Lock을 반환해야 작업이 수행이 가능하다는 의미이다.    이는 곧 SERIALIZABLE하다는 의미이며,..

[MySQL] 트랜잭션 격리수준(isolation level)과 이상현상 (with 테스트 코드)

기억에 오래남고 이해하기 쉽게 현재 조직의 웨딩 도메인의 적립금을 예시로 간단한 엔터티 설계와 더불어 테스트 코드를 작성하여 각 격리수준과 이에 따른 이상현상을 정리해보았다. 개념들은 MySQL의 공식문서를 활용하여 정리하였고, AUTO_COMMIT은 FALSE를 가정하고 예제들을 작성하였다. (예제에 필요한 기본적인 엔터티와 데이터 세팅은 아래를 참조) CREATE TABLE icash (    no INT UNSIGNED AUTO_INCREMENT PRIMARY KEY,    user_no INT UNSIGNED UNIQUE NOT NULL,    icash INT UNSIGNED DEFAULT 0 NOT NULL,    created_at TIMESTAMP DEFAULT CURRENT_TIMESTA..

typeORM을 사용하면서 왜 N+1 문제를 마주하지 못했을까?

ORM을 사용하다보면 N + 1 문제를 마주하곤 하는데, 특히 ORM의 Default Fetch Type설정이 Lazy일 경우 더 그렇다. 이제 막 typeORM을 사용해보고 있다고 하시는 분과 커피챗을 할 기회가 생겼는데 typeORM에서는 N + 1을 어떻게 해결하냐는 얘기가 나왔었다. N + 1이 어떤 것인지는 알고 있었으나 나는 typeORM을 사용하면서 실제적으로 N + 1을 마주한 경험이 없다. 실제로 실무에서도 페이징을 위한 paginate 라이브러리 사용 시 Distinct로 클러스터 인덱스를 가져와서 리스트, 페이징에 총 세 번의 쿼리를 사용하는 경우를 제외하고는 본 적이 없다. 왜 그럴까 곰곰이 생각을 해봤다. 최근에 nest에서 graphQL을 사용하고자 했을 때에도 N + 1 문제를..

복합 인덱스로 쿼리 튜닝하기

[데이터베이스] 인덱스(index) 정리인덱스 목차, 색인, 책갈피와 같은 기능을 하는 인덱스는, 데이터베이스 분야에서는 어떤 데이터를 검색할 때 속도를 높여주는 자료 구조로메모리 영역에 생성되는 일종의 책갈피이다. mag1c.tistory.com 위 글의 복합 인덱스를 통한 튜닝 부분을 따로 옮긴 포스팅입니다. 분명 일정한 기준이 있을 텐데 왜 얘기들이 조금씩 다른 것일까? DB의 버전 때문일까 옵티마이저가 무조건적으로 100% 맞다는 보장이 없어서일까? 잘 모르겠다. 그래서 직접 쿼리 튜닝의 경험들을 복기하며 복합 인덱스를 생성할 때에는 어떤 순서로 인덱스를 구성해야 하는지 알아보았다. 서비스 내부에는 모든 유저의 장바구니(앞으로 견적함이라 부름)를 볼 수 있는 기능이 존재하는데 업종으로 필터링할 경..

[알고리즘] 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)  위의 위키피디아 문서를 참조하면, 위상 정렬이란 정점의 선형 순서 지정을 통해 모든 방향 간선 uv에 대해 정점 u가 v보다 앞에 올 수 있게 정렬하기 위해 사용되는 알고리즘으로, 방향성 비순환 그래프 - DAG(Directed Acyclic Graph)에만 적용할 수 있다고 한다.     쉽게 말하자면 순서가 정해져 있는 작업을 차례로 수행해야할 때 순서를 결정해주는 알고리즘이고,더 쉽게 말하자면, 순서를 찾아주는 알고리즘이다.  특징나열한 정렬 순서만 두 가지 경우가 존재하고 추가로 여러 개의 답이 더 존재할 수 있다. 이처럼 위상 정렬은 여러 개의 답이 존재할 수 있다는 특징이 있다. 순회하는 방법이 한 가지보다 많을 수 있기 때문이다. 또한, 위에서 DAG에..

크루스칼(Kruskal) 알고리즘 (with. 백준 1197번 최소 스패닝 트리)

크루스칼 알고리즘 (Kruskal Algorithm)크루스칼 알고리즘(Kruskal Algorithm)이란 최소 신장 트리(Minimum Spanning Tree)를 찾기 위해 사용되는 알고리즘이다. 신장 트리(Spanning Tree)그래프 내의 모든 정점을 포함하는 트리 최소 신장 트리(Minimum Spanning Tree)신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리   최소 신장 트리를 찾기 위해 모든 간선을 가중치에 따라 오름차순으로 정렬하는 아이디어를 사용하여 효과적으로 MST를 구할 수 있게 된다.세부적인 구현 방법은 다음과 같다. 1. 모든 간선을 가중치에 따라 오름차순 정렬한다.2. 간선을 하나씩 선택하여 사이클이 생기지 않을 때 연결하여 모든 노드가 연결될 때 까지 반복한..

[데이터베이스] 인덱스(index) 정리

인덱스   목차, 색인, 책갈피와 같은 기능을 하는 인덱스는, 데이터베이스 분야에서는 어떤 데이터를 검색할 때 속도를 높여주는 자료 구조로메모리 영역에 생성되는 일종의 책갈피이다.    인덱스 구조보통 Hash, B-Tree, B+Tree가 있다. Hash우리가 알고있는 Key, Value형태의 자료 구조다.해시 함수로 키 값을 해시값으로 변환하고, 이 해시 값을 기반으로 데이터를 빠르게 조회할 수 있다. - O(1)   하지만 이런 해시구조의 특성상 범위 검색에 효율이 떨어진다. 키 값이 조금이라도 변하게 되면 완전히 다른 해시 값을 반환하기 때문이다.범위 검색에서의 부등호 연산을 포함한 범위 조건(BETWEEN, LIKE 등)에는 적합하지 않다.   B-TreeB-Tree는 이진 트리를 확장한 트리 ..

graphQL의 N + 1문제와 DataLoader

graphQL에 대해 알아보자 - 1 (with NestJS, typeORM)학습을 위해 생성한 예제 코드는 깃헙에 있습니다.(링크)  graphQLgraphQL은 기존 데이터로 쿼리를 실행하기 위한 API를 위한 쿼리 언어이자 런타임이다. 클라이언트가 필요한 것만 정확히 요청할mag1c.tistory.com  N + 1이전 글의 예제에서 Post를 가져오는데에 Post와 Comments는 1:N 관계를 가진다.이 관계에서 comments를 조회할 때 comment가 lazy loding되어 N + 1 문제가 발생할 수 있다. //lazy loadingasync findAll(authorId?: number): Promise {    if (authorId) return await this.postRep..

[MySQL] Lost Update와 Write Skew

Tech/데이터베이스 2024. 12. 12. 11:07
728x90
728x90

 

서론

트랜잭션의 격리 수준 포스팅에서 다루지 않았던 이상현상 중 Lost Update와 Write Skew같은 일관되지 않은 쓰기 결과를 반환하는 데이터 부정합 문제가 있다. PostegraSQL에서는 격리 수준을 REPEATABLE READ로 설정하는 것만으로도 쓰기 결과를 올바르게 보장할 수 있다. 하지만 MySQL의 MVCC(Multi Version Concurrency Control)일관된 읽기(Consistence Read)를 지원하지만 위와 같은 데이터 업데이트의 부정합 문제를 REPEATABLE READ의 격리 수준 만으로는 해결할 수 없다.

 

 

아래 그림은 MySQL에서 REPEATABLE READ 격리 수준을 사용했을 때 Lost Update가 발생하는 상황이다. 고객 A가 10,000원을 사용한 뒤 관리자가 곧바로 20,000원을 환불했지만 결과적으로 고객의 잔액은 30,000원 이 되어버렸다. 이는 두 트랜잭션이 같은 데이터를 읽고 각각의 연산 결과를 덮어버린 탓에 발생한 문제다.

 

 

 

 

 

 

 

격리 수준을 SERIALIZABLE로 설정하면 모든 데이터 부정합 문제를 해결할 수 있지만 그만큼 동시성이 보장되지 않는다. 결제, 재고, 선착순 이벤트 등과 같은 상황에서 특히 데이터 정합성이 필수적이다. 또한 그런 기능은 생각보다 보편화되어 널리 사용되고 있다.

 

위처럼, Lost Update와 Write Skew는 동시에 실행된 트랜잭션에서 같은 데이터를 조회하면서 데이터에 일관성이 깨져버린다. 그렇다면 MySQL에서 동시성을 보장하면서 Lost Update, Write Skew같은 부정합 문제도 해결하기 위해서 어떤 방법을 사용해야할까?

 

 

 

 

 

Lost Update

Lost Update란 위 예시처럼 두 트랜잭션이 동일한 레코드를 읽고 각각 수정한 결과를 커밋할 때 발생하는 문제이다. 첫 번째 트랜잭션의 업데이트가 두 번째 트랜잭션의 결과로 덮여버리며, 데이터의 정합성이 깨지게 된다.

 

 

it('REPEATABLE READ:: LOST UPDATED.', async () => {
    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();

    // 트랜잭션 A 시작
    await runnerA.startTransaction('REPEATABLE READ');
    const repoA = runnerA.manager.getRepository(ICashEntity);

    // 트랜잭션 B 시작
    await runnerB.startTransaction('REPEATABLE READ');
    const repoB = runnerB.manager.getRepository(ICashEntity);

    // 업데이트를 위해 조회
    const readA = await repoA.createQueryBuilder().where('no = :no', { no: 1 }).getOneOrFail();
    const readB = await repoB.createQueryBuilder().where('no = :no', { no: 1 }).getOneOrFail();
    
    //초기 값 테스트
    expect(readA.icash).toBe(10000);
    expect(readB.icash).toBe(10000);

    // 캐시 사용
    await repoA.update({ no: 1 }, { icash: readA.icash - 10000 });
    await runnerA.commitTransaction();

    // 캐시 적립
    await repoB.update({ no: 1 }, { icash: readB.icash + 20000 });
    await runnerB.commitTransaction();

    const result = await repoA.findOneOrFail({ where: { no: 1 } });
    expect(result.icash).toBe(20000);
});

 

 

 

 

 

위 그림을 테스트 코드로 작성했다. 거의 비슷한 시간에 고객이 캐시를 사용하면서 관리자가 캐시를 환불해주었다. 우리는 캐시 사용과 환불을 통해 2만원이라는 결과를 기대하지만, 고객의 캐시 사용에 대한 커밋은 이후의 트랜잭션에 의해 덮어졌다. 이를 개선해서 올바른 업데이트를 반영시켜보자.

 

 

 

 

 

 

Optimistic Lock(낙관적 잠금)

Optimisitic Lock은 데이터를 동시에 수정하지 않을 것이라고 가정하는 방식이다. 예를 들어, 회원 정보 수정처럼 동시에 수정될 가능성이 낮은 작업에서 효과적이다. 데이터에 Lock을 걸지 않기 때문에 동시 요청에 대해 처리 성능이 뛰어나다. 대신 충돌이 발생하면 이를 감지하고 롤백하거나 재시도해야한다.

 

it.only('REPEATABLE READ:: LOST UPDATED.', async () => {
    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();

    // 트랜잭션 A 시작
    await runnerA.startTransaction('REPEATABLE READ');
    const repoA = runnerA.manager.getRepository(ICashEntity);

    // 트랜잭션 B 시작
    await runnerB.startTransaction('REPEATABLE READ');
    const repoB = runnerB.manager.getRepository(ICashEntity);

    const readA = await repoA.createQueryBuilder().where('no = :no', { no: 1 }).getOneOrFail();
    const readB = await repoB.createQueryBuilder().where('no = :no', { no: 1 }).getOneOrFail();

    expect(readA.icash).toBe(10000);
    expect(readB.icash).toBe(10000);

    const updateResultA = await repoA
        .createQueryBuilder()
        .update(ICashEntity)
        .set({ icash: readA.icash - 10000, version: readA.version + 1 })
        .where('no = :no', { no: 1 })
        .andWhere('version = :version', { version: readA.version })
        .execute();

    if (updateResultA.affected === 0) {
        throw new Error('Optimistic Lock Conflict: Transaction A failed to update');
    }

    await runnerA.commitTransaction();

    const updateResultB = await repoB
        .createQueryBuilder()
        .update(ICashEntity)
        .set({ icash: readB.icash + 20000, version: readB.version + 1 })
        .where('no = :no', { no: 1 })
        .andWhere('version = :version', { version: readB.version })
        .execute();

    await runnerB.commitTransaction();

    const result = await repoA.findOneOrFail({ where: { no: 1 } });

    // Optimistic Lock Conflict: Transaction B failed to update
    expect(result.icash).toBe(0);
    expect(updateResultB.affected).toBe(0);
});
@Entity('icash')
export class ICashEntity {
    @VersionColumn()
    version!: number;
}

 

 

version 컬럼을 활용해 Optimistic Lock을 구현했다. Optimisitic Lock을 사용하면 version을 통해 데이터의 상태 변화를 감지하고, 트랜잭션 충돌을 방지할 수 있다. 트랜잭션 A가 업데이트하면서 version을 증가시키면, 트랜잭션 B는 자신의 version 조건이 충족되지 않아 업데이트에 실패한다.

 

하지만, 이 방식 테이블에 추가 컬럼이 필요하고, 충돌 시 롤백이나 재시도 로직이 필요하다.

위의 테스트 코드에서처럼, B에서 실패 후처리를 하지 않았기 때문에 캐시는 환불되지 않았다.

 

따라서 데이터 충돌 가능성이 높은 경우에는 배타적 잠금(Pessimistic Lock)을 활용하는 것이 더 적합할 수 있다.

 

 

 

 

 

 

Pessimistic Lock(비관적 잠금)

SERIALIZABLE은 쓰기 상황에서 동시 요청에 대해 데이터 정합성이 깨지지 않도록 보장한다. 이는 SERIALIZABLE 격리 수준의 특징으로  MySQL에서는 SERIALIZABLE 격리 수준에서 데이터를 읽을 때 항상 Shared Lock(읽기 잠금)을 건다.

 

 

 

 

 

 

비관적 잠금은 데이터가 동시에 수정될 것이라고 가정하고, 데이터를 읽는 시점에 Lock을 걸어 트랜잭션이 완료되면 반납하는 방식이다. 이를 통해 동시성 이슈를 방지하면서도 데이터 무결성을 유지할 수 있다. 이러한 비관적 잠금에는 크게 공유 잠금과 배타 잠금이 있다.

  • 공유 잠금(Shared Lock - S Lock / 읽기 잠금) - 다른 트랜잭션의 읽기는 허용
  • 배타적 잠금(Exclusive Lock - X Lock / 쓰기 잠금) - 다른 트랜잭션의 읽기 쓰기 모두 차단

 

 

아래 코드는 REPEATABLE READ 격리 수준에서 비관적 잠금을 사용하는 실제 비즈니스 로직의 예시를 단위로 분리하고, 데이터를 읽으면서 잠금을 걸었다. 이를 통해 동시 업데이트 시에도 성공적으로 데이터를 보호할 수 있다.

@Injectable()
export class ICashService {
    constructor(private readonly icashRepo: ICashRepository) {}

    async getICash(userNo: number) {
        return this.icashRepo.findICashByUserNo(userNo);
    }

    @Transactional({ isolationLevel: IsolationLevel.REPEATABLE_READ })
    async useICash(userNo: number, amount: number) {
        const icash = await this.icashRepo.findOneOrFail({ where: { userNo }, lock: { mode: 'pessimistic_write' } });
        await this.icashRepo.update(icash.no, { icash: icash.icash - amount });
    }

    @Transactional({ isolationLevel: IsolationLevel.REPEATABLE_READ })
    async refundICash(userNo: number, amount: number) {
        const icash = await this.icashRepo.findOneOrFail({ where: { userNo }, lock: { mode: 'pessimistic_write' } });
        await this.icashRepo.update(icash.no, { icash: icash.icash + amount });
    }
}


//test code
it.only('REPEATABLE READ:: LOST UPDATED WITH BUSINESS LOGIC', async () => {
    await Promise.all([iCashService.useICash(1, 10000), iCashService.refundICash(1, 20000)]);
    const result = await iCashService.getICash(1);

    expect(result!.icash).toBe(20000);
});

 

 

 

하지만 이런 방식에도 문제점이 없지는 않다. 데이터를 읽는 시점에 Lock을 획득했기 때문에 동시성을 떨어뜨릴 수 있다. 두 트랜잭션 모두 동시에 Lock을 획득했다고 가정해보자. 결국 쓰기 작업에서 타임아웃 등이 발생할 수도 있다. 그렇기 때문에 대기 시간을 관리하여야 한다. wait(nowait) 옵션을 활용하여 락 대기 시간을 조절하지 않으면, 락 대기 시간이 길어질 경우 시스템 성능에 영향을 미칠 수 있다.

 

 

 

 

 

 

Write Skew

Write Skew은 두 트랜잭션이 동일한 데이터를 읽지만 커밋된 데이터가 일관적이지 않은 것을 말한다.

 

it('REPEATABLE READ:: Write Skew - Event Registration', async () => {
    // 초기 데이터: 현재 99명 등록
    await eventRepo.save({
        eventId: 1,
        maxParticipants: 100,
        currentParticipants: 99
    });

    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();

    await runnerA.startTransaction('REPEATABLE READ');
    await runnerB.startTransaction('REPEATABLE READ');

    // 두 트랜잭션이 동시에 현재 참가자 수를 확인
    const eventA = await runnerA.manager.findOne(EventEntity, { 
        where: { eventId: 1 } 
    }); // 99명 읽음
    const eventB = await runnerB.manager.findOne(EventEntity, { 
        where: { eventId: 1 } 
    }); // 99명 읽음

    // 각 트랜잭션이 독립적으로 참가 가능 여부 확인
    if (eventA.currentParticipants < eventA.maxParticipants) {
        // 참가자 A 등록
        await runnerA.manager.insert(ParticipantEntity, { 
            eventId: 1, 
            userId: 'userA' 
        });
        await runnerA.manager.update(EventEntity, 
            { eventId: 1 }, 
            { currentParticipants: eventA.currentParticipants + 1 }
        );
    }

    if (eventB.currentParticipants < eventB.maxParticipants) {
        // 참가자 B 등록
        await runnerB.manager.insert(ParticipantEntity, { 
            eventId: 1, 
            userId: 'userB' 
        });
        await runnerB.manager.update(EventEntity, 
            { eventId: 1 }, 
            { currentParticipants: eventB.currentParticipants + 1 }
        );
    }

    await runnerA.commitTransaction();
    await runnerB.commitTransaction();

    const result = await eventRepo.findOne({ 
        where: { eventId: 1 } 
    });
    
    // Write Skew: 101명이 등록됨 (제한 100명 초과)
    expect(result.currentParticipants).toBe(101);
});

 

 

위와 같은 선착순 이벤트 시나리오에서, 100명의 정원이 있다. 두 트랜잭션에서 99라는 같은 데이터를 읽었고, 두 트랜잭션은 아직 신청이 가능하다고 판단했다. 그래서 각자 다른 레코드를 추가하여 100명 제한이 초과되어버렸다. 이는 비즈니스 규칙을 위반하는 심각한 문제가 되었다.

 

Write Skew의 경우에도, 여러 해결책이 있겠지만 데이터베이스 관점에서는 SERIALIZABLE 격리 수준을 사용하거나, 비관적 잠금과 같은 Locking Reads를 사용하는 방법으로 해결할 수 있다. 위의 비관적 잠금 예시와 동일하니 예제는 생략하도록 하자.

 

 

 

 

 

정리

Lost Update는 Write Skew의 부분집합이겠구나, 라는 생각을 하면서 차이점들을 정리해보았다.

  • Lost Update: 단일 레코드에서 발생하며 단순한 데이터 덮어쓰기 현상
  • Write Skew: 여러 레코드 또는 관련 데이터에 발생할 수 있으며 비즈니스 규칙이나 데이터 정합성을 위반한다.

 

 

동시성을 향상시키면서 데이터에도 문제가 생기지 않도록 비즈니스 로직을 구현할 때 생각을 많이 해야할 것 같다. 성능을 버리고 안정성에 몰빵하는 SERIALIZABLE부터 DB 레벨에서의 락을 활용하거나 Redis 등으로 동시성을 제어하는 등 구현하고자 하는 상황에 맞는 기술을 선택하는 것이 중요해 보인다.

 

 

 

 

 

 

 

 

 

참조

https://stackoverflow.com/questions/27826714/lost-update-vs-write-skew

https://www.cockroachlabs.com/blog/what-write-skew-looks-like/

https://dev.mysql.com/doc/refman/8.4/en/innodb-locking-reads.html

https://www.geeksforgeeks.org/transaction-isolation-levels-dbms/

 

 

 

 

 

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

[데이터베이스] MVCC(다중 버전 동시성 제어 - Multi Version Concurrency Control)

Tech/데이터베이스 2024. 12. 2. 22:47
728x90
728x90

 

동시성 제어(Concurrency Control)

DBMS에서 동시성 제어는 동시에 데이터에 접근하는 여러 사용자, 즉 여러 트랜잭션의 상호작용에서 트랜잭션의 isolation을 보장하고 일관성과 무결성을 유지할 수 있도록 하는 목적으로 사용되는 기술이다.

 

 

이러한 동시성 제어를 하는 대표적인 방식 중 가장 대표적인 Lock을 간단하게 알아보자.

 

 

공유 잠금(읽기 잠금, shared lock)이나 배타적 잠금(쓰기 잠금, exclusive lock)을 통해 Lock을 획득한 후 트랜잭션 내부의 작업을 수행하는 방식이다. (read로도 쓰기 잠금을 획득할 수 있다)  다른 트랜잭션은 이전 트랜잭션에서 Lock을 반환해야 작업이 수행이 가능하다는 의미이다.

 

 

 

 

이는 곧 SERIALIZABLE하다는 의미이며, 읽기 작업과 쓰기 작업이 서로 방해를 일으키기 때문에 병목 지점이 발생하며 데드락과 같은 동시성 문제가 발생할 수도 있다.

 

 

동시성을 제어하는 이유는 DML의 데이터 무결성을 보장하면서, 트랜잭션의 수를 최대화하는데 있다. 하지만 Lock을 사용한 동시성 제어에는 SERIALIZABLE하다는 특성 때문에 Lock이 커밋/롤백될 때까지 기다려야 한다. 이로 인해 동시 요청 처리 속도가 상당히 떨어지게 된다. 이를 해결하기 위해 등장한 방식이 MVCC이다.

 

 

 

 

MVCC(다중 버전 동시성 제어 - Multi Version Concurrency Control)

MVCC는 Lock과 같이 동시성을 제어하기 위해 사용하는 방법 중 하나이다.

MVCC는 쓰기 작업이 진행중인 레코드에 대해 원본과 변경 중인 데이터를 동시에 유지하는 방식이다. 원본 데이터에 대한  스냅샷(Snapshot)을 백업하여 보관한다. 이 스냅샷을 이용해 하나의 레코드에 대해 여러 버전을 관리하며, 데이터에 대한 변경 사항이 반영되기 전까지 다른 사용자가 변경 사항을 볼 수 없도록 보장한다. 

 

 

 

 

 

 

 

MySQL에서는 Undo Log라는 롤백 세그먼트(백업 공간)을 통해 스냅샷을 구현한다. 데이터 변경 요청이 들어오면 변경된 레코드의 이전 정보를 Undo Log에 저장한다. 이 롤백 세그먼트를 통해 트랜잭션 롤백에 필요한 실행 취소 작업을 수행한다. 마찬가지로 변경 사항이 반영되기 전에 데이터를 읽더라도 이 Undo Log를 활용하여 일관된 읽기(Consistent Read)를 수행한다.

 

 

이러한 MVCC는 Lock을 필요로 하지 않기 때문에 일반적인 RDBMS보다 매우 빠르게 작동한다. 또한 롤백 세그먼트를 활용해 데이터를 읽기 시작할 때 누군가 데이터를 변경하더라도 영향을 받지 않는다. 하지만 메모리 영역에 사용하지 않는 공간이 계속 늘어나게 되므로 데이터를 정리하는 작업이 필요하다. 하나의 레코드, 데이터에 대한 여러 버전이 생길 수 있기 때문에 데이터 버전 충돌 시 애플리케이션 영역에서 해결해야한다.

 

 

 

 

 

 

 

 

 

참조

https://dev.mysql.com/doc/refman/8.4/en/innodb-multi-versioning.html

https://www.youtube.com/watch?v=0PScmeO3Fig&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=18

 

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

[MySQL] 트랜잭션 격리수준(isolation level)과 이상현상 (with 테스트 코드)

Tech/데이터베이스 2024. 11. 27. 14:56
728x90
728x90

기억에 오래남고 이해하기 쉽게 현재 조직의 웨딩 도메인의 적립금을 예시로 간단한 엔터티 설계와 더불어 테스트 코드를 작성하여 각 격리수준과 이에 따른 이상현상을 정리해보았다. 개념들은 MySQL의 공식문서를 활용하여 정리하였고, AUTO_COMMIT은 FALSE를 가정하고 예제들을 작성하였다.
 

(예제에 필요한 기본적인 엔터티와 데이터 세팅은 아래를 참조)

 

CREATE TABLE icash (
    no INT UNSIGNED AUTO_INCREMENT PRIMARY KEY,
    user_no INT UNSIGNED UNIQUE NOT NULL,
    icash INT UNSIGNED DEFAULT 0 NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
    updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP NOT NULL
)


CREATE TABLE icash_transaction (
    no INT UNSIGNED AUTO_INCREMENT PRIMARY KEY,
    icash_no INT UNSIGNED NOT NULL,
    amount INT UNSIGNED NOT NULL,
    type ENUM('GRANT', 'USE', 'REFUND') NOT NULL,
    referenced_transaction_no INT NULL COMMENT '환불 시 트랜잭션 번호',
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
    INDEX idx_icash_no (icash_no),
    INDEX idx_type (type)
)


CREATE TABLE user (
    no INT UNSIGNED AUTO_INCREMENT PRIMARY KEY,
    id VARCHAR(100) NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL
)

 
 

icash
icash_transaction

 
 
 
 

트랜잭션 격리 수준(Isloation Level)

트랜잭션의 격리(ACID의 I)는 여러 트랜잭션이 동시에 데이터를 변경하는 등의 쿼리를 수행할 때 다른 트랜잭션의 작업이 끼어들지 못하도록 보장하며, Lock을 통해 다른 트랜잭션이 접근하지 못하도록 격리할 수 있지만, 잘못 사용하게 되면 교착 상태인 데드락(DeadLock)에 빠질 수 있다.
 
트랜잭션의 격리 수준은 트랜잭션의 격리를 어디까지 허용할 것인지 설정하는 것이다. 설정한 격리 수준에 따라 여러 트랜잭션이 동시에 처리될 때, 다른 트랜잭션에서 데이터를 변경하거나 조회하는 데이터를 볼 수 있게 허용할 수 있다.

  • SERIALIZABLE
  • REPEATABLE READ
  • READ COMMITTED
  • READ UNCOMMITTED
1. 우리는 트랜잭션을 관리해야하기 때문에 아래의 예제들에서는 AUTO_COMMIT이 FALSE인 상황만을 다룬다.
2. InnoDB의 기본값은 REPEATABLE_READ이다.
3. 격리 수준 별 이상 현상은 아래 격리 수준이 위의 격리 수준의 이상 현상을 포함하고 있다.

 
 
 
 
 
 
 

SERIALIZABLE

SERIALIZABLE은 가장 엄격한 격리수준으로, 트랜잭션을 직렬화된 순서와 동일하도록 보장한다. REPEATABLE READ와 유사하지만, 모든 SELECT문을 SELECT ... FOR SHARE로 간한다. 다시 말해 모든 조회에도 넥스트 키 락(Next-Key Lock)이 읽기 잠금(Locking Reads)으로 걸린다는 의미이고 이는 곧 조회 조건에 따라 인덱스 레코드와, 레코드 간의 간격(GAP)에 대해 읽기 잠금을 설정한다는 뜻이다.
 

넥스트 키 락(Next-Key Lock)
조건에 일치하는 인덱스 레코드에 락을 설정하며, 해당 레코드와 연관된 레코드 간의 간격(GAP)에도 잠금을 걸어 다른 트랜잭션이 GAP 내에서 새로운 데이터를 삽입하거나 수정하지 못하도록 방지한다.
SELECT ... FOR SHARE
읽은 행에 공유 모드 잠금(SHARED LOCK)을 설정한다. 다른 트랜잭션이 행을 읽을 수는 있지만, 커밋될 때 까지 변경할 수 없다. 커밋하지 않은 다른 트랜잭션에 의해 레코드가 변경된 경우, 쿼리는 트랜잭션이 끝날 때 까지 기다렸다가 최신 값을 조회한다.
읽기 잠금(Locking Reads)
InnoDB 테이블에 대해 잠금 작업을 수행하는 SELECT문으로, 트랜잭션의 격리 수준에 따라 데드락이 발생할 가능성이 있다.
MySQL의 락 매커니즘
 - MySQL에서는 테이블의 레코드가 아닌, 인덱스의 레코드를 잠근다.
 - 락이 걸리는 인덱스는 클러스터 인덱스 및 논클러스터 인덱스를 모두 포함한다.
 - 만약 PK가 없는 테이블이라면 내부적으로 자동 생성되는 PK를 이용하여 설정한다.
 - 테이블에 적절한 인덱스가 없다면, 풀 스캔을 통해 참조되는 모든 레코드에 락을 걸 수 있기 때문에 적절한 인덱스를 설정하여 성능 저하를 고려하여 적절한 인덱스를 설정해야 한다.

 
 
이를 통해 다른 트랜잭션에서 해당 레코드나 갭에 대해 절대 쓰기 작업을 할 수 없다. 동시 접근을 차단하여 부정합 문제를 절대 발생시키지 않는다. 가장 안전함과 동시에 가장 성능이 떨어져 데드락에 빠지기 쉽다.
 

1. 교착 상태(DEADLOCK)

테스트 코드를 통해 SERIALIZABLE을 구현해보고, 데드락을 발생시켜보았다.

it('SERIALIZABLE:: DEAD LOCK', async () => {
    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();

    let deadLock = false;

    try {
        // 트랜잭션 A 시작
        await runnerA.startTransaction('SERIALIZABLE');
        const repoA = runnerA.manager.getRepository(ICashEntity);
        // 트랜잭션 A에서 no = 1에 Lock
        await repoA.findOne({ where: { no: 1 } });

        // 트랜잭션 B 시작
        await runnerB.startTransaction('SERIALIZABLE');
        const repoB = runnerB.manager.getRepository(ICashEntity);
        // 트랜잭션 B에서 no = 2에 Lock
        await repoB.findOne({ where: { no: 2 } });

        // 서로 다른 트랜잭션에서 락을 건 레코드에 쓰기 작업 요청
        await Promise.all([
        	repoA.update({ no: 2 }, { icash: 3000 }),
            repoB.update({ no: 1 }, { icash: 2000 })
        ]);
    } catch (e: any) {
        console.error(e);
        if (e.code == 'ER_LOCK_DEADLOCK') {
            deadLock = true;
        }
    } finally {
        // 트랜잭션 정리
        if (runnerA.isTransactionActive) await runnerA.rollbackTransaction();
        if (runnerB.isTransactionActive) await runnerB.rollbackTransaction();
    }

    // 데드락 발생 여부 검증
    expect(deadLock).toBe(true);
}, 10000);

 
 

1. 조회를 통한 읽기 잠금 발생

await runnerA.startTransaction('SERIALIZABLE');
const repoA = runnerA.manager.getRepository(ICashEntity);
// 트랜잭션 A에서 no = 1에 Lock
await repoA.findOne({ where: { no: 1 } });

// 트랜잭션 B 시작
await runnerB.startTransaction('SERIALIZABLE');
const repoB = runnerB.manager.getRepository(ICashEntity);
// 트랜잭션 B에서 no = 2에 Lock
await repoB.findOne({ where: { no: 2 } });

 
우선, A와 B 트랜잭션에서, 각각 다른 레코드를 조회한다.
 
위에서 언급한 것 처럼 SERIALIZABLE에서는 단순한 SELECT문도 SELECT ... FOR SHARE로 간주된다.
때문에 트랜잭션 A가 no = 1에 대해 SELECT를 실행하면, 해당 레코드에 대해 읽기 잠금이 발생하며 동일하게 트랜잭션 B가 no = 2에 대해 읽기 잠금을 발생시킨다.
 

 
이 상황에서는, 두 트랜잭션이 서로 다른 레코드에 대해 잠금을 걸기 때문에, 충돌이 발생하지 않는다. 위의 그림처럼, 서로 다른 레코드에 락을 걸게 된다. 만약 같은 레코드를 조회했더라도, 읽기 잠금은 참조(읽기)가 가능하기 때문에 아무런 이상현상이 발생하지 않는다.
 
 
 

2. 쓰기(UPDATE) 발생

// 서로 다른 트랜잭션에서 락을 건 레코드에 쓰기 작업 요청
await Promise.all([
    repoA.update({ no: 2 }, { icash: 3000 }),
    repoB.update({ no: 1 }, { icash: 2000 })
]);

 
이제, 서로 다른 트랜잭션에서 락을 획득한 레코드에 대해 업데이트해보자.
 

 
트랜잭션 A는, B가 획득한 자원에 대해, 트랜잭션 B는 A가 획득한 자원에 대해 쓰기 작업을 시도한다.
각 트랜잭션들은 이미 하나의 락을 획득하였고, 다른 트랜잭션에서 할당된 자원에 대해 쓰기 작업을 시도하여 배타적 잠금을 요청하며 이전 락이 해제될 때 까지 기다리게 된다. 이로 인해 데드락이 발생하게 된다.
 
 
 

2. LOCK_WAIT_TIMEOUT

이번엔, 교착 상태는 아니지만 다른 상황을 만들어보았다.

it('SERIALIZABLE:: TIMEOUT', async () => {
    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();
    
    // InnoDB의 DEFAULT LOCK WAIT TIMEOUT = 50이기 때문에
    // 테스트를 위해 5초로 변경
    await runnerB.manager.query('SET SESSION innodb_lock_wait_timeout = 5');

    let timeout = false;

    try {
        // 트랜잭션 A 시작
        await runnerA.startTransaction('SERIALIZABLE');
        const repoA = runnerA.manager.getRepository(ICashEntity);
        // 트랜잭션 A에서 no = 1에 Lock
        await repoA.findOne({ where: { no: 1 } });

        await runnerB.startTransaction('SERIALIZABLE');
        const repoB = runnerB.manager.getRepository(ICashEntity);

		await repoB.update({ no: 1 }, { icash: 2000 });
    } catch (e: any) {
        if (e.code == 'ER_LOCK_WAIT_TIMEOUT') {
            timeout = true;
        }
    } finally {
        // 트랜잭션 정리
        if (runnerA.isTransactionActive) await runnerA.rollbackTransaction();
        if (runnerB.isTransactionActive) await runnerB.rollbackTransaction();
    }

    // 타임아웃 발생 여부 검증
    expect(timeout).toBe(true);
}, 10000);

 

// 트랜잭션 A 시작
await runnerA.startTransaction('SERIALIZABLE');
const repoA = runnerA.manager.getRepository(ICashEntity);
// 트랜잭션 A에서 no = 1에 Lock
await repoA.findOne({ where: { no: 1 } });

await runnerB.startTransaction('SERIALIZABLE');
const repoB = runnerB.manager.getRepository(ICashEntity);

await repoB.update({ no: 1 }, { icash: 2000 });

 
트랜잭션 A가 락을 획득한 레코드에 대해, B가 쓰기 작업을 시도하였다.

 
 
마찬가지로 트랜잭션 B는 트랜잭션 A가 커밋을 하기 전까지 기다리게 된다. 만약 설정된 LOCK_WAIT_TIME을 초과하게되면, LOCK_WAIT_TIMEOUT 에러가 발생하게 되고, 작업을 수행할 수 없다.
 
 
 

정리

SERIALIZABLE은 모든 SELECT에도 잠금을 발생시기 때문에 다른 트랜잭션에서 절대로 쓰기 작업을 수행할 수 없고 이전 트랜잭션에서 작업이 완료되기를 기다려야만 한다. 가장 안전할 것처럼 보이나, 작업이 오래 걸리는 트랜잭션이 겹겹이 쌓여 병목 현상이 발생하고, 원하는 작업이 수행되지 못하는 등 가장 성능이 떨어지기 때문에 극단적으로 안전한 작업이 아니라면 사용을 기피하는 것으로 알려져 있다.
 
 
 
 
 
 

REPEATABLE READ

REPEATABLE READ는 InnoDB의 기본 트랜잭션 격리 수준으로, 하나의 트랜잭션 내에서 같은 SELECT 결과가 항상 동일함을 보장한다. 이는 MVCC(Multi-Version Concurrency Control, 다중 버전 동시성 제어) 매커니즘에 의해 트랜잭션이 시작되면 그 시점의 스냅샷이 생성된다. 이후 해당 트랜잭션 내의 SELECT는 이 스냅샷을 기반으로 데이터를 읽게 된다.
 

 
 
 
REPEATABLE READ는 트랜잭션의 실행 순서를 참고하여(트랜잭션 번호) 자신보다 먼저 실행된 트랜잭션의 데이터만을 조회한다. 이 때 테이블에 자신보다 이후에 실행된 트랜잭션의 데이터가 존재할 경우 백업된 언두 로그를 활용하여 데이터를 조회한다.
 
따라서 위 그림과 같이, 트랜잭션 A보다 늦게 시작된 트랜잭션에서 데이터를 변경하더라도 조회 결과는 동일하다. 즉 REPEATABLE READ에서는 다른 트랜잭션에서 데이터를 변경하더라도 일관된 읽기(Consistent Read) 결과를 보장한다. 아래 테스트 결과를 보면, 일관된 읽기가 보장됨을 알 수 있다.
 

it.only('REPEATABLE READ:: 데이터 변경 시 팬텀리드가 발생하지 않는다.', async () => {
    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();

    // 트랜잭션 A 시작
    await runnerA.startTransaction('REPEATABLE READ');
    const repoA = runnerA.manager.getRepository(ICashEntity);

    // 트랜잭션 A에서 SELECT
    const beforeTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

    // 트랜잭션 B 시작
    await runnerB.startTransaction('REPEATABLE READ');
    const repoB = runnerB.manager.getRepository(ICashEntity);

    // 팬텀리드를 발생시키기 위해 update
    await repoB.update({ no: 10 }, { icash: 30000 });
    // 트랜잭션 B 커밋
    await runnerB.commitTransaction();

    const afterTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

    expect(beforeTrxBCommited.length).toBe(10);
    //A보다 뒤에 실행된 트랜잭션 B가 변경한 레코드는 무시한다.
    expect(afterTrxBCommited.length).toBe(10);
    expect(afterTrxBCommited[9].icash).toBe(38120);
});

 

 
 
 
그러나 REPEATABLE READ 수준에서도 특정 조건에서 데이터 부정합, 팬텀 리드와 같은 이상 현상이 발생할 수 있다. 위에서 강조했듯이 REPEATABLE READ는 데이터를 변경할 때 일관된 읽기를 보장한다고 했다. 즉 새로운 레코드가 추가될 때는 아래 그림처럼 팬텀 리드가 발생할 수 있다.
 

 
그럼 정말로 새로운 레코드가 추가되면 팬텀 리드가 발생할까? 아래 테스트를 보자.
 

it.only('REPEATABLE READ:: 팬텀 리드가 발생할 것이다.', async () => {
    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();

    // 트랜잭션 A 시작
    await runnerA.startTransaction('REPEATABLE READ');
    const repoA = runnerA.manager.getRepository(ICashEntity);

    // 트랜잭션 A에서 SELECT
    const beforeTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

    // 트랜잭션 B 시작
    await runnerB.startTransaction('REPEATABLE READ');
    const repoB = runnerB.manager.getRepository(ICashEntity);

    // 팬텀리드를 발생시키기 위해 INSERT
    await repoB.save({ userNo: 11, icash: 1000 });
    // 트랜잭션 B 커밋
    await runnerB.commitTransaction();

    const afterTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

    expect(beforeTrxBCommited.length).toBe(10);
    expect(afterTrxBCommited.length).toBe(11);
});

 

 
팬텀 리드가 발생할 것으로 생각되는 상황을 가정하고, 테스트를 돌려보면 테스트는 실패한다. MySQL에서는 레코드가 추가되는 상황에서도 MVCC 덕분에 팬텀 리드가 발생하지 않는다. 위에서 언급했듯, MVCC를 사용하여 동일 트랜잭션 내에서 같은 데이터를 읽을 때 언두 로그 기반의 일관된 스냅샷을 제공하기 때문이다. 그렇다면 언제 팬텀리드가 발생할까? 여러 테스트를 작성하여 팬텀 리드가 발생하는 상황을 알아보려고 했다.
 

describe('REPETABLE READ', () => {
    it('REPEATABLE READ:: 일반 조회 - 팬텀 리드가 발생하지 않는다.', async () => {
        runnerA = dataSource.createQueryRunner();
        runnerB = dataSource.createQueryRunner();

        // 트랜잭션 A 시작
        await runnerA.startTransaction('REPEATABLE READ');
        const repoA = runnerA.manager.getRepository(ICashEntity);

        // 트랜잭션 A에서 SELECT
        const beforeTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

        // 트랜잭션 B 시작
        await runnerB.startTransaction('REPEATABLE READ');
        const repoB = runnerB.manager.getRepository(ICashEntity);

        // 팬텀리드를 발생시키기 위해 INSERT
        await repoB.save({ userNo: 11, icash: 1000 });
        // 트랜잭션 B 커밋
        await runnerB.commitTransaction();

        const afterTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

        expect(beforeTrxBCommited.length).toBe(10);
        //A보다 뒤에 실행된 트랜잭션 B가 추가한 레코드는 무시한다.
        expect(afterTrxBCommited.length).toBe(10);
    });

    it('REPEATABLE READ:: 배타적 잠금을 통한 조회 - 팬텀리드가 발생하지 않는다.', async () => {
        runnerA = dataSource.createQueryRunner();
        runnerB = dataSource.createQueryRunner();
        await runnerB.manager.query('SET SESSION innodb_lock_wait_timeout = 3');

        let timeout: boolean = false;

        try {
            // 트랜잭션 A 시작
            await runnerA.startTransaction('REPEATABLE READ');
            const repoA = runnerA.manager.getRepository(ICashEntity);

            // 트랜잭션 A에서 SELECT (배타적 잠금 발생)
            const beforeTrxBCommited = await repoA
                .createQueryBuilder()
                .where('no < :no', { no: 15 })
                .setLock('pessimistic_write')
                .getMany();

            // 트랜잭션 B 시작
            await runnerB.startTransaction('REPEATABLE READ');
            const repoB = runnerB.manager.getRepository(ICashEntity);

            // 팬텀리드를 발생시키기 위해 INSERT
            await repoB.save({ userNo: 11, icash: 1000 });
            // 트랜잭션 B 커밋
            await runnerB.commitTransaction();

            const afterTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

            await runnerA.commitTransaction();

            //팬텀리드를 테스트하려고 하지만 타임아웃이 발생할 것이다.
            expect(beforeTrxBCommited.length).toBe(10);
            expect(afterTrxBCommited.length).toBe(11);
        } catch (e: any) {
            if (e.code == 'ER_LOCK_WAIT_TIMEOUT') {
                timeout = true;
            }
        }

        expect(timeout).toBe(true);
    }, 10000);

    it('REPEATABLE READ:: 읽기 잠금을 통한 조회 - 팬텀리드가 발생하지 않는다.', async () => {
        runnerA = dataSource.createQueryRunner();
        runnerB = dataSource.createQueryRunner();
        await runnerB.manager.query('SET SESSION innodb_lock_wait_timeout = 3');

        let timeout: boolean = false;

        try {
            // 트랜잭션 A 시작
            await runnerA.startTransaction('REPEATABLE READ');
            const repoA = runnerA.manager.getRepository(ICashEntity);

            // 트랜잭션 A에서 SELECT (읽기 잠금 발생)
            const beforeTrxBCommited = await repoA
                .createQueryBuilder()
                .where('no < :no', { no: 15 })
                .setLock('pessimistic_read')
                .getMany();

            // 트랜잭션 B 시작
            await runnerB.startTransaction('REPEATABLE READ');
            const repoB = runnerB.manager.getRepository(ICashEntity);

            // 팬텀리드를 발생시키기 위해 INSERT
            await repoB.save({ userNo: 11, icash: 1000 });
            // 트랜잭션 B 커밋
            await runnerB.commitTransaction();

            const afterTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

            await runnerA.commitTransaction();

            expect(beforeTrxBCommited.length).toBe(10);
            expect(afterTrxBCommited.length).toBe(11);
        } catch (e: any) {
            if (e.code == 'ER_LOCK_WAIT_TIMEOUT') {
                timeout = true;
            }
        }
        expect(timeout).toBe(true);
    }, 10000);

    it('REPEATABLE READ:: 쓰기 이후 배타적 잠금으로 조회 - 팬텀리드가 발생한다.', async () => {
        runnerA = dataSource.createQueryRunner();
        runnerB = dataSource.createQueryRunner();

        // 트랜잭션 A 시작
        await runnerA.startTransaction('REPEATABLE READ');
        const repoA = runnerA.manager.getRepository(ICashEntity);

        // 트랜잭션 A에서 SELECT (배타적 잠금 발생)
        const beforeTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

        // 트랜잭션 B 시작
        await runnerB.startTransaction('REPEATABLE READ');
        const repoB = runnerB.manager.getRepository(ICashEntity);

        // 팬텀리드를 발생시키기 위해 INSERT
        await repoB.save({ userNo: 11, icash: 1000 });
        // 트랜잭션 B 커밋
        await runnerB.commitTransaction();

        const afterTrxBCommited = await repoA
            .createQueryBuilder()
            .where('no < :no', { no: 15 })
            .setLock('pessimistic_write')
            .getMany();

        await runnerA.commitTransaction();

        expect(beforeTrxBCommited.length).toBe(10);
        expect(afterTrxBCommited.length).toBe(11);
    });

    it('REPEATABLE READ:: 쓰기 이후 읽기 잠금으로 조회 - 팬텀리드가 발생한다.', async () => {
        runnerA = dataSource.createQueryRunner();
        runnerB = dataSource.createQueryRunner();

        // 트랜잭션 A 시작
        await runnerA.startTransaction('REPEATABLE READ');
        const repoA = runnerA.manager.getRepository(ICashEntity);

        // 트랜잭션 A에서 SELECT
        const beforeTrxBCommited = await repoA.find({ where: { no: LessThan(15) } });

        // 트랜잭션 B 시작
        await runnerB.startTransaction('REPEATABLE READ');
        const repoB = runnerB.manager.getRepository(ICashEntity);

        // 팬텀리드를 발생시키기 위해 INSERT
        await repoB.save({ userNo: 11, icash: 1000 });
        // 트랜잭션 B 커밋
        await runnerB.commitTransaction();

            // 트랜잭션 B에서 읽기잠금으로 조회
        const afterTrxBCommited = await repoA
            .createQueryBuilder()
            .where('no < :no', { no: 15 })
            .setLock('pessimistic_read')
            .getMany();

        await runnerA.commitTransaction();

        expect(beforeTrxBCommited.length).toBe(10);
        expect(afterTrxBCommited.length).toBe(11);
    });
});

 

 
 
테스트 케이스의 결과를 통해 REPEATABLE READ에서의 팬텀 리드 발생 상황을 정리해볼 수 있었다.

  • SELECT > DML > SELECT : 팬텀리드가 발생하지 않음
  • SELECT FOR UPDATE(배타적 잠금) > DML > SELECT : 팬텀리드가 발생하지 않음
  • SELECT FOR SHARE(읽기 잠금) > DML > SELECT : 팬텀 리드가 발생하지 않음
  • SELECT > DML > SELECT FOR UPDATE(배타적 잠금) : 팬텀리드 발생
  • SELECT > DML > SELECT FOR SHARE(읽기 잠금) : 팬텀 리드 발생

 
테스트 결과를 보면, 2번 3번 테스트가 유독 긴 테스트 시간이 소요되었다. 타임아웃이 발생한 것이다.
위 테스트의 경우에 no < 15인 인덱스 레코드에 대해 조회와 동시에 잠금을 걸었기 때문에 다른 트랜잭션에서는 쓰기 작업을 위해 해당 트랜잭션에서 잠금을 해제하여야 한다. 즉, 트랜잭션 A가 해당 레코드 범위에 대해 잠금을 해제할 때 까지 트랜잭션 B는 대기상태에 들어가고, 설정해 둔 3초의 시간이 지나 타임아웃이 발생한 것이다.
 
MySQL에서 REPEATABLE READ 수준에서의 팬텀 리드는 데이터가 변경된 후 잠금을 사용하는 조회 상황에서는 팬텀 리드가 발생할 수 있다. 스냅샷이 아닌 실제 테이블 상태를 참조하기 때문에 다른 트랜잭션에서 추가한 새로운 행이 보이게 되는 것이다. 마찬가지로, 트랜잭션 없이 실행되는 SELECT에서도 팬텀 리드가 발생할 수 있다.
 
 
 

정리

MySQL의 REPEATABLE READ 수준에서 MVCC를 통해 한 트랜잭션 내에서 거의 모든 상황에 일관된 읽기를 수행할 수 있고 테이블에 잠금을 설정하지 않기 때문에 트랜잭션에서 일관된 읽기를 수행하는 동안 다른 트랜잭션에서 해당 테이블을 자유롭게 수정할 수 있다.
 
 
 
 
 
 
 

READ COMMITED

커밋된 데이터만 조회할 수 있는 격리수준이다. 아래는 테스트 코드와 이를 풀어낸 그림으로, 트랜잭션 A에서 업데이트 후 커밋하기 전의 조회 결과와 커밋한 후의 조회 결과가 다름을 보여준다.
 

it('READ COMMITTED:: 커밋된 데이터만 조회가 가능하다.', async () => {
    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();

    // 트랜잭션 A 시작
    await runnerA.startTransaction('READ COMMITTED');
    const repoA = runnerA.manager.getRepository(ICashEntity);

    // 트랜잭션 A에서 쓰기 작업
    await repoA.update({ no: 1 }, { icash: 10 });

    // 트랜잭션 B 시작
    await runnerB.startTransaction('READ COMMITTED');
    const repoB = runnerB.manager.getRepository(ICashEntity);

    // 트랜잭션 B에서 SELECT
    const beforeTrxACommited = await repoB.findOne({ where: { no: 1 } });

    // 트랜잭션 A 커밋
    await runnerA.commitTransaction();

    // 트랜잭션 B에서 SELECT
    const afterTrxACommited = await repoB.findOne({ where: { no: 1 } });

    expect(beforeTrxACommited!.icash).toBe(1000);
    expect(afterTrxACommited!.icash).toBe(10);
});

 
 

 
 
이 결과는 트랜잭션 B가 먼저 시작되더라도 동일하다. 다른 트랜잭션에서 커밋이 되었는지 안되었는지, 커밋 결과로 레코드가 업데이트 되었는지가 중요하다. 다른 트랜잭션에서의 커밋 여부에 따라 조회 결과가 계속해서 변할 수 있다.
 
이처럼 동일한 조건으로 데이터를 조회했음에도 다른 트랜잭션의 커밋 여부에 따라 결과가 달라지는 이상 현상을 반복 읽기 불가능
(Non-Repeatable Read)라고 한다. 예상 가능하겠지만, READ COMMITTED 수준에서는, 트랜잭션 내에서 실행되는 조회와 트랜잭션 밖에서 실행되는 조회의 차이가 거의 없다.
 
 
 
 
 

READ UNCOMMITTED

READ UNCOMMITTED는 트랜잭션 처리가 완료되지 않은 데이터까지도 읽을 수 있는 격리 수준이다. READ COMMITTED와 같은 예시에서, READ UNCOMMITTED 수준에서는 반영이 되지 않은 데이터에 접근할 수 있음을 알 수 있다.

it('READ UNCOMMITTED:: 커밋되지 않은 데이터도 조회가 가능하다.', async () => {
    runnerA = dataSource.createQueryRunner();
    runnerB = dataSource.createQueryRunner();

    // 트랜잭션 A 시작
    await runnerA.startTransaction('READ UNCOMMITTED');
    const repoA = runnerA.manager.getRepository(ICashEntity);

    // 트랜잭션 A에서 쓰기 작업
    await repoA.update({ no: 1 }, { icash: 10 });

    // 트랜잭션 B 시작
    await runnerB.startTransaction('READ UNCOMMITTED');
    const repoB = runnerB.manager.getRepository(ICashEntity);

    // 트랜잭션 B에서 SELECT
    const beforeTrxACommited = await repoB.findOne({ where: { no: 1 } });

    // 트랜잭션 A 커밋
    await runnerA.commitTransaction();

    // 트랜잭션 B에서 SELECT
    const afterTrxACommited = await repoB.findOne({ where: { no: 1 } });

    expect(beforeTrxACommited!.icash).toBe(10);
    expect(afterTrxACommited!.icash).toBe(10);
});

 

 
 
 
이렇게, 작업이 완료되지 않았는데도 데이터를 읽을 수 있는 이상 현상을 Dirty Read라고 한다. 커밋이나 롤백되지 않은, 작업이 완료되지 않은 결과를 읽고 다른 작업을 수행한다. 특히 롤백 상황에서, 롤백 전의 데이터로 무언가 작업이 일어날 우려가 있기 때문에
READ UNCOMMITTED는 데이터 정합성에 문제가 많은 격리 수준이다.
 
 
 
 
 
 
 

참조

https://dev.mysql.com/doc/refman/8.4/en/innodb-storage-engine.html
https://dev.mysql.com/doc/refman/8.4/en/innodb-transaction-isolation-levels.html
https://dev.mysql.com/doc/refman/8.4/en/glossary.html
https://dev.mysql.com/doc/refman/8.4/en/innodb-consistent-read.html
https://dev.mysql.com/doc/refman/8.4/en/innodb-next-key-locking.html
https://mangkyu.tistory.com/
https://velog.io/@onejaejae/DB-MVCC
https://medium.com/daangn/mysql-cats-contention-aware-transaction-scheduling-71fe6956e87e
https://techblog.woowahan.com/2606/
https://www.youtube.com/watch?v=704qQs6KoUk
https://www.youtube.com/watch?v=4wGTavSyLxE&t=148s
 
 
 
 
 
 

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

typeORM을 사용하면서 왜 N+1 문제를 마주하지 못했을까?

Tech/NodeJS 2024. 8. 27. 17:37
728x90
728x90

 
ORM을 사용하다보면 N + 1 문제를 마주하곤 하는데, 특히 ORM의 Default Fetch Type설정이 Lazy일 경우 더 그렇다.
 
이제 막 typeORM을 사용해보고 있다고 하시는 분과 커피챗을 할 기회가 생겼는데 typeORM에서는 N + 1을 어떻게 해결하냐는 얘기가 나왔었다.
N + 1이 어떤 것인지는 알고 있었으나 나는 typeORM을 사용하면서 실제적으로 N + 1을 마주한 경험이 없다.
 
실제로 실무에서도 페이징을 위한 paginate 라이브러리 사용 시 Distinct로 클러스터 인덱스를 가져와서 리스트, 페이징에 총 세 번의 쿼리를 사용하는 경우를 제외하고는 본 적이 없다.
 
왜 그럴까 곰곰이 생각을 해봤다. 최근에 nest에서 graphQL을 사용하고자 했을 때에도 N + 1 문제를 마주했으며
그 때는 DataLoader로 해결했었다.
 

graphQL의 N + 1문제와 DataLoader

graphQL에 대해 알아보자 - 1 (with NestJS, typeORM)학습을 위해 생성한 예제 코드는 깃헙에 있습니다.(링크)  graphQLgraphQL은 기존 데이터로 쿼리를 실행하기 위한 API를 위한 쿼리 언어이자 런타임이다.

mag1c.tistory.com

 
 
마주하지 않는 문제더라도, 궁금증이 생겨서 직접 실험해보고 포스팅을 남기기로 했다.
 
 


 
 
 

import { UpdatableEntity } from 'src/abstract/base.entity';
import { Column, Entity, JoinColumn, ManyToOne, OneToMany } from 'typeorm';
import { Enrollment } from './enrollment.entity';
import { Teacher } from './teacher.entity';

@Entity('lecture', { database: 'test' })
export class Lecture extends UpdatableEntity {
  @Column('int', { name: 'teacher_id', nullable: false })
  teacherId!: number;
  
  @Column('varchar', { length: 100, unique: true, nullable: false })
  title!: string;
  
  @Column('text', { nullable: false })
  content!: string;
  
  @Column('int', { nullable: false })
  price!: number;
  
  @OneToMany(() => Enrollment, (enrollments) => enrollments.lecture)
  @JoinColumn({ referencedColumnName: 'enrollmentId' })
  enrollments?: Enrollment[];
  
  @ManyToOne(() => Teacher, (teacher) => teacher.lectures, { eager: true })
  @JoinColumn({ name: 'teacher_id', referencedColumnName: 'id' })
  teacher?: Teacher;
}

 
나는 엔터티의 관계 매핑을 할 때 RelationOptions에 loding (eager, lazy) 옵션을 따로 두지 않는다.
예를 들어 위와 같은 강의 엔터티가 있을 때 연관 관계가 있는 테이블이 있을 때, 따로 옵션 설정을 하지 않는다.
 
왜?
필요하면 relations을 명시해주거나, QueryBuilder로 JoinSelect을 하여 사용하기 때문이다.
알고보니 자연스러운 이 코드 작성 습관이 알아서 N + 1 문제를 직면하지 않도록 만들어 주었다. (좋은건지는 모르겠다.)

 
 
만약 위처럼 강의 도메인에서, 강사 명이 필요하거나 수강생 정보가 필요하다면 아래처럼 작성 할 것이다.

type TLectureList = Pick<Lecture, 'title' | 'content' | 'price' | 'teacher'>[];

//강의 리스트 반환.
async findLecturesWithTeachers(): Promise<TLectureList> {
    return await this.createQueryBuilder('l')
      .innerJoinAndSelect('l.teacher', 't')
      .select(['l.title, l.content, l.price', 't.name'])
      .getMany();
}

 
 
물론 아래처럼 Repository API의 find를 사용하여 relations을 명시해 줄 수 있다.
하지만 관계를 명시한 하위 테이블의 필드는 선택할 수 없다. 그렇기 때문에 개인적으로는 OverFetching 때문에 사용하지 않는 편이다.

//강의 리스트 반환.
async findLecturesWithTeachers(): Promise<TLectureList> {
    return await this.find({
      select: ['title', 'content', 'price'],
      relations: ['teacher'],
    });
}

 
 
 
정리해보면
 
1. RelationOptions의 Loding 설정을 따로 명시하지 않는다.
2. 쿼리 빌더를 주로 사용한다. (스칼라 서브쿼리나 인라인 뷰가 다수 들어가는 복잡한 쿼리는 raw query를 사용한다.)
 
이런 습관들 때문에 N + 1 문제를 인지하지 못하고 있었다.
 
 
typeORM의 Default Fetch Type을 알아보고자 공식문서를 뒤져봤지만 디폴트 타입에 대한 명시는 없었다.
Lazy Loding을 사용하고 싶으면 반드시 비동기처리를 하라는 주의사항 밖에 없었다.
 

/**
 * Describes all relation's options.
 */
export interface RelationOptions {
    //...생략...
    
    lazy?: boolean;
    eager?: boolean;
    
    //...생략...
}

 
코드를 열어보면,  둘 다 옵셔널인 것을 보아하니 default는 없는 것 같다. 실제로 확인해보기 위해 아래 코드를 돌려보았다.
 
 

async findLectures(): Promise<void> {
    const lecture = await this.lectureRepo.findOneBy({ id: 1 });
    console.log(lecture);
    console.log('Teacher: ', lecture?.teacher);
}

 
옵션이 없을 때는 1개의 쿼리를 실행했고
Lazy Loding이 적용되었을 때는 Teacher을 찾기 위한 N + 1 쿼리가 발생했다.
마지막으로 Eager Loding에서는 Lecture를 조회할 때 이미 Teacher가 같이 등장한다.
 
 
 


 
 
 

정리

1. typeORM에서 Lazy Loding은 프로미스 객체로 반환된다.

Note: if you came from other languages (Java, PHP, etc.) and are used to use lazy relations everywhere - be careful. Those languages aren't asynchronous and lazy loading is achieved different way, that's why you don't work with promises there. In JavaScript and Node.JS you have to use promises if you want to have lazy-loaded relations. This is non-standard technique and considered experimental in TypeORM.

 
공식문서에서 언급했듯이, 아래처럼 변경해주면 되겠다.

async findLectures(): Promise<void> {
    const lecture = await this.lectureRepo.findOneBy({ id: 1 });
    console.log(lecture);
    console.log('Teacher: ', await lecture?.teacher);
}

 
 
 

2. 현재의 습관

현재의 코드 습관들이 자연스레 OverFetching과 N + 1 문제를 피하고 있었다.
사내에서는 혼자 백엔드 개발을 하다보니 코드 레벨에서의 관점을 나눌 사람이 없었다.
외부로 눈을 돌려 typeORM을 사용하는 다른 분들과 커피챗을 통해 관련된 코드 습관들이 올바른 방향인지 점검할 필요는 있을 것 같다.

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

복합 인덱스로 쿼리 튜닝하기

Tech/트러블슈팅 2024. 7. 26. 16:30
728x90
728x90

[데이터베이스] 인덱스(index) 정리

인덱스   목차, 색인, 책갈피와 같은 기능을 하는 인덱스는, 데이터베이스 분야에서는 어떤 데이터를 검색할 때 속도를 높여주는 자료 구조로메모리 영역에 생성되는 일종의 책갈피이다.   

mag1c.tistory.com

 

위 글의 복합 인덱스를 통한 튜닝 부분을 따로 옮긴 포스팅입니다.

 
 


 
 
 
분명 일정한 기준이 있을 텐데 왜 얘기들이 조금씩 다른 것일까?
DB의 버전 때문일까 옵티마이저가 무조건적으로 100% 맞다는 보장이 없어서일까? 잘 모르겠다.
그래서 직접 쿼리 튜닝의 경험들을 복기하며 복합 인덱스를 생성할 때에는 어떤 순서로 인덱스를 구성해야 하는지 알아보았다.
 
 

 
서비스 내부에는 모든 유저의 장바구니(앞으로 견적함이라 부름)를 볼 수 있는 기능이 존재하는데 업종으로 필터링할 경우의 집계를 위한 쿼리의 일부이다.
(사진과 드레스를 선택했을 경우를 예시로 platform_A 테이블에 대한 인덱스 생성만 예시로 든다.)

SELECT cart_group_no
FROM platform_A.cart c
INNER JOIN service.product p
    ON p.no = c.product_no
WHERE p.category IN ("사진", "드레스")
    AND c.cart_group_no != 0
    AND c.option != 1;

 

 
 
COUNT(DISTINCT) 쿼리로 간단하게 카디널리티를 확인해 본 결과는 위와 같았고, 당연히 나는 아래와 같이 인덱스를 생성했다.

CREATE INDEX IDX_REALTIME_QUOTATION
ON platform_A (cart_group_no, product_no, option_product);

 
 

 

 

 

쿼리 실행 시간이 어느 정도 눈에 보이는 수치로 감소했다. 하지만 여전히 Fetch는 비슷했다.

 
 
인덱스 생성 전에는, 해당 테이블에서 풀스캔(ALL)을 했다. 전체 테이블 row를 스캔한 것으로 보인다.
인덱스 생성 후에는 INDEX RANGE SCAN을 통해 조회하였고 테이블 row의 스캔 개수도 20%가량 줄어들었다.
추측건대 fetch time이 개선되지 않은 이유는 스캔하는 row가 여전히 많기 때문이라고 판단했다.
 
쿼리에서는 조인을 먼저 수행하지만 쿼리 실행 계획을 보면 조인 시 인덱스를 효율적으로, 아니 전혀 사용하지 못하는 것처럼 보였다. 
 
왜 이런 결과가 나올까 생각해 보다가 쿼리 실행 순서를 바탕으로 인덱스 순서를 변경해 보았다.

CREATE INDEX IDX_REALTIME_QUOTATION
ON platform_A (product_no, cart_group_no, option_product);

 

 

p의 인덱스 길이는 category가 varchar(150)이기 때문인 것 같다

 
 
변경 후에도 결과가 다소 개선되었는데 Duration도 개선되었지만 Fetch Time이 대폭 개선되었음을 볼 수 있다. 실제로 스캔하는 row의 수가 100배 가까이 줄었기 때문이라고 유추해 볼 수 있었다. 추가로 c 테이블의 KEY LENGTH가 1이 줄었는데, 이 쿼리의 결과에서 option_product을 참조하지 않았다고 판단할 수 있다. (option_product는 tinyint이다)
 
카디널리티는 cart_group_no가 두 배 높았지만, 실제로 product_no를 앞에 사용해 줘야 올바르게 튜닝이 된 것을 확인할 수 있었다.
 

위 쿼리에 대해 모든 인덱스를 참조하게 되는데, 이런 인덱스를 커버링 인덱스라고 한다.

 
 
실제 쿼리를 튜닝하는 과정을 통해 카디널리티가 낮더라도 첫 번째 조건 절에서 사용된 컬럼을 인덱스 컬럼으로 사용하지 않는다면 올바르게 동작하지 않는다는 것을 알 수 있었다. 
 
정리하자면 선행 조건 컬럼은 반드시 인덱스 선행 컬럼이 되어야 하고, 다음과 같은 조건절이 있을 때 

WHERE col1 = ?
    AND col2 = ?
    AND col3 BETWEEN ? AND ?
    AND col4 = ?
    AND col5 = ?
CREATE INDEX ON IDX ON TB1 (col1, col2, col3, col4, col5);

 
 
인덱스를 위와 같이 생성했다면 col4, col5는 인덱스를 타지 않고 조건 필터링만 수행하게 되며 쿼리 실행 순서와 마찬가지로 WHERE 조건 절은 ORDER BY 컬럼보다 우선한다.
 

모든 인덱스를 참조하게 하고 싶다면 col1, col2, col4, col5, col3 순으로 생성해야 한다.

 
 
 
 
 

향로님 포스팅 일부 발췌

 
 
 
이왕이면 카디널리티도 위의 규칙을 지키면서 고려하면 좋다고 생각했지만, 카디널리티는 복합 인덱스에서 고려할 사항이 아니라는 자료도 있고 아예 선행 조건절이 일치한다면 후행 조건절에서는 순서가 유의미하지 않다는 글도 있다.
 
최근엔 이전과 같이 꼭 인덱스 순서와 조회 순서를 지킬 필요는 없는 것 같다. 인덱스 컬럼들이 조회 조건에 포함되어 있는지가 중요하고, 내가 사용하고 있는 데이터베이스 엔진에 맞게 인덱스를 활용하고 튜닝할 줄 아는 게 중요한 것 같다.
 
 
 

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

[알고리즘] 위상 정렬(Topology Sort)

Tech/알고리즘 2024. 7. 22. 22:42
728x90
728x90

 

위상 정렬(Topology Sort)

위키피디아: Topological sorting

 

 

위의 위키피디아 문서를 참조하면, 위상 정렬이란 정점의 선형 순서 지정을 통해 모든 방향 간선 uv에 대해 정점 u가 v보다 앞에 올 수 있게 정렬하기 위해 사용되는 알고리즘으로, 방향성 비순환 그래프 - DAG(Directed Acyclic Graph)에만 적용할 수 있다고 한다.

 

 

 

 

 

쉽게 말하자면 순서가 정해져 있는 작업을 차례로 수행해야할 때 순서를 결정해주는 알고리즘이고,

더 쉽게 말하자면, 순서를 찾아주는 알고리즘이다.

 

 

특징

나열한 정렬 순서만 두 가지 경우가 존재하고 추가로 여러 개의 답이 더 존재할 수 있다. 이처럼 위상 정렬은 여러 개의 답이 존재할 수 있다는 특징이 있다. 순회하는 방법이 한 가지보다 많을 수 있기 때문이다.

 

또한, 위에서 DAG에만 적용할 수 있다고 했다. 이 의미는, 시작점이 반드시 존재하는 사이클이 없는 그래프를 뜻한다. 즉 특정 정점 하나 이상은 반드시 가리키는 대상이 되어서는 안된다. 다시말해 진입 차수가 0이어야만 한다.

 

 

동작 과정

위상 정렬은 다음과 같은 과정을 통해 위상 정렬 가능 여부와, 위상 정렬의 결과를 반환한다.

 

1. 진입 차수가 0인 정점을 스택 / 큐에 삽입한다.

2. 원소를 스택 / 큐에서 꺼내 연결된 모든 간선을 제거한다.

 

1~2번의 과정을 반복하면서, 위상 정렬을 진행한다.

 

정점의 개수만큼 반복이 올바르게 동작한다면 위상 정렬이 가능한 것이며 올바른 위상 정렬 결과를 반환하게 된다. 반대로 모든 정점을 순회하지 못한다면 위상 정렬을 올바르게 수행하지 못한 것이다. 올바른 그래프 구조라고 했을 때, 사이클이 발생한다는 것이다.

 

 

필자는 P.S. 문제에서 bfs와 더불어 위상 정렬이 필요한 경우가 많았기 때문에 자연스레 큐로 구현한다.

위의 출근 그래프를 가지고 위상 정렬을 수행해보자.

 

 

 

이 때, 8번 그림과 같이 5번 정점의 진입차수는 1이기 때문에, 큐에 삽입하지 않는다.

 

 

 

 

 

 

 

 

 

 

 

코드(Java)

원리도 알았고, 동작 과정도 그림으로 표현해봤으니 코드로 작성해보자.

public class Main {
	public static void main(String[] args) {
    	int TOTAL_NODE = 10;
        
        //진입 차수 배열
    	int[] degree = new int[TOTAL_NODE + 1];
        //그래프 정보
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= TOTAL_NODE; i ++) {
        	graph.add(new ArrayList<>());
        }
        
        graph.get(1).add(2);
        graph.get(1).add(7);
        graph.get(2).add(3);
        graph.get(2).add(4);
        graph.get(3).add(5);
        graph.get(4).add(5);
        graph.get(5).add(6);
        graph.get(6).add(9);
        graph.get(7).add(8);
        graph.get(8).add(9);
        graph.get(9).add(10);
        
        degree[2] = 1;
        degree[3] = 1;
        degree[4] = 1;
        degree[5] = 2;
        degree[6] = 1;
        degree[7] = 1;
        degree[8] = 1;
        degree[9] = 2;
        degree[10] = 1;
        
        topologySort(TOTAL_NODE, degree, graph);
    }
    
    public static void topologySort(int N, int[] degree, List<List<Integer>> graph) {
    	Queue<Integer> que = new LinkedList<>();
        int pollCnt = 0;
        
        //진입차수가 0인 정점을 큐에 삽입한다.
        for (int i = 1; i <= N; i ++) {
        	if (degree[i] == 0) que.offer(i);
        }
        
        while(!que.isEmpty()) {
        	//큐에서 원소를 뺀다.
        	int V = que.poll();
            pollCnt++;
           
            //간선을 제거하고 진입차수가 0인 정점을 큐에 삽입한다.
            for (int next: graph.get(V)) {
            	if (--degree[next] == 0) que.offer(next);
            }
        }
        
        //정점의 개수보다 큐에 삽입된 원소가 작다면, 사이클이 발생한 것이다.
        if (pollCnt < N) {
        	System.out.println("CYCLE");
        }
    }
}

 

 

 

 

 

참조

https://en.wikipedia.org/wiki/Topological_sorting

 

Topological sorting - Wikipedia

From Wikipedia, the free encyclopedia Node ordering for directed acyclic graphs In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u t

en.wikipedia.org

 

https://www.geeksforgeeks.org/topological-sorting/

 

Topological Sorting - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

 

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

크루스칼(Kruskal) 알고리즘 (with. 백준 1197번 최소 스패닝 트리)

Tech/알고리즘 2024. 7. 16. 16:15
728x90
728x90

 

크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘(Kruskal Algorithm)이란 최소 신장 트리(Minimum Spanning Tree)를 찾기 위해 사용되는 알고리즘이다.

 

신장 트리(Spanning Tree)
그래프 내의 모든 정점을 포함하는 트리

 

최소 신장 트리(Minimum Spanning Tree)
신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리

 

 

 

최소 신장 트리를 찾기 위해 모든 간선을 가중치에 따라 오름차순으로 정렬하는 아이디어를 사용하여 효과적으로 MST를 구할 수 있게 된다.

세부적인 구현 방법은 다음과 같다.

 

1. 모든 간선을 가중치에 따라 오름차순 정렬한다.

2. 간선을 하나씩 선택하여 사이클이 생기지 않을 때 연결하여 모든 노드가 연결될 때 까지 반복한다.

 

여기서, 사이클의 생성 여부와 노드의 연결은 Union-Find를 통해 수행된다.

사이클의 생성 여부를 Find를 통해 확인하여 연결이 가능한 상태라면 Union을 수행하는 것이다.

 

 

 

예제를 통한 이해

이해를 돕기 위해 실제 P.S. 예제인 백준의 최소 스패닝 트리 문제로 차근차근 알아가보자.

 

 

 

 

입력 첫 줄에 정점(Vertex)과 간선(Edge)이 주어지고, 간선에 대한 정보들이 주어진다.

각 간선에 대한 정보에는 A와 B의 정점이 가중치가 C인 간선으로 연결되어 있다고 한다.

 

예제 데이터는 위키 백과의 크루스칼 알고리즘 글에서 발췌해서 사용했다.

 

출처: 위키백과 크루스칼 알고리즘

 

위 그래프의 간선들의 정보를 저장하면 다음과 같다. (편의상 A = 1, B = 2와 같이 표현했다.)

 



 

모든 간선의 정보를, 간선을 기준으로 오름차순 정렬하여 하나하나 연결하면 된다.

최소 가중치에 대한 보장은, 이미 오름차순 정렬을 통해 연결되는 간선이 최소 가중치라고 보장받을 수 있게 된다.

또한 위에서 말한 것 처럼 Union-Find를 사용하여 사이클의 여부를 파악하고 연결을 수행하면 되겠다.

 

하나하나 연결해보자.

 

 

 

이제 다음 상황인 2와 5의 연결에서 2의 부모 노드는 1이고 5의 부모 노드는 3이다.

부모 노드가 다름은 곧 연결이 되지 않았음을 의미하기 때문에 Union을 진행한다.

Union 과정에서 5번 노드의 부모 노드가 바뀌는 것이 아니라, 각 노드의 부모 노드인 1, 3번 노드의 연결을 내부적으로 수행하게 된다.

 

위 그림처럼 5번 노드의 부모 노드가 변경되는 것이 아닌, 3번 노드의 부모 노드가 변경된다.

 

 

 

이제 2번 노드와 3번 노드의 차례인데, 이미 같은 부모 노드를 가지고 있다.

위에서 언급한 사이클이라는 것이 바로 이런 경우를 말하는데, 같은 부모 노드를 가질 경우 사이클이 존재한다고 판단한다.

즉, 최소 신장 트리를 구해야 하기 때문에 굳이 추가로 연결하지 않는다.

 

 

 

 

5번과 6번 노드를 확인할 때도 마찬가지다.

5번 노드의 부모 노드를 따라가보면, 5 -> 3 -> 1번 노드가 나오고, 6번 노드 또한 1번 노드이다.

재귀적으로 부모 노드를 탐색하여 결국 5번 노드의 부모 노드는 1번 노드가 되고 부모 노드가 같기 때문에 Union은 진행하지 않는다.

 

 

 

 

 

이와 같은 방식으로, 계속해서 사이클 여부를 판단하여 연결을 진행해준다.

 

 

 

 

시간 복잡도

Union-Find 알고리즘의 시간 복잡도가 상수이기 때문에, 정렬을 수행하는 데 걸리는 시간이 곧 크루스칼 알고리즘의 시간복잡도가 된다.

일반적으로, 정점과 간선이 주어질 때 O(ElogV)의 시간복잡도를 가진다.

 

 

 

 

구현 코드(with Java, 백준 1197번)

위의 백준 1197번을 한 번 풀어보자.

위에서 언급했던 것 처럼, 구현 방법은 정렬 -> 사이클 파악 여부에 따른 연결로 진행된다.

 

 

입력받은 정보를 바탕으로 간선의 가중치를 기준으로 오름차 정렬한다.

int[][] graph = new int[E][3];

for (int i = 0; i < E; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int v1 = Integer.parseInt(st.nextToken());
    int v2 = Integer.parseInt(st.nextToken());
    int edge = Integer.parseInt(st.nextToken());
    graph[i][0] = v1;
    graph[i][1] = v2;
    graph[i][2] = edge;
}

Arrays.sort(graph, (o1, o2) -> o1[2] - o2[2]);

 

 

 

사이클이 존재하지 않는 경우(부모 노드가 서로 다를 경우) 연결한다.

int mstCost = 0;

for (int i = 0; i < E; i ++)  {
    int v1 = graph[i][0];
    int v2 = graph[i][1];
    if (find(parent, v1) != find(parent, v2)) {
        union(parent, v1, v2);
        mstCost += graph[i][2];
    }
}

 

 

 

전체 코드는 아래와 같다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int[][] graph = new int[E][3];

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int edge = Integer.parseInt(st.nextToken());
            graph[i][0] = v1;
            graph[i][1] = v2;
            graph[i][2] = edge;
        }
        
        int[] parent = new int[V + 1];

        for (int i = 1; i <= V; i ++) {
            parent[i] = i;
        }
        
        Arrays.sort(graph, (o1, o2) -> o1[2] - o2[2]);
        int mstCost = 0;

        for (int i = 0; i < E; i ++)  {
            int v1 = graph[i][0];
            int v2 = graph[i][1];
            if (find(parent, v1) != find(parent, v2)) {
                union(parent, v1, v2);
                mstCost += graph[i][2];
            }
        }

        bw.write(String.valueOf(mstCost));
        bw.flush();
        bw.close();
    }

    private static int find(int[] parent, int x) {
        if (parent[x] == x) {
            return x;
        }

        return parent[x] = find(parent, parent[x]);
    }

    private static void union(int[] parent, int x, int y) {
        x = find(parent, x);
        y = find(parent, y);

        if (x == y) return;
        
        if (x < y) {
            parent[y] = x;
        }
        else parent[x] = y;
    }
}

 

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

[데이터베이스] 인덱스(index) 정리

Tech/데이터베이스 2024. 7. 10. 17:41
728x90
728x90

인덱스

 

 
 
목차, 색인, 책갈피와 같은 기능을 하는 인덱스는, 데이터베이스 분야에서는 어떤 데이터를 검색할 때 속도를 높여주는 자료 구조로
메모리 영역에 생성되는 일종의 책갈피이다.
 
 
 
 

인덱스 구조

보통 Hash, B-Tree, B+Tree가 있다.

실제 사용하고있는 MySQL MYISAM의 인덱스 일부

 

Hash

우리가 알고있는 Key, Value형태의 자료 구조다.
해시 함수로 키 값을 해시값으로 변환하고, 이 해시 값을 기반으로 데이터를 빠르게 조회할 수 있다. - O(1)
 

 
 
하지만 이런 해시구조의 특성상 범위 검색에 효율이 떨어진다. 키 값이 조금이라도 변하게 되면 완전히 다른 해시 값을 반환하기 때문이다.
범위 검색에서의 부등호 연산을 포함한 범위 조건(BETWEEN, LIKE 등)에는 적합하지 않다.
 
 
 

B-Tree

B-Tree는 이진 트리를 확장한 트리 구조이다. 자식 노드를 2개보다 더 많이 가질 수 있다.
 

 
 
Root, Branch, Leaf의 구조로 되어있으며 Branch가 곧 리프가 되는 경우도 있다.
B-Tree의 주요 특징 중 하나는 모든 리프 노드가 동일한 깊이에 있다는 점이다.
이는 트리의 균형을 유지하여 연산 시간의 복잡도 logN으로 보장하여 효율적인 검색을 가능하게 한다.
 
B-Tree의 구조가 효율적인 이유는 위에서 언급한 균형 잡힌 구조와 더불어 대수 확장성에 있다.
대수 확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미한다.
4차 B-Tree구조가 있다고 가정해보자. 각 노드는 최대 4개의 자식노드를 가질 수 있다. 즉 트리의 깊이가 1씩 증가할 때마다 최대 4배의 인덱스가 추가될 수 있다. 따라서 깊이가 d인 4차 B-Tree는 최대 4^d의 리프 노드를 가질 수 있다. 깊이가 10만 되어도 리프 노드수는 100만 개가 넘는다.

트리의 깊이가 낮기 때문에 I/O작업이 적고 연산이 빠르게 일어날 수 있다.

 
 
 

B+Tree

B-Tree를 개선시킨 자료 구조로 각 노드에는 인덱스 키만 저장되고, 실제 데이터리프 노드에 저장된다.
 

 
 
리프 노드들은 서로 연결 리스트 형태로 연결되어 있어 범위 검색에 효율적이다. 하지만 데이터를 조회하기 위해선 반드시 리프 노드까지 탐색(log2N)이 되어야 한다.
 
 
 
 

주의사항

 

DML의 성능 저하

DML(insert, update, delete) 명령에 따라 레코드에 해당하는 인덱스를 생성, 삭제, 변경해야 하기 때문에 성능 저하가 발생한다.
또한 인덱스의 개수가 너무 많으면 레코드 당 인덱스 변경의 횟수가 많아지기 때문에 성능 저하를 발생시킬 수 있다.
인덱스의 개수가 많아지면 옵티마이저가 잘못된 인덱스를 선택하여 조회 성능에 영향을 미치지 못하는 경우도 있다.
 
 

페이지 크기와 레코드 저장

MySQL에서는 디스크와 메모리에 데이터를 읽고 쓰는 최소 작업의 단위를 페이지라 한다.

인덱스를 포함해 PK와 테이블 모두 페이지 단위로 관리된다.

 
우리는 하나의 레코드를 읽기 위해서 여러 레코드가 포함된 페이지를 읽어서 그 중 일치하는 레코드를 읽는 것이다.
(당연히 페이지에는 여러 레코드가 기록되어 있을 수 있다.)
만약 레코드를 찾기 위해 1개의 페이지로 해결이 되지 않는다면 다른 페이지들을 읽어야 하는 추가적인 디스크 I/O가 발생하게 된다. 
 
(참고)
InnoDB의 경우 페이지 크기 16KB로 고정되어 있었지만, 공식 문서에 따르면 MySQL 5.7.6 이후부터는 페이지 크기를 32KB, 64KB로 설정하는 것이 가능하다고 한다. 하지만 한 레코드의 크기는 16KB로 여전히 제한된다고 한다.
 

 
 
인덱스 역시 페이지 단위로 관리가 된다. 인덱스로 사용되는 PK, 컬럼의 크기가 크면 클수록 인덱스 페이지가 줄어들게 된다. 그럼 인덱스를 활용한 조회 시에도 여러 인덱스 페이지를 읽어야 하는 문제가 발생한다. 그렇기에 인덱스 키는 길면 길수록 성능 저하를 발생시킨다.
 


InnoDB의 경우 하나의 레코드 크기가 페이지 크기의 절반 이상일 경우 레코드에서 외부에 저장할 가변 길이 컬럼을 선택해서 외부 페이지(off-page)에 데이터를 저장하고 기존의 페이지에는 off-page를 가리키는 포인터를 저장한다.

 
 
 
 

인덱스 컬럼 기준

 

단일 인덱스

단일 인덱스를 생성할 때는 카디널리티(Cardinality)가 가장 높은 것을 잡아야 한다.

카디널리티란 중복된 수치를 얘기한다. Unique 한 값일수록 카디널리티가 높다.
예를 들어 성별은 카디널리티가 낮고, 주민등록번호는 카디널리티가 높다.

 
카디널리티가 높은 컬럼을 인덱스로 생성해야 하는 이유는 인덱스로 많은 부분을 걸러낼 수 있어야 하기 때문이다. 인덱스를 통해 많이 걸러내면 걸러낼수록 조회 성능이 올라간다.
 
 

복합 인덱스

복합 인덱스를 최적화하기 위해서는 카디널리티를 포함하여 다음 상황들을 고려해야 한다.

  • 공통으로 사용되는 필수 조건
  • =, IN 연산
  • 정렬
  • 범위 비교 연산 (BETWEEN, LIKE, 비교연산자)

여러 자료를 통해 학습을 했을 때, 인덱스는 범위 비교 시에는 다음 인덱스 컬럼은 사용되지 않는다고 했다.
인덱스를 지정할 때 위의 상황들을 오름차순으로 생성하는 게 효율적이라는 자료도 있었다.
 
 
 

복합 인덱스를 통한 현업에서의 튜닝 시도

 

최대 5초가 걸리는 쿼리 개선하기

[데이터베이스] 인덱스(index) 정리인덱스   목차, 색인, 책갈피와 같은 기능을 하는 인덱스는, 데이터베이스 분야에서는 어떤 데이터를 검색할 때 속도를 높여주는 자료 구조로메모리 영역에

mag1c.tistory.com

 

 

 

종류

인덱스는 분류에 따라 여러 종류의 인덱스가 있다.

  • Unique - Non-Unique Index
  • Single - Composite Index
  • Clustered - Non-Clustered Index
  • Function-Based, Bitmap, Reverse key, Hash Index

등등 여러 인덱스들이 있지만 여기서는 클러스터의 분류에 따른 인덱스를 살펴보자
 
 

Clustered Index

클러스터드 인덱스는 데이터가 테이블에 물리적으로 저장되는 순서를 정의한다. 이 뜻은 인덱스가 되는 컬럼을 기준으로 데이터들을 정렬시킴을 의미한다.

primary key의 제약 조건은 클러스터드 인덱스를 자동 생성하기 때문에 일반적인 상황에서는 PK가 곧 클러스터드 인덱스가 된다.
 
테이블당 하나의 클러스터드 인덱스만 존재할 수 있고 인덱스 페이지의 리프 노드에 실제 데이터의 페이지가 들어있다.
 

출처: https://gwang920.github.io/database/clusterednonclustered/

 
 
 
실제 데이터가 인덱스 순서에 따라 정렬되어 검색 시 매우 빠른 성능을 보일 수 있다. 하지만 위에서 말한 것처럼 정렬된 상태여야 한다. no, id값의 일반적인 auto_increment값을 가진 PK라면 문제가 되지 않겠으나, UUID 같은 정렬되지 않은 키를 사용한다면 정렬을 위해 추가적인 리소스를 발생시킬 수 있다. 성능이 저하될 수 있다는 의미이다.

 

PK의 보안 때문에 UUID를 고려한다면 UUIDv7을 사용해 보는 것도 괜찮을 것 같다.
UUIDv7은 UNIX_TIMESTAMP를 ms 단위로 인코딩하여 효율적인 색인화가 가능하다고 한다.

 
 
 
 

Non-Clustered Index

논-클러스터드 인덱스는 테이블에 저장된 물리적 순서에 따라 데이터를 정렬하지는 않는다.
 
클러스터드 인덱스와 달리 리프 노드에는 데이터 페이지에 대한 포인터가 있어 포인터를 통해 데이터 페이지를 조회할 수 있는 형태이고 데이터 페이지는 렬되어있지 않다.
 

출처: https://gwang920.github.io/database/clusterednonclustered/

 
 
클러스터드 인덱스와 달리 데이터를 찾는 데 여러 개의 인덱스를 생성할 수 있다.
 
데이터를 찾을 때 추가적인 스텝 (리프 레벨에서 데이터 페이지에 접근)이 필요하기 때문에, 클러스터드 인덱스보다는 속도가 느리고 데이터 입력 시 별도의 공간에 인덱스를 생성해야 하기 때문에 추가 작업이 요구된다. 별도의 공간도 따로 할당되어야 한다. (약 10%)
 
 
 
 

마무리

블로그를 돌아보니 DB 포스팅이 SQLD를 취득하기 위한 학습 이후에 멈춰있었는데, 사실상 현재 해나가고 있는 모든 것들을 포스팅하는 내 성격상 현재 가장 많이 다루고 있는 것이 데이터베이스인데, 네트워크와 PS에 빠져서 소홀했다는 생각이 들었다. 
 
리팩토링 과정에서 단순히 실행 계획을 바탕으로 튜닝을 이것저것 많이 처리하고, 일의 양이 많아 바로 다음 작업으로 넘어가다 보니 정확히 쿼리 튜닝을 위해 관련된 지식들을 학습할 필요를 느껴 다시 하나하나 시작해보려 한다. DB의 여러 부분들의 공부를 깊게 해 보면서 실제로 적용시켜 보며 정리를 위한 포스팅을 계속 이어나갈 수 있도록 해야겠다.
 
 
 
 

참조

 

Real MySQL 시즌 1 - Part 1 강의 | 이성욱 - 인프런

이성욱 | MySQL의 핵심적인 기능들을 살펴보고, 실무에 효과적으로 활용하는 방법을 배울 수 있습니다. 또한, 오랫동안 관성적으로 사용하며 무심코 지나쳤던 중요한 부분들을 새롭게 이해하고,

www.inflearn.com

 

CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조 강의 | 큰돌 - 인프런

큰돌 | 국내 1위 '면접을 위한 CS 전공지식노트' 저자의 디자인패턴, 네트워크, 운영체제, 데이터베이스 등 CS 지식 강의! CS 면접에 필요한 모든 개념과 최신 기출을 다룬다!, [사진] [사진] [실제 카

www.inflearn.com

 

[Database] 인덱스(index)란?

1. 인덱스(Index)란? [ 인덱스(index)란? ] 인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 만약 우리가 책에서 원하는 내

mangkyu.tistory.com

 

MySQL Ascending index vs Descending index - tech.kakao.com

용어 정리 이 설명에서는 인덱스의 정렬 순서와 데이터 읽기 순서 등 방향에 대한 ...

tech.kakao.com

 

MySQL :: MySQL 5.7 Release Notes :: Changes in MySQL 5.7.6 (2015-03-09, Milestone 16)

These functions are deprecated in favor of the ST_ names: Area(), AsBinary(), AsText(), AsWKB(), AsWKT(), Buffer(), Centroid(), ConvexHull(), Crosses(), Dimension(), Distance(), EndPoint(), Envelope(), ExteriorRing(), GeomCollFromText(), GeomCollFromWKB(),

dev.mysql.com

 

[mysql] 인덱스 정리 및 팁

MySQL 인덱스에 관해 정리를 하였습니다. MySQL을 잘 알아서 정리를 한것이 아니라, 잘 알고 싶어서 정리한 것이라 오류가 있을수도 있습니다. 1. 인덱스란? 인덱스 == 정렬 인덱스는 결국 지정한 컬

jojoldu.tistory.com

 

2. 페이징 성능 개선하기 - 커버링 인덱스 사용하기

2. 커버링 인덱스 사용하기 앞서 1번글 처럼 No Offset 방식으로 개선할 수 있다면 정말 좋겠지만, NoOffset 페이징을 사용할 수 없는 상황이라면 커버링 인덱스로 성능을 개선할 수 있습니다. 커버링

jojoldu.tistory.com

 

[MySQL] B-Tree로 인덱스(Index)에 대해 쉽고 완벽하게 이해하기

인덱스를 저장하는 방식(또는 알고리즘)에 따라 B-Tree 인덱스, Hash 인덱스, Fractal 인덱스 등으로 나눌 수 있습니다. 일반적으로 B-Tree 구조가 사용되기 때문에 B-Tree 인덱스를 통해 인덱스의 동작

mangkyu.tistory.com

 

 

Goodbye to sequential integers,  hello UUIDv7!

Exploring the tradeoffs of different database indexes; from sequential integers, randomly generated UUIDs, to time-based identifiers and the latest & greatest UUIDv7

buildkite.com

 
 

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

graphQL의 N + 1문제와 DataLoader

Tech/NodeJS 2024. 6. 29. 22:34
728x90
728x90
 

graphQL에 대해 알아보자 - 1 (with NestJS, typeORM)

학습을 위해 생성한 예제 코드는 깃헙에 있습니다.(링크)  graphQLgraphQL은 기존 데이터로 쿼리를 실행하기 위한 API를 위한 쿼리 언어이자 런타임이다. 클라이언트가 필요한 것만 정확히 요청할

mag1c.tistory.com

 
 

N + 1

이전 글의 예제에서 Post를 가져오는데에 Post와 Comments는 1:N 관계를 가진다.
이 관계에서 comments를 조회할 때 comment가 lazy loding되어 N + 1 문제가 발생할 수 있다.

 

//lazy loading
async findAll(authorId?: number): Promise<Post[]> {
    if (authorId) return await this.postRepo.find({ where: { authorId: authorId } });
    return await this.postRepo.find();
}

//eager loading
async findAll(authorId?: number): Promise<Post[]> {
    const options: FindManyOptions<Post> = {
        relations: ['author', 'comments', 'comments.author']
    };

    if (authorId) {
        options.where = { authorId: authorId };
    }

    return await this.postRepo.find(options);
}

 
 
 

graphQL의 N + 1

미리 join연산을 통해 fetch하더라도 N + 1문제가 발생할 수 있다.
이전 글과 동일하게 데이터를 post 10개, user 10명, comment는 post당 10개로 설정했다.

//Post Resolver
@ResolveField(() => User)
async author(@Parent() post: Post): Promise<User> {
    return await this.userService.findOne(post.authorId);
}

@ResolveField(() => [Comment])
async comments(@Parent() post: Post): Promise<Comment[]> {
    return await this.postService.getCommentsByPostId(post.id);
}


//Comment Resolver
@ResolveField(() => User)
async author(@Parent() comment: Comment): Promise<User> {
    return await this.userService.findOne(comment.authorId);
}

 
 
기존의 코드는 각 리졸버에서 개별적으로 가져오는 방식으로 동작하기때문에 아래와 같이 동작한다.

  1. 10개의 post를 가져오는 쿼리
  2. 각 post에 대해 author를 가져오는 10개의 쿼리
  3. 각 post에 대해 comments을 가져오는 10개의 쿼리
  4. comments 각각의 author을 가져오는 쿼리 (게시물 당 10개의 댓글 - 10 x 10)

이러한 방식으로 총 121개의 쿼리가 실행된다;;;;;;

 
 
만약 리졸버에서 join해서 fetch하더라도, 데이터를 실제로 가져오는 백단에서는 여전히 OverFetching이 발생한다.
 
OverFetching을 방지하고자 select를 커스터마이징할 수도 없다. 일관성을 해치고 다른 쿼리를 위해 추가로 코드를 작성해야한다. 다른 잠재적인 문제들도 발생할 것이다.
 
엔터티 간의 관계를 명시할때, TypeORM에서 eager을 제공해주긴 하지만, 위의 경우는 이런 속성들로 해결할 수 없다.
 
 
 

DataLoader

dataloader은 페이스북에서 만든 라이브러리로 여러 요청을 하나의 배치로 묶어서 한 번에 데이터베이스에 요청을 보낼 수 있다.
 

@Injectable({ scope: Scope.REQUEST })
export class UserLoader {

    constructor(
        private readonly userRepo: UserRepository,
    ) { }

    findById = new DataLoader<number, User>(
        async (authorIds: number[]) => {
            const user: User[] = await this.userRepo.findByIds(authorIds);
            return authorIds.map((id: number) => user.find((user: User) => user.id === id));
        }
    );
}
@Injectable({ scope: Scope.REQUEST })
export class CommentLoader {
    constructor(
        private readonly commentRepo: CommentRepository,
    ) { }
    findByPostId = new DataLoader<number, Comment[]>(
        async (postIds: number[]) => {
            const comments: Comment[] = await this.commentRepo.findByPostIds(postIds);
            return postIds.map((id: number) => comments.filter((comment: Comment) => comment.postId === id));
        }
    )
}

 
 
DataLoader를 사용하면 각 요청이 배치로 처리되어 쿼리 수가 대폭 줄어든다.

@Resolver(of => Post)
export class PostResolver {
    constructor(
        private postService: PostService,
        private userLoader: UserLoader,
        private commentLoader: CommentLoader,
    ) {  }

    @Query(() => [Post])
    posts(): Promise<Post[]> {
        return this.postService.findAll();
    }

    @ResolveField(() => User)
    author(@Parent() post: Post): Promise<User> {
        console.log(this.userLoader.findById)
        return this.userLoader.findById.load(post.authorId);
    }

    @ResolveField(() => [Comment])
    comments(@Parent() post: Post): Promise<Comment[]> {
        return this.commentLoader.findByPostId.load(post.id);
    }

}

 
 
반면 DataLoader은 각 요청이 배치처리되어 필요할 때 한번에 데이터를 요청하기 때문에 쿼리 수가 대폭 줄어들게 된다.

  1. post 10개를 가져오는 쿼리
  2. post 각각의 author을 한 번에 가져오는 쿼리
  3. comments를 한 번에 가져오는 쿼리

 
 
DataLoader 인스턴스가 생성되고 내부적으로 요청을 수집한다. 아래의 로그는 posts에 대한 각 author들의 정보를 받아오는 DataLoader의 인스턴스 로그이다. load(1), load(2)와 같은 함수 호출에서 DataLoader의 배치된 요청들은 tick에서 한 번에 처리하여 데이터베이스에 fetch요청을 보낸다.

DataLoader {
  _batchLoadFn: [AsyncFunction (anonymous)],
  _maxBatchSize: Infinity,
  _batchScheduleFn: [Function (anonymous)],
  _cacheKeyFn: [Function (anonymous)],
  _cacheMap: Map(0) {},
  _batch: null,
  name: null
}
DataLoader {
  _batchLoadFn: [AsyncFunction (anonymous)],
  _maxBatchSize: Infinity,
  _batchScheduleFn: [Function (anonymous)],
  _cacheKeyFn: [Function (anonymous)],
  _cacheMap: Map(1) { 1 => Promise { <pending> } },
  _batch: { hasDispatched: false, keys: [ 1 ], callbacks: [ [Object] ] },
  name: null
}
DataLoader {
  _batchLoadFn: [AsyncFunction (anonymous)],
  _maxBatchSize: Infinity,
  _batchScheduleFn: [Function (anonymous)],
  _cacheKeyFn: [Function (anonymous)],
  _cacheMap: Map(2) { 1 => Promise { <pending> }, 2 => Promise { <pending> } },
  _batch: {
    hasDispatched: false,
    keys: [ 1, 2 ],
    callbacks: [ [Object], [Object] ]
  },
  name: null
}

(...생략...)

DataLoader {
  _batchLoadFn: [AsyncFunction (anonymous)],
  _maxBatchSize: Infinity,
  _batchScheduleFn: [Function (anonymous)],
  _cacheKeyFn: [Function (anonymous)],
  _cacheMap: Map(10) {
    1 => Promise { <pending> },
    2 => Promise { <pending> },
    3 => Promise { <pending> },
    4 => Promise { <pending> },
    5 => Promise { <pending> },
    6 => Promise { <pending> },
    7 => Promise { <pending> },
    8 => Promise { <pending> },
    9 => Promise { <pending> },
    10 => Promise { <pending> }
  },
  _batch: {
    hasDispatched: false,
    keys: [
      1, 2, 3, 4,  5,
      6, 7, 8, 9, 10
    ],
    callbacks: [
      [Object], [Object],
      [Object], [Object],
      [Object], [Object],
      [Object], [Object],
      [Object], [Object]
    ]
  },
  name: null
}

 
 
 
아래는 DataLoader의 load 함수다. 요청을 배치로 묶어 처리하고, 캐싱을 통해 중복을 방지하는 역할 또한 수행한다.
코드를 간략히 살펴보면, 배치를 가져와 캐시 키를 생성하고 캐시의 활성 여부에 따라 promise를 재활용할지 생성할지를 결정해 캐시를 업데이트 후 promise를 반환한다. 그래서 위 예제에서, 1부터 10번까지의 key에 대해 배치를 쌓아나갈 수 있던 것이다.

_proto.load = function load(key) {
    if (key === null || key === undefined) {
      throw new TypeError('The loader.load() function must be called with a value, ' + ("but got: " + String(key) + "."));
    }

    var batch = getCurrentBatch(this);
    var cacheMap = this._cacheMap;

    var cacheKey = this._cacheKeyFn(key); // If caching and there is a cache-hit, return cached Promise.


    if (cacheMap) {
      var cachedPromise = cacheMap.get(cacheKey);

      if (cachedPromise) {
        var cacheHits = batch.cacheHits || (batch.cacheHits = []);
        return new Promise(function (resolve) {
          cacheHits.push(function () {
            resolve(cachedPromise);
          });
        });
      }
    } // Otherwise, produce a new Promise for this key, and enqueue it to be
    // dispatched along with the current batch.


    batch.keys.push(key);
    var promise = new Promise(function (resolve, reject) {
      batch.callbacks.push({
        resolve: resolve,
        reject: reject
      });
    }); // If caching, cache this promise.

    if (cacheMap) {
      cacheMap.set(cacheKey, promise);
    }

    return promise;
}

 
 

이벤트 루프와 태스크 큐에서의 DataLoader 처리
DataLoader은 Node의 이벤트 루프와 태스크 큐를 활용하여 요청을 배치로 처리한다.
Promise는 다음 tick에서 실행되므로 배치 처리는 여러 요청을 수집한 후 다음 tick에서 한 번에 처리할 수 있게 된다.

 
 
 
 
 
 
 

참조

 

GitHub - graphql/dataloader: DataLoader is a generic utility to be used as part of your application's data fetching layer to pro

DataLoader is a generic utility to be used as part of your application's data fetching layer to provide a consistent API over various backends and reduce requests to those backends via batching...

github.com

 

 

GraphQL DataLoader를 이용한 성능 최적화

이번 포스팅에서는 GraphQL 에서 N+1 문제를 해결하기 위한 솔루션인 DataLoader에 대한 소개와 GraphQL 에 DataLoader를 어떤식으로 적용해야되는지를 정리해보려고 한다. N+1 문제N+1 문제는 ORM을 사용할때

y0c.github.io

 
 

 

typeorm/docs/eager-and-lazy-relations.md at master · typeorm/typeorm

ORM for TypeScript and JavaScript. Supports MySQL, PostgreSQL, MariaDB, SQLite, MS SQL Server, Oracle, SAP Hana, WebSQL databases. Works in NodeJS, Browser, Ionic, Cordova and Electron platforms. -...

github.com

 

 

nestjs-dataloader

A NestJS decorator for dataloader. Latest version: 9.0.0, last published: 2 years ago. Start using nestjs-dataloader in your project by running `npm i nestjs-dataloader`. There are 5 other projects in the npm registry using nestjs-dataloader.

www.npmjs.com

 

 

Node.js — The Node.js Event Loop

Node.js® is a JavaScript runtime built on Chrome's V8 JavaScript engine.

nodejs.org

 
 

728x90
300x250
mag1c

mag1c

2년차 주니어 개발자.

방명록