출처 : 자바 ORM 표준 JPA 프로그래밍 (김영한 지음)

 

JPA는 자바 진영의 ORM 기술 표준으로 애플리케이션과 JDBC 사이에서 동작하며 JPA를 구현한 대표 ORM 프레임워크는 하이버네이트이다. 

 

 

JPA는 지루하고 반복적인 CRUD SQL을 알아서 처리해줄 뿐만 아니라 객체 모델링과 관계형 데이터베이스 사이의 차이점도 해결해준다. CRUD SQL을 작성할 필요가 없고, 조회된 결과를 객체로 매핑하는 작업도 대부분 자동으로 처리해주다보니 코드의 양을 많이 줄일 수 있게 된다. 가장 중요한 것은 애플리케이션을 SQL이 아닌 객체 중심으로 개발하니 생산성과 유지보수가 확연이 좋아지고 테스트를 작성하기도 편리해진 점이다.

 

JPA를 사용했을 때의 이점은?

  • 반복적인 CRUD SQL을 작성하지 않아도 된다.
  • 조회된 결과 객체 매핑 자동으로 처리해준다.
  • 객체중심의 개발을 통해 생산성을 증가시킨다. 
  • 성능 최적화가 가능하다. (같은 트랜잭션 안에 같은 회원 2번 조회시 한번의 쿼리만 날라감)
  • 벤더독립성 (다른 DB사용해도 이를 JPA에 알려주기만 하면 된다)

 

SQL을 직접 다루게 되면 발생하는 문제점은?

자바로 작성한 애플리케이션은 JDBC API 를 사용해서 SQL을 DB에 전달하는데, 문제는 객체를 DB에 CRUD하려면 너무 많은 SQL과 JDBC API를 코드로 작성해야 한다는 점.

String sql = "SELECT ~~";
ResultSet rs = stmt.executeQuery(sql);
String id = rs.getString("MEMBER_ID");
String name = rs.getString("NAME");

Member member = new Member();
member.setMemeberId(id);
member.setName(name);

그리고 SQL에 의존적인 개발을 하게 되는데 예를 들어 회원 정보에 연락처(TEL)필드가 추가되었다고 가정해보자. 그렇게 되면 조회, 저장, 수정 등등의 쿼리를 일일이 수정해야 하는데 이처럼 SQL에 모든 것을 의존하는 상황에서는 개발자들이 엔티티를 신뢰하고 사용할 수 없다. 논리적으로 엔티티와 강한 의존관계를 지니게 되는 것은 진정한 의미의 계층 분할이라고 볼 수 없으며 SQL에 굉장히 의존적인 개발이라고 볼 수 있다. 

 

 

JPA를 사용하면 객체를 데이터베이스에 저장하고 관리할 때, 개발자가 직접 SQL을 작성하는 것이 아니라 JPA가 제공하는 API를 사용하면 된다. 그러면 JPA가 개발자 대신에 적절한 SQL을 생성해서 데이터베이스에 전달한다. 

 

패러다임의 불일치 해결

관계형 데이터베이스와 객체 지향 프로그래밍 사이엔 패러다임의 불일치 문제가 존재한다. 객체지향 프로그래밍은 추상화, 캡슐화, 정보은닉, 상속, 다형성 등 시스템의 복잡성을 제어할 수 있는 다양한 장치들을 제공한다. 하지만 관계형 데이터베이스는 데이터 중심으로 구조화되어 있고, 집합적인 사고를 요구하며 추상화, 상속, 다형성 같은 개념이 없다. 문제는 이 패러다임의 차이를 극복하려고 개발자가 너무 많은 시간과 코드를 소비한다는 점이다. 결국, 객체 모델링은 힘을 잃고 점점 데이터 중심의 모델로 변해가게 되는 것이다. 자바 진영에서는 오랜 기간 이 문제에 대한 숙제를 안고 있었고, 이 문제를 해결하기 위해 JPA라는 결과물을 만들어냈다. 

  • 상속
    • JPA를 사용하여 Item이란 테이블을 상속한 Album 객체를 저장해보자.
    • .persist(album) 이라고 입력하면 JPA는 Item과 Album 테이블에 INSERT 쿼리를 알아서 각각 날려준다.
    • 또, Item에 저장된 id로 검색한다고 하면 Album album = jpa.find(Album.class, id); 를 통해 JPA는 Item과 Album 두 테이블을 조인해서 필요한 데이터를 알아서 조회해준다. 
  • 연관관계
    • member.setTeam(team); // 회원과 팀 연관관계 설정
    • jpa.persist(member); // 회원과 연관관계 함께 저장
    • Team team = member.getTeat(); // 객체를 조회할 때 외래 키를 참조로 변환하는 일도 알아서 처리 
  • 객체 그래프 탐색
    • 지연로딩을 사용히야 객체를 불러오는 시점에 jpa는 데이터베이스에 테이블을 조회한다. 
    • . 으로 계속 연관된 객체들을 탐색해 나갈 수 있다. 

 

+통계 쿼리 처럼 복잡한 SQL은 어떻게 하나요?

JPA는 실시간 처리용 쿼리에 더욱 최적화되어 있기 때문에 복잡한 통계 쿼리는 SQL을 직접 작성하는 것이 더 쉬운 경우가 많다. 그래서 JPA가 제공하는 네이티브 SQL을 사용하거나 마이바티스나 스프링의 JdbcTemplate과 같은 SQL 매퍼 형태의 프레임워크를 사용하는 것이 좋다. 

 

 

 

JPA 트랜잭션 격리수준 

일관성이 없는 데이터를 허용하는 수준

트랜잭션이 보장해야 하는 ACID중 격리성과 관련된 내용인데 격리성을 완벽히 보장하려면 동시성 처리 성능이 매우 나빠진다. 이런 문제로 인해 ANSI 표준은 트랜잭션의 격리 수준을 4단계로 나누어 정의했다. 

A : Atomicity / C : Consistency / I : Isolation / D : Durability

 

트랜잭션 관리 포인트 3

1. Dirty Read : 변경된 데이터가 아직 미완성인데 다른 트랜잭션에서 읽어가는 것

2. Nonrepeatble Read : 트랜잭션이 수행중인데 다른 트랜잭션이 읽고 있는 데이터를 수정해서 쿼리 결과가 달라지는 것

3. Phantom Read : 동일한 쿼리가 다른 값을 반환하는 것 

 

 

아래로 내려 갈수록 동시성이 높아지는 대신 속도가 느려진다.  ( lv.0 -> lv.3)

위로 올라 갈수록 동시성이 떨어지는 대신 속도가 빨라진다.  (lv.3 -> lv.0)

 

