treecode

EC2(Elastic Compute Cloud)

- 가상의 서버로, 가상 서버를 실행하는 머신 이미지를 AMI(Amazon Machine Image),실행된 가상 서버는 인스턴스라고 부른다.

ELB(Elastic Load Balancing)

- 앞(front)에서 요청을 받아 여러 개의 EC2 인스턴스로 통신을 분산시켜 준다. 보통 Auto Scaling과 함께 쓴다.

Auto Scaling

- CPU 또는 메모리 사용량 등에 따라 EC2 인스턴스를 자동으로 조절하는 서비스

S3(Simple Storage Service)

- 온라인 스토리지 서비스로 데이터 조작에 HTTP/HTTPS API가 사용된다. 매우 높은 내구성과 가용성을 가지므로 대부분의 파일은 S3에 저장, 백업해둔다. (EBS에 보관하는 경우 데이터 손실 위험)

Glacier

- 데이터를 장기 보관하기 위해 설계된 서비스로, S3와 동등한 신뢰성 설계에 저렴한 비용으로 사용할 수 있다. 장기간 보관하는 데이터는 S3에서 Glacier에 보관하도록 활용할 수 있다.

EBS(Elastic Block Store)

- EC2 인스턴스에서 사용하는 스토리지로, EC2와는 네트워크 기반으로 연결 된다. EBS는 스토리지 이미지를 스냅샷 형식으로 S3에 백업해서 보관, 복제를 쉽게 할 수 있다.

VPC(Virtual Private Cloud)

- AWS 네트워크 내부에서 논리적으로 분리된 네트워크를 생성하는 서비스

RDS

- AWS 데이터베이스 PaaS로 트랜잭션 로그를 사용한 레플리케이션(데이터 저장 또는 백업하는 방법과 관련된 데이터를 다른 컴퓨터로 복제)으로 마스터/ 슬레이브 구성, 특정 시간 백업 같은 AWS에서 제공하는 기능이 많다.

CloudFront

- 콘텐츠 전송 네트워크(CDN) 서비스로 콘텐츠를 엣지 로케이션이라고 부르는 전 세계에 퍼져 있는 거점을 기반을 전달한다.

Route 53

- DNS 서비스로 취약성 또는 DDoS 공격에 대한 대응, DNS 운용을 쉽게 할 수 있게 해주는 서비스로 100%의 SLA(Service Level Agreement)를 보증

AWS의 글로벌 인프라를 지탱하는 물리적 구성으로는 리전과 가용 영역(AZ)가 있는데 리전은 AWS가 서비스를 제공하는 거점(국가와 지역)을 나타내고 AZ는 데이터 센터와 같은 의미라고 할 수 있다. 각각의 리전에는 2개 이상의 AZ가 존재한다.

RDS에서 멀티 AZ 옵션을 사용하면 마스터/슬레이브 구성의 DB 서버가 생성되며 데이터가 동기화된다. 마스터 DB에 장애 발생시 마스터 DB와 슬레이브 DB가 교체가 되며 쉽게 가용성/내결함성이 높은 인프라를 구축할 수 있다.

AWS가 제공하는 네트워크는 크게 AWS 네트워크와 VPC 네트워크로 AWS 네트워크는 인터넷에서 접근할 수 있는 네트워크를 나타내며, VPC 네트워크는 VPC 환경 내부에서만 사용할 수 있는 닫힌 네트워크를 나타낸다.

IAM

AWS에 처음 회원 가입을 하면 Root 사용자 계정으로 로그인을 할 수 있는데 그냥 사용하면 취약하기 때문에 MFA를 설정하는 것이 좋다.

그리고 Root 계정을 직접적으로 사용하기보다는 개별적인 사용자 계정인 IAM 계정을 사용하는 것이 안전하다. (세부적인 권한 설정과 해킹 당했을 경우에 루트 계정에서 제어)

