Lucene의 동시성 버그: 낙관적인 동시성 실패를 수정하는 방법

Elastic 자격증을 취득하고 싶으신가요? 다음 Elasticsearch Engineer 교육이 언제 진행되는지 알아보세요! 지금 무료 클라우드 체험을 시작하거나, 내 로컬 기기에서 Elastic을 사용해 볼 수 있습니다.

네, 또 다른 버그 수정 블로그입니다. 하지만 이번 이야기는 반전이 있습니다. 오픈소스 영웅이 나타나서 하루를 구해줍니다.

동시성 버그를 디버깅하는 것은 쉬운 일이 아니지만, 이제부터 시작하겠습니다. 불안정한 장애를 안정적으로 재현 가능한 장애로 전환하는 CMU의 PASTA Lab의 결정론적 동시성 테스트 프레임워크인 Fray를 사용해 보세요. 프레이의 영리한 섀도 잠금 설계와 정밀한 스레드 제어 덕분에 저희는 까다로운 루씬 버그를 추적하여 마침내 문제를 해결했습니다. 이 게시물에서는 오픈 소스 영웅과 도구가 어떻게 동시성 디버깅의 고통을 덜어주고 소프트웨어 세계를 훨씬 더 나은 곳으로 만드는지 살펴봅니다.

동시성 버그: 소프트웨어 엔지니어의 골칫거리