격리수준

  1. READ UNCOMMITED (lv.0)
    • 커밋되지 않은 데이터도 읽을 수 있음
      • A트랜잭션에서 데이터를 변경하려다 에러가 발생해서 Rollback을 했다고 치면 A트랜잭션이 실행되는 동안 데이터를 요청한 B 트랜잭션은 잘못된 데이터를 읽고 있을 수가 있다. Dirty Read, Dirty Write이 가능함
      • Dirty Read는 방지 X, Noorepeatable read방지 X, Phantom Read 방지 X
  2. READ COMMITED (lv.1)
    • 커밋된 데이터만 불러온다. (= 반복해서 같은 데이터를 불러올 수 없다) 
      • SELECT 문장이 수행되는 동안 해당 데이터에 Shared Lock(읽기 가능, 변경 불가)이 걸리는 레벨
        • 어떠한 사용자가 A라는 데이터를 B라는 데이터로 변경하는 동안 다른 사용자는 해당 데이터(B)에 접근할 수 없습니다.
      • Dirty Read 방지 O , Noorepeatable read 방지 X
  3. REPEATABLE READ (lv.2)
    • 트랜잭션 동안에는 한번 조회한 데이터를 계속 조회해도 같은 데이터가 나오지만, 만약 다른 트랜잭션에서 데이터를 추가한 경우 기존 트랜잭션에서 반복 조회하면 결과 집합이 새로 추가된 데이터를 포함한 결과를 가져오게 된다.  
      • Dirty Read 방지 O, Noorepeatable read 방지 O, Phantom Read 방지 X 
  4. SERIALIZABLE (lv.3)
    • 모든 트랜잭션을 순서대로 실행한다.
    • Dirty Read 방지 O, Noorepeatable read 방지 O, Phantom Read 방지 O

 

 

JPA를 사용하면 격리 수준을 READ_COMMITED로 가정하는데 만약 일부 로직에 더 높은 격리 수준이 필요하면 비관적 락과 낙관적 락 중에 선택을 하여 사용해야 한다. 

 

비관적 락

트랜잭션 간 충돌이 발생한다고 가정하여 우선 락을 건다, 데이터베이스가 제공하는 락 기능을 사용한다.  

데이터를 수정하는 즉시 트랜잭션 충돌을 감지하며 예외를 발생시킨다. 

비관적 락을 사용하면 락을 획득할 때까지 트랜잭션이 대기한다. 무한정 기다릴 수 없으므로 타임아웃 시간을 줄 수 있다. 

 

낙관적 락

트랜잭션 대부분은 충돌이 발생하지 않는 다고 가정하며, JPA가 제공하는 버전 관리 기능을 사용한다. (어플리케이션 단 레벨)

트랜잭션을 커밋하기 전까지는 트랜잭션의 충돌을 알 수 없다는 특징이 있다. 

JPA에서 제공하는 @Version 어노테이션을 사용하며, 최초 커밋만 인정되어 두번째 커밋에선 예외를 발생시킨다. 

 

JPA의 추천하는 전략은 READ_COMMITTED  + 낙관적 락 

 

 

 

참고.

https://kafcamus.tistory.com/48

 

https://openjdk.java.net/jeps/8277131?fbclid=IwAR1A4nFUHY58UBPisTmhNucUP9ZIKKo1UvhSDdVh1Y63HWLWsih5vISghJE 

 

 

JEP draft: Virtual Threads (Preview)

JEP draft: Virtual Threads (Preview) AuthorsRon Pressler, Alan BatemanOwnerAlan BatemanTypeFeatureScopeSEStatusDraftComponentcore-libsCreated2021/11/15 16:43Updated2021/11/18 14:02Issue8277131 Summary Drastically reduce the effort of writing, maintaining,

openjdk.java.net

위의 글을 번역한 내용입니다.

 

Created 2021/11/15 16:43
Updated 2021/11/18 14:02

JEP : JDK Enhancement Proposal

 

 

(먼저 요약부터)

기존의 자바 스레드(Thread)는 운영체제 레벨에서 관리되는 네이티브 스레드로, 스레드 생성 시 운영체제에서 새로운 스레드를 생성하고, 스레드 스케줄링 및 동기화를 위해 운영체제의 자원을 사용합니다. 따라서 운영체제에서 생성 가능한 스레드의 수에 제한이 있습니다. 이로 인해 자바 애플리케이션에서 너무 많은 스레드를 생성하면 운영체제의 자원 부족으로 성능 저하나 애플리케이션 충돌 등의 문제가 발생할 수 있습니다. JVM 내부에서 스레드 스케줄링과 동기화를 처리하기 때문에 가벼워지고, 더 많은 수의 스레드를 생성할 수 있습니다.

 

반면 자바 가상 스레드는 JVM 내부에서 스레드 스케줄링과 동기화를 처리하기 때문에 운영체제의 자원을 사용하지 않습니다. 이로 인해 운영체제에서 생성 가능한 스레드의 수에 제한이 없어지며, 대규모 서버 애플리케이션에서 높은 스레드 수가 필요한 경우에도 안정적으로 처리할 수 있습니다.


자바 가상 스레드는 더 적은 메모리와 더 높은 확장성을 제공합니다. 이는 여러 개의 가상 스레드를 생성하더라도 운영체제에서 새로운 스레드를 생성하지 않아도 되기 때문입니다. 이러한 이점은 높은 스레드 수가 필요한 대규모 서버 애플리케이션에서 특히 유용합니다.
자바 16부터는 가상 스레드를 지원하는 Project Loom이 추가되어, 자바 가상 스레드를 보다 쉽게 사용할 수 있도록 개선되었습니다.

 

 

Summary

가상의 경량 스레드를 통해 사용할 수 있는 하드웨어를 최대한 활용하고 고처리가 가능한 Concurrent한 응용 프로그램을 작성할 수 있으며 유지 보수 하는데에 드는 공수를 줄입니다.

 

Goals

  • 가상 스레드로 지정된 java.lang.Thread을 추가하면 몇 기가 바이트의 heap에서 수백만 개의 활성 인스턴스로 확장되는데 이는 기존 스레드와 거의 동일한 동작을 나타낸다.
  • 가상 스레드의 트러블슈팅, 디버깅, 프로파일링을 지원하는데 이때 플랫폼 스레드와 최대한 유사한 방식으로 기존 JDK 도구 및 툴링 인터페이스를 이용합니다.

Non-Goals

  • 플랫폼 스레드의 구조를 바꾸는 것은 아니다 (기존 스레드)
  • 자바 메모리 구조를 바꾸는 것이 아님
  • 새로운 데이터 병렬 구조를 제시하는 것이 아님 (parallel stream)

Motivation

개발자는 지난 수십 년 동안 Java를 광범위하게 사용하여 동시성(Concurrent) 응용 프로그램을 작성했고 이때 java.lang.Thread가 core한 역할을 수행했습니다. 스레드는 일부 동시성 단위의 응용 프로그램 단위를 나타낼 때는 잘 작동했습니다. (예를 들면 Transaction). Exception에 대해선 트러블 슈팅을 할 때면 스레드의 스택을 추적하고, 스레드 덤프를 떠서 모든 스레드의 스택을 가져와 프로그램이 수행하는 작업의 Snapshot을 얻는 방식으로 진행했죠. 

 