인증(Authentication)과 권한 부여(Authorization)가 나뉘는데 인증에 대한 부분이 Group, Role이고 권한 부여에 대한 부분은 IAM Policy다. Group, User는 말 그대로 그룹별  IAM 사용자 계정을 만드는 것이고 IAM Role은 일시적으로 특정 개체에게 리소스의 접근 권한을 부여하기 위해 사용한다. 그리고 User든 Role이든 어디까지 권한을 줄 것인지를 결정하는 것이 IAM Policy가 된다. IAM Role은 아무나 호출할 수 없도록 신뢰 관계(Role을 얻을 수 있는 대상)를 설정하는 것이 중요하다.

[참고]

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소 (실제 사용 영역은 제한적)
  • Memory 사용량 감소
  • 빠른 응답 시간 (의미 있는 것을 더 올려놓기 때문)

페이지 테이블에는 valid-invalid bit가 있는데 물리 메모리에 페이지가 올라와 있는지를 체크해주는 역할을 한다. 물리 메모리 오른쪽의 그림은 swap area로 사용되지 않는 페이지를 backing store(Disk)에 두는 것인데 요청한 페이지가 물리 메모리에 없을 경우 Page Fault가 발생하고 swap area에서 페이지를 읽어온다.

page fault가 발생하면 MMU(메모리 주소 변환을 해주는 하드웨어)는 trap을 발생시키는데 이때 CPU가 현재 프로세스에서 운영체제로 넘어가고 page fault handler가 동작한다 .

page fault handler는 먼저 정상적인 메모리 요청인지 확인을 한 뒤 물리 메모리의 비어 있는 페이지 프레임을 찾고 없으면 replace 작업을 한다.

DIsk I/O 작업은 비교적 굉장히 오래 걸리기 때문에 프로세스를 block 상태로 만들고 I/O 작업이 끝나면 Invalid bit를 valid로 바꾸고 프로세스를 Ready Queue에 넣는다.

페이지 교체 알고리즘 (Replace Algorithm)

• Optimal Algorithm
  • 가장 먼 미래에 참조되는 페이지를 쫓아내는데 사실상 미래를 예측하기 어려워서 비현실적
  • 이상적인 케이스를 통해 다른 알고리즘과의 성능 비교를 위해 사용(upper bound)
• FIFO
  • FIFO Anomaly : 메모리 크기를 늘리면 page fault가 오히려 증가할 수 있다
• LRU (Least Recently Used)
  • 가장 오래전에 사용된 것을 교체 (들어온 것 기준 x)
  • 과거에 많이 참조가 되었더라도 가장 오래 전에 사용이 됐으면 교체가 되는 단점
  • 링크드 리스트로 구현을 해서 교체 시간 O(1)
• LFU (Least Frequently Used)
  • 참조 횟수가 가장 적은 페이지를 지움
  • 이제 막 참조가 시작된 페이지가 교체되어버리는 경우가 생기는 단점
  • heap 구조 O(log n)

가상 메모리 페이징 기법에서는 LRU, LFU 같은 알고리즘 적용이 어렵다. 왜냐하면 메모리 주소 변환 작업을 운영체제가 관여하지 않아서 언제 어떤 페이지가 참조되었고 얼마나 참조 되었는지 이런 부분을 체크하기 어렵기 때문이다.

Clock Algorithm

• 최근에 페이지가 참조가 되면 reference bit를 1로 설정 (하드웨어가 함)
• 운영체제는 reference bit가 1이면 0으로 바꾸고 그 다음 페이지 비트 검사
• reference bit가 0인 페이지를 만나면 교체
• 가장 오래 전에 참조된 페이지를 교체하진 않지만 LRU와 어느정도 비슷한 효과
• modified bit : 최근에 페이지가 변경되었는지 확인
• modified bit가 0이면 그냥 메모리에서 지우면 되는데 modified bit가 1이면 변경(write)이 있다는 것이므로 디스크에 수정된 내용을 반영

Thrashing

동시에 실행되는 프로그램이 증가하면 프로세스마다 할당되는 메모리가 부족해지고 최소한의 page frame을 할당받지 못해서 Page Fault가 증가하게 된다. 그러면 Disk I/O 작업으로 인해 CPU 이용률이 떨어지게 되는데 이때 운영체제는 CPU 이용률이 부족한 것을 멀티프로그래밍 개수를 늘려야겠다고 판단하는데 이러한 현상을 Thrashing이라 한다.

