<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Giyoon Park on Medium]]></title>
        <description><![CDATA[Stories by Giyoon Park on Medium]]></description>
        <link>https://medium.com/@workspaceforice?source=rss-db62e036d783------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*VFv02FFPWi68sUDh</url>
            <title>Stories by Giyoon Park on Medium</title>
            <link>https://medium.com/@workspaceforice?source=rss-db62e036d783------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 03:05:36 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@workspaceforice/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Airflow 주요 컴포넌트(scheduler, triggerer, worker)에 대한 커널 메모리 누수(memory leak)현상]]></title>
            <link>https://medium.com/@workspaceforice/airflow-%EC%A3%BC%EC%9A%94-%EC%BB%B4%ED%8F%AC%EB%84%8C%ED%8A%B8-scheduler-triggerer-worker-%EC%97%90-%EB%8C%80%ED%95%9C-%EC%BB%A4%EB%84%90-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EB%88%84%EC%88%98%ED%98%84%EC%83%81-8584247cc924?source=rss-db62e036d783------2</link>
            <guid isPermaLink="false">https://medium.com/p/8584247cc924</guid>
            <dc:creator><![CDATA[Giyoon Park]]></dc:creator>
            <pubDate>Mon, 06 Jul 2026 02:02:17 GMT</pubDate>
            <atom:updated>2026-07-14T14:31:37.623Z</atom:updated>
            <content:encoded><![CDATA[<h3>TL;DR</h3><p>Airflow 2.x 버전에서는 시간이 지날 수록, 일부 Airflow 컴포넌트에서 메모리 사용량이 점진적으로 증가한다. 문제의 원인은 pycache 파일과 관련있다. pycache 파일의 경우, 생성 과정에서 임의의 파일명을 갖는 파일이 활용된다.</p><p>Airflow 컴포넌트는 python 기반의 liveness 명령어를 주기적으로 수행하는데, 이 과정에서 생성 되어야할 pycache 파일이 write 권한 이슈 때문에 생성되지 못하고 있다. 결과적으로 liveness 명령어를 수행 할 때마다, pycache 파일 생성을 시도하고, 시도 과정에서 임의의 파일을 생성한다. 이 임의의 파일에 대한 메타데이터가 점점 커널 메모리에 쌓이게되어, 결과적으로 Airflow 컴포넌트는 RSS가 낮음에도, 높은 메모리 점유율을 보이게된다.</p><p>작성자의 경우, pycache 파일 생성 시도 자체를 비활성화 했으며(PYTHONDONTWRITEBYTECODE=1), 확인된 바로는 3.1.5 버전에서 이 문제가 fix 되었다고 한다.</p><p>이젠 Airflow 3.0 이상 많이 사용하기 때문에 이걸 작성할까 고민했지만, 환경상 아직 2.x 버전을 사용하고 계신 분들을 위해, 그리고 아카이빙용으로 일단 기록했다.</p><h3>현상</h3><p>회사에서 Kubernetes 위에 Airflow 클러스터를 운영하고 있으며 scheduler, triggerer, 5대 이상의 celery worker 등을 사용하고 있다. Airflow를 운영하면서 worker에서 OOM(<a href="https://airflow.apache.org/docs/apache-airflow/2.9.3/troubleshooting.html#localtaskjob-killed">LocalTaskJobKilled</a>)이 발생한적이 있었는데, 이를 해결하기 위해 <a href="https://docs.celeryq.dev/en/stable/userguide/configuration.html#worker-max-memory-per-child">worker_max_memory_per_child</a>, <a href="https://docs.celeryq.dev/en/stable/userguide/configuration.html#worker-max-tasks-per-child">worker_max_tasks_per_child</a>를 설정했다. OOM은 더 이상 발생하지 않았지만, 시간이 지나면서, 메모리 사용량이 점진적으로 늘어나는 것을 그라파나 모니터링을 통해 확인했다. 실행 중인 dag가 없음에도, worker에 대한 과도한 메모리 사용량은 이해 할 수 없었다. 다른 컴포넌트들도 확인해봤는데, 모두 메모리를 많이 사용하고 있다는 사실을 알게됐고, 원인을 찾아봐야겠다는 결심을 했다.</p><h3>해결과정</h3><p>그라파나를 통해 알 수 있는 사실은, 하나의 Kubernetes pod에 대한 RSS이다. 따라서, scheduler pod에서 사용하는 메모리 양과 실제 scheduler 프로세스가 차지하는 실제 물리적인 메모리 양간의 차이 또는 비율을 알 수 있다. 확인 결과, scheduler와 triggerer는 모두 RSS 값이 500MB 내외인 것에 비해, pod가 사용하는 메모리 양이 limits.memory 값(각각 4GB, 2GB)에 근접했고, worker의 경우, 이 정도만큼의 괴리는 아니지만, pod 메모리 사용량과 RSS 값의 차이가 약 2GB였기 때문에 무시 할 수는 없다.</p><p>위의 사실을 통해서, 알 수 있는 공통점은 현재 RSS가 아닌 다른 곳에서 메모리를 많이 사용하고 있다는 사실이다. 따라서 어느 곳에서 이렇게 메모리를 많이 사용하고 있는지 알아야한다.</p><p>아시다시피, Airflow base image은 기본적인 리눅스 명령어들이 거의 없다. 따라서, 프로세스에 대한 메모리 사용량 세부 정보가 있는 파일을 찾아서 확인해야한다. 이는 /sys/fs/cgroup/memory.stat 에서 확인 할 수 있다. 작성자 의 경우, worker pod에 접속해서 확인해봤으며, 다양한 annon, file, kernel_stack 등 다양한 정보가 있다는 사실을 확인했다. 여기서 slab, slab_reclaimable에 주목했다. slab은 커널에서 빈번하게 사용하는 객체를 캐싱하기위해 사용되는 메모리 영역으로, 약 2GB를 차지하고 있으며 slab_reclaimable 값과 차이가 거의 없다. 따라서 대부분 회수 가능하다. scheduler, tiggerer 또한 마찬가지였다.</p><p>이제는 어떤 커널 객체가 지나치게 많이 캐싱되는지 확인해야한다. 하지만 이는 pod 수준에서는 알 수 없다. 만약 pod security를 활용하여, priviliged 를 true로 설정 후, root로 실행한다면, /proc/slabinfo 를 조회 할 수 있지만, 이 정보는 Kubernetes node 수준의 slabinfo이다. 그리고 pod 수준에서도 확인 가능한지 알기 위해, node에 직접 접속했으나, 대부분 권한이 없어 볼 수 있는 정보가 없었다.</p><p>그래도 node 수준에서 slabinfo로부터 알 수 있었던 사실은, dentry 사용량이 가장 높다는 것이다. 우선 Airflow pod도 마찬자기로 dentry 사용량이 높을 것이라고 가정하고, 무엇이 dentry 객체를 많이 생성하는지 알아보기 시작했다.</p><p>dentry는 디렉토리 또는 파일과 관련이 있기 때문에, 처음엔 Airflow 로그와 관련이 있다고 생각했다. 모든 컴포넌트들은 로그를 갖고 있으며, “opt/airflow/log/{dag_id}/{dag_run}/{task_id}/{retry_number.log}” 형식으로 로그가 관리되고 있다. 15일 기준, 약 27,000개의 로그파일과 각 경로마다 dentry 객체가 생성되는 것, 그리고 분산 블록 스토리지 오픈소스를 통해서 로그를 영속적으로 저장하고 있어서, 처음엔 로그 때문에 문제가 된다고 생각했다. 따라서 로그 파일 보관 주기를 15일 -&gt; 10일로 줄여, 로그 파일 수(약 18,000)를 줄인 후, 일주일 동안 그라파나로 모니터링했다.</p><p>여전히 시간이 흘러감에 따라, 메모리 사용량이 증가하고 있고, 결과적으로 15일의 로그 보관 주기에 따른 메모리 사용량과 크게 다르지 않았다. 다시 말해, 로그 파일 수는 dentry 객체가 지나치게 많이 생성되는 것과는 큰 관련이 없었다.</p><p>이후, /proc/sys/fs/dentry-state 에서 dentry에 대한 구체적인 정보를 확인 할 수 있다는 사실을 알았다. <a href="https://www.kernel.org/doc/html/v6.6/admin-guide/sysctl/fs.html#dentry-state">https://www.kernel.org/doc/html/v6.6/admin-guide/sysctl/fs.html#dentry-state</a> 링크에서 자세한 내용을 확인 할 수 있다. 여기서 negative_dentry 객체도 있다는 사실을 알았다. negative_dentry는 존재하지 않는 경로에 대한 dentry 객체를 생성한다. negative_dentry 정의를 보고, pycache 파일을 떠올렸다. 왜냐하면 과거에 빠른 처리를 위해 pycache 파일이 필요한데, 서버에 write 권한이 없어서 깃허브에 커밋할까를 고민했기 때문이다. 물론, pycache 파일명은 py파일명을 따라가기 때문에(i.e. 파일명이 고정), 큰 영향을 줄 것 같지는 않을 것 같다는 생각을 했지만, 생각은 생각이고 실험은 실험이라고 생각해서, pycache 생성을 비활성화(i.e. PYTHONDONTWRITEBYTECODE=1)하고, 일주일동안 메모리 사용량을 모니터링했다. 결과는 이전 대비 메모리 사용량이 증가하지 않았다.</p><p>pycache 파일 생성 시도를 제일 많이 하는 곳은 바로 Airflow 컴포넌트의 python 기반 liveness 명령어이다. 쉘스크립트를 만들어서 반복문을 통해 이 명령어를 여러번 수행 한 후, /proc/sys/fs/dentry-state 에서 조회한 결과 negative_dentry 객체가 증가한 것을 확인했다.</p><ul><li>triggerer pod에서 사용되는 liveness 명령어 기준, 한 번 수행 시 450개 negative_dentry 객체가 생성됨</li><li>1분마다 주기적으로 수행된다면, 하루에 생성되는 객체는 450 * 60 * 24 = 648,000개</li></ul><p>그렇다면, 생성 여부와 상관없이 pycache 파일이름은 고정될텐데, 왜 저 객체가 늘어나는지 궁금했다. 그래서 Dockerfile에서 Airflow image와 함께, strace 명령어를 구성했고, docker-compose로 로컬에서 Airflow를 구축했다. triggerer 서버에 접속 후, 창 2개를 띄워 하나는 liveness 명령어를, 다른 하나는 strace 명령어를 수행했다. 그리고 다음의 결과를 확인했다.</p><pre>newfstatat(AT_FDCWD&lt;/opt/airflow&gt;, &quot;/usr/local/lib/python3.12/encodings/aliases.py&quot;, {st_mode=S_IFREG|0644, st_size=15677, ...}, 0) = 0 &lt;0.000351&gt;<br>newfstatat(AT_FDCWD&lt;/opt/airflow&gt;, &quot;/usr/local/lib/python3.12/encodings/__pycache__&quot;, {st_mode=S_IFDIR|0755, st_size=4096, ...}, 0) = 0 &lt;0.000751&gt;<br><br># openat: 파일을 여는 시스템 콜, 여기서는 파일 생성 시도로 사용<br># 쓰기 전용 | 없으면, 새로 생성 | 이미 있으면 실패 | exec 시, fd 자동 닫기<br># 0644: 생성을 위해, 필요한 권한<br># -1 EACCESS (Permission denied): 권한이 없어, 쓰기 실패.<br>openat(AT_FDCWD&lt;/opt/airflow&gt;, &quot;/usr/local/lib/python3.12/encodings/__pycache__/aliases.cpython-312.pyc.281473565478896&quot;, O_WRONLY|O_CREAT|O_EXCL|O_CLOEXEC, 0644) = -1 EACCES (Permission denied) &lt;0.000375&gt;</pre><p>이게 liveness 명령어 수행 과정에서 나온 시스템 콜이라는 것을 장담 할 수는 없지만, 적어도 pycache 파일 이름이 고정되어도, negative_dentry 객체가 늘어나는지 알 수 있는 메세지이다. 다시 말해, pycache 파일을 생성하는 과정에서, 임의의 이름을 갖는 임시 파일이 생성 시도 되는데, 사용 중인 서버 계정이 write 권한이 없어, 결과적으로 pycache 파일 생성에 실패한다. 이 과정을 매 liveness 명령어 수행 할 때마다 반복한다.</p><p>원인을 알게된 후, Airflow image 구성을 수정할까 고민했지만, 여건상 어려워서 일단, 동일한 이유로 높은 메모리 사용량을 갖는 나머지 Airflow 컴포넌트에 대해서도, PYTHONDONTWRITEBYTECODE=1로 하여, pycache 생성을 비활성화 했다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8584247cc924" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries 리뷰]]></title>
            <link>https://medium.com/@workspaceforice/rapidstore-an-efficient-dynamic-graph-storage-system-for-concurrent-queries-%EB%A6%AC%EB%B7%B0-b43f4654c985?source=rss-db62e036d783------2</link>
            <guid isPermaLink="false">https://medium.com/p/b43f4654c985</guid>
            <dc:creator><![CDATA[Giyoon Park]]></dc:creator>
            <pubDate>Tue, 12 May 2026 08:17:21 GMT</pubDate>
            <atom:updated>2026-05-12T13:53:07.397Z</atom:updated>
            <content:encoded><![CDATA[<p>논문링크: <a href="https://arxiv.org/pdf/2507.00839">https://arxiv.org/pdf/2507.00839</a></p><h3>소개</h3><p>동적 그래프 스토리지 시스템은 그래프 데이터가 계속 진화하는 실시간 애플리케이션(e.g. 소셜네트워크, 추천)에 대하여, 중요한 역할을 합니다. 하지만 현재 시스템은 동시에 발생하는 read/write 연산을 효율적으로 다루는데 어려움이 있고, 대표적으로 나타나는 현상은 다음과 같습니다.</p><ul><li>write 쿼리가 read 효율성을 방해</li><li>per-edge versioning 방식 때문에, 공간에 대한 오버헤드가 상당히 발생</li><li>다양한 연산에 대한 성능의 불균형. e.g. 동시성 작업에서는 검색 작업이 느림</li></ul><p>위 문제들을 해결하기 위해, 논문은 읽기 집약적 작업을 위해 설계된 효율적인 in-memory 동적 그래프 스토리지를 제안하며, 아이디어의 핵심은 다음과 같습니다.</p><ul><li>read 쿼리의 관리와 write 쿼리의 관리를 분리</li><li>그래프 데이터로부터 version 데이터 분리</li></ul><p>또한 논문은 그래프 동시성 메커니즘과 협동하기 위해, 효율적인 동적 그래프 스토어를 설계했습니다. 이 글에서는 기존 방법의 문제와 논문에서 제안한 방식 그리고 실험결과를 설명합니다.</p><h3>동기</h3><p>논문은 Sortledton을 언급하며, 기존 방식의 문제점을 설명하고 있습니다. 내용의 이해를 위해 Sortledton를 간략하게 설명하겠습니다. Sortledton은 동적 그래프를 위한 그래프 자료구조로, 각 vertex은 독립적인 이웃 vertex에 대한 sorted set을 갖습니다. vertex마다 개별적인 자료구조를 갖음으로써, 병렬 업데이트에 장점이 있습니다. 또한 edge block이 정렬되어있기 때문에, 읽기 연산도 충분히 효율적입니다.</p><p>하지만 논문에서 32개의 물리코어를 갖는 서버와 그래프 데이터셋인 livejournal(lj)와 graph500(g5)으로 실험한 결과, 3가지의 문제점이 있다는 사실을 발견했습니다.</p><h4>1. 동시 read/write 간의 간섭</h4><p>기존 방식의 경우, read/write 연산은 모두, 두 이웃 vertex 집합 또는 기준 vertex의 속성에 접근하기전에, 기준 vertex 상에서 lock을 반드시 획득해야합니다. 이는 쿼리 사이의 직렬화를 보장하기 위함입니다. 하지만 이는 다수 쿼리가 동일한 vertex에 접근을 시도하려고 할 때, lock 경합을 초래하고 이로인해, read/write에 대한 성능 저하가 발생합니다. 특히, degree가 높은 vertex에서 성능 저하가 크게 발생하는데, 이는 다수의 연결을 갖고 있어, 해당 vertex에 자주 접근되기 때문입니다. 첫번째 문제에 대한 실험 결과는 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/874/1*vZlqJq_y8ZcuF-OV8UNkYw.png" /></figure><p>figure2에서는 read 쿼리(page rank연산)들만 존재함에도, 지연이 높게 나온다는 사실을 알 수 있습니다. 이는 page rank 연산 과정에서, 빈번한 그래프 스캔이 수반되는데, 이 과정에서 메모리 대역폭 압박이 발생하여, 지연에 영향을 미치기 때문입니다. figure3에서는 read 쿼리가 증가 할 수록, write 쿼리(edge 추가)에 대한 처리량이 줄어드는 것을 확인 할 수 있으며, 이는 read/write 쿼리 간의 lock 경합 때문입니다. 따라서 우리는 이 문제를 해결해야합니다.</p><p>그래프 스토리지 시스탬 내의 성능과 확장성을 향상 시키기 위해, read/write 쿼리간의 간섭을 어떻게 완화 할 수 있는가?</p><h4>2.per-edge versioning으로 인한 시간/공간 오버헤드</h4><p>read, write 쿼리를 동시 수행하는 것을 지원하기 위해, 기존 방법은 edge 단위로 version을 관리하기도 합니다. 하지만 version을 갖는 것은 스캔, 검색 연산의 성능을 저하시키니는데, 이는 아래의 실험 결과에서 확인 할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DtAvOeqQcscRSlgftSuJEQ.png" /></figure><p>table 1에서 확인 할 수 있는 것처럼, version이 존재 할 때 스캔, 검색 연산의 처리량이 낮다는 것을 알 수 있습니다. 뿐만 아니라, version을 갖는다는 것 자체가 추가 메모리 사용량을 요구합니다. 따라서, version을 갖으면서, 시간/공간 오버헤드를 줄일 수 있는 방법을 찾아야합니다.</p><h4>3.빠른 검색 연산에 대한 비효율적인 지원</h4><p>그래프 탐색 알고리즘은 이웃 정점을 모두 스캔하는 연산에 강하게 의존합니다. 그래서 기존 방법들은 검색 연산(e.g 패턴 매칭) 대신, 스캔 연산의 성능을 최적화하는데 높은 우선순위를 두고 있습니다. 기존 방법의 검색 성능에 대한 실험 결과는 아래에서 확인 할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/982/1*v5Go1ATGuqVLucENNYoakA.png" /></figure><p>특히, Sortledton 방식은 일반 vertex, 낮은 degree를 갖는 vertex, 높은 degree를 갖는 vertex에 대해서 낮은 처리량을 갖고 있다는 것을 확인 할 수 있습니다. 따라서, 우리는 스캔, 삽인 연산의 성능을 유지하면서, 빠른 검색 연산을 지원하는 효율적인 그래프 데이터 스토어를 어떻게 설계해야 할 지 고민해야합니다.</p><h3>RapidStore 개요</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OUcDnEA88QVHFqzG8iFKuA.png" /></figure><p>RapidStore는 쿼리 실행과 versioning을 위해, 전역적인 logical clock을 사용하며, 직렬화를 보장하기 위해, MV2PL 프로토콜을 사용합니다. 이 때, versioning의 경우, edge 단위가 아닌 sub-graph단위로 진행합니다.</p><p>write 쿼리의 실행 과정은 다음과 같습니다.</p><ol><li>수정될 sub-graph 집합을 식별합니다.</li><li>sub-graph 상에 lock을 획득하여, write 쿼리 사이에서 업데이트 연산이 진행되는 동안, 베타적 접근을 보장합니다.</li><li>copy-on-write 전략을 사용하여, sub-graph의 최신 버전을 새로 생성합니다.</li><li>변경사항을 커밋하고, sub-graph의 최신 상태를 나타내기 위해, clock을 하나 증가시킵니다.</li><li>리소스 확보를 위해, read 쿼리 실행을 기반으로 오래된 version을 제거합니다.</li></ol><p>read 쿼리의 실행 과정은 다음과 같습니다.</p><ol><li>현재 clock 값을 시작 시간으로 잡고, 이 시간과 함께 쿼리를 등록합니다.</li><li>시작 시간을 기반으로 sub-graph들의 적절한 버전들을 선택해서, 스냅샷을 구축합니다.</li><li>쿼리를 완료하기 위해, 스냅샷 상에서 그래프 데이터 접근 연산을 수행합니다.</li><li>실행 완료 후, 쿼리 등록을 해제합니다.</li></ol><p>한편, RapidStore는 빈번한 메모리 할당/해제로 인한 오버헤드를 줄이기 위해, 메모리 풀을 사용합니다.</p><p><strong>이점<br></strong> 이 시스템 디자인의 특징은 write 쿼리 관리와 read 쿼리 관리를 분리한 것인데, 베타적 lock을 통해, 동시 write 쿼리에 대해서도 직렬화를 보장하는 한편, 다수의 read 쿼리에서는 이미 커밋된 스냅샷만 보게함으로써, 동시성을 보장 할 수 있습니다. Sortleton이나 Teseo 방식 또한, read/write 쿼리를 서로 다르게 관리하지만, read 쿼리의 경우 vertex의 이웃 집합 상의 공유 lock 획득을 요구하여, 쿼리 사이의 블로킹을 초래합니다. 반면 RapidStore는 위에서 언급한 방식에 따라, write 쿼리가 실행 중이여도 read 쿼리를 수행 할 수 있으며, 그 반대도 마찬가지입니다.</p><p>versioning을 사용하는 시스템은 필요한 version을 빠르게 찾는 것이 중요합니다. 기존의 edge기반의 versioning 방식은 스냅샷 검색이 느렸는데, 왜냐하면 각 edge에 대하여 전체 그래프를 스캔해서 정확한 버전을 찾고 저장해야했기 때문입니다. 반면 RapidStore는 sub-graph 수준에서 스냅샷을 구성하기 때문에, 각 edge를 개별적으로 스캔하거나 저장할 필요가 없기 때문에 상대적으로 스냅샷 검색을 빠르게 할 수 있습니다. 결과적으로 version 관리와 연관된 시간, 공간 비용을 줄일 수 있습니다.</p><p>그리고 RapidStore는 실행시점에 version 검사를 확인할 필요가 없습니다. 기존 방식은 version, 그래프 데이터가 함께 저장되는데, 결과적으로 그래프 연산이 수행되는 동안, 빈번한 version 검사를 해야합니다. 반면 RapidStore는 version 데이터가 그래프 데이터로부터 분리됐고, coarse-grained versioning을 활용하기 때문에, read/write 쿼리 모두 version 검사를 할 필요가 없습니다.</p><p>그 외, RapidStore의 최적화 그래프 데이터 스토어는 언급된 그래프 데이터 관리와 스캔, 검색, 삽입 연산에 대하여, 일관적인 효율성을 제공합니다. 지금부터는 RapidStore의 핵심 메커니즘에 대해 알아보겠습니다.</p><h3>Sub-graph-Centric Concurrency Control</h3><p>sub-graph 중심의 동시성 제어는 coarse-grained verion 관리, 동시성 제어 프로토콜, GC로 구성됩니다.</p><h4>Coarse-Grained Version 관리</h4><p>시점 t에서 read 쿼리, R이 주어질 때, R은 G_t상에서 read 연산이 수행되어야합니다. 앞서 언급했던 것처럼 edge 기반의 versioning은 정확한 version을 찾고 저장하기 위해, 모든 edge를 스캔해야하며, 이는 시간적, 공간적 오버헤드를 초래합니다. 이 문제를 다루기 위해, RapidStore는 sub-graph 수준에서 version을 관리하며, 이를 위해 그래프 G를 vertex 기반으로 파티셔닝합니다. 각 파티션의 크기는 서로 같습니다. 예를들어 G에 존재하는 vertex 개수가 64이고, 파티션 크기를 4로 정한다면, 하나의 파티션에는 16개의 vertex가 존재합니다. 그리고 하나의 파티션의 있는 vertex와 각 vertex에 인접한 edge가 하나의 sub-grpah를 구성합니다.</p><p>RapidStore는 단순한 파티셔닝 전략을 취합니다. |P| vertex들의 연속적인 block을 각 파티션에 할당합니다. 앞의 예제를 바탕으로 설명하면, 0~3 vertex들과 이들의 edge들은 sub-graph1에 4~7 vertex들과 이들의 edge들은 sub-graph2에 8~15 vertex, 이들의 edge는 sub-graph3에 할당되는 방식으로 진행됩니다. 그림으로 단순하게 표현하면 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zhD2YRX1aL1gFqB1mj7g9Q.png" /></figure><p>RapidStore는 각 sub-graph의 version 체인을 관리하며, 이 때 최신 version은 이전 version을 가리킵니다. 그리고 각 version은 이에 대응되는 sub-graph 스냅샷을 가리키며, 결과적으로 그래프 데이터로부터 version 데이터가 효과적으로 분리됐습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/321/1*BHUhvx54GEfweEzvz75hbA.png" /></figure><h4>동시성 제어 프로토콜</h4><p>기존 방법의 경우, read/write 쿼리 모두 vertex 상에서 lock을 획득해야했기 때문에, 결과적으로 동시성이 떨어질 수 밖에 없습니다. RapidStore의 경우 read 쿼리 관리와 write 쿼리 관리를 분리했는데, 각각을 살펴보겠습니다.</p><p><strong>write 쿼리<br></strong> write 쿼리에서는 MV2PL(Multi Version Two Phase Lock)을 사용합니다. write 쿼리, W0에서 vertex들을 업데이트한다면, 우선 이 vertex들을 갖고 있는 sub-graph들을 식별해야합니다. 그리고 sub-graph 상에서 lock을 획득해야하는데, 이 때 write 쿼리 간에 dead lock이 발생하지 않도록, sub-graph의 ID 오름차순으로 lock을 획득합니다. 이후 sub-graph에 대한 최신 스냅샷을 바탕으로 vertex들을 수정 후, 새로운 스냅샷을 생성합니다.</p><p>read/write 쿼리들을 조정하고, 일관성을 유지하기 위해, 2개의 타임스탬프를 사용합니다. 하나는 write를 위한 전역 타임스탬프(t_w)로, write 쿼리 커밋의 순서를 추적합니다. 다른 하나는 read를 위한 전역 타임스탬프(t_r)로, read 쿼리가 사용 할 수 있는 최신 스냅샷을 가리킵니다. W0의 커밋단계에서, t_w를 원자적으로 하나 증가시킨 후, 그 값을 W0의 로컬 타임스탬프에 할당합니다. 그러면 W0는 로컬 타임스탬프 값을 수정된 sub-graph의 version에 할당하고, 이를 version 체인의 head에 연결합니다. 한편 t_r의 경우, 값이 t-1이라면, t_r의 값을 원자적으로 하나 증가시킵니다.</p><ul><li>clock에 대한 더 이상의 언급이 없는데, 글의 맥락만 놓고보면, t_w + 1의 값으로 업데이트 되는 것 같습니다.(의견)</li></ul><p>결과적으로, write 쿼리가 커밋 타임스탬프 기반의 직렬화 순서대로 커밋이 이루어지는 것을 보장하고, read 쿼리의 경우 t_r을 바탕으로 일관성 있는 스냅샷에 접근 할 수 있습니다. 커밋 이후 W0에서는 쓸모없는 version들을 제거하고 lock을 해제합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/832/1*PZaTQLQs1otExmyOiBrung.png" /></figure><p><strong>read 쿼리<br></strong> read 쿼리들은 sub-graph 스냅샷 상에서 lock을 필요로하지 않기 때문에, write 쿼리에 영향을 미치지 않고, 다른 read 쿼리에 의해 block 되지 않아, 결과적으로 높은 동시성을 보장합니다. 활성화된 read 쿼리들을 추적하기 위해, RapidStore는 read tracer를 도입했습니다. read tracer는 8-byte 정수를 원소로 갖는 배열이며, 각 정수의 가장 높은 비트는 slot의 활용 여부이며, 나머지 비트들은 read 쿼리의 타임스탬프를 저장합니다. 배열의 개수는 cpu 코어 수만큼 설정하면 됩니다. read tracer는 read 쿼리 추적용이기 때문에 먼저 read 쿼리를 tracer에 등록해야합니다. 과정은 다음과 같습니다.</p><ol><li>가장 높은 비트에서 slot이 활용되고 있는지 확인하고, 빈 슬롯이면 해당 슬롯에 read 쿼리를 등록합니다.</li><li>슬롯 사용에 대한 비트 값을 1로 설정하고, clock으로부터 시작 타임스탬프를 설정합니다. i.e. 나머지 비트들에 할당</li></ol><p>read 쿼리를 tracer에 등록하는 연산 CAS 방식으로 이루어지며, 등록 후, read 쿼리는 sub-graph의 version들 중, 적절한 스냅샷을 가져옵니다. 앞서 read 쿼리는 lock을 필요로하지 않는데, 그 이유는 다음과 같습니다.</p><ul><li>시작 타임스탬프는 커밋된 sub-graph 스냅샷만 read 쿼리에 제공됨을 보장합니다.</li><li>write 쿼리는 copy-on-write를 통해, 새로운 sub-grpah 스냅샷을 생성하는데, 이 작업은 기존 스냅샷에는 영향을 미치지 않습니다.</li></ul><p>read 쿼리 작업이 완료되면, slot을 반환하는데, 슬롯 사용에 대한 비트를 0으로 설정하고, 나머지 비트를 최대 값으로 설정합니다.</p><h4>Garbage Collection</h4><p>write 쿼리에서 수행하며, 쓸모 없는 version을 제거합니다. 수행 과정은</p><ol><li>write 쿼리는 read tracer를 스캔해서, 모든 활성화된 reader의 타임스탬프를 수집합니다. 다른 쿼리를 block 시키지 않기 위해, 각 값은 원자적 연산을 통해 가져옵니다.</li><li>수집된 시작 타임스탬프 기반으로, 수정된 sub-graph의 version 체인들을 보고, 과거 version을 제거할지 말지 결정합니다.</li></ol><p>결과적으로 GC가 수행되는 조건은 최신이 아니면서 tracer 내 활성화된 모든 read 쿼리가 더 이상 사용하지 않는 version이라고 보면 될 것 같습니다.</p><h3>Multi-Version Graph Store</h3><p>동시성 read/write 쿼리를 효율적으로 달성하기 위해, 그래프 스토어는 2가지 핵심사항을 만족해야합니다.</p><ol><li>업데이트 시, 빠른 sub-graph 스냅샷을 생성해야합니다. 이는 sub-graph 중심의 동시성 제어를 지원하고, 동시성 쿼리의 정확성을 보장하기 위함입니다.</li><li>그래프 쿼리는 “vertex-neighbor” 접근 패턴을 따르기 때문에, 스토어는 반드시 vertex의 이웃들을 효율적으로 검색 할 수 있어야하고, 스캔, 검색, 삽입 연산을 빠르게 수행하기 위해 지원해야합니다.</li></ol><p>이를 위해, RapidStore는 read 쿼리가 write 쿼리에 의해 영향을 받지 않으면서, sub-graph S를 업데이트하기 위해, copy-on-write 방식을 취합니다. 아래의 그림을 예시로 설명드리겠습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/858/1*2_Ty8wS5rj0z9Gsb0TimBw.png" /></figure><p>t_w가 2일 때, W0는 e(1, 6)을 추가하려고 합니다. 그러면, sub_graph0이 영향받고, sub-grpah에 대한 0번 인덱스에 접근하여, 최신 version을 얻습니다. 각 version은 vertex index들을 갖고 있고 각 index는 이웃 vertex들을 저장하는 radix tree를 가리킵니다. 여기서 radix tree가 언급됐는데, 이 자료구조에 대해 간략하게 알아보겠습니다.</p><h4>Radix tree</h4><p>radix tree는 메모리 최적화된 트라이 자료구조로도 알려져있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UQYhIJV4uy5_2RcmjFbYoQ.png" /></figure><p>일반적으로 trie 자료구조는 하나의 edge(또는 node)에 하나의 문자를 갖습니다. 세상에 존재하는 단어 개수를 생각해보면, 결과적으로 trie 자료구조는 많은 메모리를 사용 할 수 밖에 없습니다. 이 문제를 다루기 위해, radix tree는 하나의 edge(또는 node)에 공용 prefix를 갖음으로써, 메모리 사용량을 절약할 수 있습니다. radix tree의 검색, 삽입 연산에 대한 시간 복잡도는 O(K)로 K는 문자열 길이입니다.</p><p>다시 본론으로 돌아와서, radix tree의 특성으로 인해, 공용 prefix를 갖는 vertex들은 동일한 leaf node에 존재하는 것을 확인 할 수 있습니다.</p><ul><li>leaf node1에는 vertex 0, 2가 존재하는데, 각각을 4-bit로 해석하면 0000, 0010으로 표현되며 여기서 앞의 두 비트, 00이라는 공용 prefix를 갖고 있다는 것을 알 수 있습니다.</li><li>leaf node2의 경우 vertex 6, 7이 존재하는데, 각각을 4-bit로 해석하면 0110, 0111로 표현되며, 여기서 앞의 두 비트 01이라는 공용 prefix를 갖고 있다는 것을 알 수 있습니다.</li></ul><p>새로운 edge를 삽입하는 연산은 copy-on-write 연산을 일으키며, 영향을 받는 radix-tree 경로가 복제됩니다.(from leaf to root)</p><p>위에서 언급된 단순한 파티셔닝을 통해, sub-graph를 구성하는 vertex는 연속적인 공간에 저장되며, 결과적으로 vertex ID로 이웃 vertex를 찾는 연산의 시간복잡도가 O(1)입니다.</p><p>한편, 현실 세계에서는 high-degree vertex도 존재하고 low-degree vertex도 존재합니다. RapidStore는 각각 다른 자료구조로 다루며 구체적으로</p><ul><li>high-degree vertex는 tree 구조로 다루며, 구체적으로 Compressed Adaptive Radix Tree를 사용합니다.</li><li>low-degree vertex는 작은 배열로 다뤄지며, 메모리 최적화를 위해 향후 tree로 그룹화 될 수 있습니다.</li></ul><h4>Compressed Adaptive Radix Tree</h4><p>Radix Tree는 trie에 비해 메모리 효율적이지만, 많은 자식 포인터들이 사용되지 않는다면, 여전히 낭비를 유발합니다. 이를 해결하기 위해 Adaptive Radix Tree(이하 ART)는 자식 노드 수에 따라 노드의 크기를 동적으로 조절합니다. ART의 특징은 다음과 같습니다.</p><ul><li>byte 시퀀스를 통해, key들을 색인해서 radix tree를 구축합니다.</li><li>크게 4개의 node 타입으로, N4, N16, N48, N256이 있으며, 뒤에 숫자는 갖을 수 있는 자식 포인터 개수를 의미합니다. 주어진 그래프에 대하여, 각 vertex마다 적절한 node 타입을 고르면 됩니다.</li><li>각 leaf node는 vertex를 갖고 있습니다.</li><li>N4 node는 4개의 (키, 포인터) 쌍을 갖고, N256은 오직 포인터만 저장하면 포인터 배열의 인덱스는 키를 암시합니다.</li><li>경로 압축이 발생하여, 노드들이 제거 될 수 있고, 이에 따라 tree의 depth가 낮아질 수 있습니다. 예를들어, 단 하나의 문자열 “FOO”만 존재한다면, 기존 radix tree F -&gt; O -&gt; O를 ART에서는 이를 압축하여, FOO로 압축합니다. 이후 FOX, FOOD 같은 “FO”라는 공용 prefix가 온다면, tree 경로를 확장합니다.</li></ul><p>ART의 예시는 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*ZL5nhrDVdzBJig00bJHTxA.png" /></figure><p>결과적으로 자식 포인터를 동적으로 조절 할 수 있다는 장점이 있지만, 여전히 high-degree vertex, low-degree vertex에 대응하지 못하여, 각 세그먼트 내 차지하고 있는 실제 vertex 비율이 낮을 수 있습니다. 이를 보완하기 위해 RapidStore는 Compressed Adaptive Radix Tree(이하 C-ART)를 만들어, leaf들을 압축했고, 그 결과 Adaptive Radix Tree 대비 더 높은 압축율을 보여줬습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/810/1*CZf8e882z3xzK91rzC-SNQ.png" /></figure><p>여기서 ratio는 각 세그먼트 내 실제 차지하고 있는 vertex에 대한 비율입니다.</p><p>한편, 그래프 탐색시 이웃 vertex들을 스캔하기 때문에, 하나의 leaf node에 하나의 이웃 vertex를 갖고 있는 것은 비효율적입니다. 기존 adaptive radix tree는 이 구조를 취하고 있는 반면 RapidStore의 C-ART는 하나의 leaf에 다수 이웃 vertex들을 갖고 있습니다. RapidStore에서 사용하는 tree는 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/862/1*J91TuXoVwPhfqcZ5eD26og.png" /></figure><p>하나의 leaf는 leaf 내 모든 vertex의 최대 공통 접두사(Longest Common Prefix, 이하 LCP)에 의해 정의되며 leaf의 depth는 LCP의 길이입니다. 예를들어 leaf3의 경우, LCP가 0x0102로 2개의 바이트를 갖고 있기 때문에, leaf3의 depth는 2입니다. 여러 키를 갖는 leaf들이 하나의 leaf로 압축됐기 때문에, 한 node안에 있는 다수의 키에서 동일한 leaf를 가리킬 수 있습니다.</p><p>결과적으로 leaf 상의 압축을 통해 스캔 성능을 향상 시키고, 메모리 소비를 줄일 수 있습니다.</p><p>다음은 C-ART 상에서의 검색, 스캔, 삽입 연산 과정을 설명합니다.</p><p>Search(u, v)<br> 연산을 수행하며 u의 이웃 v를 찾는 것입니다. v의 byte 시퀀스를 기반으로 C-ART node들을 탐색하며, 이 때 binary search가 사용됩니다.</p><p>Scan(u)<br> DFS를 이용하여, u를 찾습니다. leaf 안에 vertex들이 연속적으로 저장됐기 떄문에, 순차 메모리 접근을 가능하게 합니다. 따라서 그래프 분석 쿼리에도 유리합니다.</p><p>Insert(u, v)<br> v를 u의 이웃으로 추가하는 연산이며, search(u, v)를 수행한 후, 적절한 leaf에 추가합니다. 논문에서는 하나의 leaf에 256개의 vertex를 갖는 것으로 설명하고 있는데, 그러면 leaf가 갖는 vertex 개수에 따라 3가지 경우가 발생합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/876/1*PsywVzQRZZQkEu9uVP92Sw.png" /></figure><p>Delete(u, v)<br> u의 이웃 v를 제거하는 연산으로, search(u, v)이후 v를 삭제합니다. 삭제 후, leaf가 갖는 vertex의 개수가 절반 이하라면, 향후, 동일한 depth의 이웃 leaf와 합쳐지게 될 것입니다.</p><p>C-ART의 그림을 보면 서로 다른 2개의 bitmap을 볼 수 있는데, 각 역할은 다음과 같습니다.</p><ul><li>하나의 leaf에서 LCP 기반으로 vertex들을 갖다보니, vertex ID의 마지막 byte만 다른 경우가 있을 수 있습니다. 이 경우, vertex는 bitmap으로 저장됩니다.</li><li>node 당 256개의 자식 포인터를 갖을 수 있고, 여기서 대부분은 비어 있을 수 있습니다. 이러한 오버헤드를 방지하기 위해, 실존하는 자식 포인터를 기록합니다. 이후 AVX2 instruction을 사용하여, 비어있는 포인터를 우회 할 수 있습니다.</li></ul><h4>Clustered Index</h4><p>low-degree vertex의 경우, C-ART를 사용하는 것이 의미없습니다. 왜냐하면 C-ART의 depth는 vertex ID 길이에 의존하는데, 이웃들이 없으면 depth가 낮기 때문에, 굳이 사용할 필요 없습니다. 대신, B+ tree로 clustered index를 사용하며, 키는 edge 쌍, e(u, v)입니다. edge 쌍은 순차 접근을 위해 연속적으로 저장됩니다.</p><p>low-degree vertex이기 때문에, 일반적으로 clustered index의 크기는 작아(일반적으로 2 depth), 그래프 접근 연산이나 업데이트가 효율적으로 수행될 수 있습니다.</p><h3>실험</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/808/1*-hJB_hP9kFAch55lgov_aA.png" /></figure><p>Hyperparameters</p><ul><li>파티션 크기: 64</li><li>Leaf내 vertex 개수: 512</li><li>256GB 램, 61.2 메모리 대역폭, 60mb L3 캐시를 갖는 32cores</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fvGj5PaP_gQSDaTOfx6xzw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/818/1*4T-ZXcNhyupHYhKR6u4NeQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*Fjk9CwmTRNWgAYqXLOuPzw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/874/1*0-hhOqLLDAjLeVQv4kS0UQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/1*pPZ7f2fV7z2Pybwhz5vGPA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/874/1*tqecCwofo-abQ-OqUsNuVA.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b43f4654c985" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores 논문 리뷰]]></title>
            <link>https://medium.com/@workspaceforice/delta-lake-high-performance-acid-table-storage-over-cloud-object-stores-%EB%85%BC%EB%AC%B8-%EB%A6%AC%EB%B7%B0-3cfdda8cb336?source=rss-db62e036d783------2</link>
            <guid isPermaLink="false">https://medium.com/p/3cfdda8cb336</guid>
            <dc:creator><![CDATA[Giyoon Park]]></dc:creator>
            <pubDate>Tue, 24 Feb 2026 05:50:32 GMT</pubDate>
            <atom:updated>2026-02-24T08:51:40.105Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://www.vldb.org/pvldb/vol13/p3411-armbrust.pdf">https://www.vldb.org/pvldb/vol13/p3411-armbrust.pdf</a> 논문을 읽고 리뷰하는 포스트입니다.</p><h3><strong>개요</strong></h3><p>클라우드 오브젝트 스토어(e.g. S3)는 데이터를 대규모로 저장하고, 비용이 저렴하지만, 트랜잭션과 메타데이터 연산(e.g. 오브젝트 나열) 같은 고성능을 보장하지 않습니다.</p><p>이러한 한계를 극복하기 위해, Databricks는 클라우드 오브젝트 스토리지 상에 존재하는 ACID 테이블 스토리지 레이어를 만들고 이를 오픈소스로 공개했습니다. 이 오픈소스가 바로 Delta Lake입니다.</p><p>뿐만 아니라, Delta Lake는 이외에도 원자적 데이터 레이아웃 최적화, upsert, 캐싱, 감사 로그, time travel, 스트리밍 I/O같은 기존 클라우드 스토어에서 제공하지 못하는 고수준 기능도 제공하며, 결과적으로 파이프라인을 다음과 같이 (a) -&gt; (b)로 개선 할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/547/1*rRwHPzJRrcRtAW_rIo23Vg.png" /></figure><p>한편 테이블은 아파치 스파크, 하이브, 프레스토등 다양한 실행 엔진을 통해 접근 될 수 있습니다. 그렇다면 Delta Lake를 구성하는 요소들을 살펴보고, 이 요소들이 어떻게 트랜잭션을 보장하는지 설명하겠습니다.</p><h3><strong>Delta Lake Storage Format And Access Protocols</strong></h3><p>하나의 Delta Lake 테이블은 클라우드 오브젝트 스토어에 있는 디렉토리이며, 테이블 내용을 담고 있는 데이터 오브젝트와 트랜잭션 연산 로그(또는 체크포인트)를 갖고 있습니다. 예시는 아래의 figure와 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/519/1*aagmf3FNhc51UNLRJpHN8g.png" /></figure><p>클라이언트는 낙관적 동시성 제어를 활용하여, 데이터들을 업데이트하는데, 스토리지 포맷과 액세스 프로토콜은 각 절에서 구체적으로 살펴보겠습니다.</p><h4>a. Storage Format</h4><p>테이블은 파일 시스템 디렉토리 내 저장 될 수 있고, 또는 오브젝트 스토어 안에서, 같은 디렉토리 키를 prefix로 시작하는 오브젝트로써 저장 될 수 있습니다. 데이터 오브젝트는 parquet 포맷으로 저장 될 수 있습니다. 다른 오픈소스 포맷도 존재하지만, 논문에 따르면 테이블이 날짜 기준으로 파티셔닝되어, 데이터 오브젝트들이 날짜를 기반으로 개별 디렉토리에 저장된 점을 생각해보면, parquet는 칼럼 지향적이고, 다양한 압축을 지원, 반구조화에 대한 nested data type 지원 그리고 많은 엔진들이 이 포맷을 읽을 수 있기 때문에, parquet 포맷을 스토리지 포맷으로 선택해서 설명하고 있습니다. 한편, Delta에 존재하는 각 데이터 오브젝트는 고유한 이름을 갖을 수 있으며, writer가 GUID로 생성 할 수 있습니다.</p><h4>b. Log</h4><p>트랜잭션 로그는 테이블의 각 버전에 존재할 데이터 오브젝트를 결정합니다.<br>로그는 _delta_log 하위 디렉토리에 안에 저장되며, JSON 오브젝트의 시퀀스를 포함합니다. JSON object는 로그 레코드와 체크포인트를 저장하기 위해 0-padding이 적용된 증가하는 방향의 ID를 갖습니다.</p><p>각 로그 레코드 오브젝트는 액션의 관한 배열을 포함합니다. 이 배열을 테이블의 이전 버전에 적용하여, 다음 버전을 생성 할 수 있습니다. 가용한 액션는 다음과 같습니다.</p><p><strong>Change Metadata<br></strong> 이 메타데이터 관련 액션는 테이블의 현재 메타데이터를 변경합니다. 이후의 메타데이터 관련 액션는 현재의 메타데이터를 완전히 overwrite 합니다.</p><p>여기서 메타데이터가 언급됐는데, 간단하게 설명드리면 스키마, 파티션 칼럼 이름(예제의 경우 날짜), 기타 구성(e.g. append-only로 테이블 마킹)등을 포함하는 자료구조입니다.</p><p><strong>Add or Remove Files<br></strong> 추가/삭제 액션는 테이블 안의 데이터를 modify하는데 사용되는 액션입니다. 이 액션을 이용하여, 클라이언트는 액션과 관련된 로그를 찾아서, 테이블에 존재하는 모든 추가된 오브젝트를 찾아서, 테이블을 구성하는 오브젝트 집합을 결정 할 수 있습니다.</p><p>추가 액션에 대한 레코드의 경우, 데이터 통계를 포함 할 수 있습니다. 예를들어, 전체 레코드 개수, 칼럼당 최대/최소 값 , null 개수가 있습니다.</p><p>삭제 액션의 경우, 레코드가 언제 제거됐는지 알 수 있는 타임스탬프 정보를 포함하고 있습니다. 이를 활용하여, 클라이언트는 한 레코드에 대하여, 삭제 액션이 발생했지만, 물리적으로 그 레코드가 남아있는 경우에 대응 할 수 있습니다. 다시 말해, 삭제 액션에 대한 레코드는 데이터 오브젝트가 삭제될 때 까지, 반드시 로그 또는 체크포인트에 tombstone으로 남아있어야합니다.</p><p>동일한 레코드 안에서, 다른 액션와 같이 사용할 때, 추가/삭제 액션같은 dataChange 플래그를 설정을 false로 하여, 해당 액션을 생략하고, 기존 데이터 재배열, 통계 추가만을 할 수 있습니다. 예를들어, 로그를 tail하는 스트리밍 쿼리는 이 옵션을 활용해서 추가/삭제 액션을 생략 할 수 있습니다.</p><p><strong>Add Provenence Information<br></strong> 각 로그 오브젝트는 commitInfo 액션에서, 출처 정보를 포함하고 있습니다. 따라서, 어떤 사용자가 이 연산을 했는지 로그를 통해 알 수 있습니다.</p><p><strong>Update Application Transaction<br></strong> Delta Lake는 애플리케이션이 그들의 데이터를 레코드에 포함시키는 것을 허용해서, E2E 트랜잭션을 지원하는 애플리케이션을 구현 할 수 있습니다. 구체적으로, 애플리케이션이 로그 레코드 안에, appId와 버전을 갖는 custom txn 액션에 관한 write를 할 수 있습니다.</p><h4>c. Log Checkpoints</h4><p>성능을 위해, 로그는 주기적으로 체크포인트로 압축되어야합니다. 체크포인트는 parquet로 저장되는데 , 이 때 테이블 로그, 특정 로그 레코드 ID가 포함됩니다. 액션는 중복 될 수 있지만, 제거 될 수 있습니다. 체크포인트는 구체적으로 다음을 수행합니다.</p><ul><li>동일한 데이터에 대하여, add 후 remove 액션이 일어난다면, add 액션은 제거하고, remove 액션은 유지합니다.</li><li>동일한 데이터에 대한, 다수의 add 액션이 일어난다면, 이들은 모두 마지막 연산으로 대체됩니다. 왜냐하면, 새로운 데이터는 단순히 통계만 추가하기 때문입니다.</li><li>동일한 appId로부터 다수의 트랜잭션 액션은최신 것으로 대체됩니다.</li><li>changeMetadata, protocol 관련 액션들도 가장 최신의 metadata만 남습니다.</li></ul><p>결과적으로, 체크포인트에 대한 parquet 파일은 오브젝트(테이블에 실재로 존재하는)의 add 레코드, 그리고 나중에 지워질 remove 레코드, txn, protocol, changeMetadata 등의 작은 레코드들을 포함합니다.</p><p>이 체크포인트를 사용해서 한 쿼리에서 오브젝트를 읽는 속도는, list 연산, parquet 파일의 footer를 읽어서 오브젝트를 읽는 속도보다 대부분의 경우에 빠릅니다.</p><p>마지막으로, 최신 체크포인트는 _delta_log/_last_checkpoint에 존재하는데, eventual consistency로 마지막 체크포인트가 최신화되지 않을 수 있습니다.</p><h4>d.Access Protocols</h4><p>Delta Lake의 액세스 프로토콜은 클라이언트가 오직 오브젝트 스토어에서 제공되는 연산만을 활용하여 직렬화 가능한 트랜잭션을 달성하도록 설계됐습니다. 이게 되는 이유는 버전과 관련있는 로그레코드입니다.</p><p>버전을 활용하여, 클라이언트는 오브젝트 스토어로부터, 다른 오브젝트를 읽을 수 있고, eventual consistency로 볼수 없는 오브젝트에 때문에 지연이 발생 할 수 있고, 테이블 데이터를 읽을 수 있습니다.</p><p>write를 수행하는 트랜잭션의 경우, 클라이언트는 단 하나의 writer만 이용해서 다음 로그 레코드를 만든 후, 이 레코드를 활용하여 낙관적 동시성 제어를 구현 할 수 있습니다.</p><p><strong>Reading from Tables<br></strong> 이 절에는 Delta Lake에대하여, read-only 트랜잭션을 수행하는 방법에 대해 설명하겠습니다. 이 트랜잭션의 역할은 테이블의 버전을 안전하게 읽는 것입니다. read-only 트랜잭션은 다음의 5가지 스텝으로 이루어져 있는데,</p><ol><li>테이블 로그 내에, 마지막 체크포인트 오브젝트를 읽어서, 만약 존재한다면 그 체크포인트 ID를 얻습니다.</li><li>만약 존재한다면, 시작 키가 마지막 체크포인트 ID를 갖는, list 연산을 사용하고, 새로운 json, parquet 파일을 찾습니다. 이들은 리스트 파일을 제공하는데, 이 파일은 최신 체크포인트부터 시작하는 테이블의 상태를 재구성하는데 사용 될 수 있습니다. 그리고 체크포인트ID가 존재하지 않는다면 0을 반환합니다.</li><li>이전 단계에서 식별된 체크포인트, 후속 레코드를 활용하여 테이블 상태를 재구성하는데, 주 대상은 remove 레코드를 갖지 않고, add 레코드를 갖는 데이터 오브젝트, 관련 통계입니다. 이 작업은 병렬로 수행될 수 있습니다. (e.g. spark connector를 활용해서, parquet 파일과 로그 오브젝트 읽는 경우)</li><li>통계를 활용하여, 읽기 쿼리에 대하여, 관련 있는 데이터 오브젝트 파일 집합을 식별합니다</li><li>관련 데이터 오브젝트를 읽기위해, 오브젝트 스토에어 질의합니다. 이 작업은 클러스터 안에서 병렬로 처리 될 수 있습니다. eventually consistency 때문에, 워커노드에 아직 데이터가 없어, 쿼리 플래너가 찾지 못할 경우, 조금 기다렸다 다시 시도합니다.</li></ol><p>각 단계에서, eventual consistency 이슈를 감내하도록 설계한 것을 알 수 있습니다.</p><p><strong>Write Transaction<br></strong> write 트랜잭션의 경우 5가지 단계에 걸쳐 처리됩니다.</p><ol><li>최신 로그레코드 ID를 식별합니다. 찾는 방법은 read-only 트랜잭션과 동일합니다. 여기서 최신 레코드 ID를 r이라고 가정하겠습니다. 이후 트랜잭션은 필요하다면, 테이블 버전 r에서 데이터를 읽습니다. 그리고 r + 1의 ID를 갖는 로그 레코드를 write하려고 시도합니다.</li><li>필요하다면 테이블 버전 r에서 데이터를 읽는데, 방법은 read-only 트랜잭션과 동일합니다.</li><li>새로운 데이터를 write합니다. 트랜잭션은 데이터 디렉토리에 있는 새로운 파일에 테이블을 추가하는 것을 목표로하며, GUID를 사용하여 오브젝트 이름을 생성합니다. 결국 이 오브젝트들은 새로운 로그 레코드 안에서 참조될 준비가 되어있습니다.</li><li>어떠한 클라이언트들도 로그 오브젝트에 write 연산을 하지 않았다면, 트랜잭션의 로그 레코드를 r + 1.json 오브젝트에 write 합니다. 이 단계는 원자적이여야합니다. 만약 실패한다면 쿼리 시맨틱에 따라, 트랜잭션은 재시도 될 수 있습니다.</li><li>(선택) 로그 레코드 r+1에 대한 parquet 체크포인트를 write합니다. write가 완료되면, _last_checkpoint 파일을 업데이트하여, 체크포인트가 r+1을 가리키도록 합니다.(기본 구현은 10개마다 하나의 새로운 체크포인트가 만들어지도록 구현됐습니다.)</li></ol><p>마지막 단계가 성능에 영향을 미칩니다. (e.g. 작은 변경사항들이 자주 커밋되는 경우) 그리고 write 트랜잭션 과정에서 클라이언트 실패가 어느곳에서 발생하든, 데이터는 corrupt 되지 않습니다. 왜냐하면 4번째 단계가 성공하다면, 트랜잭션은 원자적으로 커밋하기 때문입니다.</p><p><strong>Adding Log Records Atomically<br></strong> 4번째 단계에서 r+1.json 로그 레코드 오브젝트를 생성하는 것은 원자적으로 이루어져야합니다. 다시 말해, 오직 하나의 클라이언트만 이 이름으로 생성 할 수 있어야합니다. 하지만 모든 대규모 스토리지 시스템이 원자적 put-if-absent 연산을 지원하는 것은 아니기 때문에, Delta Lake는 다음의 다른 스토리지 시스템에 대하여, 다른 방식으로 이 과정을 구현했습니다.</p><ul><li>구글 클라우드 스토리지와 애저 블롭은 원자적 put-if-absent를 지원합니다. 따라서 이것을 그대로 활용합니다.</li><li>HDFS의 경우, 원자적 rename 연산을 활용하여, 임시파일의 이름을 변경합니다(e.g. 000004.json). 만약 변경된 이름이 이미 존재한다면, 이 rename 연산은 실패합니다. 애져 데이터 레이크 스토리지 역시 원자적 rename 연산을 위한 API를 제공하는데, 이를 활용합니다.</li><li>AWS S3 원자적 put-if-absent 또는 rename 연산을 지원하지 않기 때문에, Databricks는 별도의 경량화 코디네이션 서비스를 사용하여, 오직 하나의 클라이언트가 각 로그 ID를 갖는 하나의 레코드를 추가하도록 보장합니다.</li></ul><h4>Available Isolation Levels</h4><p>Delta Lake의 동시성 제어 프로토콜로, 모든 wirte 트랜잭션 연산은 직렬화되어, 로그 레코드 ID가 증가하는 방향으로 나아갈 수 있습니다. read 트랜잭션도 테이블의 한 스냅샷만 읽어서, 직렬화를 달성 할 수 있습니다. 더 나아가, 클라이언트가 서로 다른 직렬화 트랜잭션 사이의 read 연산 실행을 원한다면, dummy write 수행을 포함하는 read-write 트랜잭션을 수행해서, 이를 달성 할 수 있습니다. Delta Lake는 테이블의 최신 로그 레코드를 메모리 상에 캐싱하는 것을 구현했는데, 이 덕분에 클라이언트는 스냅샷 격리 상황 속에서도, 본인이 write한 결과를 읽을 수 있고, 다수의 read를 수행할 때, 테이블 버전을 적어도 단조 증가하는 방향으로 읽을 수 있습니다.</p><p>여기서 중요한 사실은 오직 한 테이블에서만 트랜잭션을 지원한다는 것입니다.</p><h4>Transaction Rates</h4><p>Delta Lake의 write 트랜잭션 연산 속도는 새로운 로그 레코드를 write하기 위한 put-if-absent 연산에 의한 지연때문에 제한됩니다. 낙관적 동시성 제어에서, write 트랜잭션 연산 속도가 빠르면, 커밋이 높은 확률로 실패합니다. 따라서, 연산 속도를 제한해야했지만, 그 정도의 속도는 현재 모든 Delta Lake 애플리케이션을 구동하는데 충분한 속도입니다.</p><p>반면 read 트랜잭션 연산은 경쟁이 없기 때문에, 속도에 제한받지 않습니다.</p><h3>Performance Expriment</h3><p>이 절에서는 오픈소스 빅데이터 시스템 상에 존재하는 수 많은 오브젝트 또는 파티션을 갖는 테이블의 영향과 선별된 쿼리 워크로드 상에서 z-order의 영향을 연구합니다. 참고로 전자의 경우, 메타데이터와 통계를 체크포인트 안에서 중앙화하는 동기가 됐습니다.</p><p>뿐만 아니라, TPC-DS 상에서 parquet와 Delta Lake에서 개선된 쿼리 성능을 비교합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1014/1*3FHT0of_6gasJC4gkNTaGQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1014/1*c5fKt0liL80OVfsBmlVNFQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/992/1*3f0lJYL9xwthWFRzou-YmQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1016/1*zVC2quvjTak6EYrWIb3IXg.png" /></figure><h3>Discussion And Limitation(20년에 발표된 논문 고려)</h3><p>Delta Lake는 클라우드 스토리지 상에서 트랜잭션이 보장되는 이점이 있지만 한계도 존재합니다. 각 테이블은 그들 고유의 트랜잭션 로그를 갖기 때문에, 단일 테이블 내에서의 트랜잭션만 보장합니다. 다수의 테이블에 걸쳐 트랜잭션 로그를 공유 할 수 있지만, 낙관적 동시성 제어 내에서 경쟁을 심화 시킬 수 있습니다.</p><p>스트리밍 워크로드의 경우, 클라우드 스토리지 때문에(e.g. 관련 연산), 지연의 영향을 받는다는 점이 있지만, 엔터프라이즈에서는 클라이언트는 잡을 병렬로 돌리기 때문에, 이 지연은 어느정도 수용 할 수 있습니다.</p><p>마지막으로 Delta Lake는 보조 색인을 지원하지 않는 한계가 있습니다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3cfdda8cb336" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Graph-R1 논문 리뷰]]></title>
            <link>https://medium.com/@workspaceforice/graph-r1-%EB%85%BC%EB%AC%B8-%EB%A6%AC%EB%B7%B0-531b6a3257d0?source=rss-db62e036d783------2</link>
            <guid isPermaLink="false">https://medium.com/p/531b6a3257d0</guid>
            <dc:creator><![CDATA[Giyoon Park]]></dc:creator>
            <pubDate>Mon, 27 Oct 2025 15:58:28 GMT</pubDate>
            <atom:updated>2025-10-27T16:09:24.675Z</atom:updated>
            <content:encoded><![CDATA[<p>이 포스트는 <a href="https://arxiv.org/abs/2507.21892">Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning</a>을 리뷰합니다.</p><h3>이 논문은 무엇을 해결하는가</h3><p>이 논문은 GraphRAG의 한계를 보완합니다. 논문에 따르면, GraphRAG는 지식을 개체-관계 그래프로 모델링함으로써, 시맨틱을 구조적으로 표현 할 수 있는 장점이 있지만, 다음의 단점도 존재합니다.</p><ul><li>비싼 그래프 구축 비용</li><li>단 한 번만 수행되는 검색</li><li>답변 생성 시, 지나치게 긴 컨텍스트와 프롬프트 설계에 의존</li></ul><p>그래프 구축 시, LLM을 이용하여 문서 내 존재하는 문장들로부터 개체와 관계를 추출 후, 그래프를 구축하는데 이는 비용이 굉장히 큽니다. 그리고 종종 원본에 비해, 상대적으로 의미론적 손실이 발생합니다.</p><p>GraphRAG의 검색 단계의 경우, 기존에 존재하는 GraphRAG는 효율적인 검색을 위해, 다양한 전략들을 설계하지만, 기존 방법들은 모두 단 한 번의 고정된 검색에서 충분한 지식들을 모으는 것을 목표로합니다. 하지만 이 목표는 복잡한 질의에 대한 성능을 제한합니다.</p><p>GraphRAG의 답변생성 과정의 경우, 검색된 그래프 기반 지식을 바탕으로 답변을 생성하는 것은 지나치게 긴 컨텍스트로 이루어진 추론을 요구하는데, 이는 출력 품질이 LLM의 규모와 프롬프트 설계에 의존하게 만드며, 결과적으로 불안정한 추론과 생성을 야기합니다.</p><p>이 문제들을 해결하기 위해, 논문은 Graph-R1을 제안하며, 각 문제들을 다음과 같은 방식으로 해결합니다.</p><ul><li>경량화된 지식 하이퍼그래프(hypergraph) 구축</li><li>multi-turn 에이전틱 상호작용</li><li>생성 품질, 검색 관련성 등을 통일된 최적화 objective로 통합하는 보상 메커니즘</li></ul><p>방법의 구체적인 내용은 다음 절에 기술하겠습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/894/1*Gj2WZmGqaH63yOo2guXxHQ.png" /></figure><h3>이 논문은 언급된 문제들을 어떻게 해결하는가</h3><p>Graph-R1의 흐름은 다음과 같으며, 해결 과정을 그래프 생성, 검색, 답변 생성 관점에서 설명하겠습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*e4xs8ekZxZ2q8K_5uw2PUw.png" /></figure><h4>지식 생성 및 에이전트 초기화</h4><p>Graph-R1은 경량화된 방법으로 문서로부터 하이퍼그래프를 구축합니다. 여기서 <a href="https://en.wikipedia.org/wiki/Hypergraph">하이퍼그래프</a>는 하나의 간선으로 3개 이상의 정점을 연결 할 수 있습니다. 따라서 LLM 기반의 extractor를 사용해서, 시맨틱 세그먼트와 엔티티로 구성된 m개의 n-ary 관계를 추출합니다. 이후, 엔티티와 관계에 대하여 인코더를 통해 임베딩을 수행합니다.</p><p>결과적으로 구축된 하이퍼그래프는 high-order 관계형 구조를 풍부한 시맨틱 기반으로 인코딩합니다. 추출 프롬프트는 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XqHB7unaU6dSrRGIYFdP_g.png" /></figure><p>Appendix.A에 따르면, 위 프롬프트는 <a href="https://arxiv.org/pdf/2503.21322">HyperGraphRAG</a>에서 사용하는 프롬프트와 동일하지만, Graph-R1은 confidence score를 생략하고, 더 단순한 검색 방법을 사용했다는 점에서, 구축 비용을 줄였습니다.</p><p>이번엔 에이전트 초기화에 대해서 알아보겠습니다. 에이전트 행위는 아래와 같습니다.</p><ul><li>Thinking: 추론을 계속할지 중단할지 결정합니다.</li><li>Query Generation: 검색 질의를 공식화합니다.</li><li>Graph Retrieval: 하이퍼그래프로부터 관련 지식을 추출합니다.</li><li>Answering: 추론이 끝났다면 최종 답변을 생성합니다.</li></ul><p>에이전트 행위는 두가지 구성적 형식을 가지고 있으며, log-likelihood는 다음과 같이 정의됩니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/673/1*ogFNo5Bii-v8VOOcx0MrsA.png" /></figure><p>각 스텝 t에서, 에이전트는 처음에 Thinking을 하고, 이후 추론(Query Generation, Graph Retrieval)을 계속할지 또는 답변 생성(Answering)을 할지를 조건에 따라 선택합니다. 그리고 s_t는 에이전트 상태 공간 집합에 속하며, 입력 질의로부터 초기화된 s_1과 함께, (s_1, a_1, a_2, … a_t)로 정의됩니다.</p><p>지금까지 지식 생성과 에이전트 초기화에 대해서 알아봤습니다. 이번에는 검색 단계에서 이루어지는 multi-turn 에이전틱 상호작용에 대하여 알아보겠습니다.</p><h4>Multi-turn 그래프 상호작용을 통한 지식 추론</h4><p>Graph-R1은 하이퍼그래프와 에이전트를 통해 추론을 모델링했습니다. 이를 위해 프롬프트로 작성된 스텝별(step-wise)정책을 정의하고, 각 스텝안에서 질의를 기반으로 지식을 검색하는 방법을 기술하고, 최종적으로 답변 생성을 최적화하는 objective를 나타냅니다.</p><p>프롬프트로 작성된 스텝별 정책은 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/678/1*nd0lVl2d1x6H2OCJSahmUQ.png" /></figure><p>구체적인 프롬프트는 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XcyypMfJT3u9OXiXZtQHqw.png" /></figure><p>스텝별 추론 모델링에 대해 부연 설명을 더 하자면, 각 추론 스텝 t에서, LLM은 구조화된 출력을 생성함으로써, 에이전트의 행위를 다스립니다. 여기서 구조화된 출력을 아래와 같이 구성됩니다.</p><ul><li>Thinking Reflection: 현재 상태를 요약하고, 잠재적 지식 격차를 강조합니다.</li><li>Composition Indicator: 하위 행위 구조를 결정합니다. (질의 후 검색 또는 답변)</li><li>Content Output: 검색 질의 또는 최종 답변을 나타냅니다.</li></ul><p>의사 결정 프로세스는 에이전트의 상태에 따른 계층적 정책으로써 모델링 됐으며, 이전 행위와 검색된 정보의 히스토리를 인코딩합니다. 수식은 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/784/1*wjHwlF4QVVInA9orILlBUg.png" /></figure><p>이번에는 하이퍼그래프 검색을 통한 지식 상호작용이 어떻게 동작하는지 살펴보겠습니다. LLM에 의해 생성된 질의가 주어지면, Graph-R1은 이중 경로 상호작용 프로세스를 통해, 하이퍼그래프로부터 관련 지식을 검색합니다. 여기서, 이중 경로 상호작용 프로세스는 다음으로 구성됩니다.</p><ul><li>엔티티를 이용한 하이퍼엣지 검색(Entity-based HyperEdge Retrieval)</li><li>하이퍼 엣지를 직접 검색(Direct Hyperedge Retrieval)</li></ul><p>엔티티 기반 하이퍼엣지 검색은 우선, 질의에 있는 엔티티를 추출한 후, 이 엔티티와 유사한 하이퍼그래프에 존재하는 상위 후보 엔티티를 식별합니다. 그리고 식별된 상위 후보 엔티티를 연결하는 하이퍼엣지를 수집합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/629/1*PJShdBODlXdsOnFeTFK7OQ.png" /></figure><p>동시에, 하이퍼엣지를 직접 검색하는 작업도 수행되는데, 이 작업은 질의-하이퍼엣지 유사도를 기반으로 검색을 수행하며, 관련 관계형 사실들을 수집합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/551/1*cKur2tOWBQpV0NwdFbaoKQ.png" /></figure><p>검색 결과로 나온, n-ary 관계형 사실들은 랭크 기반 fusion을 통해, 집계되어, 다운스트림 추론 지원에 활용됩니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/477/1*LuUYrQ-WJRbcSMvQnz_f_Q.png" /></figure><p>한편, 에이전트는 추론 궤적을 학습하는 것을 목표로합니다.</p><ul><li>추론 궤적은 신뢰 할 수 있고, 맥락에 바탕을 둔 답변을 생성합니다.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/255/1*R_YTT5NuYUrIbEG85HN5lw.png" /></figure><p>다시 말해, 궤적이 주어졌을 때 올바른 답변을 생성 할 수 있도록 정책을 최적화해야합니다. 이에 대해서는 다음절에서 살펴보겠습니다.</p><h4>결과 지향적 종단간 강화학습</h4><p>Graph-R1은 믿을 수 있고, 구조화가 잘된 답변을 생성하도록, 추론 정책을 최적화를 하는데, 이를 위해 GRPO기반의 종단간 강화학습을 사용하고, 결과지향 보상 함수를 설계합니다. 각각을 하나씩 살펴보면 다음과 같습니다.</p><p><strong>종단간 RL Objective GRPO</strong></p><p>질문 데이터셋이 주어졌을 때, 에이전트는 multi-turn 추론 궤적 그룹을 생성하기 위해, 하이퍼그래프와 상호작용하는데, 여기서 GRPO 기반의 objective를 이용하여, 정책을 최적화하며 수식은 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/613/1*q6mqdEf5jn7ZPdp5f5A-dw.png" /></figure><p>이 식은 하이퍼그래프 상에서 높은 보상과 안정적인추론을 장려합니다.</p><p><strong>결과 지향 보상함수</strong></p><p>결과에 대한 요구사항을 만족시키기 위해, Graph-R1은 두 부분으로된 보상함수를 정의합니다. 두 부분은 Format Reward와 Answer Reward로 내용은 다음과 같습니다.</p><p>Format Reward</p><p>이 보상 부분은 에이전트가 의도된 추론 구조를 따를 수 있도록 장려합니다. 매 스텝마다, Graph-R1은 결과가 좋은 형식을 갖춘 블록을 포함하는지 점검합니다. 각 스텝에서 유효하면 0.5의 보상을 받으며, 전체적으로는 1.0으로 제한되며 수식은 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/482/1*ztTNOSzUjaken5SPBHFd-w.png" /></figure><p>Answer Reward</p><p>이 보상은 생성된 답변과 실제 정답을 비교해서 의미론적 정확도를 보고, 보상을 측정합니다. 비교를 위해 F1-Score를 사용합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*5XUnb8-9zbT7_ZKdam0f2w.png" /></figure><p>결과적으로 위 둘의 보상 함수를 이용하여, 정의한 식은 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/554/1*kxaCQT8ei-aHzBhEf7JZTQ.png" /></figure><h3>실험</h3><p>논문에서는 Graph-R1에 대한 아래의 연구적 의문들에 대해 답변합니다.</p><ul><li>Graph-R1이 다른 방법들보다 뛰어나는가?</li><li>Graph-R1의 주요 컴포넌트가 동작하는가? 그리고 비교분석은 어떻게 되는가?</li><li>Graph-R1의 그래프 구축 비용, 검색 효율성, 생성 품질, 일반화 능력은 어떻게 되는가</li></ul><p>평가 지표의 경우, Exact Match(EM), 검색 유사도(R-S), 생성 평가(G-E)가 사용됐고, 사용한 LLM은 지식 구축의 경우, GPT-4o-mini를 사용했고 검색의 경우, bge-large-en-v1.5를 사용했습니다. 주요 결과는 다음의 표와 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/818/1*46XL47srym479BY5a43nvA.png" /></figure><p>각 질문에 대한 답변은 다음과 같습니다.</p><p><strong>Graph-R1이 다른 방법들보다 뛰어나는가?</strong></p><p>위의 테이블에서 확인 할 수 있듯이, 대부분의 상황에서 Graph-R1은 다른 방법보다 더 나은 결과를 보여주고 있습니다. 여기서 2가지를 관측 할 수 있는데, 하나는 강화학습이 그래프 표현의 능력을 향상시킨다는 것과 더 큰 파라미터 사이즈를 갖는 LLM이 더 나은 성능을 보여준다는 것입니다.</p><p><strong>Graph-R1의 주요 컴포넌트가 동작하는가? 그리고 비교분석은 어떻게 되는가?</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/713/1*3Vrgv061va06W6-LYPZe_Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*StJT2Pm5npiMwptClPc8eQ.png" /></figure><p>주요 컴포넌트 동작의 확인을 위해, Graph-R1의 3가지 핵심 컴포넌트(지식 구축, multi-turn 상호작용, 강화학습) 중 하나를 제거하고, 평가를 수행했고, 결과는 위의 figure5 (a)에서 확인 할 수 있습니다. ablation study 결과 3가지 컴포넌트 중 하나라도 없으면, 성능이 더 안나온다는 것을 확인 할 수 있습니다.</p><p>이번엔 비교 분석 질문에 대한 논문의 답변을 확인해보겠습니다. 논문에서는 다음 3가지 관점에서 비교분석을 수행했는데,</p><ul><li>다른 지식 표현에 따른 비교 분석</li><li>다른 데이터 셋, 베이스 모델에 따른 비교 분석</li><li>다른 RL 알고리즘에 따른 비교 분석</li></ul><p>다른 지식 표현에 따른 비교 분석의 경우, 외부 지식이 없을 때, 지식 표현의 성능이 좋지 않다는 것을 확인할 수 있습니다.(figure4, figure5-b) 강화학습을 사용한 청크 기반의 지식은 이전보다 나은 성능을 보여주지만, 이진 관계 그래프 기반 방법보다는 낮습니다. 반면, RL이 있는 하이퍼지식그래프는 가장 좋은 표현력을 보여주고있습니다. 이는 강화학습이 있을 때, 그래프의 표현력에 대한 성능이 우수하다는 것을 보여주고 있습니다.</p><p>다른 데이터 셋, 베이스 모델에 따른 비교 분석의 경우, figure5의 c와 d에서 Graph-R1이 꾸준하게 다른 모델보다 더 나은 성능을 보여주는 것을 확인 할 수 있습니다. 흥미로운 점은 Qwen3–4B의 경우 이미 RL로 잘 훈련이 됐음에도, 전반적인 성능에 대한 실링이 조금 낮다는 것을 알 수 있습니다.</p><p>다른 RL 알고리즘에 따른 비교 분석의 경우, figure5-f에서 확인 할 수 있는데, GRPO가 나머지 방법보다 성능이 높게 나온 것을 확인 할 수 있습니다.</p><h4>Graph-R1의 그래프 구축 비용, 검색 효율성, 생성 품질, 일반화 능력은 어떻게 되는가?</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/751/1*ZlwyYt02RoQRq55tTxSuMg.png" /></figure><p>그래프 구축 비용은 아래의 테이블을 통해 확인 할 수 있습니다. 1k 토큰 생성에 걸린 시간, 1M 토큰당 발생한 비용이 생성된 정점과 간선의 개수를 비교해봤을 때, 그렇게 나쁘지 않다는 것을 확인 할 수 있습니다.</p><p>검색 및 생성의 경우 비용이 전혀 발생하지 않는 것을 확인 할 수 있는데, 이는 종단간 강화학습과 지역화된 지식 검색을 사용하기 때문입니다. 다른 데이터 셋, 베이스 모델에 따른 비교 분석에서 나온 결과를 고려해봤을 때, 프로덕션에도 활용할 수 있는 잠재력을 갖고 있습니다.</p><p>검색 효율성 측정을 위해, 논문은 응답 길이, 상호작용 turn의 개수, 평균 검색 내용 길이를 분석했고 결과는 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gYM8xypaUr_EFY_Sp-GbFg.png" /></figure><p>figure6-a와 figure-b를 보면, Graph-R1에서 step이 길어질수록, 응답 길이와 상호작용 turn 개수가 많다는 것을 볼 수 있는데, 이는 안정적이고 정확한 검색을 야기합니다. 다시 말해, 정확한 Thinking과 적절한 상호작용을 하려는 경향이 있다고 볼 수 있습니다.</p><p>figure6-c를 보면, 적당한 길이의 검색된 내용을 가지면서 높은 F1-Score를 가지는 것을 확인 할 수 있습니다.</p><p>이번에는 생성 품질에 대한 결과를 살펴보겠습니다. 아래는 생성 평가 결과입니다. Graph-R1은 다른 강화학습 기반의 방법과 HyperGraphRAG 보다 더 우수한 결과를 갖는 것을 확인 할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/501/1*OWEjapeEYadWuz9eprljfQ.png" /></figure><p>마지막으로 일반화 능력에 대한 평가를 확인해보겠습니다. 아래는 Search-R1과 Graph-R1에 대하여, OOD cross-validation을 수행하여, 결과를 히트맵으로 표현한 figure입니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VeLsbugMlBqPrMvwR1c9Mg.png" /></figure><h3><strong>한계</strong></h3><p>이 논문에서 언급한 한계로 하이퍼그래프 구축 비용(특히 관계 추출과 인코딩은 여전히 비자명적), 구조적 추론 능력이 부족한 검색, 텍스트 기반 지식만 지원한다는 점을 언급하고 있습니다.</p><p>참고로 Graph-R1의 작동 과정은 아래에서 확인 할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/676/1*OKmxHYp0Ya5sLDCEee0UDQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=531b6a3257d0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Survey of Graph Retrieval-Augmented Generation
for Customized Large Language Models 논문 리뷰]]></title>
            <link>https://medium.com/rate-labs/a-survey-of-graph-retrieval-augmented-generation-for-customized-large-language-models-%EB%85%BC%EB%AC%B8-%EB%A6%AC%EB%B7%B0-7b546442199c?source=rss-db62e036d783------2</link>
            <guid isPermaLink="false">https://medium.com/p/7b546442199c</guid>
            <dc:creator><![CDATA[Giyoon Park]]></dc:creator>
            <pubDate>Tue, 05 Aug 2025 06:22:51 GMT</pubDate>
            <atom:updated>2025-08-05T06:25:18.278Z</atom:updated>
            <content:encoded><![CDATA[<p>링크: <a href="https://arxiv.org/pdf/2501.13958">https://arxiv.org/pdf/2501.13958</a></p><p>LLM은 여러 task에서 뛰어난 능력을 보여줬지만, 전문 분야에 LLM을 적용하는 것은 어려움이 있습니다. 왜냐하면 전문 분야는 깊은 전문 지식을 필요로하기 때문입니다. 이 문제는 RAG(Retrieval-Agumented Generation)를 통해 해결 할 수 있지만, 기존 RAG는 지식에 대한 구조화 또는 계층을 고려하지 않습니다. 기존RAG가 겪는 문제와 한계를 다루기 위해, GraphRAG가 등장했으며, 이 논문은 GraphRAG의 기술적 기반을 체계적으로 분석하고, 다양한 전문 분야에 걸쳐, 현재 구현체들을 검토합니다. GraphRAG 관련 리소스(e.g. 논문, 오픈소스 데이터, 프로젝트 등)은 <a href="https://github.com/DEEP-PolyU/Awesome-GraphRAG">https://github.com/DEEP-PolyU/Awesome-GraphRAG</a>에서 확인 할 수 있습니다.</p><h3>기존 RAG의 한계</h3><p>기존 RAG는 데이터 구조 자체의 제약으로 인해, 다음의 한계가 있습니다.</p><ul><li>Complex query understanding</li><li>Distributed domain knowledge</li><li>Inherent constraints of LLMs</li><li>Efficiency and scalability</li></ul><h4>Complex query understanding</h4><p>기존 RAG는 복잡한 질의에 답변 할 수 없는 어려움을 겪고 있는데, 이는 지식 구조의 본질적인 한계에 기인합니다. 도메인 지식은 효과적인 이해를 위해 다단계 추론을 요구하는데, 텍스트를 chunk 단위로 분리 한 후, vector db에 저장하는 방식 다단계 추론(multi-hop reasoning) 작업을 어렵게 만듭니다.</p><p>복잡한 질의 이해를 개선하기 위한 시도로, 검색 전에 질의를 개선하는 방법, re-ranking을 위한 다양한 질의 후보를 개선하는 방법, 관련 메타데이터를 사용하여 더 풍부한 정보를 제공하는 방법등 다양한 방법이 시도됐으나, 지식 구조가 여전히 chunk 기반 방식이기 때문에, 복잡한 질의 속에서 다중 정보를 파악하는 것은 여전히 어려운 일입니다.</p><h4>Distributed domain knowledge</h4><p>도메인에 특정된 질의는 전문용어를 포함할 수 있으며, 이 용어는 문맥적 이해를 요구합니다. 하지만 도메인 지식은 일반적으로 여러 문서와 데이터 소스에 걸쳐, 희소하게 분포합니다. 여기서 chunk 기반의 방식을 사용하면 도메인 지식에 대한 하나의 문맥이 분리되고, 또 지식의 계층화 없이 chunk가 vector db에 저장되기 때문에, 검색의 정확도와 문맥의 이해가 떨어지는 문제가 있습니다.</p><h4>Inherent constraints of LLMs</h4><p>기존 RAG는 방대한 지식베이스로부터, 검색된 결과들을 효과적으로 필터링하는 능력이 부족합니다. 따라서 질의와 관련없는 내용들이 과도하게 나올 수 있는데, LLM의 context window size와 복잡한 문서에서 long-range 의존성을 완전히 이해하는 것이 어렵다는 것을 고려해보면, LLM이 과도하게 나온 검색 결과들 중, 필요한 정보를 보는 것은 쉽지 않습니다.</p><p>핵심 인사이트를 얻기 위해, 검색된 정보를 필터링하고 평가하는 방법이 있지만, 여전히 LLM이 long-range 의존성을 이해하는 것은 어려운 일입니다. 이는 vector similarity 기반의 검색 방식 때문인데, 이 방식은 서로 다른 검색 결과간의 명료한 연결을 못하기 때문입니다.</p><h4>Efficiency and scalability</h4><p>대규모 지식 소스는 도메인에 특정되지 않은 정보가 상당히 많은 반면, 도메인에 특정된 용어는 다양한 출처에서 희소하게 분포하고 있습니다. 도메인에 특정된 질의에 답변하기 위해, 기존 RAG는 관련 정보를 상당한 양의 비구조화된 텍스트 안에서 찾습니다. 하지만 이는 상당한 컴퓨팅 리소스와 시간을 요구합니다.</p><p>지금까지 기존 RAG가 갖는 한계를 알아봤고, 대부분의 한계는 지식을 구조화, 계층화하지 않는데서 발생한 것임을 확인했습니다. 지금부터는 GraphRAG 개념과 기존 RAG 대비 GraphRAG가 갖는 이점에 대해 설명하겠습니다.</p><h3>GraphRAG</h3><p>GraphRAG는 지식의 구성과 검색을 위해, 그래프를 사용하는 RAG 프레임워크의 하위 분류로 정의 될 수 있습니다. 그래프는 용어와 용어, 용어와 문서, 문서와 문서간의 연결 및 관계를 표현할 수 있습니다. 그래프를 구축함으로써, 주제 또는 entity를 중심으로 관련된 지식 조각들을 발견하여, 포괄적인 지식 검색을 보장합니다. 게다가 그래프 안에 존재하는 연결은 관련 경로 탐색을 통한 검색과 관련 없는 정보를 제거하는 것을 지원합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*meOphyD3rIbDfRDGlcGOAA.png" /></figure><p>기존 RAG과 비교했을 때, GraphRAG가 갖는 이점은 다음과 같습니다.</p><ul><li>Enhanced Knowledge Representation</li><li>Flexibility in Knowledge Sources</li><li>Efficiency and Scalability</li><li>Interpretability</li></ul><h4>Enhanced Knowledge Representation</h4><p>GraphRAG는 entity와 개념간의 복잡한 관계, 계층, 연관 그리고 다단계관계를 표현하기 때문에, 기존 RAG보다 더 나은 문맥적 이해를 허용합니다. 또한 그래프에서 여러 가능한 해석이나 관계를 표현함으로써, GraphRAG는 모호한 질의도 다룰 수 있습니다.</p><h4>Flexibility in Knowledge Sources</h4><p>GraphRAG는 다양한 지식 출처에 대하여, 적응하고 통합 할 수 있습니다. 하나의 그래프 구조 안에, 이미지, 텍스트, 숫자, JSON 데이터를 포함 할 수 있습니다. 따라서 포괄적인 지식 표현이 가능하고, 멀티 모달리티 특성을 갖는 질의에 대해서도 답변 할 수 있습니다.</p><h4>Efficiency and Scalability</h4><p>빠른 graph db 상에 구축된 GraphRAG는 대규모 데이터셋을 효과적으로 다룰 수 있습니다. graph db는 복잡한 데이터 구조의 빠른 탐색을 지원하고 있어, 관계 기반의 질의에 최적화되어있습니다. 연구에 따르면, GraphRAG는 기존 RAG보다 26%~97% 더 적은 토큰을 사용해서 응답을 생성 할 수 있습니다. 또 GraphRAG는 그래프 안에 있는 정점과 간선을 추가함으로써, 지식 베이스 업데이트를 쉽게 할 수 있습니다. 따라서 실시간 업데이트에 유리하며, 결과적으로 GraphRAG는 항상 최신화된 정보를 볼 수 있습니다.</p><h4>Interpretability</h4><p>그래프 구조는 사람이 시각적으로 쉽게 이해 할 수 있으며, 시스템이 어떻게 이 응답에 도달했는지 이해 할 수 있게합니다. 이러한 투명성은 AI 시스템 안에서 신뢰를 구축하는데 중요합니다. e.g. 헬스케어, 금융</p><p>또한 그래프 안의 여러 정점들을 경유하는 논리 체인을 따를 수 있는데, 이 능력은 다단계 질의를 허용하고, 단일 문서 안에서 명시적으로 언급되지 않은 인사이트를 이끌어 낼 수 있게합니다.</p><p>이번엔 지식을 그래프로 표현 했을 때, 기존 RAG 대비 얻는 이점들을 알아봤습니다. 그렇다면 지식을 어떻게 구축하고, 구축된 지식에 대해 어떻게 검색하고, 검색 결과를 바탕으로 어떻게 질의에 대한 답변을 할까요? 하나씩 하나씩 살펴봅시다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cgkLtNQ3ofO5pvIbuzd9eA.png" /></figure><h3>Knowledge Organization</h3><p>GraphRAG에서 가장 먼저 할 일은 그래프를 구축하는 것입니다. 다시 말해, 다양한 원본 출처 데이터로부터, 지식을 구성하는 것입니다. 지식을 구성하는 방법으로 크게 3가지 방법이 있습니다.</p><ul><li>Graphs for Knowledge Indexing</li><li>Graphs as Knowledge Carriers</li><li>Hybrid GraphRAG</li></ul><h4>Graphs for Knowledge Indexing</h4><p>텍스트 chunk를 노드로 표현하고, 이 chunk들을 연결합니다. 이 때, 임의로 연결하는 것이 아닌, 질의 지향으로 연결합니다. 이렇게 함으로써, 관련 지식을 지역화 할 수 있습니다.</p><p>이 방법으로 구축한다면, 주의 사항이 있는데, 관련성 관점에서, 불필요한 연결 없이 오직 관련성 있는 chunk들만 연결되어야하고, 일관성 관점에서 각 chunk 사이에서 발생 할 수 있는 충돌을 해결 할 수 있어야합니다.</p><p>그렇다면 chunk는 어떻게 연결될까요? 만약 원본 출처가 마크다운과 같은 반구조화 형식이라면, 섹션별로 chunk들을 연결 할 수 있습니다. (개인 의견) 또 다른 방법으로 관련 키워드를 바탕으로 연결하는 방법이 있습니다. chunk들 안에서 공통된 키워드가 있다면, 그 chunk들을 연결하는 것입니다.</p><h4>Graphs as Knowledge Carriers</h4><p>텍스트 chunk로부터 요약된 지식이 추출되고, 추출된 지식은 지식베이스에 통합되어, 지식 전달자의 역할자를 합니다. GraphRAG는 기존에 이미 구축된 그래프를 사용하기도 하고, 또는 말뭉치에서 직접 그래프를 구축하기도 합니다.</p><p>말뭉치에서 직접 그래프를 구축하는 경우, 비구조화된 텍스트로부터 구조화된 지식 그래프를 구축하기 위해 OIE(Open Information Extraction)을 사용합니다. 이 방법의 목표는 귀납적 편향을 통합시키는 것인데, 이는 불필요한 복잡성을 줄이면서, 필수적인 특정 도메인의 정보를 포함하는 그래프 구조를 설계하기 위함입니다.</p><p>하지만 이 방법도 한계가 있습니다. 만약 기존에 존재하는 그래프를 GraphRAG에 사용한다고 결심한다면, 고품질의 지식 그래프가 많지 않다는 것을 알게됩니다. 또한 일원화된 온톨로지를 갖는 그래프가 존재하지 않기 때문에, 검색을 위한 계획 알고리즘을 설계하는데 어려움이 있습니다.</p><p>또 다른 문제점으로 효율성과 효과성의 트레이드 오프가 있습니다. 지식의 세분화가 높아질수록, 그래프 규모가 커지는데 이는 연산 효율성을 방해합니다. 반면, 세분화가 덜 될 수록, 잠재적인 정보 손실이 발생 할 수 있습니다. 이러한 트레이드 오프는 지식 요약 프로세스를 어렵게 만듭니다.</p><h4>Hybrid GraphRAG</h4><p>위의 첫번째 방법과 두번째 방법을 혼용해서 사용합니다. 논리적 추론을 지원하면서, 동시에 원본 텍스트에 기술된 지식에 대한 세부사항을 유지할 수 있습니다.</p><h3>Knowledge Retrieval</h3><p>그래프를 구축하는 방법에 대해 간단하게 알아보았습니다. 이제는 구축된 그래프에 접근해서 질의와 관련있는 지식을 찾아야합니다. 지식 검색 프로세스는 3가지 과정을 거치며, 각 과정에 대한 설명은 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IfJnGhp2wDUVowzzsbjm0w.png" /></figure><h4>1. Query/Graph processing</h4><p>전처리 단계는 질의와 그래프 상에서 발생합니다. 질의 전처리의 경우, GraphRAG는 입력 질의를 벡터화 또는 핵심 용어 추출을 통해, 구조화된 표현으로 변환합니다. 이 표현은 차후 검색 연산을 위한 검색 색인 역할을 합니다.</p><p>그래프 전처리의 경우, graph db는 포괄적인 처리를 겪는데, 여기에서 그래프를 이루는 요소들이 언어 모델에 의해, 검색 앵커 역할을 하는 벡터로 표현됩니다.</p><p>추가적으로 언어 모델이 아닌 그래프 신경망을 사용하여, 고수준의 구조적 특성을 추출 할 수 있고, 룰 마이닝 알고리즘을 사용하여, 그래프 지식의 검색가능한 색인으로써, rule bank를 생성 할 수 있습니다.</p><h4>2. Matching</h4><p>질의와 그래프 색인을 비교해서, 관련 지식들을 식별합니다. 매칭 알고리즘은 그래프 내 semantic similarity, 구조적 관계 모두 고려합니다. 매칭 스코어를 기반으로, 질의와 높은 관련성이 있는 연결된 컴포넌트 또는 하위 그래프를 검색하여, 후보 지식의 초기 집합을 생성합니다.</p><h4>3. Knowledge Pruning</h4><p>이 단계에서는 초기에 검색된 결과들을 정재해서, 품질과 관련성을 개선합니다. 정제 프로세스는 질의와 관련없는 불필요한 정보들을 제거합니다. 이후, 관련 지식 파편들을 통합하고, 이 지식들에 대한 정확한 요약을 생성합니다.</p><p>요약을 생성하는 이유는 포괄적인 지식 통합을 용이하게 하기 위함인데, 이는 LLM이 검색 결과를 쉽게 이해하여, 결과적으로 더 정확하고 의미있는 답변을 생성 할 수 있습니다.</p><h3>Retrieval Enhanced Strategies</h3><p>목표 질의에 맞는 검색 결과를 향상시키는 전략으로 아래의 방법들이 존재합니다.</p><h4>Multi-round Retrieval</h4><p>이 전략은 문맥 정보와 사용자 피드백을 통합하여, 검색 프로세스를 동적으로 정제합니다. 이 방법은 검색 메커니즘을 특정 사용과 진화하는 사용자 의도에 맞게 동작하는 것을 목표로합니다.</p><h4>Post-retrieval</h4><p>기본적으로 GraphRAG는 답변을 생성하기 전에, 검색 프로세스를 수행합니다. 사후 검색은 생성 후에도, 검색을 수행합니다. 이 방법은 생성된 답변이 믿을만하고 정확한지 평가하기위해 사용됩니다.</p><h4>Hybrid Retrieval</h4><p>검색을 위해 다른 형태의 데이터를 조합해서 사용합니다. 구체적으로 검색 단계에서 그래프 데이터와 벡터 데이터를 함께 사용하는 것이 있습니다.</p><h3>Knowledge Integration</h3><p>지금까지 검색 과정, 검색 기술, 검색 향상 전략에 대해서 알아봤습니다. 검색 결과는 LLM에게 제공하여, LLM이 질의에 맞는 답변을 해야합니다. 이를 위한 방법으로 fine-tuning과 in-context learning이 존재하지만, 여기서는 in-context learning만 볼 것입니다. in-context learning의 방법으로 graph-enhanced CoT와 collaborative knowledge graph refinement가 있습니다.</p><h4>Graph-enhanced CoT</h4><p>지식 통합 상에서, CoT기반의 프롬프팅 방식은 복잡한 다단계 추론에서 강력한 잠재력을 이끌어냅니다. Graph-enhanced CoT의 경우 LLM과 그래프사이의 상호작용을 기반으로 연쇄 추론을 강조합니다.</p><h4>Collaborative Knowledge Graph Refinement</h4><p>프롬프팅 기술을 사용하는 대신, LLM의 답변을 지식 그래프 안에 있는 사실적 지식을 기반으로 정제할 수 있습니다. 이는 LLM이 환각 증상을 일으키는 것을 방지 할 수 있습니다. 이 방법을 사용하려면, 지식그래프의 품질이 보장되어야합니다.</p><p>한편, 지식 통합을 향상 시키는 전략도 있는데, 그 중 하나가 multi-round integration입니다. 검색 결과의 정제를 반복적으로 진행함으로써, 검색 결과내 비일관성을 완화 할 수 있습니다.</p><h3>Limitation and Future Opportunities</h3><p>이번엔 GraphRAG가 갖는 한계에 대해 알아보겠습니다. 우선 그래프를 구축하는데 많은 비용과 공수가 듭니다. 그리고 지식은 불변이 아니라서, 어제의 사실이 오늘은 거짓일 수 있습니다. 그리고 서로 다른 출처에서 동일한 지식을 가져오는 과정에서 지식이 서로 충돌 할 수 있습니다.</p><p>한편, 만약 비정형 텍스트로부터, 그래프를 구축할 경우, 문장에 있는 entity를 추출하고 또 entity간의 관계를 형성함으로써 그래프를 구축하는데, 이 작업은 LLM 성능에 의존합니다. 또한 문장 내에서는 “그” 또는 “이것” 같은 대명사도 있는데, 만약 entity의 속성을 추가해야하는 상황이 있다면, LLM을 통해 이 대명사가 어떤 entity를 가리키는지 확인해야합니다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7b546442199c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/rate-labs/a-survey-of-graph-retrieval-augmented-generation-for-customized-large-language-models-%EB%85%BC%EB%AC%B8-%EB%A6%AC%EB%B7%B0-7b546442199c">A Survey of Graph Retrieval-Augmented Generation
for Customized Large Language Models 논문 리뷰</a> was originally published in <a href="https://medium.com/rate-labs">취미로 논문 읽는 그룹</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>