하지만 이는 어디까지나 어플리케이션(동시 트랜잭션 모음)에 대한 개발자의 논리적 관점에 스레드가 반응하는 경우에 한해서 입니다.  불행히도, Thread을  구현하고 있는 현재 방식은 각 Java 스레드에 대해 OS 스레드를 소비하는데 문제는 OS스레드는 무려 소켓보다도 귀중하고 비용이 많이 드는 자원이라는 것입니다. 이는 최신식의 서버가 OS 스레드보다 훨씬 더 많은 동시 트랜잭션을 처리할 수 있음을 뜻합니다. 높은 처리량을 필요로 하는 서버를 개발하는 개발자들은 하드웨어를 효과적으로 사용하여 낭비를 줄여야 했기 때문에 트랜잭션 간에 스레드를 공유해야 했습니다. 먼저는 스레드 생성비용을 줄이기 위해 스레드풀을 사용했고, 이것이 충분하지 않은 경우에는 I/O를 기다리는 트랜잭션 중간에도 스레드 풀에 스레드를 반환하기 시작했습니다. 이는 비동기식 프로그래밍 방식으로 이어 졌는데 단순히 API 세트를 분리하는 수준이 아니라 플랫폼이 아예 어플리케이션의 logical unit을 알지 못하는 수준으로까지 이어지길 바랬습니다. 결과적으로 플랫폼의 컨텍스트(스레드)가 더 이상 트랜잭션을 나타내지 않아 스레드가 그다지 유용하지 않게 되었기 때문에 문제 해결, 관찰, 디버깅 및 프로파일링이 매우 어려워지는 결과를 초래하게 됩니다. 더 나은 하드웨어 활용도 때문에 개발 및 유지보수가 어려워지게 되었는데 이것 또한 낭비로 볼 수 있겠죠. 그러면 개발자는 논리적 동시성 단위를 스레드로 직접 모델링하는 방식과 하드웨어가 지원할 수 있는 상당한 처리량을 낭비하는 것 중에서 선택해야 하는 경우에 처합니다. 

 

(스레드의 역할 UP vs 스레드의 역할 DOWN)

(OS 스레드 자원을 막 사용 but 개발 및 유지보수 편함 vs 하드웨어 활용도를 높임 but 개발 및 유지보수 어렵)

 

가상 스레드(java.lang.Thread의 구현)는 두 가지 장점을 모두 제공합니다. 가상 스레드에 동일한 동기 API를 사용할 경우 저렴한 스레드는 차단(block)합니다. (우리의 귀중한 OS 스레드를 블록하지 않은 상태로).  이렇게 되면 하드웨어 활용도는 최적화가 되고 높은 수준의 동시성과 높은 처리량을 허용하는 동시에 스레드 기반의 Java 플랫폼 및 해당 도구의 설계와 조화를 유지합니다. 가상 스레드는 플랫폼 스레드에 대한 것이며 가상 메모리는 물리적 RAM에 대한 것입니다. 이것은 물리적 리소스에 대한 자동 및 효율적인 mapping을 통해 가상 리소스에 환상적인 매커니즘을 가져옵니다. 가상 스레드는 저렴하고 풍부하기 때문에 스레드 사용 패턴이 바뀔 것으로 예상할 수 있겠죠? 예를 들면 두 개의 원격 서비스를 참조하여 동시에 응답을 기다리는 오늘날의 서버의 경우 일부 스레드 풀에 두 개의 차단 HTTP 클라이언트 작업을 제출하거나 완료 시 일부 콜백을 알리는 두 개의 비동기 HTTP 클라이언트 작업을 시작할 수 있습니다. 그 대신 각각 트랜잭션을 대신하여 HTTP 클라이언트 호출을 수행하는 것 외에는 아무것도 하지 않는 두 개의 가상 스레드를 생성할 수 있습니다. 이것은 비동기식 옵션만큼 효율적입니다. 스레드 풀 옵션과 달리 요청 기간 동안 두 개의 소중한 OS 스레드를 유지하지 않기 때문이죠. 코드는 스레드 풀 옵션만큼 친숙하고 단순할 뿐만 아니라 스레드가 여러 작업에서 공유되지 않아 스레드 로컬 오염의 위험이 있기 때문에 더 안전하기도 하죠. 

 

가상 스레드를 사용하기 위해 새로운 프로그래밍 모델을 배울 필요가 없습니다. 오늘날 Java를 사용하여 동시 응용 프로그램을 작성하는 사람은 누구나 이 모델을 이미 알고 있으며 이 모델은 Java's original programming model과 같습니다. 우리는 이제 오래된 습관을 버려야 될 것이며 특히 스레드 풀의 사용은 풀링 중인 리소스가 부족하거나 생성하는 데 비용이 많이 드는 경우에만 유용합니다.

 


http://gunsdevlog.blogspot.com/2020/09/java-project-loom-reactive-streams.html

=> 기존 스레드는 자원 사용면에서 효율적이지 못했고, 비동기로 개발할 경우에는 작성 및 디버깅이 어려웠음

=> 이를 가상 스레드를 통해 해결하고자 함.

 

기존 비동기 프로그래밍의 단점은? 

=>  비동기 프로그래밍을 개선한 Future, Promise, Reactive stream을 사용하더라도 로직 제어를 위해 부가적인 코드를 많이 필요로 하기 때문에 기본적으로 비동기 프로그래밍은 제어 흐름을 복잡하게 가져가야 하는 단점이 있다.

=> 스택 트레이스가 유용하지 않아서 스레드에 대한 정보를 파악하기가 어렵다.

=> 어떤 메소드가 Future를 반환하면 다른 메소드들도 마찬가지로  Future을 반환해야 하는데 이는 특정 패러다임을 강제하게 한다. 

 


Description

가상 스레드를 사용하면 동일한 프로세스에서 많은 활성 인스턴스가 공존할 수 있도록 하는 방식으로 JDK에 의해 구현된 java.lang.Thread의 인스턴스입니다.

Thread thread = Thread.ofVirtual().name("duke").unstarted(runnable);

스레드가 가상인지 아닌지는 Thread::isVirtual 메서드로 쿼리할 수 있습니다.

실제로 오늘날과 같이 개발자는 빌더를 사용하여 가상 스레드를 직접 구성하는 경우가 거의 없지만 대신 스레드 생성을 추상화하는 구성을 사용하여 빌더로 생성된 ThreadFactory의 인스턴스를 다음과 같이 사용할 수 있습니다.

ThreadFactory factory = Thread.ofVirtual().factory();