동시성 버그는 최악입니다. 고치기 어려울 뿐만 아니라 안정적으로 실패하게 만드는 것이 가장 어려운 부분입니다. 이 테스트 실패( TestIDVersionPostingsFormat#testGlobalVersions)를 예로 들어 보겠습니다. 여러 문서 작성 및 업데이트 스레드를 생성하여 루씬의 낙관적인 동시성 모델에 도전합니다. 이 테스트는 낙관적인 동시성 제어에서 경쟁 조건을 노출했습니다. 즉, 문서 작업이 일련의 작업 중 최신 작업이라고 거짓으로 주장할 수 있습니다 😱. 즉, 특정 조건에서는 낙관적인 동시성 제약 조건에 따라 실패해야 할 업데이트 또는 삭제 작업이 실제로 성공할 수도 있습니다.

Java 스택 추적을 싫어하는 분들께 사과드립니다. 삭제가 반드시 '삭제'를 의미하는 것은 아닙니다. Lucene의 세그먼트는 읽기 전용이므로 문서 "업데이트"를 나타낼 수도 있습니다.

Apache Lucene은 DocumentsWriter 클래스를 통해 문서를 작성하는 각 스레드를 관리합니다. 이 클래스는 문서 작성을 위한 스레드를 생성하거나 재사용하며 각 쓰기 작업은 DocumentsWriterPerThread (DWPT) 클래스 내에서 해당 정보를 제어합니다. 또한 작성자는 DocumentsWriterDeleteQueue (DWDQ)에서 어떤 문서가 삭제되었는지 추적합니다. 이러한 구조는 모든 문서 변경 작업을 메모리에 보관하고 주기적으로 플러시하여 인메모리 리소스를 확보하고 구조를 디스크에 지속합니다.

스레드 차단을 방지하고 동시 시스템에서 높은 처리량을 보장하기 위해 Apache Lucene은 매우 중요한 섹션에서만 동기화를 시도합니다. 이는 실제로는 좋을 수 있지만 다른 동시 시스템과 마찬가지로 용두사미가 될 수 있습니다.

거짓 희망

초기 조사를 통해 적절하게 동기화되지 않은 몇 가지 중요한 섹션을 발견했습니다. 주어진 DocumentsWriterDeleteQueue 에 대한 모든 상호 작용은 둘러싸는 DocumentsWriter 에 의해 제어됩니다. 따라서 개별 메소드가 DocumentsWriterDeleteQueue 에서 적절하게 동기화되지 않을 수 있지만 월드에 대한 액세스는 동기화되어 있습니다(또는 동기화되어야 합니다). (소유권과 액세스 권한이 어떻게 혼동되는지 자세히 설명하지 않겠습니다. 많은 기여자가 작성한 오랜 프로젝트이므로 여기서는 다루지 않겠습니다. 조금만 여유를 가지세요.)

하지만 플러시 중 동기화되지 않은 한 곳을 발견했습니다.

이러한 작업은 단일 원자 작업으로 동기화되지 않습니다. 즉, newQueue 이 생성되고 getMaxSeqNo 을 호출하는 사이에 다른 코드가 documentsWriter 클래스에서 시퀀스 번호를 증가시키면서 실행되었을 수 있습니다. 버그를 찾았습니다!

하지만 대부분의 복잡한 버그가 그렇듯 근본 원인을 찾는 것도 쉽지 않았습니다. 바로 그때 영웅이 등장했습니다.

전투의 영웅

우리의 영웅을 소개합니다: 파스타 연구소의 아오 리와 그의 동료들. 프레이가 어떻게 하루를 구했는지 설명해 드리겠습니다.

Fray는 카네기멜론 대학교의 PASTA 연구소의 연구진이 개발한 결정론적 동시성 테스트 프레임워크입니다. 결정론적 동시성 테스트는 20년 이상 학계에서 광범위하게 연구되어 왔지만, 실무자들은 여전히 신뢰할 수 없고 불안정한 것으로 널리 알려진 스트레스 테스트에 의존하여 동시성 프로그램을 테스트하고 있습니다. 따라서 저희는 일반성과 실제 적용 가능성을 주요 목표로 삼아 결정론적 동시성 테스트 프레임워크를 설계하고 구현하고자 했습니다.

핵심 아이디어

프레이의 핵심은 순차적 실행이라는 간단하지만 강력한 원칙을 활용합니다. Java의 동시성 모델은 프로그램에 데이터 경합이 없는 경우 모든 실행이 순차적으로 일관되게 표시된다는 핵심 속성을 제공합니다. 즉, 프로그램의 동작은 일련의 프로그램 문으로 표현할 수 있습니다.

Fray는 대상 프로그램을 순차적으로 실행하는 방식으로 작동하며, 각 단계에서 하나의 스레드를 제외한 모든 스레드를 일시 중지하여 Fray가 스레드 스케줄링을 정밀하게 제어할 수 있도록 합니다. 스레드는 동시성을 시뮬레이션하기 위해 무작위로 선택되지만, 이후 결정론적 리플레이를 위해 선택 사항이 기록됩니다. 실행을 최적화하기 위해 Fray는 스레드가 잠금 또는 원자/휘발성 액세스와 같은 동기화 명령을 실행하려고 할 때만 컨텍스트 전환을 수행합니다. 데이터 레이스 자유의 좋은 특성은 이러한 제한된 컨텍스트 전환만으로도 스레드 인터리빙으로 인해 관찰 가능한 모든 동작을 탐색하기에 충분하다는 것입니다(저희 논문에는 증명 스케치가 있습니다).

과제: 스레드 스케줄링 제어

핵심 아이디어는 간단해 보이지만, 프레이를 구현하는 데는 상당한 어려움이 있었습니다. 스레드 스케줄링을 제어하려면 Fray가 각 애플리케이션 스레드의 실행을 관리해야 합니다. 언뜻 보기에는 동시성 프리미티브를 사용자 정의 구현으로 대체하는 것이 간단해 보일 수 있습니다. 하지만 바이트코드 명령어, 하이레벨 라이브러리, 네이티브 메서드가 혼합되어 있는 JVM의 동시성 제어는 복잡합니다.

이것은 토끼굴로 밝혀졌습니다:

• 예를 들어, 모든 MONITORENTER 인스트럭션에는 동일한 방법의 MONITOREXIT 인스트럭션이 있어야 합니다. Fray가 MONITORENTER 를 스텁/모의 메서드 호출로 대체하는 경우, MONITOREXIT 도 대체해야 합니다.
• object.wait/notify 을 사용하는 코드에서 MONITORENTER 을 대체하는 경우 해당 object.wait 도 대체해야 합니다. 이 교체 체인은 object.notify 이상으로 확장됩니다.
• JVM은 네이티브 코드 내에서 특정 동시성 관련 메서드(예: 스레드가 종료될 때 object.notify )를 호출합니다. 이러한 작업을 대체하려면 JVM 자체를 수정해야 합니다.
• 클래스 로더 및 가비지 컬렉션(GC) 스레드와 같은 JVM 함수도 동시성 프리미티브를 사용합니다. 이러한 프리미티브를 수정하면 해당 JVM 함수와 불일치가 발생할 수 있습니다.
• JDK에서 동시성 프리미티브를 교체하면 초기화 단계에서 JVM 충돌이 발생하는 경우가 많습니다.

이러한 문제들로 인해 동시성 프리미티브의 포괄적인 대체가 불가능하다는 것이 분명해졌습니다.

솔루션: 섀도락 디자인

이러한 문제를 해결하기 위해 Fray는 새로운 섀도 잠금 메커니즘을 사용해 동시성 프리미티브를 대체하지 않고 스레드 실행을 오케스트레이션합니다. 섀도 락은 스레드 실행을 안내하는 중개자 역할을 합니다. 예를 들어 잠금을 획득하기 전에 애플리케이션 스레드는 해당 섀도 잠금과 상호 작용해야 합니다. 섀도 잠금은 스레드가 잠금을 획득할 수 있는지 여부를 결정합니다. 스레드를 진행할 수 없는 경우 섀도 락이 스레드를 차단하고 다른 스레드가 실행되도록 허용하여 교착 상태를 방지하고 동시성을 제어할 수 있습니다. 이러한 설계를 통해 Fray는 동시성 시맨틱의 정확성을 유지하면서 스레드 인터리빙을 투명하게 제어할 수 있습니다. 각 동시성 프리미티브는 섀도 잠금 프레임워크 내에서 신중하게 모델링되어 건전성과 완성도를 보장합니다. 자세한 기술적인 내용은 백서에서 확인할 수 있습니다.

또한 이 디자인은 미래에도 사용할 수 있도록 설계되었습니다. 동시성 프리미티브에 대한 섀도 잠금의 계측만 요구함으로써 최신 버전의 JVM과의 호환성을 보장합니다. 이는 JVM의 동시성 프리미티브 인터페이스가 비교적 안정적이며 수년 동안 변경되지 않았기 때문에 가능합니다.

테스트 프레이

Fray를 구축한 후 다음 단계는 평가였습니다. 다행히도 Apache Lucene과 같은 많은 애플리케이션에는 이미 동시성 테스트가 포함되어 있습니다. 이러한 동시성 테스트는 여러 스레드를 생성하고 일부 작업을 수행한 다음 (일반적으로) 해당 스레드가 완료될 때까지 기다린 다음 일부 속성을 어설트하는 일반 JUnit 테스트입니다. 대부분의 경우 이러한 테스트는 인터리빙을 한 번만 실행하기 때문에 통과합니다. 더 큰 문제는 앞서 설명한 대로 일부 테스트는 CI/CD 환경에서 가끔씩만 실패하기 때문에 이러한 실패를 디버깅하기가 매우 어렵다는 것입니다. Fray로 동일한 테스트를 실행했을 때 수많은 버그를 발견했습니다. 특히, 프레이는 이 블로그의 초점인 TestIDVersionPostingsFormat.testGlobalVersions 을 포함하여 이전에 보고된 버그 중 신뢰할 수 있는 재현이 없어 수정되지 않은 채로 남아 있던 버그를 재발견했습니다. 다행히도 프레이를 사용하면 문제를 결정적으로 재생하고 개발자에게 자세한 정보를 제공하여 문제를 안정적으로 재현하고 수정할 수 있습니다.

프레이의 다음 단계

Elastic의 개발자들로부터 Fray가 동시성 버그 디버깅에 도움이 되었다는 이야기를 듣게 되어 매우 기쁩니다. 앞으로도 더 많은 개발자가 프레이를 사용할 수 있도록 지속적으로 노력할 것입니다.

우리의 단기 목표는 무작위 값 생성기나 object.hashcode 사용과 같은 다른 비결정적 연산이 있는 경우에도 일정을 결정론적으로 재생하는 Fray의 기능을 강화하는 것입니다. 또한 개발자가 수동 개입 없이 기존 동시성 테스트를 분석하고 디버깅할 수 있도록 Fray의 사용성을 개선하는 것을 목표로 하고 있습니다. 무엇보다도 프로그램에서 동시성 문제를 디버깅하거나 테스트하는 데 어려움을 겪고 계신다면 여러분의 의견을 듣고 싶습니다. 주저하지 마시고 프레이 깃허브 리포지토리에서 이슈를 생성해 주세요.

동시성 버그 수정 시간

Ao Li와 PASTA 연구소 덕분에 이제 이 테스트가 안정적으로 실패한 사례가 생겼습니다! 드디어 이 문제를 해결할 수 있게 되었습니다. 핵심 문제는 DocumentsWriterPerThreadPool 에서 스레드 및 리소스 재사용을 허용하는 방식에 있었습니다.

여기에서 각 스레드가 생성되는 것을 볼 수 있으며, 0 생성 시 초기 삭제 대기열을 참조합니다.

그러면 대기열에서 이전 7개의 작업이 올바르게 표시되는 플러시에서 대기열 진행이 이루어집니다.

그러나 모든 스레드가 플러싱을 완료하기 전에 두 개의 스레드가 추가 문서에 재사용됩니다:

numDocsInRAM 그러면 플러시 중에 7로 계산된 가정된 최대값보다 seqNo 이 증가합니다. 세그먼트 _3 및 _0

따라서 Lucene이 플러시 중 문서 작업의 순서를 잘못 설명하여 이 테스트가 실패하게 됩니다.

모든 좋은 버그 수정이 그렇듯, 실제 수정 사항은 약 10줄의 코드입니다. 하지만 두 명의 엔지니어가 실제로 알아내는 데 며칠이 걸렸습니다:

모든 영웅이 망토를 입는 것은 아닙니다

네, 진부한 표현이지만 사실입니다.

동시 프로그램 디버깅은 매우 중요합니다. 이러한 까다로운 동시성 버그는 디버깅하고 해결하는 데 엄청난 시간이 걸립니다. Rust와 같은 새로운 언어에는 이와 같은 경쟁 조건을 방지하는 메커니즘이 내장되어 있지만, 전 세계 대부분의 소프트웨어는 이미 Rust가 아닌 다른 언어로 작성되어 있습니다. 자바는 오랜 시간이 지난 지금도 여전히 가장 많이 사용되는 언어 중 하나입니다. JVM 기반 언어에서 디버깅을 개선하면 소프트웨어 엔지니어링 세계가 더 좋아집니다. 그리고 일부 사람들은 코드가 대규모 언어 모델에 의해 작성될 것이라고 생각하기 때문에, 엔지니어로서 우리가 하는 일은 결국 나쁜 코드가 아니라 나쁜 LLM 코드를 디버깅하는 것일지도 모릅니다. 그러나 소프트웨어 엔지니어링의 미래와 상관없이 동시 프로그램 디버깅은 소프트웨어를 유지 관리하고 구축하는 데 여전히 중요할 것입니다.

이보다 훨씬 더 나은 서비스를 만들어준 PASTA Lab의 Ao Li와 동료들에게 감사드립니다.

자주 묻는 질문