멀티 프로그래밍 개수를 조절하기 위해 Working-Set 모델이 있는데 working-set이란 특정 시간에 집중적으로 참조되는 page들의 집합으로 프로세스가 일정 시간동안 원활하게 수행되기 위해서 해당 페이지 집합을 전부 메모리에 올리는 것을 말한다. working-set이 보장이 안 되면 모든 프레임을 반납하고 swap-out(suspend) 시켜서 thrashing 현상을 방지할 수 있다.

페이지 단위가 너무 작으면 내부 단편화를 방지할 수 있지만 페이지 테이블 크기가 증가하고 Page Fault로 인한 Disk I/O가 많이 발생한다. 반면 페이지 단위가 클 경우 내부 단편화와 transfer 시간이 오래 걸리고 필요없는 정보까지 메모리에 올라오는 단점이 있다.

[참고]

일반적으로 사용하는 HashMap 의 경우 동시성을 보장해주지 않아서 멀티 스레드 환경에서 의도한대로 동작하지 않는다.

이전에 HashMap의 동작 방식에 대해 학습을 해봤는데 간단하게 정리하면 HashMap은 key 값으로 사용하는 객체의 hashCode()를 활용해서 배열(버킷)의 index를 구한다. 하지만 버킷의 크기는 제한적이고 동적으로 확장 시키면서 사용하기 때문에 다른 key, 같은 index를 가지는 경우가 생기고 이런 경우 자바에서는 링크드 리스트 또는 트리 노드 형태로 연결(Chaining) 시키면서 값을 저장한다.

다음은 HashMap을 사용하고 동시에 여러 스레드에서 User를 저장하는 코드이다. save() 메서드는 id 값을 늘리고 user에 담아서 HashMap에 저장하는 간단한 동작이다.

테스트 코드는 ThreadPool을 여러개 생성하고 스레드별로 for문을 돌리면서 save()를 호출하도록 한다. CountDownLatch는 스레드가 종료될때마다 값을 countDown()으로 내리면서 0이 될때까지 대기(await)를 하는데 Main 스레드가 동작하는 것을 막기 위해 사용했다.

리뷰어님한테 동시성 테스트의 경우 확률에 따라 영향을 받는다는 점을 유의하라는 피드백을 받고 @RepeatedTest를 통해 테스트를 반복해봤는데 여러번 돌려보니까 첫번째는 항상 실패를 하고 이후부터는 거의 다 성공을 한다.

뭔가 이상해서 테스트 수행 시간을 보니 첫번째 테스트를 하기 전에 초기화(?) 작업들을 하면서 시간이 오래 걸리고 그 영향으로 계속 실패를 하는 것 같았다. 실제로는 테스트 케이스가 너무 적어서 동시성 문제가 거의 발생하지 않는 상황인 것이다. 그래서 테스트 케이스를 확 늘려보니 의도한 결과가 나왔다. 동시성 테스트를 할 때는 반복 횟수와 테스트 케이스를 높게 주는 것을 신경 써야겠다.

자바는 HashMap의 동시성 문제를 해결하기 위해 ConcurrentHashMap(java.util.concurrent)을 제공하는데 ConcurrentHashMap으로 바꿔봐도 테스트는 여전히 실패한다. ConcurrentHashMap의 key 값으로 사용하는 Long 타입의 값을 증가시키는 과정에서 동시성 문제가 발생하기 때문이다. 자바는 언어 명세상 long, double을 제외한 변수를 읽고 쓰는 것이 원자적으로 수정이 완전히 반영된 값을 읽어오지만 한 스레드가 변경한 값이 다른 스레드에서 보이는가를 보장하지 않는다. 그래서 한 스레드가 변경한 값이 반영되기 전에 다른 스레드가 값을 읽어온 상태면 같은 id 값을 가지는 문제가 생긴다. (이펙티브 자바)

AtomicLong(java.util.concurrent)을 사용하면 이런 문제를 해결할 수 있다. 스레드는 메인 메모리에서 값을 읽어와서 CPU 캐시 메모리에 저장을 하는데 volatile 키워드를 사용하면 메인 메모리에서 직접 값을 읽어올 수 있다.