Java 코드에 관한 한 가상 스레드의 의미는 모두 단일 ThreadGroup에 속하고 열거할 수 없다는 점을 제외하면 플랫폼 스레드의 의미와 동일합니다. 그러나 이러한 스레드에서 호출된 Native Code는 다른 동작이 관찰될 수 있습니다. 예를 들어, 동일한 가상 스레드에서 여러 번 호출되면 각 인스턴스에서 다른 OS 스레드 ID를 관찰할 수 있습니다. 또한 OS 수준 모니터링에선 프로세스가 생성된 가상 스레드보다 적은 OS 스레드를 사용하는 되는 것을 관찰할 수 있습니다. 가상 스레드는 OS가 존재를 인식하지 못하기 때문에 OS 수준 모니터링에 보이지 않습니다. JDK는 스택을 포함한 상태를 Java 힙에 저장하여 가상 스레드를 구현합니다. 가상 스레드는 자바 라이브러리의 스케쥴러를 통해 스케쥴링 되는데 작업자 스레드는 가상 스레드가 실행될 때 등에 가상 스레드를 탑재하여 캐리어가 됩니다. 가상 스레드가 고정되면(예: 일부 I/O 작업이나 java.util.concurrent 동기화 구성에서 차단될 때) 가상 스레드는 일시 중단되고 가상 스레드의 캐리어는 다른 작업을 자유롭게 실행할 수 있습니다. 가상 스레드가 풀리게(비고정) 되면(예: I/O 작업 완료에 의해) 스케줄러에 제출되며, 이전에 실행했던 것과 반드시 ​​같을 필요는 없는 일부 캐리어 스레드에서 가상 스레드를 마운트하고 재개합니다. 이런 식으로 가상 스레드가 blocking operation을 수행할 때 OS 스레드를 점유하는 대신 JVM과 그 자리에 예약된 다른 스레드에 의해 일시 중단되는데 모두 OS 스레드를 차단하지 않습니다.

 

가상 스레드를 업고 있는 캐리어 스레드가 해당 OS 스레드를 공유하지만 Java 코드의 관점에서 보면 캐리어와 가상 스레드는 완전히 별개입니다. 캐리어의 신원은 가상 스레드에 알려지지 않고 두 스레드의 스택 추적은 독립적으로 가능합니다. JVM Tool Interface는 플랫폼 스레드와 마찬가지로 가상 스레드를 관찰하고 조작할 수 있지만 아래에 요약한 내용 처럼 일부 작업은 지원되지 않습니다. 특히 JVM TI는 모든 가상 스레드를 열거할 수 없습니다. 마찬가지로 디버거 인터페이스 JDI는 가상 스레드에서 대부분의 작업을 지원하지만 열거할 수는 없습니다. JFR은 가상 스레드에서 발생하는 이벤트를 가상 스레드와 연결합니다. 일반 스레드 덤프는 실행 중인 모든 플랫폼 스레드와 탑재된 가상 스레드를 표시하지만 새로운 종류의 스레드 덤프가 추가되었기 때문에 이는 나중에 설명합니다.


기존에는 스레드가 운영 체제에 의해 관리 및 예약되는 반면 가상 스레드는 가상 머신에서 관리 및 예약 됩니다. 

 

 

java.lang.Thread API

+ Platform 스레드는 현재 Java 플랫폼 버전에서 우리 모두에게 친숙한 스레드를 일컫는다.

 

java.lang.Thread API가 다음과 같이 업데이트되었습니다.

  • Thread.ofVirtual() 및 Thread.ofPlatform과 함께 Thread.Builder가 가상 및 플랫폼 스레드를 생성하는 새로운 API로 추가되었습니다. Thread.Builder를 사용하여 ThreadFactory를 만들 수도 있습니다.
  • Thread.startVirtualThread(Runnable)는 가상 스레드를 시작하기 위한 편리한 방법으로 추가되었습니다.
  • 스레드가 가상 스레드인지 테스트하기 위해 Thread::isVirtual이 추가되었습니다.
  • Thread.join 및 Thread.sleep의 추가되어 wait/sleep 시간을 java.time.Duration으로 제공할 수 있습니다.
  • Thread.getAllStackTraces()는 모든 스레드가 아닌 모든 플랫폼 스레드의 맵을 반환하도록 다시 지정됩니다.

이 외에는 동일하며 생성장에도 변함은 없습니다.

가상 스레드와 플랫폼 스레드 간의 API 차이점은 다음과 같습니다.

  • public constructor는 가상 스레드를 만드는 데 사용할 수 없습니다.
  • 가상 스레드는 데몬 스레드이므로 Thread::setDaemon 메서드를 사용하여 가상 스레드를 데몬이 아닌 스레드로 변경할 수 없습니다.
  • 가상 스레드는 Thread::setPriority 메서드로 변경할 수 없는 고정된 우선 순위인 Thread.NORM_PRIORITY를 갖습니다. 이 제한 사항은 향후 릴리스에서 다시 확인할 수 있습니다.
  • 가상 스레드는 스레드 그룹의 활성 구성원이 아닙니다. Thread::getThreadGroup은 비어 있는 자리 표시자 "VirtualThreads" 스레드 그룹을 반환합니다. Thread.Builder API는 가상 스레드에 대한 스레드 그룹을 설정하는 데 사용할 수 없습니다.
  • SecurityManager 세트로 실행할 때 가상 스레드에는 권한이 없습니다.
  • 가상 스레드는 stop, suspend 또는 resume 메소드를 지원하지 않습니다. 이러한 메서드는 가상 스레드에서 호출되는 경우 예외를 throw하도록 지정됩니다.

 

ThreadFactory virtualThreadFactory = Thread.builder().virtual().factory();
Thread virtualThread = virtualThreadFactory.newThread(printThread);
virtualThread.start();

 

Thread locals

가상 스레드는 플랫폼 스레드와 마찬가지로 스레드 로컬 및 상속 가능한 스레드 로컬을 지원하므로 스레드 로컬을 사용하는 기존 코드를 실행할 수 있습니다. 가상 스레드를 위해  java.base 모듈에서 많이 사용되고 있단 스레드로컬들을 제거하였습니다. 이렇게 하면 수백만 개의 가상 스레드로 실행할 때 메모리 공간에 대한 우려를 줄일 수 있습니다. Thread.Builder API는 스레드를 생성할 때 스레드 로컬을 opt-out하는 방법을 정의합니다. 또한 상속 가능한 스레드 로컬의 초기 값 상속을 거부하는 메서드를 정의합니다. 스레드 로컬을 지원하지 않는 스레드에서 호출될 때를 말하는데 ThreadLocal::get 메서드는 초기 값을 반환하고 ThreadLocal::set 메서드는 예외를 던지게 되어 있습니다. 

JEP: Scope Locals(Preview)는 일부 사용 사례에 대해 스레드 로컬에 대한 더 나은 대안으로 Scope Locals의 추가를 제안합니다.

 

java.util.concurrent APIs

