증분식 데이터 형상관리 : Increment Data Versioning

현재 진행중인 MovieWiki 프로젝트의 1차 API 작성을 완료했다.

이제 다음 스텝은 성능 개선 및 기능 고도화다.

그중에서도 가장 난이도가 높을 것으로 예상되는 것이 프로젝트의 핵심 기능인 데이터 형상관리 (Data Versioning)이다.

지난주 멘토링에서 코치님이 증분식 데이터 형상관리(Increment Data Versioning)를 사용하는 것으로 방향성을 제시해주셨다. 그래서 그에 대해 학습한 것을 정리해본다.

 

 

증분식 데이터 형상관리(Increment Data Versioning)

 데이터의 변경 이력을 증분 방식으로 관리하는 방법이다.

데이터의 일부분이 변경되었을 때 전체를 저장하거나 복사하는 대신 변경된 부분만 저장하여

저장 공간을 절약하고 데이터 전송 시간을 단축시키는 장점이 있다.

 현재 MovieWiki는 유저들이 영화를 검색하고 특정 영화의 정보를 공동으로 작성하고 수정하는 것이

핵심 기능이기 때문에 데이터가 주기적으로 업데이트되어 변동성이 높다.

그래서 새로 작성된 영화 정보에 대한 post를 통째로 저장하고 전송하는 것은 비효율적이다.

따라서 데이터의 변경 사항을 추적하여 저장하고 불러오는 증분 방식의 형상 관리가 적절하다는 생각이 든다.

 

증분식 데이터 형상관리(Increment Data Versioning)의 구현

1. 변경 내역 추적
   데이터가 변경되었을 경우 변경된 부분을 식별하고 추적
   
   
2. 변경 내역 적용
   변경 내역을 이전 버전의 데이터에 적용하여 새로운 버전 생성
   
   
3. 버전 관리
   각 버전은 이전 버전과의 차이(증분)만을 저장
   (변경된 부분을 효율적으로 저장하는 방법으로 주로 Diff 알고리즘을 사용한다.)

 

 

디프(Diff) 알고리즘

• diff 알고리즘은 이전 버전과의 차이를 나타내는 데이터를 생성한다.
• diff 알고리즘은 이진 트리 기반의 알고리즘이다.
• 비교 대상이 되는 두 개의 파일 또는 데이터 집합을 비교하여 차이점을 탐지한다.
• 변경된 부분만을 나타내는 데이터를 생성한다.
• 디프(Diff) 알고리즘은 최장 공통 부분 수열(LCS)에 기반을 둔다.

 

 

최장 공통 부분 수열(Longest Common Subsequence)

다음과 같이 두 개의 데이터가 있다.

a b c d f g h j q z

a b c d e f g i j k r x y z

두 데이터의 공통이 되는 가장 긴 부분은 다음과 같다.

a b c d f g j z

두 개의 데이터를 비교하여 추가(+ 기호로 표시)되거나 삭제(- 기호로 표시)되는 부분들은 다음과 같이 나타낸다.

       e   h i   q   k r x y
       +   - +   -   + + + +

 

 

최장 공통 부분 수열(Longest Common Subsequence) 알고리즘 예시 코드

longestCommonSubsequence 함수는 text1과 text2를 입력받는다.

dp[i][j]는 text1의 i번째 문자까지와 text2의 j번째 문자까지의 LCS 길이를 나타낸다.

dp 배열을 구성한 후 i와 j를 역으로 이동하면서 문자가 같으면 lcs에 해당 문자를 추가한다.

최종적으로 lcs에는 가장 긴 공통 부분 수열이 저장된다.

아래 예시 코드에서 console.log(lcs)의 출력은 'BCAB'가 된다.

function longestCommonSubsequence(text1: string, text2: string): string {
  const m = text1.length;
  const n = text2.length;
  const dp: number[][] = [];

  // dp 배열 초기화
  for (let i = 0; i <= m; i++) {
    dp[i] = [];
    for (let j = 0; j <= n; j++) {
      if (i === 0 || j === 0) {
        dp[i][j] = 0;
      } else if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  // LCS 추적
  let i = m;
  let j = n;
  let lcs = '';
  while (i > 0 && j > 0) {
    if (text1[i - 1] === text2[j - 1]) {
      lcs = text1[i - 1] + lcs;
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return lcs;
}

// 예시 사용
const text1 = 'ABCBDAB';
const text2 = 'BDCAB';

const lcs = longestCommonSubsequence(text1, text2);
console.log(lcs);

 

 

Diff 알고리즘 예시코드

generateDiff 함수는 두 개의 문자열을 입력받아 변경 사항을 추적하여 change 객체의 배열로 반환한다.

변경 사항 추적을 위해 dp 테이블을 구성하고 역추적을 통해 변경된 문자 및 유형을 추출한다.

변경 유형은 add, remove, equal, modify 중 하나로 나타낸다.

코드를 실행하면 changes 배열에 변경 사항이 저장되고 각 변경 사항에 대한 정보가 출력된다.

interface Change {
  type: 'add' | 'remove' | 'equal';
  value: string;
}

function generateDiff(originalText: string, modifiedText: string): Change[] {
  const diff: Change[] = [];

  const maxLength = originalText.length + modifiedText.length;
  const dp: number[][] = [];

  // DP 테이블 초기화
  for (let i = 0; i <= originalText.length; i++) {
    dp[i] = [];
    dp[i][0] = i;
  }

  for (let j = 0; j <= modifiedText.length; j++) {
    dp[0][j] = j;
  }

  // 최소 편집 거리 계산
  for (let i = 1; i <= originalText.length; i++) {
    for (let j = 1; j <= modifiedText.length; j++) {
      if (originalText[i - 1] === modifiedText[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1, // 삭제
          dp[i][j - 1] + 1, // 추가
          dp[i - 1][j - 1] + 1 // 수정
        );
      }
    }
  }

  // 변경 사항 추적
  let i = originalText.length;
  let j = modifiedText.length;
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && originalText[i - 1] === modifiedText[j - 1]) {
      diff.unshift({ type: 'equal', value: originalText[i - 1] });
      i--;
      j--;
    } else if (
      i > 0 &&
      j > 0 &&
      dp[i][j] === dp[i - 1][j - 1] + 1 &&
      originalText[i - 1] !== modifiedText[j - 1]
    ) {
      diff.unshift({ type: 'modify', value: modifiedText[j - 1] });
      i--;
      j--;
    } else if (j > 0 && (i === 0 || dp[i][j] === dp[i][j - 1] + 1)) {
      diff.unshift({ type: 'add', value: modifiedText[j - 1] });
      j--;
    } else {
      diff.unshift({ type: 'remove', value: originalText[i - 1] });
      i--;
    }
  }

  return diff;
}

// 예시 사용
const originalText = 'Hello World';
const modifiedText = 'Hello OpenAI World';

const changes = generateDiff(originalText, modifiedText);
console.log(changes);

 

데이터 형상관리부터 시작해서 증분 방식까지 하나도 이해가 안되고 있었는데

위키백과와 gpt의 도움을 받아 기초 개념을 정리할 수 있었다.

지속적인 추가학습을 통해 팀원들에게 내용을 공유하고 빠르게 프로젝트에 적용해보면 좋겠다.

 

 

참고

https://ko.wikipedia.org/wiki/Diff

diff - 위키백과, 우리 모두의 백과사전