AtomicLong은 CAS(Compare-And-Swap) 알고리즘을 활용한 lock free 방식으로 동작하는데 내부적으로 volatile을 사용해서 스레드에 저장된 값과 메인 메모리의 값을 비교하고 같으면 변경하는 식으로 동작한다. 만약 값을 비교해서 다르면 재시도를 하기 때문에 synchronized처럼 락을 걸 필요가 없다. 다시 테스트를 해보니 정상적으로 통과가 되었다.

ConcurrentHashMap은 CAS와 부분적으로 lock을 사용해서 동시성을 보장하는데 빈 버킷에 값을 저장할때는 CAS를 사용하고 버킷에 노드가 존재하는 경우 블록 단위로 synchronized를 사용해서 값을 저장한다. read를 할 때는 락을 걸지 않기 때문에 성능도 준수한 편이다.

멀티 스레드 환경에서는 공유 자원으로 인해 발생하는 문제를 조심해야 하는데 상황에 따라 ThreadLocal을 활용하는 것도 좋을 것 같다. (ThreadPool의 경우 스레드를 재사용하기 때문에 초기화에 신경써야 한다.)

[참고]

https://www.geeksforgeeks.org/concurrenthashmap-in-java/

코드스쿼드 미션으로 게시판을 구현해보는데 이전에 혼자 게시판을 만들어 볼 때는 구현하기 급급했다면 이번에는 왜 이걸 썼는지 좀 생각하면서 구현을 해보려고 한다.

먼저 DB 연동 없이 자바 코드로 Repository를 구현하면서 동시성 처리를 위해 ConcurrentHashMap을 사용했는데 대충 알고 쓰는 것 같아서 정리를 하기 위해 HashMap의 구조부터 학습을 했다.

해싱(Hashing)이란 해시 함수를 이용해서 데이터를 해시 테이블에 저장하고 검색하는 방법으로 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 알고리즘 함수이다.

HashMap은 해싱을 구현한 컬렉션 자료구조로 키에 대한 해시 값을 사용하여 값을 저장하는 Associate array(key-value의 형태로 키를 통해 연관되는 값을 얻을 수 있는 자료 구조)이다.

HashMap은 배열 + 링크드 리스트의 조합으로 되어 있는데 링크드 리스트는 데이터의 삽입, 삭제와 같은 동작에는 효율적이지만 검색 속도는 비효율적이다. 하지만 HashMap은 Node를 배열(버킷)로 가지고 있는 형태이기 때문에 조회 속도가 O(1)로 빠른 편이다.

그런데 왜 HashMap은 왜 배열 + 링크드 리스트 구조로 되어 있을까? 자바의 HashMap은 객체의 hashCode()를 해시 함수로 사용하는데 Object 클래스의 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시 코드를 만들어 내며 int 값을 반환한다. 하지만 HashMap 배열(버킷)의 용량이 값을 모두 수용할 수 없으며 메모리 효율 문제도 있기 때문에 해시 코드 값에 나머지 연산을 활용하여 버킷의 index를 구한다. (균등하게 index를 분포하기 위해 보조 해시 함수도 사용한다고 한다.)  그렇게 되면 중복된 key 값을 가지는 경우가 생기는데 이를 해시 충돌이라 한다.

해시 충돌이 발생할 경우를 대비해여 Open Addressing, Separate Chaining 이 있다.

HashMap은 Separate Chaining 방식을 사용하는데 같은 Key를 가지는 경우 equals()를 비교해서 같으면 동일 객체로 판단하여 교체를 하고 다르면 Chaining으로 연결을 한다.

Java8 부터는 데이터가 많아질 경우 개수에 따라 Tree로 변환한다.

HashMap의 버킷 용량이 동적으로 확장될 때마다 모든 key-value를 읽어서 Separate Chaining을 재구성해야 하기 때문에 상황에 따라 생성자로 initialCapacity, loadFactor를 정의해주는 것도 좋을 것 같다.

[참고]

https://d2.naver.com/helloworld/831311