잠금을 지원하는 기본 API인 LockSupport가 가상 스레드를 지원하도록 업데이트되었습니다. 가상 스레드가 고정되면 다른 작업을 수행하기 가능한 상태일 때  캐리어 스레드를 할당해줍니다. 가상 스레드가 unpark되게 되면 스케쥴러에게 반납되게 되어 계속 진행할 수 있게 합니다. LockSupport에 대한 업데이트를 통해 이를 사용하는 모든 API(Locks, Semaphores, blocking queues 등)를 가상 스레드에서 사용할 때 정상적으로 park할 수 있습니다.

 

소수의 API가 추가되었습니다.

  • 완료된 작업의 결과 또는 예외를 얻기 위해 새로운 메서드가 Future에 추가되었습니다. 또한 enum 값으로 작업 상태를 가져오는 새로운 방법으로 업데이트되었습니다. 이러한 추가 기능을 결합하면 Future 객체를 스트림의 요소로 쉽게 사용할 수 있습니다(필터링으로 상태를 테스트할 수 있고 맵을 사용하여 결과 스트림을 얻을 수 있음). 이러한 방법은 구조적 Concurrency를 위해 제안된 API 추가와 함께 사용됩니다.
  • Executors.newThreadPerTaskExecutor 및 Executors.newVirtualThreadPerTaskExecutor가 추가되어 각 작업에 대해 새 스레드를 생성하는 ExecutorService를 반환합니다. 이는 스레드 풀 및 ExecutorService를 사용하는 기존 코드와의 마이그레이션 및 상호 운용성을 위해 사용할 수 있습니다.

블로킹 구간에서 진입하는 경우 실제 스레드가 blocking되는 것이 아니고 LockSupport의 park()가 호출된다. 이때, Continuation.yield()를 통해 캐리어 스레드를 반납하게 되고, IO작업이 끝나면 다시 unpark()가 호출되고 스케줄러가 새로운 캐리어 스레드를 할당하고 scheduler.submit(Continuation)를 통해 계속 진행하게 된다. 

JVM에서 Project Loom을 위한 지원

  • Socket의 블로킹 부분 -> 논블로킹으로 변경
  • java.util.concurrent 논블로킹으로 변경
  • Thread.sleep() 논블로킹으로 변경

가상 스레드는 일반적으로 캐리어 스레드로 사용되는 작은 플랙폼 스레드 세트를 사용합니다. 가상 스레드에서 실행되는 코드는 일반적으로 기본 캐리어 스레드를 인식하지 못합니다. blocking 및 I/O 작업은 캐리어 스레드가 한 가상 스레드에서 다른 가상 스레드로 다시 스케줄링되는 포인트가 됩니다. 가상 스레드가 park되어 schdeuling이 불가능할 수 있는데 parked된 가상 스레드는 unpark하여 스케쥴링을 다시 활성화 시킬 수 있습니다.

 


Networking APIs

java.net 및 java.nio.channels API 패키지에 정의된 네트워킹 API 구현이 가상 스레드와 함께 작동하도록 업데이트되었습니다. block하는 작업(예: 네트워크 연결을 설정하거나 소켓에서 읽는 것)은 다른 작업을 수행하기 위해 캐리어 스레드를 해제합니다.

interruption및 cancellation를 허용하기 위해 java.net.Socket, java.net.ServerSocket 및 java.net.DatagramSocket에 의해 정의된 blocking I/O 메소드는 컨텍스트에서 가상 스레드가 호출될 때 인터럽트 가능하도록 다시 지정되었습니다. 소켓에서 차단된 가상 스레드를 중단하면 스레드가 풀리고, 소켓을 닫습니다.


정의에 따르면 기존 비동기 API는 시스템 호출을 차단하지 않으므로 가상 스레드에서 실행할 때 특별한 처리가 필요하지 않습니다. 동기 API 예를 들어 Socket / ServerSocket/ DatagramSocket, java.nio.channels SocketChannel/ ServerSocketChannel / DatagramChannel같은 API의 경우 비동기 API와 마찬가지로 가상 스레드 안에서 동작하는 데 별다른 조치를 하지 않아도 됩니다. 왜냐면 I/O 동작이 blocking system 자체를 호출하지 않고 selector에 맡겨지기 때문입니다. 하지만 java.net Socket 유형과 NIO 채널은 아닙니다... 동기 네트워킹 Java API는 가상 스레드에서 실행될 때 기본 소켓을 비차단 모드로 전환합니다. Java코드에서 호출된 I/O 작업이 즉시 완료되지 않으면 기본 네이티브 소켓이 JVM 전체 이벤트 알림 메커니즘(poller)에 등록되며 가상 스레드는 parking됩니다. 그리고 그 I/O 작업이 준비되면 (이벤트가 Poller에 도착하면) 가상 스레드는 unparked 상태가 되고 기본 소켓 작업은 재시도됩니다. 

java.io APIs

java.io 패키지는 바이트 및 문자 스트림에 대한 API를 제공합니다. 이러한 API의 구현은 무겁게 동기화되며 가상 스레드에서 이러한 API를 사용할 때 고정되지 않도록 반드시 변경해야 합니다. 원래 바이트 지향 입/출력 스트림은 스레드로부터 안전하지 않았으며 스레드가 read 혹은 write 메소드로 부터 차단되는 동안 close가 호출되었을 때 예상되는 동작을 명시하지 않았습니다. 대부분의 경우에선 concurrent한 스레드에서 input 혹은 output 스트림을 사용하는 게 이해되지 않을 수 있습니다. 문자 지향 reader/writer는 스레드로부터 안전하도록 지정되지 않았지만 하위 클래스에 대한 lock object를 노출시킵니다. 고정하는 것 외에도 동기화는 일관성이 없고 문제가 많습니다, 예를 들면 InputStreamReader와 OutputStreatWriter에서 사용되는 encoder/decoder 스트림은 잠금 개체가 아니라 스트림 단위에서 동기화합니다. 

고정을 피하기 위해 구현은 다음과 같이 변경됩니다.

  • BufferedInputStream, BufferedOutputStream, BufferedReader, BufferedWriter, PrintStream 및 PrintWriter는 직접 사용할 때 모니터가 아닌 명시적 잠금을 사용하도록 변경됩니다. 이러한 클래스는 하위 클래스로 분류될 때 이전과 같이 동기화됩니다.
  • InputStreamReader 및 OutputStreamWriter에서 사용하는 스트림 인코더/디코더는 둘러싸는 InputStreamReader 또는 OutputStreamWriter와 동일한 잠금을 사용하도록 변경됩니다.
  • PushbackInputStream::close는 기본 입력 스트림을 닫을 때 잠금을 유지하지 않도록 변경됩니다.

locking을 변경하는 것 외에도 BufferedOutptuStream, BufferedWriter 및 OutputStreamWriter 구현을 위한 기본 스트림 인코더에서 사용하는 버퍼의 초기 크기가 변경되어 heap에 많은 output스트림 또는 writer가 있는 경우 메모리 사용량을 줄입니다.

 

 

Scheduler

가상 스레드용 스케줄러는 ForkJoinPool을 모방하였는데, First-on-first-out(비동기) 모드에서 작동하며 병렬 처리는 사용 가능한 프로세서 수로 설정됩니다. 일부 blocking API는 대부분의 파일 I/O 작업과 같이 캐리어 스레드를 일시적으로 고정합니다. 이러한 API의 구현은 ForkJoinPool "managed blocker" 메커니즘을 통해 병렬 처리를 일시적으로 확장하여 고정되는 것을 보완합니다. 결과적으로 캐리어 스레드의 수가 사용 가능한 프로세서의 수를 일시적으로 초과할 수 있습니다.
스케줄러는 조정을 위해 두 가지 시스템 속성으로 구성할 수 있습니다.

  • 병렬 처리를 설정하기 위해 jdk.defaultScheduler.parallelism을 사용하며 이것의 기본값은 사용 가능한 프로세서 수로 설정됨
  • 병렬 처리가 확장될 때 캐리어 스레드 수를 제한하는 jdk.defaultScheduler.maxPoolSize. 기본값은 256입니다.

Java Native Interface (JNI)

JNI는 개체가 가상 스레드인지 테스트하기 위해 하나의 새로운 함수인 IsVirtualThread를 정의하도록 업데이트되었습니다. 다른 JNI 사양은 변경되지 않았습니다.

Debugger

debugger 아키텍처는 JVM 도구 인터페이스(JVM TI), 자바 디버그 와이어 프로토콜(JDWP) 및 자바 디버그 인터페이스(JDI)의 세 가지 인터페이스로 구성됩니다. 세 가지 인터페이스 모두 가상 스레드를 지원하도록 업데이트되었습니다.

  • jthread(Thread 객체에 대한 JNI 참조)로 호출되는 대부분의 함수는 가상 스레드에 대한 Thread 객체에 대한 참조로 호출할 수 있습니다. PopFrame, ForceEarlyReturn, StopThread, AgentStartFunction 및 GetThreadCpuTime과 같은 소수의 함수는 가상 스레드에서 지원되지 않습니다. SetLocalXXX 기능은 제한된 경우에만 가상 스레드에서 지원됩니다.
  • GetAllThreads 및 GetAllStackTraces 함수는 모든 스레드가 아닌 모든 플랫폼 스레드를 반환하도록 다시 지정되었습니다.

기존 JVM TI 에이전트는 대부분 이전과 같이 작동하지만 가상 스레드에서 지원되지 않는 기능을 호출하는 경우 오류가 발생할 수 있습니다. 이것은 "가상 스레드를 인식하지 못하는" 에이전트가 가상 스레드를 사용하는 애플리케이션과 함께 사용될 때 발생합니다. 플랫폼 스레드만 포함하는 배열을 반환하도록 GetAllThreads로 변경하는 것도 일부 에이전트의 문제일 수 있습니다. 이벤트를 플랫폼 스레드로만 제한하는 기능이 없기 때문에 ThreadStart/ThreadEnd 이벤트를 활성화하는 기존 에이전트에 대한 성능 문제도 있을 수 있습니다.

JDWP는 다음과 같이 업데이트됩니다.

  • 스레드가 가상 스레드인지 debugger가 테스트할 수 있도록 프로토콜에 새 명령이 추가되었습니다.
  • debugger가 스레드 시작/종료 이벤트를 플랫폼 스레드로 제한할 수 있도록 EventRequest 명령에 새로운 수정자가 추가되었습니다.

JDI는 다음과 같이 업데이트됩니다.

위에서 언급했듯이 가상 스레드는 스레드 그룹의 활성 스레드로 간주되지 않습니다. 결과적으로 스레드 그룹의 플랫폼 스레드 목록을 반환하면 가상 스레드 목록은 반환하지 않습니다.

 

Degrade java.lang.ThreadGroup API

java.lang.ThreadGroup은 가상 스레드를 그룹화하는 데 적합한 API가 아니라 최신 애플리케이션에서는 거의 사용되지 않는, 스레드 그룹화를 위한 deprecated된 레거시 API입니다. ThreadGroup API는 JDK 1.0부터 시작되었고, 스레드에 대한 작업을 제어하는 형식으로 의도된 것입니다. (예를 들면 "stop all threads") 최신 코드는 Java 5부터 java.util.concurrent API에서 제공하는 스레드 풀 API를 사용할 가능성이 더 높습니다. ThreadGroup은 초기 JDK 릴리스에서 애플릿의 격리를 지원했습니다. ThreadGroup은 진단 목적으로도 유용하게끔 의도되었지만 이것은 Java 5 이후 모니터링 및 관리 지원 및 java.lang.management API로 대체되었습니다. 이 외에도 일단 ThreadGroup에는 많은 문제들이 있습니다.. (이와 관련된 문제점은 생략하겠습니다)


Limitations

VM이 가상 스레드를 일시 중단할 수 없는 상황이 있는데 이런 상황을 가지고 가상 스레드를 고정이라고 일컫습니다. 현재로선 두가지의 상황이 있습니다. 

- native 메소드가 현재 가상 스레드에서 실행 중인 경우(Java로 다시 호출하는 경우에도)

- native 모니터가 가상 스레드에 의해 유지되는 경우, 즉 현재 동기화된 블록 또는 메서드 내에서 native monitor가 실행되고 있을 때

첫 번째 제한 사항은 그대로 가겠지만 두 번째 제한 사항은 향후 제거될 수 있습니다. 가상 스레드가 예를 들어 blocking I/O 작업을 수행하여 고정을 시도하면 고정된 상태에서 해제되지 않고 그 밑의 OS 스레드가 작업 기간 동안 차단됩니다. 이러한 이유로 장기간 자주 고정되는 일이 발생하면 가상 스레드의 확장성이 손상될 수 있습니다. 따라서 가상 스레드를 최대한 활용하려면 자주 실행되고 잠재적으로 긴 I/O 작업을 보호하는 동기화된 블록 또는 메서드를 java.util.concurrent.ReentrantLock으로 교체해야 합니다.


Risks and Assumptions

이 제안의 주요 위험은 기존 API 및 구현의 변경으로 인한 호환성 위험입니다.

  • java.io 패키지의 여러 API에서 사용하는 내부 locking이 변경되었습니다. 구체적으로 BufferedInputStream, BufferedOutputStream, BufferedReader, BufferedWriter, PrintStream 및 PrintWriter의 locking이 변경되었습니다. 이는 I/O 작업이 스트림에서 동기화된다고 가정하는 코드에 영향을 줄 수 있습니다. 이 변경은 이러한 클래스를 확장하고 상위 클래스에 의한 locking을 가정하는 코드에는 영향을 미치지 않습니다. 또한 java.io.Reader 또는 java.io.Writer를 확장하고 해당 API에 의해 노출된 lock object를 사용하는 코드에 영향을 주지 않습니다.
  • Legacy인 java.lang.ThreadGroup이 크게 변경되었습니다. ThreadGroup을 명시적으로 없앨 수 있는 기능이 제거 되었고, 데몬 ThreadGroup의 개념도 제거되었습니다. ThreadGroup 일시 중단, 재개 및 중지 메서드는 예외를 던지게끔 변경되었습니다.

가상 스레드나 새 API를 사용하는 신규 코드를 사용하는 기존 코드를 활용 할 때 플랫폼 스레드와 가상 스레드 사이에 몇 가지 동작 차이를 발견할 수 있습니다.

  • Thread stop, suspend 및 resume 메소드는 가상 스레드에서 호출될 때 UnsupportedOperationException을 발생시키도록 지정됩니다.
  • Thread setPriority 메서드는 가상 스레드에서 호출될 때 작동하지 않습니다(가상 스레드의 우선 순위는 항상 Thread.NORM_PRIORITY이므로).
  • 스레드 setDaemon 메서드는 가상 스레드를 데몬이 아닌 스레드로 변경하기 위해 호출되는 경우 UnsupportedOperationException을 발생시킵니다.
  • Thread local을 지원하지 않는 스레드 생성이 가능하도록 업데이트 되었습니다. ThreadLocal::set 및 Thread::setContextClassLoader는 스레드 로컬을 지원하지 않는 스레드 컨텍스트에서 호출되는 경우 UnsupportedOperationException을 발생시키도록 변경되었습니다.
  • Thread.getAllThreadStacks는 모든 스레드가 아닌 모든 플랫폼 스레드의 맵을 반환하도록 다시 지정되었습니다.
  • java.net.Socket, java.net.ServerSocket 및 java.net.DatagramSocket에 의해 정의된 blocking I/O 메소드는 가상 스레드 컨텍스트에서 호출될 때 인터럽트가 가능하게끔 바뀌었습니다. 
  • 가상 스레드는 ThreadGroup의 활성 구성원이 아닙니다. 가상 스레드에서 Thread::getThreadGroup을 호출하면 비어 있는 더미 "VirtualThreads" 그룹이 반환됩니다.
  • SecurityManager 세트로 실행할 때 가상 스레드에는 권한이 없습니다.

 

 

 

 


가상 스레드는 운영 체제가 아닌 Java 가상 머신에 의해 예약된 user-mode 스레드입니다. 가상 스레드는 리소스가 거의 필요하지 않으며 단일 Java 가상 머신은 수백만 개의 가상 스레드를 지원할 수 있습니다. 가상 스레드는 대부분의 시간을 차단하고 I/O 작업이 완료될 때까지 기다리는 작업을 실행하는 데 적합합니다.

 

 

 

결론.

하드웨어 자원을 효율적으로 사용하는 한편, 동시 프로그래밍을 훨씬 더 쉽게 만드는 것이 목표인 가상스레드이다. 처리량이 많은 동시 애플리케이션을 작성, 유지관리, 모니터링하는 데 필요한 리소스를 ‘크게’ 줄이기 위한 자바용 가상 스레드가 세상에 출현하게 된 것이다.  가상 스레드는 JVM에 의해 관리되므로 할당하는 데에 있어 시스템 호출이 필요하지 않고, Context Switching이 없다는 장점을 가지고 있으며, 기존 비동기 프로그래밍보다 디버깅이 쉽다.

가상 스레드는 내부적으로 사용되는 실제 커널 스레드인 캐리어스레드에서 실행되기 때문에 아주 많이 생성할 수 있으며 가상 스레드는 캐리어 스레드를 차단하지 않는다(하지만 네이티브 메소드에서 blocking IO를 수행하면 블로킹되긴 함). 가상스레드를 구성하는 것은 'continuation'과 'scheduler'이다. 

 

 

+ 추가

JEP 444 내용 (https://openjdk.org/jeps/444?fbclid=IwAR2zOZjrxeDCvWHcgnVOkpBLWNKPlrO1DaGU_gjeppWxv7XPfWP1CKpduH8&mibextid=S66gvF)

 

JEP 444에서는 가상 스레드 실행 시스템을 구현하는 내용에 대한 개요를 다루고 있습니다. 구현에 대한 구체적인 내용은 자세히 다루지 않았지만, 구현 과정에서 고려해야 할 몇 가지 주요 개념들을 언급하고 있습니다.

첫째, 가상 스레드 실행 시스템은 기존의 자바 스레드 실행 시스템과 유사하지만, 자바 가상 스레드가 네이티브 스레드와 1:1 대응되지 않으므로, 스레드 풀이나 스레드 생성/제거 등의 동작을 다르게 처리해야 합니다.

둘째, 가상 스레드의 실행 시간과 생명 주기를 관리하기 위해, 새로운 개념인 "Continuation"이 도입됩니다. Continuation은 일시 중지된 가상 스레드의 상태를 저장하고, 이를 다시 로드하여 실행을 재개할 수 있는 객체입니다. Continuation을 사용하면, 더 효율적인 가상 스레드 실행 시간 관리 및 스레드 상태 저장/로드가 가능합니다.

셋째, 가상 스레드 실행 시스템은 기존의 자바 스레드와 호환성을 유지해야 합니다. 이를 위해, 가상 스레드와 자바 스레드가 혼합되어 실행될 수 있도록 구현되어야 합니다.

마지막으로, 가상 스레드 실행 시스템은 높은 확장성과 성능을 보장해야 합니다. 이를 위해, 다양한 스레드 스케줄링 알고리즘과 I/O 관리 방식 등이 고려되어야 합니다.

이러한 개념들을 고려하여, JEP 378에서는 가상 스레드 실행 시스템을 구현하는 내용이 다루어집니다. JEP 378은 JEP 376과 함께 자바 가상 스레드에 대한 API와 실행 시스템을 제공하는 데 필요한 JEP 중 하나입니다.

 

 

 

참고 

http://gunsdevlog.blogspot.com/2020/09/java-project-loom-reactive-streams.html

-내용 출처 : 우아한 Tech 채널 (디디의 Redis)

 

  • Redis
    • Remote Dictonary Server
    • 원격의 Key,Value 구조 서버로 해석할 수 있다. 
  • Cache
    • 나중의 요청에 대한 결과를 미리 저장했다가 빠르게 사용하는 것
    • 어디에 ? 메모리 구조를 먼저 살펴보자.
  • 메모리구조
    • Storage (SSD, HDD) -> Main Memory (DRAM) -> CPU Cache -> CPU Register
      • -> 이 순으로 속도가 빠르고, 비싸다.
    • 맥북을 예로 들면?
      • i7 CPU - 12 MB Cache Memory / 16GB DRAM / 512GB SSD
        • 12MB Cache Memory (SRAM) : 엄청 빠르고, 비싼데 용량이 작음->데이터베이스로 사용하기엔 작음
        • 16GB DRAM : 적당히 빠르고, 비싸고, 크고 휘발성임 -> 휘발성이라는 것은 컴퓨터가 꺼지면 데이터가 전부 날라가게 됨
        • 512GB SSD : 비교적 느리고, 저렴하고, 용량이 엄청큼, 그리고 비휘발성! 
    • 데이터베이스는 컴퓨터가 꺼져도 데이터를 유지해야 하기 때문에 SSD에 기본적으로 저장함
    • 하지만 기술이 발달하고, 하드웨어가 커지다 보니 메인메모리에 저장해서 좀 더 빠르고 쉽게 데이터에 접근하면 어떨까? 하는 접근방식으로 나온 것이 Redis
Database보다 더 빠른 Memory에 더 자주 접근하고 덜 자주 바뀌는 데이터를 저장하자
In-memory Database Redis (Cache)

 

  • Data Structure
    • Collection을 지원함 (Memcached와 다른 점)
    • 자바를 예로 들면 아래와 같은 자료구조를 제공한다.
      • Map.Entry
      • LinkedList
      • HashSet
      • TreeSet
      • HashMap
  • 어디에서 쓰나요?
    • 여러 서버에서 같은 데이터를 공유할 때
  • 주의해야 할 점
    • Single Thread 서버 이므로 시간 복잡도를 고려해야 한다.
      • Redis는 기본적으로 Single Threaded를 활용함, 이를 통해 여러 개의 Thread가 경합하는 Race Condition을 피하려고 했음 (이 외에도 여러 방법을 통해 Race Condition을 방지하려 함)
      • 네트워크로 부터 요청을 받아서 처리를 할 때 Command가 오랜 시간이 걸리는 경우 나머지 요청들이 더 이상 받아지지 않고 서버가 다운되는 문제가 발생될 수 있음
      • O(N)의 명령어 같은 경우는 지양해야 한다. (싱글쓰레드기 때문에 처리가 그만큼 빨라야 한다)
        • 예를 들면 모든 Key들을 가져오는 명령어, Flush(), GetAll() 같은 것
    • In-memory 특성상 메모리 파편화, 가상 메모리 등의 이해가 필요
  • 메모리 관리
    • 메모리 파편화
    • 가상메모리 Swap
    • Replication - Fork
      • 메모리 데이터 저장소이기 때문에 데이터 유실될 문제를 안고 있음
      • 복사 기능을 제공해주기 때문에 slave redis server 혹은 디스크에 데이터를 복사 저장함
      • 복사를 할 때 프로세스를 그대로 복사해서 사용하는 과정을 거치는데 만약 메모리가 꽉 차 있다면 복사가 잘 안되어 서버가 죽는 경우가 생길 수 있기 때문에 메모리를 여유있게 사용해야 함

분할정복 알고리즘으로 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각을 하나로 합친다. 

  @Test
    public void mergeSortTest() {
        // divide-and-conquer 알고리즘
        // 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각을 하나로 합친다.
        // 병합정렬 성능은 O(nlogn), 각각의 병합시간이 O(n)이다.
        // 왼쪽으로 나눈 리스트를 정렬하고 -> 오른쪽으로 나눈 리스트를 정렬한다.

        List<Integer> values = Arrays.asList(7,1,3,2,3,9,2,5);
        List<Integer> sorted = divide(values);
        System.out.println(sorted);
    }

    public List<Integer> divide(final List<Integer> values) {
        if (values.size() < 2) {
            return values;
        }

        int listSize = values.size();

        final List<Integer> leftHalf = values.subList(0, listSize / 2);
        final List<Integer> rightHalf = values.subList(listSize / 2, listSize);

        System.out.println("-- dividing..leftHalf : " + leftHalf + " , rightHalf : " + rightHalf);

        return conquer(divide(leftHalf), divide(rightHalf));
    }

    private List<Integer> conquer(final List<Integer> left, final List<Integer> right) {
        System.out.println("## merging.. leftHalf : " + left + " , rightHalf : " + right);
        int leftPtr = 0;
        int rightPtr = 0;

        final List<Integer> merged = new ArrayList<>(left.size() + right.size());

        int leftSize = left.size();
        int rightSize = right.size();

        while (leftPtr < leftSize && rightPtr < rightSize) {
            if (left.get(leftPtr) < right.get(rightPtr)) {
                merged.add(left.get(leftPtr));
                leftPtr++;
            } else {
                merged.add(right.get(rightPtr));
                rightPtr++;
            }
        }

        while (leftPtr < leftSize) {
            merged.add(left.get(leftPtr));
            leftPtr++;
        }

        while (rightPtr < rightSize) {
            merged.add(right.get(rightPtr));
            rightPtr++;
        }

        System.out.println("## merged : " + merged);

        return merged;
    }
-- dividing..leftHalf : [7, 1, 3, 2] , rightHalf : [3, 9, 2, 5]
-- dividing..leftHalf : [7, 1] , rightHalf : [3, 2]
-- dividing..leftHalf : [7] , rightHalf : [1]
## merging.. leftHalf : [7] , rightHalf : [1]
## merged : [1, 7]
-- dividing..leftHalf : [3] , rightHalf : [2]
## merging.. leftHalf : [3] , rightHalf : [2]
## merged : [2, 3]
## merging.. leftHalf : [1, 7] , rightHalf : [2, 3]
## merged : [1, 2, 3, 7]
-- dividing..leftHalf : [3, 9] , rightHalf : [2, 5]
-- dividing..leftHalf : [3] , rightHalf : [9]
## merging.. leftHalf : [3] , rightHalf : [9]
## merged : [3, 9]
-- dividing..leftHalf : [2] , rightHalf : [5]
## merging.. leftHalf : [2] , rightHalf : [5]
## merged : [2, 5]
## merging.. leftHalf : [3, 9] , rightHalf : [2, 5]
## merged : [2, 3, 5, 9]
## merging.. leftHalf : [1, 2, 3, 7] , rightHalf : [2, 3, 5, 9]
## merged : [1, 2, 2, 3, 3, 5, 7, 9]
[1, 2, 2, 3, 3, 5, 7, 9]

 

병합정렬의 성능은 O(nlogn)이고 각각의 병합시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반만큼만 발생한다는 사실을 다시 한번 기억하자.

출처 : JAVA 프로그래밍 면접 이렇게 준비한다

'알고리즘과 디자인패턴' 카테고리의 다른 글

Java Decorator Pattern 설명과 예시  (0) 2023.03.09
알고리즘 관련 to know list  (0) 2022.03.29
리스트 정렬하기  (0) 2022.01.23
자바 알고리즘 스터디  (0) 2021.08.11

+ Recent posts