1️⃣ 발단

공차를 주문하려고 배달의 민족에 들어갔다. 블랙 밀크티 펄 추가 당도 100짜리 밀크티를 장바구니에 담다가 문득 궁금해졌다.

🤔 배달 장바구니랑 배민1 장바구니는 따로인가?

2️⃣ 전개

담아봤다. 같은 가게의 메뉴만 담을 수 있다는 경고문이 뜬다. 동일한 가게라도 배달 서비스와 배민1 서비스의 장바구니를 공유할 수 없다.

애초에 배달 서비스 입점 가게와 배민 1 서비스 입점 가게를 다른 가게로 분류하고 있다. 단, 같은 가게라면 함께 주문 서비스는 동일 장바구니를 이용한다. 그럼 B마트는 어떨까?

담아진다. (+ 간편식/밀키트 서비스는 B마트 장바구니에 담아진다.) 그렇다면 배민스토어는?

담아진다. 배달/배민1과 B마트와는 다른 장바구니가 생긴다. 전국 별미도 마찬가지로 별개의 장바구니에 담아진다. 선물하기 서비스는 구매 후 바로 선물로 넘어가기에 장바구니가 따로 없다.

대강 정리해보면 이렇게 된다.

• 배달 서비스와 배민 1 서비스는 같은 장바구니를 공유한다.

  • 배달 서비스 가게의 메뉴를 장바구니에 담은 경우, 배민 1의 메뉴는 추가 불가능
  • 배달 서비스의 가게와 배민 1 서비스의 가게는 다른 가게로 취급
  • 함께주문 서비스는 배달/배민1 서비스와 동일 장바구니를 사용한다

• B마트 서비스엔 별도의 장바구니가 존재한다.

• 배민 스토어 서비스엔 별도의 장바구니가 존재한다.

• 전국 별미 서비스에도 별도의 장바구니가 존재한다.

장바구니.. 짱많아...!

그럼 이제 몇 가지 의문이 생긴다.

[ 서비스 관련 의문 ]

• 배민 1은 왜 별도의 장바구니를 갖지 않는가?
  • 배민 1은 나중에 추가된 서비스다.
  • 배민 1은 일반 배달 서비스와는 배달비 책정 방식, 배달 시간, 쿠폰 적용 등등이 전부 다르게 적용된다.
  • 배민 1은 배달 서비스와 별도의 카테고리로 분류된다.
  • B마트, 배민스토어 등과 동일하게 별도의 장바구니를 만들어도 되지 않나?

[ 개발 관련 의문 ]

• 장바구니 서비스 내부에서 도메인별 장바구니를 구분하는 방법은 뭘까?
  • 배달의 민족은 각 도메인을 마이크로 서비스로 분리한 MSA 구조로 설계되어 있다(고 들었다.)
  • 그럼 장바구니 서비스도 아마 마이크로 서비스로 분리되어 있을 것이다.
• 특정 도메인 (ex. B마트)에 어떻게 해당 도메인의 장바구니를 제공해줄 수 있을까?
  • API를 분리하나? 근데 그럼 클라쪽에서 도메인별 장바구니 맵핑 로직을 관리해야하는걸?
  • 테이블을 다 분리하나?
  • 아니면 하나의 테이블 안에서 컬럼으로 구분해?
  • RDB가 맞긴 할까?
• 신규 서비스가 런칭되면 또 장바구니 종류를 추가해야 한다. 기존 장바구니들을 건드리지 않으면서 신규 장바구니를 추가하는 방법은 뭘까?

배달의 민족 (우아한형제들)은 기술 블로그가 정말 잘 되어있다. 한번 장바구니 서비스를 검색해보자.

아쉽지만 장바구니 관련 게시글은 없었다. (근데 왜 페이지 사이즈를 3으로 정한걸까?) 그럼 이제 뇌피셜을 펼쳐보자.

3️⃣ 위기

일단 RDB를 쓴다고 가정하자. 1. 도메인별 관계가 명확하고 2. 스키마가 고정적이기 때문이다. 요구사항은 아래와 같다.

• 유저는 도메인별 장바구니를 가질 수 있다 (배달, 배민스토어, B마트 등)
• 각 장바구니는 가게와 1:1 관계를 가진다 (한 장바구니에는 같은 가게 메뉴만 담을 수 있음)
• 장바구니에는 여러 메뉴가 담길 수 있고, 담을 수 있는 메뉴에 개수 제한은 없다.
• 장바구니에 담은 메뉴는 당장 주문하지 않더라도 삭제할 때까지 장바구니에 남아있어야 한다.

유저가 도메인별 장바구니를 가지게 하는 방법을 몇 가지 고민해보자.

1. 1:N 관계를 만들고 장바구니 테이블에 도메인 구분 컬럼을 갖게 한다.

깊게 생각 안하고 바로 그려봤다. boolean 타입의 컬럼으로 어떤 도메인에 해당하는 장바구니인지를 구분하는 방식이다.

괜찮은데? 싶을지 몰라도 문제가 아주 많다.

(1) 새로운 서비스를 런칭하려면 ddl를 이용해야 한다. 기존 저장된 모든 데이터 레코드 구조를 변경해야 한다. 유저의 수 x n개 만큼의 장바구니 레코드가 있을텐데, 이 데이터를 한꺼번에 변경하는 것은 위험하고, 시간이 얼마나 걸릴지도 알 수 없는 일이다.

물론 운영 환경과 동일한 테스트 환경을 만들고 예상 시간을 측정해볼 수도 있지만, 혹시라도 예상치 못한 이슈가 발생할 수 있고, 그로 인해 데이터 무결성이 손상될 수도 있다는 점을 생각하면 딱히 고르고 싶은 선택지는 아니다.

운영 환경에서 발생할 수 있는 모든 잠재적 위험성을 체크하고, 유저들에게 서버 점검 공지를 날리고, ddl을 수행하고... 일단 난 심장이 떨린다ㅋㅋ

(2) *중복 값이 너무 많아진다. * 위 예시는 PK, FK, 구분컬럼만 뒀지만 실제로는 더 많은 정보가 필요할 것이다. 구분자 컬럼에 true, false 값을 할당하기 위해 유저별로 구분 컬럼의 개수만큼 레코드가 필요하고, 따라서 그만큼 데이터가 중복된다.

(3) 장바구니를 초기화하는 방식이 더러워진다.

신규 유저가 회원가입을 하면, 모든 도메인별로 장바구니 데이터를 추가해 초기화해야한다. (그래야 유저가 장바구니에 아이템을 바로바로 담을 수 있을테니까)

위 설계에선 케이스별로 CART 생성자를 만들어야하며, 신규 서비스가 런칭이 될 경우 기존 만들었던 생성자들을 전부 수정해줘야 한다.

정적 팩토리 메소드를 이용한 예시. 해당 메소드를 호출하는 클라이언트단을 수정할 필요는 없겠지만, 그래도 팩토리 메소드 하나하나를 수정해줘야 하는건 동일하다.

그래서 이번엔 boolean이 아니라 enum 컬럼을 이용해 장바구니를 구별해봤다. 위에서 발생했던 문제들을 하나하나 되짚어보자.

(1) 새로운 서비스를 런칭하려면 ddl를 이용해야 한다. => 해결 안됨 => 기존 레코드에 값을 Update 쳐 줄 필요는 없지만 enum 선택지를 늘려주기 위해 ddl을 이용해야하는 건 마찬가지다. => boolean 사용 방식보단 나아졌지만 여전히 완벽한 대안은 아니다.

(2) 중복 값이 너무 많아진다. => 해결 안됨 => type (도메인) 수 만큼 레코드를 추가해야하므로 데이터 중복은 여전하다.

(3) 장바구니를 초기화하는 방식이 더러워진다. => 해결?!

이제 신규 서비스가 런칭되었다고 생성자를 수정할 필요는 없다. Type 값만 넘겨주면 되니까!

도메인별 장바구니 생성하는 것도 간단하다. enum을 순회돌면서 cart를 생성하면 끝. 따라서 enum 클래스에 신규 값만 추가해주면 그 외 코드는 수정하지 않아도 된다.

언뜻 보면 해결된 것 같지만, (1), (2)의 문제가 그대로 남아있다. 그러니 enum을 이용한 1:N 관계는 일단 킵해보자.

2. 장바구니 테이블을 도메인별로 분리한다.

음 일단 테이블이 엄청나게 늘어났다ㅋㅋ

4️⃣ 결말

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

📢 키-값 저장소 : 고유 식별자 키에 매칭되는 값의 키-값 쌍(pair) 구조의 비 관계형 데이터베이스

• 키는 유일하며, 키를 통해서만 값에 접근할 수 있다.
  • 키는 텍스트 또는 해시 값
  • 키가 짧을 수록 성능 상 좋다

1️⃣ 문제 이해 및 설계 범위 확정

🤔 이런 요소들을 고민해보기

• 읽기, 쓰기, 메모리 사용량 사이에서 균형 찾기
• 데이터 일관성과 가용성 사이에서 타협적 결정 내리기
• Ex. 이런 특성을 고민해보자~~
  • 키-값 쌍의 크기
  • 큰 데이터 저장 가능
  • 높은 가용성 :: 장애 있어도 빠른 응답 가능
  • 높은 규모 확장성 :: 트래픽 양에 따라 자동으로 서버 증설/삭제 가능
  • 데이터 일관성 수준 조정 가능
  • 응답 지연 시간

✨ 단일 서버 키-값 저장소

• 키-값 쌍 모두를 메모리에 해시 테이블로 저장한다
  • 가장 직관적이고 빠르지만 모든 데이터를 메모리 안에 두는 것이 불가능 할 수 있다.
  • 이를 해결하기 위해 데이터 압축, 자주 쓰이는 데이터만 메모리에 저장하는 등의 방식을 사용한다.
• 하지만 한 대 서버로 부족하게 된다면? 분산 저장소를 만들어야 한다.

2️⃣ 분산 키-값 저장소 설계

📢 = 분산 해시 테이블 : 키-값 쌍을 여러 서버에 분산시킨다.

📍 CAP 정리

• 데이터 일관성, 가용성, 파티션 감내의 세 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다.
  • 데이터 일관성 (consistency): 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐와 관계 없이 언제나 같은 데이터를 보게 되어야 한다.
  • 가용성 (availability) : 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생해도 항상 응답을 받을 수 있어야 한다.
  • 파티션 감내 (partition tolerance) : 파티션은 두 노드 사이에 통신 장애가 발생했음을 알린다. 따라서 파티션 감내는 파티션이 생겨도 시스템은 계속 동작해야 한다는 의미!

• 키-값 저장소의 분류
  • CP 시스템 : 일관성과 파티션 감내를 지원. 가용성 희생
    • 서버 A, B, C에서 C가 죽은 순간부터 서버에 읽기/쓰기 불가능
      • 일관성 = 언제, 무슨 일이 있어도 각 서버에 있는 모든 데이터가 동기화 됨’을 보장하겠다
      • 따라서 C가 죽은 순간, 데이터 일관성을 유지할 수 없으니 서버는 에러를 보낸다.
  • AP 시스템 : 가용성과 파티션 감내 지원, 데이터 일관성 희생
    • 서버 A, B, C에서 C가 죽은 순간 서버에 연산은 가능
      • 서버가 요청에 대해 ‘사용 가능’한 상태
      • 그러나 일관성을 희생했으므로, 서버에 저장된 데이터는 조금씩 다르다
      • 서버는 변경사항을 임시로 들고, 파티션 문제가 해결되면 데이터 동기화를 진행한다 = 어느 특정 시점에서 데이터 불일치 가능
  • CA 시스템 : 일관성과 가용성 지원, 파티션 감내 희생
    • 단, 통상 네트워크 장애는 피할 수 없는 문제! 분산 시스템은 반드시 파티션 이슈를 감내할 수 있어야 한다.
    • 따라서 개념상으로만 존재하지, 실세계에는 존재 X

📍 분산 시스템 데이터 보관 예시

• 세 대의 복제 (replica) 노드 n1, n2, n3에 데이터를 복제해서 보관하는 케이스를 가정
  • 이상적 상태
    • 네트워크 파티션? 응 절대 안일어나~
    • n1에 있는 데이터는 n2, n3에 자동으로 복제 → 일관성, 가용성 만족
  • 실세계의 분산 시스템
    • 네트워크 파티션? 응 절대 일어나~
      • 파티션 발생 시, 일관성과 가용성 둘 중 하나를 선택해야 한다.
    • Ex. n3가 죽어서 n1, n2와 통신할 수 없는 상황
      • CP 시스템 : 데이터 일관성을 위해 n1, n2에 대해 쓰기 연산 중단!
      • AP 시스템 : 시스템 가용성을 위해 n1, n2에 쓰기 연산 허용, 파티션 문제 해결 후 새 데이터를 n3에 전송!

📍 시스템 컴포넌트

📢 키-값 저장소 구현에 사용될 핵심 컴포넌트들

데이터 파티션

• 대규모 서비스의 경우, 데이터를 작은 파티션으로 분할한 다음 여러 대의 서버에 저장한다.
• 데이터를 파티션 단위로 나눌 때는 아래를 고려한다
  • 데이터를 여러 서버에 고르게 분산할 수 있는가?
  • 노드가 추가되거나 삭제될 때 _데이터 이동을 최소화_할 수 있는가?
• 안정 해시를 이용해 데이터를 파티션하면 이런 점이 좋다
  • 규모 확장 자동화 (automatic scaling) : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제
  • 다양성 (heterogeneity) : 각 서버 용량에 맞게 가상 노드 수를 조정할 수 있다 (= 고성능 서버는 더 많은 가상 노드)

데이터 다중화 (replication)

• 목적 : 높은 가용성과 안정성을 확보하기 위함
• 방법 : 데이터를 N개 (튜닝 가능한 값) 서버에 비동기적으로 다중화
  • N개 서버 선정 과정
    • 어떤 키를 해시 링 위에 배치 → 거기서부터 시계방향으로 링 순회하다 만나는 첫 N개 서버에 데이터 사본 보관
• 문제 : 가상 노드 사용 시, 선택한 N개 노드가 대응될 실제 물리 서버 개수가 N보다 작아질 수 있다.
• 해결 : 노드 선택 시 같은 물리 서버 중복 선택하지 않게 처리한다.
• 기타 문제 : 데이터 센터는 물리적 (정전, 자연재해 등) 문제를 겪을 수 있으니, 안정성을 위해 _데이터 사본을 다른 데이터 센터 서버에 보관_하고, _센터들은 고속 네트워크로 연결_한다.

일관성 (consistency)

• 여러 노드에 다중화된 데이터는 적절한 동기화가 필요하다.
• 정족수 합의 프로토콜 (Quorum Consensus)
  • 읽기/쓰기 연산 모두에 일관성 보장 가능
  • 관계 정의
    • N = 사본 개수
    • W = 쓰기 연산에 대한 정족수 :: 쓰기 연산 성공 = 중재자는 W개의 서버로부터 쓰기 연산 성공 응답 받아야 함
    • R = 읽기 연산에 대한 정족수 :: 읽기 연산 성공 = 중재자는 R개의 서버로부터 응답 받아야 함
  • 면접에서 N, W, R 정하기
    • W = 1, R = N : 빠른 쓰기 연산에 최적화
      • 중재자는 클라이언트와 노드 사이에서 프록시 역할 수행
    • W = N, R = 1 : 빠른 읽기 연산에 최적화
      • 중재자는 한 대 서버의 응답만 받으면 됨 :: 응답속도 굿
    • W 또는 R이 1보다 큰 경우
      • 시스템의 데이터 일관성은 향상
      • 중재자 응답 속도는 느려짐 :: 가장 느린 서버로부터의 응답 기다려야 함
    • W + R > N : 강한 일관성 보장
      • 보통 N = 3, W = R = 2
    • W + R ≤ N : 강한 일관성 보장 X
• 일관성 모델 (consistency model)
  • 데이터 일관성의 수준을 결정한다.
  • 종류
    • 강한 일관성 (strong consistency)
      • 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환
      • 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기 금지해서 달성
      • 새로운 요청의 처리가 중단되기 때문에, 고가용성 시스템에 적합 X
    • 약한 일관성 (weak consistency)
      • 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
    • 최종 일관성 (eventual consistency)
      • 약한 일관성의 한 형태
      • 갱신 결과가 결국에는 모든 사본에 반영 (=동기화) 된다.
      • 쓰기 연산이 병렬적으로 발생할 경우, 시스템에 저장된 값의 일관성이 깨질 수 있다.
        • 클라이언트가 직접 데이터 버전 정보를 이용해, 일관성이 깨진 데이터를 읽기 않게 처리한다. ⇒ 비일관성 해소 기법 사용

일관성 불일치 해소 (inconsistency resolution)

• 데이터 다중화 :: 가용성은 높아져도, 사본 간 일관성 깨질 가능성 높아짐
• 해결
  • 버저닝 (versioning) : 데이터 변경할 때마다 새로운 버전 생성
    • 각 버전의 데이터는 변경 불가능 (immutable)
  • 벡터 시계 (vector clock) : 버저닝에서 두 버전 사이의 충돌 해소
    • 동작 방식
      • [ 서버, 버전 ]의 순서쌍을 데이터에 맵핑
        • 어떤 버전이 선행인지, 후행인지, 다른 버전과 충돌이 있는지 판별하는데 사용!
      • 데이터 D를 서버 Si에 기록한다고 할 때, 시스템은 아래 작업 수행
        • [ Si, vi ] 가 있으면 버전 카운터 vi를 증가시킨다.
        • 그렇지 않으면 새 항목 [ Si, 1 ] 을 만든다.
    • 장점
      • 어떤 버전 X가 버전 Y의 이전 버전인지 (따라서 충돌이 없는지) 쉽게 판단 가능!
      • 버전 Y에 포함된 모든 구성 요소 값이 X에 포함된 모든 구성 요소 값보다 같거나 큰지만 체크하면 된다.
    • 단점
      • 충돌 감지 및 해소 로직이 클라이언트단에 추가 :: 클라이언트 구현 복잡
      • [서버:버전] 순서쌍 개수가 빠르게 증가
        • 길이에 임계치 정하고, _임계치 초과할 때 오래된 순서쌍을 벡터 시계에서 제거_해야 한다.
        • 단, 이 경우 버전 간 선후 관계가 정확하게 결정될 수 없어 충돌 해소 효율성이 낮아진다.
          • Amazon dynamoDB말로는 이런 적이 없다고 하니, 사실상 안전한 솔루션이긴 하다. 참고만..!

장애 처리

• 장애 감지 (failure detectinon)
  • 분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 특정 서버의 장애를 보고해야, 해당 서버에 실제로 장애가 발생했다고 간주한다.
  • 서버 적을 때
    • 모든 노드 사이에 멀티캐스팅 (multicasting) 채널을 구축해 서버 장애 감지
  • 서버 많을 때
    • 분산형 장애 감지 (decentrallized failure detectino) 솔루션 사용
      • Ex. 가십 프로토콜 (gossip protocol)
        • 각 노드는 멤버십 목록을 유지 :: 멤버십 목록 = 각 멤버 ID와 박동 카운터 (heartbeat counter) 쌍 목록
          • 각 노드는 주기적으로 자신의 박동 카운터를 증가
          • 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다
          • 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
          • 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않는다면? → 해당 멤버는 장애 상태인 것으로 간주
• 장애 해소 (failure resolution)
  • 일시적 장애 처리
    • 가십 프로토콜로 장애 감지 → 가용성 보장을 위해 조치
      • 엄격한 정족수 (strict quorum) 접근 : 읽기, 쓰기 연산 금지
      • 느슨한 정족수 (sloppy quorum) 접근 : 임시 위탁 (hinted handoff)

          1. 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고른다. (장애 서버 무시)
          2. 장애 서버로 가는 요청은 위에서 고른 서버들이 맡아 처리한다. 
          3. 변경사항들은 장애 서버가 복구되었을 때 일괄 반영해 데이터 일관성을 보존한다. 이를 위해 임시 쓰기 연산 처리 서버는 단서 (hint)를 남긴다. 

  • 영구적 장애 처리
    • 반-엔트로피 (anti-entropy) 프로토콜을 이용해 사본 동기화
      • 사본들을 비교해 최신 버전으로 갱신
      • 사본 간의 일관성이 망가진 상태 탐지 → 전송 데이터 양을 줄이기 위해 머클 트리 사용 (Merkle)
        • 머클 트리 = 해시 트리
          • 각 노드에 그 자식 노드들에 보관된 값의 해시 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리
          • 대규모 자료 구조의 내용을 효과적이고 안전하게 검증 가능
          • 동기화해야 하는 데이터의 양은 존재하는 차이 크기에 비례하지, 두 서버에 보관된 데이터 총량과는 무관하다.
          • 단, 실제 시스템의 경우 버킷 크기가 크다는 것 참고
  • 데이터 센터 장애 처리
    • 데이터를 여러 데이터 센터에 다중화하자!

시스템 아키텍처 다이어그램

• 아키텍처의 주된 기능 예시
  • 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, get과 put와 통신한다.
  • 중재자 (coordinator)는 _클라이언트에게 키-값 저장소에 대한 프록시 역할을 하는 노드_다.
  • 노드는 _안정 해시의 해시 링 위에 분포_한다.
  • 노드를 자동으로 추가 또는 삭제할 수 있게 시스템은 완전히 분산된다.
  • 데이터는 여러 노드에 다중화된다.
  • 모든 노드가 같은 책임을 지므로, SPOP (Single Point of Failure)는 존재하지 않는다.

쓰기 경로 (write path)

• 쓰기 요청이 특정 노드에게 전달되었을 때 벌어지는 일
  • 카산드라 구조 참고
    • 쓰기 요청이 커밋 로그 파일에 기록
    • 데이터가 메모리 캐시에 기록
    • 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록된다.

읽기 경로 (read path)

• 읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지부터 살핀다.
  • 있으면 해당 데이터를 클라에게 반환
  • 없으면 디스크에서 가져온다
    • 어느 SSTable에 있는지 알아내기 위해 블룸 필터 (Bloom filter) 등을 사용한다.

3️⃣ 요약

[230204] 노션 -> 벨로그 이동 :: 가독성 개선 예정 😇

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

📢 안정 해시 : 수평적 규모 확장성을 위해 요청 또는 데이터를 서버에 균등하게 나누는 기술

안정 해시

0️⃣ 해시 키 재배치 (rehash)

• N개의 캐시 서버에 부하를 균등하게 나누는 해시 함수

    serverIndex = hash(key) % N

  • 특정 키가 보관된 서버를 찾기 위한 나머지 연산을 수행
  • 추천 환경
    • 서버 풀 (server pool) 크기 고정된 환경
    • 데이터 분포가 균등한 환경
  • 비추천 환경
    • 서버가 추가되거나, 기존 서버가 삭제될 가능성이 있는 환경
    • 즉, 키 분포가 변화 될 가능성이 있을 경우 대규모 캐시 미스 (cache miss) 발생 가능성 존재

• 위 문제를 해결하기 위해 안정 해시 사용

  • 전통적 해시 테이블은 보통 슬롯 수가 바뀌면 전체 키를 재배치한다

1️⃣ 안정 해시 (consistent hash)

• 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 해시 기술
  • k = 키의 개수
  • n = 슬롯 개수
• 동작 원리
  • 기본 용어
    • 해시 공간 : 해시 함수의 출력 값 범위 공간
    • 해시 링 : 해시 공간의 양쪽을 구부려 접은 것
    • 해시 서버 : 해시 함수 f를 사용해 서버 IP 또는 이름을 해시 링 위에 배치
    • 해시 키 : 해시 함수를 이용, 캐시할 키를 해시 링 위에 배치
  • 서버와 키 배치 : 균등 분포 해시 함수를 이용해, 해시 링에 서버와 키 배치
  • 서버 조회 : 해당 키의 위치로부터 시계 방향으로 링을 탐색하는 중 만나는 첫 번째 서버에 키가 저장된다.
  • 서버가 추가/제거될 경우, 키 가운데 일부를 재배치한다.
• 문제
  • 서버 추가/제거 상황에서 파티션 크기를 균등하게 유지할 수 없다.
    • 파티션 : 인접한 서버 사이의 해시 공간
  • 키의 균등 분포 (uniform distribution)을 달성하기 어렵다.
  • 위 문제를 해결하기 위해 가상 노드 (= 복제) 기술 사용

2️⃣ 가상 노드 (virtual node) = 복제 (replica)

• 가상 노드 : 실제 노드 또는 서버를 가리키는 노드
  • 서버를 링에 배치할 때 여러 개의 가상 노드를 이용, 여러 개의 파티션을 관리한다.
• 서버 조회 : 해당 키의 위치로부터 시계 방향으로 링을 탐색하는 중 만나는 첫 번째 가상 노드가 나타내는 서버에 키가 저장된다.
  • 가상 노드 개수가 많을 수록 표준 편차가 작아져, 키의 분포가 균등해진다.
    • 표준 편차 : 데이터가 어떻게 퍼져 나갔는지 보이는 척도
    • 단, 가상 노드를 저장할 공간이 증가하니 trade-off 필요
• 재배치할 키 결정
  • 서버 추가 / 삭제 : 새로 추가 / 삭제된 노드부터 반시계 방향에 있는 첫 번째 서버 까지에 있는 키들을 재배치

3️⃣ 안정 해시의 이점

• 서버 추가 / 삭제될 때 재배치되는 키의 수를 최소화할 수 있다.
• 데이터가 보다 균등하게 분포되어 수평적 규모 확장성을 달성하기 쉽고, 따라서 핫스팟 키 문제를 줄일 수 있다.
  • 핫스팟 : 특정 샤드에 대한 접근이 지나치게 빈번할 때 서버 과부하 문제가 생길 수 있다.
• 예시
  • 아마존 dynamoDB의 파티셔닝 관련 컴포넌트
  • 아파치 카산드라 클러스터에서의 데이터 파티셔닝
  • 디스코드 채팅 어플리케이션 등…..

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

처리율 제한 장치 (rate limiter)

💡 클라이언트 또는 서비스가 보내는 트래픽 처리율을 제어하기 위한 장치

0️⃣ 왜 필요한가?

• Dos 공격에 의한 자원 고갈 (resource starvation)을 방지할 수 있다.
• 처리를 제한함으로써 서버를 많지 않게 두거나, 우선 순위가 높은 API에 더 높은 자원을 할당하는 식으로 비용을 절감할 수 있다.
• 잘못된 이용 패턴으로 유발된 트래픽을 막는 등 서버 과부하를 방지할 수 있다.
• 예시
  • HTTP : 특정 기간 내 전송되는 클라이언트 요청 횟수를 제한
    • 요청 횟수가 threshold를 넘어서면 추가로 요청된 호출은 모두 block
  • 사용자는 초당 2회 이상 새 글을 올릴 수 없다
  • 같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다

1️⃣ 문제 이해 및 설계 범위 확정 :: 필요한 알고리즘 특정

• 요구에 따라 알고리즘의 장단점을 따지며 뭘 쓸지 고민해보자
  • 이런 질문을 해보자
    • 어떤 종류의 처리율 제한 장치? 서버? 클라이언트?
    • 어떤 기준? IP 주소? 사용자 ID?
    • 시스템 규모? 스타트업? 대규모 요청?
    • 환경? 분산 환경? 모놀리틱?
    • 독립적? 코드에 종속?
    • 사용자 요청이 걸러진 경우 그 사실을 알려야 하는가?

2️⃣ 개략적인 설계안 제시 및 동의 구하기

• 처리율 제한 장치를 어디에 둘건가?
  • 클라이언트측 : 위변조가 쉽고, 모든 구현을 통제하기 어렵기에 일반적으로 안정적이지 못하다.
  • 미들웨어측 : 처리율 제한 미들웨어를 만들어 거기서 API 서버로의 요청을 통제하게 만들자.
    • API gateway가 이를 지원해준다.
    • 만약 마이크로서비스이고, API 게이트웨이를 이미 설계에 포함했거나, 또는 처리율 제한 장치 구현 인력이 부족하다면 API 게이트웨이를 이용하는게 바람직하다.
  • 서버측 : 프로그래밍 언어 등이 서버측 구현을 지원할만큼 효율이 높은지 검토해보자. 만약 서버에서 직접 구현할 경우 알고리즘은 자유롭게 선택 가능

• 처리율 제한 알고리즘

  • 토큰 버킷 : 간단하고, 세간의 이해도도 높아 폭넓게 사용되는 중
    • 버킷이 꽉 찼다면 추가로 공급된 토큰은 추가되지 않고 버려진다 (overflow)
    • 요청은 처리할 때마다 토큰을 사용한다. 토큰이 있으면 꺼내고 요청을 전달하고, 없으면 요청을 버리는 방식
    • 장점
      • 구현쉽고, 메모리 효율적이고, 짧은 시간에 집중되는 (burst of traffic)도 커버 가능하고, 버킷에 토큰 남아 있으면 요청은 무조건 시스템에 전달된다.
    • 단점
      • 버킷 크기와 토큰 공급률을 정하기가 까다롭다.
        • 보통 API endpoint마다 버킷을 둔다.
        • 만약 IP주소마다 처리율을 제한해야 한다면 IP주소마다 버킷을 둬야 하고, 초당 요청으로 제한하고 싶다면 모든 요청이 하나의 버킷을 쓰게 해야 한다.
  • 누출 버킷 : 요청 처리율 고정되어 있는 토큰 버킷 알고리즘, FIFO 큐로 구현
    • 동작 원리
      • 큐에 빈 자리가 있는지 확인
      • 가득 찼으면 새 요청을 버리고, 빈 자리가 있으면 큐에 요청 추가
      • 지정된 시간마다 큐에서 요청 꺼내서 처리
    • 장점
      • 큐 크기 제한적이라 메모리 효율적, 고정된 처리율이라 안정적 출력(stable outflow rate)이 필요할 때 적합
    • 단점
      • 단시간에 많은 트래픽 몰리면 큐에 오래된 요청이 쌓여지고, 그 요청 제때 처리 못하면 새 요청이 버려짐
      • 버킷 크기 (= 큐 사이즈), 처리율(= 정해진 시간에 몇 개 처리?) 인자를 관리하기 힘듬
  • 고정 윈도 카운터
    • 동작 원리
      • 타임라인을 고정 간격의 윈도로 나누고, 윈도마다 카운터 붙인다
      • 요청 접수된 카운터 += 1
      • 카운터 값이 사전 정의된 임계에 도달하면 새 요청은 새 윈도 열릴 때까지 버려진다
    • 장점
      • 메모리 효율 좋고, 이해하기 쉽고, 특정 트래픽 패턴 처리에 적합
    • 단점
      • 윈도 경계 부근에서 일시적인 트래픽이 몰려들 때, 기대했던 처리 한도보다 많은 양의 요청을 처리하게 됨
  • 이동 윈도 로깅 : 고정 윈도의 윈도 부근 트래픽 문제를 해결
    • 동작 방식
      • 요청 타임스탬프 추적 (보통 레디스 등 캐시에 보관)
      • 새 요청이 오면 만료된 타임스탬프(= 윈도 시작 시점보다 오래된 것) 제거
      • 새 요청 타임스탬프를 로그에 추가
      • 로그 크기가 허용치보다 같거나 작으면 요청 전달, 아니면 처리 거부
    • 장점
      • 어느 순간의 윈도도 허용 요청 개수는 시스템 처리 한도를 넘지 않음
    • 단점
      • 거부된 요청의 타임스탬프도 보관 ⇒ 메모리 많이 잡아먹음
  • 이동 윈도 카운터 : 고정 윈도 카운터 + 이동 윈도 로깅
    • 장점
      • 이전 시간대 평균 처리율에 따라 윈도 상태 계산 → 짧은 시간 트래픽 대응 O
      • 메모리 효율 굿
    • 단점
      • 직전 시간대 요청이 균등히 분포되어 있다고 가정 → 느슨
        • 실험 결과 그렇게 심각하지 않음

• 개략적인 아키텍처

  • 얼마나 많은 요청이 접수되었는지 추적할 수 있는 카운터를 추적 대상별로 생성 → 카운터 값이 한도를 넘어서면 요청 거부
    • 카운터를 어디에 보관할건지?
      • DB는 디스크 접근이라 느리니까 안됨
      • 캐시가 적절 : 빠르고 시간에 기반한 만료 정책 쓰기 때문
        • redis : 클라이언트가 처리율 제한 미들웨어에게 요청을 보내면, 미들웨어는 레디스 지정 버킷에서 카운터를 가져와 한도 도달 여부를 확인한다.

3️⃣ 상세 설계

• 처리율 제한 규칙은 어떻게 만들어지고 어디에 저장되나?
  • 보통 오픈소스 등을 활용할 수 있고, 설정 파일 형태로 디스크에 저장된다.
• 처리가 제한된 요청들은 어떻게 처리하나? (= 처리율 한도 초과 트래픽 처리 = throttle)
  • HTTP 429 응답만 보내거나
    • HTTP 응답 헤더로 확인할 수도 있다.
      • X-Ratelimit-Remaining
      • X-Ratelimit-Limit
      • X-Ratelimit-Retry0After
  • 또는 나중에 처리하기 위해 큐에 보관한다.
• 분산 환경에서의 처리율 제한 장치의 구현
  • 여러대의 서버와 병렬 스레드 지원하도록 시스템 확장하기.
  • 경쟁 조건 (race condition)
    • 요청을 처리하는 스레드가 병렬로 레디스에서 값을 읽었다면, 그리고 둘 중 어느쪽도 아직 변경 값을 저장하지 않았다면 카운터가 이상하게 작동한다.
    • 락을 걸어 해결할 수 있지만, 성능 이슈가 있다.
      • 이 경우 루아 스크립트 또는 정렬 집합 자료구조를 이용해 해결할 수 있다.
  • 동기화 (synchronization)
    • 처리율 제한 장치 서버가 여러 대인 경우 동기화가 필요하다.
    • 고정 세션 (sticky session)을 활용해 같은 클라이언트 요청을 같은 장치로 보내게 만들 수 있다.
      • 확장이 불가능하고 유연하지 않아 비추천
    • 레디스같은 중앙 집중형 데이터 저장소를 쓸 수 있다.
• 성능 최적화
  • 데이터 센터 지원
    • 에지 서버를 이용해 트래픽 전달 지연 시간을 줄인다.
  • 제한 장치 간 데이터 동기화에 최종 일관성 모델 사용 (eventual consistency model)
• 모니터링
  • 아래를 모니터링을 통해 확인한다
    • 채택된 처리율 제한 알고리즘이 효과적인지
    • 정의한 처리율 제한 규칙이 효과적인지

4️⃣ 마무리 :: 설계에 대한 후속 질문 및 추가 논의

• 경성 (hard) 또는 연성 (soft) 처리율 제한
  • 경성 처리율 제한 : 요청 개수는 임계치를 절대 못 넘는다
  • 연성 처리율 제한 : 요청 개수는 잠시 동안은 임계치를 넘을 수 있다
• 다양한 계층에서의 처리율 제한
  • OSI 계층 어디에서나 처리율 제한이 가능하다
• 처리율 제한을 회피하는 방법
  • 클라이언트를 어떻게 설계할 것인가?
    • 캐시 사용으로 API 호출 횟수 줄이기
    • 짧은 시간에 너무 많은 메시지 보내지 말기
    • 예외나 에러 처리 코드를 도입해 클라이언트가 예외 상황에서 복구될 수 있게 하기
    • 재시도 로직 구현에는 충분한 백오프 시간을 두기

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

💡 만약에 내가 구글 면접을 가. 근데 시스템 설계 면접을 볼거래. 내가…. 구글 시스템 설계를?....

👉 정답 기대하는게 아님!

1️⃣ 팁

💡 시스템 설계는 정해진 정답이 없는 질문이다.

• 보려는 것

  • 설계 기술 시연

  • 설계 과정에서 내린 결정에 대한 방어 능력

    → 왜 그렇게 설계했는지에 대한 질문을 받아 칠 수 있는지?

  • 면접관의 피드백을 건설적으로 처리할 자질

    → 피드백을 받아 내 설계에 반영할 수 있는지?

• 보려는 이유

  • 협력에 적합한 사람인지?
  • 압박이 심한 상황에서 잘 판단 내릴 수 있는지?
  • 모호한 문제를 건설적으로 해결할 수 있는지?
  • 좋은 질문을 할 수 있는지?
  • 완고하지 않고, 편협하지 않고…

2️⃣ 효과적 면접을 위한 4단계 접근법

💡 시스템 설계 면접의 공통 분모

1. 문제 이해 및 설계 범위 확정 :: 모호함 없애기

• 빠른 답변 필요 X
  • 요구사항과 가정을 분명히 하기 위해 신중하게 생각하자
  • 올바른 질문, 적절한 가정, 시스템 구축에 필요한 정보를 모으는게 중요. 답변에 시간 좀 들어도 된다
• 이런 질문을 해보자
  • 구체적으로 어떤 기능들이 필요? 가장 중요한 기능은?
  • 제품 사용자 수는?
  • 회사 규모의 확대 속도와 기대 수명은?
  • 회사 사용 기술 스택은? 설계 단순화를 위한 기존 서비스는?

2. 개략적인 설계안 제시 및 동의 구하기 :: 면접관과 협력하기

• 이런걸 해보자
  • 설계 최초 청사진 제시 후 의견 구하기
    • 면접관이 팀원인 것처럼!
  • 핵심 컴포넌트를 포함하는 다이어그램 그리기
    • 클라, API, 웹 서버, DB, 캐시, CDN, 메세지 큐 등…
  • 최초 설계안이 시스템 규모 제약을 만족하는지 계산해보기
    • 개략적인 추정이 필요한지 미리 확인 받고!
  • 시스템 구체적 사용 사례 확인하기
    • 엣지 케이스가 있는지?
  • 질문에 따라 API 엔드포인트, DB 스키마도 고려
    • 전체 시스템이 아닌 백엔드 시스템을 설계하라는 질문이면 필요할 것!

3. 상세 설계 :: 설계 컴포넌트 우선순위 정하기

• 면접관이 강조한 설계 영역
  • 보통 시니어라면?
    • 시스템 성능 특성 → 병목 구간, 자원 요구량 추정치
    • 컴포넌트 세부사항에 초점 맞췄을 것
• 시간 관리하기
  • 사소한건 버리고, 면접관이 관심 있어하는 요소에 집중하자

4. 마무리 :: 설계에 대한 후속 질문 및 추가 논의

• 시스템 개선 방법에 대한 질문
  • 비판적 사고 → 일단 그 자리에서 내가 완벽퍼펙트어메이징한 설계를 하진 않았을 것ㅋㅋ 뭘 놓쳤을까 한번 찾아보자
• 설계 요악
• 오류 발생했을 때 어떤 일이 생기는지?
• 운영 이슈 (메트릭 수집, 모니터링, 로그, 배포…)
• 규모 확장
• 등등

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

💡 만약에 내가 면접에 가. 근데 면접자가 시스템 용량이나 성능 요구사항을 추정해보래. 그럼 뭐라고 대답해야 하게요?

👉 보편적인 성능 수치 측정 도구를 이용해 추정치를 계산해보자!

1️⃣ 2의 제곱 수

• 데이터 볼륨 단위를 2의 제곱수로 표현하자.
  • 최소 단위 : 1바이트 (= ASCII 문자 하나가 차지하는 메모리 크기)

2️⃣ 응답 지연 (latency) 값

• 대충 이런걸 알 수 있다
  • 메모리는 빠르지만 디스크는 느리니까 가능한 디스크 탐색은 피해라
  • 단순 압축 알고리즘은 빠르니까, 데이터를 전송하기 전에 가능한 압축해라
  • 데이터센터는 분산되어 있고, 센터간 데이터 주고받는데는 시간이 걸린다

3️⃣ 가용성 관련 수치

• 시스템이 중단 없이 지속적으로 운영될 수 있는지 측정하는 방법
• 100%면 한번도 중단 된 적 없다는 의미

4️⃣ 팁

💡 결과보다 과정이 중요! 문제 해결 능력에 초점

• 근사치 활용해서 계산하기
• 가정를 확인하기 위해 적어두기
• 단위 붙여서 정확하게
• 주로 QPS, 최대 QPS, 저장소 요구량, 캐시 요구량, 서버 수 추정을 많이 물어본다.

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

새해가 되면서 스터디를 진행했는데, 노션에만 열심히 적는게 아까워서 벨로그에도 올려봅니다👀 아니 근데 마크다운 양식인데도 복사 붙여넣기 했을 때 깨지는게 많아서 일일이 수정해야 하네요..? 처음부터 블로그에 쓸 걸 😇

🖥 단일 서버 시스템 구성

💡 웹, DB, 캐시 등이 모두 서버 한 대에서 실행된다면?

도메인 이름을 IP 주소로 변환하는 과정을 거쳐 사용자가 웹 사이트에 접속하고, 해당 IP 주소에서 HTTP 요청과 응답이 오고 간다.

🤔 사용자가 늘어나도 해당 구조를 그대로 유지하나?

💡 당근빠따 안되기 때문에 아래 행위 고려하기

데이터베이스 서버 분리

1. 웹/모바일 트래픽 처리용 서버와 데이터베이스 서버를 분리해서 독립적으로 확장한다.
2. 데이터베이스는 시스템에 따라 RDB 또는 NoSQL을 선택할 수 있다.

수직적 규모 확장 (= 스케일 업)

• 서버에 고사양 자원 (더 좋은 CPU, 더 많은 RAM, …)을 추가하는 행위
• 장점 : 트래픽 양이 적을 때 단순하니 좋은 선택
• 단점

    1. 한계 존재 : 하나의 서버에 무한대의 자원을 추가할 수 없다 (당연함)
    2. 장애 대응 : 장애 자동 복구 (failover)이나 다중화 방안 X (고가용성 X)

수평적 규모 확장 (= 스케일 아웃)

• 더 많은 서버를 추가해 성능을 개선하는 행위
• 대규모 애플리케이션에 적합

로드 밸런서

1. 등장 배경

   • 사용자가 웹 서버에 바로 연결되면 서버 상태에 서비스가 직접적인 영향을 받는다
   • 사용자가 몰리면 웹 서버 응답 속도가 느려지거나, 접속이 어려워진다

   👉 부하 분산기, 또는 로드 밸런서를 이용해 위 문제를 해결하고자 함

2. 역할

   • 부하 분산 집합에 속한 웹 서버들에게 트래픽 부하를 고르게 분산한다.

3. 동작 방식

   • 사용자는 웹 서버가 아닌 로드 밸런서의 공개 IP로 접속한다.
   • 로드 밸런서는 요청을 사설 IP 주소를 이용해 웹 서버와 통신한다.
   • 로드 밸런서는 부하 분산 집합에 존재하는 웹 서버들에게 요청을 분산하여 나눠준다.

4. 웹 가용성 향상

   • 서버 1이 다운되면 로드 밸런서는 서버 2에게 트래픽을 전송한다. 👉 웹 사이트 전체가 다운되는 일 방지 가능

   • 유입 트래픽이 증가하면 웹 서버 계층에 더 많은 서버를 추가해서, 로드밸런서가 적절하게 서버로 트래픽을 나눠주게 만든다. 👉 많은 트래픽을 간단하게 관리할 수 있음

데이터베이스 다중화

1. master-slave 관계 설정
   • master (주서버)
     1. 쓰기 연산 지원 (insert, update, delete). 데이터 원본 저장
   • slave (부서버)
     1. 읽기 연산만 지원 (only read). 마스터의 데이터 사본을 전달받는다
     2. 보통 서비스는 읽기를 많이 하니까, 슬레이브 데이터베이스 수가 더 많은게 보편적
2. 장점
   • 성능 개선 : 데이터 변경 연산은 마스터로, 읽기 연산은 슬레이브로 분산되므로 병렬 처리 가능한 쿼리 수가 늘어난다.
   • 안정성 : 데이터베이스 서버 일부에 장애가 발생하거나 파괴되어도 사본이 남아있으므로 데이터는 보존된다.
   • 가용성 : 데이터베이스 서버 일부에 장애(이하생략) 다른 서버에 있는 데이터를 가져오면 되므로 서비스는 중단되지 않는다.
3. 예시
   1. 부서버가 한대인데 다운 발생
      • 읽기 연산이 일시적으로 주서버에 전달됨
      • 새로운 부서버가 올라와 장애 서버 대체
   2. 부서버가 여러대인데 그 중 하나에 다운 발생
      • 나머지 부서버들로 읽기 연산 분산
      • 새로운 부서버가 올라와 장애 서버 대체
   3. 주서버가 다운
      • 부서버 한대면 해당 서버가 주 서버를 대체하며, 읽기/쓰기 연산이 일시적으로 주 서버에서 처리
      • 부서버 데이터가 최신 데이터가 아닌 경우 복구 스크립트를 활용
      • 다중 마스터 구조, 원형 다중화 구조를 도입해 해결할 수도 있음

개선된 구조

⚡️ 난 응답 시간도 개선하고 싶어요!

💡 캐시와 CDN을 이용해 응답 시간 개선하기

캐시 : DB 부하를 줄여요~

1. 의미
   • 처리가 오래 걸리는 연산 결과 또는 자주 참조되는 데이터를 메모리에 두고, 이후 요청을 보다 빠르게 처리해주는 저장소
   • 어플리케이션 성능은 데이터베이스 호출 수에 크게 좌우된다 (디스크까지 다이빙하기 힘드니까)
2. 캐시 계층
   • 데이터가 잠시 보관되는 곳으로 DB보다 훨씬 빠르다.
   • 캐시 계층을 이용해 DB 부하를 줄이고, 캐시 계층 규모를 독립적으로 확장시킬 수 있다
     • 캐시 주도 전략 : 캐시에 없으면 DB 조회하는 방식!
3. 주의할 점
   1. 캐시는 데이터 갱신은 적지만, 참조는 자주 일어나는 데이터에 적절하다
   2. 휘발성 메모리를 사용하므로, 중요한 데이터는 지속적 저장소에 두어야 한다.
   3. 데이터가 계속 캐시에 남는 걸 막기 위해, 적절한 만료 기한을 두어야 한다.
   4. 단일 트랜잭션을 이용, 지속적 저장소의 데이터와 캐시에 있는 데이터의 일관성을 관리해야 한다.
   5. 단일 장애 지점(SPOF)이 되는 걸 막기 위해 캐시 서버를 분산시켜야 한다.
   6. 캐시 메모리를 과할당하여 데이터 방출(eviction) 현상을 방지한다.
   7. 캐시가 꽉 차는 경우를 대비하여 데이터 방출(eviction) 정책을 마련한다.
      1. LRU : 마지막으로 사용된 시점이 가장 오래된 친구부터 방출
      2. LFU : 사용된 빈도가 가장 낮은 친구부터 방출
      3. FIFO : 가장 먼저 캐시에 들어온 친구부터 방출

콘텐츠 전송 네트워크 (CDN) : 정적 컨텐츠는 웹 서버를 거치지 않아요~

1. 의미
   • 정적 콘텐츠 전송에 쓰이는 지리적으로 분산된 서버의 네트워크. 정적 파일을 캐싱한다.
   • 요청 경로, 쿼리 스트링, 쿠키, 헤더 등을 이용해 HTML 페이지 캐시하는 방식
2. 동작 방식
   • 사용자가 웹 사이트에 방문하면, 해당 사용자에게 물리적으로 제일 가까운 CDN 서버가 정적 컨텐츠를 전달해준다.
   • 만약 컨텐츠가 CDN에 없다면 웹 서버에서 가져온다. 캐시를 활용하는거 맞아요.
3. 고려할 점
   1. 서드파티 제공자가 운영하므로 비용에 주의한다.
   2. 시간에 민감한 콘텐츠의 만료 시한에 주의한다.
   3. CDN이 죽었을 경우 어떻게 처리할건지 주의한다.
   4. 아직 만료되지 않은 콘텐츠에 문제가 생긴 경우, 콘텐츠 무효화 처리가 필요하다.

🤖 웹 계층의 수평적 확장

💡 사용자 세션 정보와 같은 상태 정보를 웹 계층에서 제거해 웹 수평적 확장을 구현한다.

무상태 웹 계층 : 상태 정보를 DB에 저장해요~

1. 상태 정보 의존적인 아키텍처
   • 상태를 서버에 저장하기 때문에, 동일 클라이언트의 요청은 항상 동일 서버로 전송되어야 한다.
   • 로드밸런서가 고정 세션 기능을 제공해주지만, 부담이 크다.
   • 로드밸런서 뒷단에 서버의 추가와 제거가 어려워지고, 장애 대응도 빡세다.
2. 무상태 아키텍처
   • 클라 요청은 어떤 웹 서버로든 전송될 수 있다.
   • 웹 서버는 상태 정보가 필요하면, 웹 서버와 물리적으로 분리된 상태 저장소에서 정보를 가져온다.
   • 따라서 구조가 단순하고, 안정적이고, 확장에 유연해진다.

💽 가용성을 높이자

💡 높은 가용성을 위해 데이터 센터를 여러개 지원하는게 필수적!

데이터 센터

1. 지리적 라우팅
   • 장애가 없는 상황에서 사용자가 가장 가까운 데이터 센터로 안내되는 것
     • geoDNS : 사용자 위치에 따라 도메인 이름을 어떤 IP 주소로 변환할지 결정해주는 DNS 서비스
   • 데이터 센터 중 하나에 장애 발생하면, 가까운 데이터 센터로 트래픽이 전송된다.
2. 다중 데이터 센터 아키텍처 구현을 위한 기술 난제
   • 트래픽 우회 : 올바른 데이터 센터로 트래픽 보내는 방법
   • 데이터 동기화 : 데이터센터마다 다른 데이터베이스를 쓴다면, 페일오버 전략이 필요하다.
     • 보통 데이터를 여러 데이터 센터에 걸쳐 다중화한다.
   • 테스트와 배포 : 웹 사이트와 어플리케이션을 여러 위치에서 테스트해봐야 한다. 배포 자동화를 통해 모든 데이터 센터에 동일한 서비스를 설치하는 걸 도울 수 있다.

⛑ 더 큰 시스템을 위하여

💡 시스템 컴포넌트를 분리해 각각 독립적으로 확장될 수 있는 구조를 만들어야 한다.

메시지 큐

1. 의미
   • 데이터 무손실을 보장하는 비동기 통신을 지원하는 컴포넌트. 보통 메시지 버퍼 역할
   • 뭔 🐕소리야? : 한번 메시지 큐에 저장되면 데이터를 꺼내 갈 때까지 안전히 보관된다는 소리
2. 메시지 큐 기본 아키텍처
   • 입력 서비스 ( = 생산자 또는 발행자)가 메시지를 만들어 메시지 큐에 발행한다.
   • 큐에 연결된 서비스 혹은 서버 ( = 소비자 도는 구독자)가 메시지를 받아, 역할을 수행한다.
3. 장점
   • 서비스, 또는 서버 간 결합이 느슨해짐 → 규모 확장성이 보장되어 안정적
     • 생산자는 소비자가 죽어도 메시지를 발행할 수 있고, 소비자는 생산자가 죽어도 메시지를 수신할 수 있다.
     • 큐가 크면 소비자를 추가하고, 큐가 비어있으면 소비자를 줄이는 방식!

로그, 메트릭, 자동화

1. 로그
   1. 시스템 오류와 문제를 찾기 위한 에러 로그 모니터링
   2. 로그를 단일 서비스로 모아주는 서비스를 이용하면 다중 서버 환경에서 편리하다
2. 메트릭
   1. 사업 현황에 대한 정보와 시스템 현재 상태에 대한 정보를 얻을 수 있다.
   2. 유용한 메트릭 친구들
      1. 호스트 단위 메트릭 : CPU, memory, disk I/O에 관한 친구들
      2. 종합 메트릭 : DB 계층 성능, 캐시 계층 성능에 관한 친구들
      3. 핵심 비즈니스 메트릭 : 일별 능동 사용자, 수익, 재방문에 관한 친구들
3. 자동화
   1. 시스템이 크고 복잡해지면 생산성을 높이기 위한 자동화 시스템을 도입하자.
   2. CI, 빌드, 테스트, 배포 등…

개선된 구조 2

📈 DB 규모를 확장하자

💡 저장할 데이터가 많아졌어요 뭘 해야 돼요 DB를 확장해야 돼요

수직적 확장

1. 의미
   • 기존 서버에 더 많은 고성능 자원 증설해주기
   • 성능을 아주~~ 좋게 만들어서 많은 데이터를 처리할 수 있게 하는 방법
2. 단점
   • 증설 한계가 있어용
   • SPOF 위험성
   • 서버 성능이 좋아질 수록 비용이 따블로 든다

수평적 확장

1. 의미
   • 더 많은 서버를 추가하기
   • 샤딩 : 데이터베이스를 샤드라는 작은 단위로 분할하는 것. 모든 샤드는 같은 스키마를 공유하지만, 보관하는 데이터에는 중복이 없다.
2. 고려할 점
   • 샤딩 키(=파티션 키)를 정해야 해요 : 데이터가 어떻게 분산될지 정하는 하나 이상의 컬럼
     1. 샤딩 키를 이용해 올바른 DB에 질의를 보낼 수 있다.
     2. 효율적인 처리를 위해 데이터를 고르게 분할 할 수 있는 샤딩 키를 지정한다.
   • 샤딩을 도입하면 시스템이 이렇게 복잡해져요
     1. 데이터의 재샤딩
        • 데이터가 너무 많아졌을 때, 샤드간 데이터 분포가 균등하지 않아 샤드 소진이 발생할 때 재 샤딩이 필요하다.
        • 안정 해시 기법으로 해결 가능!
     2. 유명인사 (= 핫스팟 키)
        • 특정 샤드에 질의가 집중되어 서버 과부하 걸리는 문제
        • 자주 쓰이는 데이터 (유명인사)가 모두 한 샤드에 저장될 경우, 해당 유명인사 각각에 샤드를 할당해야 한다.
     3. 조인과 비정규화
        • 하나의 데이터베이스를 여러 샤드 서버로 나누었으니, 여러 샤드에 걸친 데이터를 조인하기 어려워진다.
        • 해결하기 위해 데이터베이스를 비정규화하여 하나의 테이블에서 질의를 수행한다.

오브젝트 : 코드로 이해하는 객체지향 설계 (조영호 저) 를 읽고 정리합니다.

GRASP 패턴으로 알아보는 책임 할당 기준

어떤 객체에게 어떤 책임을 할당해야할까? 🧐

1️⃣ 책임 주도 설계 리마인드

• 객체의 책임과 협력에 초점 맞추기
  1. 데이터보다 행동을 먼저 결정할 것 : 협력에 참여하기 위해, 외부에 제공하는 행동(= 협력 속에서 수행할 책임)을 먼저 결정해야 한다.
  2. 협력이라는 문맥 안에서 책임을 결정할 것 : 책임은 객체가 아닌 객체가 참여하는 협력에 적합해야 한다. : 메시지를 전송하는 클라이언트의 의도에 적합하도록, 메시지를 결정한 후 객체를 선택해야 한다.

• 책임 주도 설계의 흐름
  • 책임을 결정한 후, 책임을 수행할 객체를 결정하기
    1. 시스템이 사용자에게 제공해야 하는 기능, 전체 시스템 책임 파악
    2. 시스템 책임을 더 작은 책임으로 분할
    3. 분할된 책임을 수행할 수 있는 적절한 객체 또는 역할을 찾아 책임 할당
    4. 객체가 책임을 수행하는 중 다른 객체 도움이 필요한 경우, 해당 도움을 수행할 적절한 객체 또는 역할 찾기
    5. 찾은 객체 또는 역할에게 책임 할당 = 두 객체의 협력 관계 구축 완료

2️⃣ GRASP 패턴?

일반적인 객체 책임 할당을 위한 소프트웨어 패턴.

👣 도메인 개념에서 출발하기

• 설계를 시작할 때, 도메인에 대한 개략적인 모습을 그려보면 좋다.
  • 도메인에 존재하는 개념들을 책임 할당의 대상으로 사용하자.
• 이때, 도메인을 완벽하게 정리하는 것에 집착하지 말자!
  • 단순히 출발점의 목적으로 활용할 것
  • 책임을 할당받을 객체들의 종류와 관계에 대한 정보를 수집하는 선으로 족하다.
• 올바른 도메인 모델?
  • 그런건 없다..! 단지 구현에 도움이 되는 실용적인 모델이 필요할 뿐이다.

🦾 정보 전문가에게 책임 할당하기

• 책임 수행에 필요한 메시지를 결정하자.
  • 메시지를 전송할 객체의 의도를 반영하여 아래 질문을 생각하며 메시지를 결정해야 한다.
    • 메시지를 전송할 객체는 뭘 원할까?
    • 메시지를 수신할 객체는 누가 적당할까?
• 메시지 수신 객체는 캡슐화의 단위에서 결정해야 한다.
  • INFORMATION EXPERT (정보 전문가) 패턴
  • 책임을 수행할 정보를 알고 있는 객체에게 책임을 할당하자.

정보 전문가 패턴

• 객체가 자신이 소유한 정보와 관련된 작업을 수행하는 직관
  • 이때, 정보 전문가는 데이터를 반드시 저장할 필요가 없다는 점에 주의
    • 정보를 제공할 수 있는 다른 객체를 알거나, 필요한 정보를 직접 계산해서 제공할 수 있기 때문
• 따라서 상태와 행동을 함께 가지는 단위(=객체)를 책임 할당 관점에서 표현한다.

⛑ 높은 응집도, 낮은 결합도

• 위 과정대로 했는데, 동일한 기능을 구현할 수 있는 여러 설계 선택지가 있다면?
  • 응집도를 높이고 결합도를 낮게 만들 수 있는 설계를 선택하자.
• 높은 응집도 패턴 (HIGH COHESION)
  • 어떤 협력 관계를 만들어야 각 객체의 변경 책임을 분리할 수 있을까?
• 낮은 결합도 패턴 (LOW COUPLING)
  • 어떤 협력 관계를 만들어야 설계 전체적으로 결합도를 추가하지 않을 수 있을까?

⚒ 창조자에게 객체 생성 책임 할당하기

• 창조자 패턴 (CREATOR)
  • 객체 A를 생성할 때, 아래 조건을 최대한 많이 만족하는 B에게 책임을 할당하라
    • B가 A 객체를 포함하거나 참조한다
    • B가 A 객체를 기록한다
    • B가 A 객체를 긴밀하게 사용한다
    • B가 A 객체를 초기화하는 데 필요한 데이터를 가지고 있다 (= B는 A에 대한 정보 전문가 )

구현을 통해 설계 검증하기

설계가 협력과 책임을 잘 반영했는지 검증하기 위해서 코드를 작성하고 실행해봐야 한다.

1️⃣ 클래스 응집도 판단하기

메세지가 객체를 선택해야 한다!

• 객체가 협력하는 객체의 내부 구현에 대해 지식이 없을 때, 각 객체의 깔끔한 캡슐화가 가능하다.
• 객체간 연결고리가 메시지 뿐이기 때문에, 메시지가 변경되지 않는 한 내부 구현은 영향을 받지 않기 때문

• 변경에 취약한 클래스가 존재하는가?
  • 변경에 취약한 클래스 : 코드를 수정해야 하는 이유가 하나 이상인 클래스
  • 높은 응집도를 위해 변경의 이유에 따라 클래스를 분리해야 한다.
    • 따라서 설계 개선 작업은 변경의 이유가 여러개인 클래스가 있는지 확인하면서 시작하면 좋다.
  • 변경의 이유를 파악하는 방법
    • (1) 인스턴스 변수 초기화 시점 파악 : 클래스 속성이 서로 다른 시점에 초기화되거나 Or 일부만 초기화된다 = 응집도가 낮다 : 함께 초기화되는 속성을 기준으로 코드를 분리하자!
    • (2) 메서드들이 인스턴스 변수를 사용하는 방식 파악 : 메서드가 객체의 모든 속성을 사용할 때 클래스 응집도가 높다. : 속성 그룹과 해당 그룹에 접근하는 메서드 그룹을 기준으로 코드를 분리하자22!

2️⃣ 설계 개선하기

⛑ 타입 분리하기

• 독립적인 타입은 서로 다른 클래스로 분리하자
  • 자신의 인스턴스 변수를 모두 함께 초기화 가능
  • 클래스에 있는 모든 메서드는 동일한 인스턴스 변수 그룹을 사용

타입 분리로 인해 발생할 수 있는 문제들 🔨

• 특정 클래스 응집도는 높아져도, 변경과 캡슐화 관점에서 보면 전체 설계 품질은 나빠지는 케이스
  • 전체 설계의 결합도가 높아질 수 있다
  • 새로운 기능을 추가하기 위해 여러 클래스에 접근해야 한다

⛑ 다형성을 통해 분리하기

• 역할을 이용해 객체 타입을 추상화하자
  • 동일한 책임을 수행한다 = 동일한 역할을 수행한다. 따라서 역할에 대해 결합하게 의존성을 제한하자
  • 역할을 대체할 클래스들 사이의 관계에 따라 추상화 방법을 골라보자 (Java)
    • (1) 클래스들 사이서 구현을 공유해야 함 = 추상 클래스
    • (2) 구현 공유할 필요 없이 책임만 정의하면 됨 = 인터페이스
• POLYMORPHISM (다형성) 패턴
  • 객체 타입에 따라 변하는 행동이 있다면? 타입을 분리하고, 변하는 행동을 각 타입의 책임으로 할당하자
  • if-else가 아니라, 객체의 타입에 따라 변화를 컨트롤하는 방식

⛑ 변경으로부터 보호하기

• PROTECTED VARIATIONS (변경 보호) 패턴
  • 변경을 캡슐화하도록 책임을 할당하는 방식
    • 변화가 예상되는 불안정한 지점들을 클래스로 인터페이스를 이용해 변경을 캡슐화한다

캡슐화를 이용해 설계 결합도와 응집도 향상하기 (1) 하나의 클래스가 여러 타입의 행동을 구현하는 것 같다 = 다형성 패턴으로 책임 분산 (2) 예측 가능한 변경으로 인해 클래스들이 불안정해진다 = 변경 보호 패턴으로 인터페이스를 이용한 캡슐화

3️⃣ 변경과 유연성

클래스가 작고 한 가지 일만 수행할 때, 책임이 적절하게 분배되어 있을 때, 다른 클래스와 느슨하게 결합되어 있을 때 변경에 유연한 코드를 만들 수 있다.

• 개발자가 변경에 대비하는 두 가지 방법
  • (1) 코드를 수정하기 쉽도록 최대한 단순하게 설계하기
  • (2) 코드를 수정하지 않고도 변경을 수용할 수 있게 유연하게 설계하기
• 유연성은 요소들 사이의 의존성에 의해 결정된다

책임 주도 설계의 대안

적절한 책임을 찾는게 어렵다면, 일단 코드부터 짜고 이후 리팩토링을 통해 구조를 개선해보자.

• 리팩토링 (Refactoring)
  • 겉으로 보이는 동작은 바꾸지 않은 채 내부 구조를 개선(변경)하는 것

1️⃣ 메서드 응집도

• 긴 메서드 = 몬스터 메서드 (monster method)
  • 문제
    • 코드의 전체적인 컨텍스트 파악이 오래 걸린다
    • 코드 변경할 때 수정해야 할 부분 찾기가 어렵다
    • 메서드 내부 일부 로직을 수정했을 때, 다른 로직이 영향을 받을 가능성이 크다
    • 로직의 일부를 재사용하는 것이 불가능하다
    • 코드 재사용을 위해 복붙하게 되어, 코드 중복이 발생하기 쉽다
  • 요약
    • 응집도가 낮아서 보기도 어렵고 쓰기도 어렵고 재활용도 어렵고 어쨌든 모든게 어려워진다!
  • 주석이 주렁주렁 필요하다? 높은 확률로 메서드 응집도가 낮은 경우!
    • 메서드를 작게 분해해서 응집도를 높이자. 작은 메서드는 일종의 주석과 같다
• 메서드를 작고 응집도 높은 메서드로 분리할 때, 각 메서드를 적절한 클래스로 이동 (책임 할당)하기가 더 쉬워진다.

2️⃣ 자율적인 객체 만들기

• 메서드가 사용하는 데이터를 가지고 있는 클래스로 메서드를 이동시키자
  • 자율적인 객체 = 데이터를 처리하기 위해 타 객체에게 의존할 필요가 없는 객체 = 내가 가진 데이터를 스스로 처리하는 객체
  • 메서드를 이동할 때는 캡슐화, 응집도, 결합도의 측면에서 해당 이동이 적절한지 판단한다.

오브젝트 : 코드로 이해하는 객체지향 설계 (조영호 저) 를 읽고 정리합니다.

품질 척도

유지보수성! 오늘의 기능을 수행하면서 내일의 변경을 수용할 수 있는지?

🌱 캡슐화

• 목적은 변경의 영향 통제!
• 객체 내부 구현을 외부로부터 감춰, 특정 변경의 파급 효과를 조절하게 하는 것.
  • 구현 : 변경될 가능성이 높은 부분
  • 인터페이스 : 상대적으로 안정적인 부분
• 불안정한 구현이 아닌, 안정적인 인터페이스에 의존하게 관계를 조절할 때 객체지향이 구현될 수 있다.

🔨 응집도와 결합도

• 응집도 (⬆️)
  • 내부 요소들이 연관되어 있는 정도
  • 객체 또는 클래스에 얼마나 관련 높은 책임을 할당했는가? 를 확인하는 척도
• 결합도 (⬇️)
  • 다른 모듈에 대해 얼마나 많은 지식을 가지고 있는가. 즉 의존성의 정도
  • 객체 또는 클래스가 협력에 필요한 적절한 수준의 관계만을 유지하고 있는가? 를 확인하는 척도
• 내 설계를 쉽게 변경할 수 없다면, 구성 요소들의 응집도가 너무 낮지 않은지, 결합도가 너무 높지 않은지를 점검해 볼 타이밍..! 😇

변경의 관점에서 응집도와 결합도를 살펴보자.

• 응집도 : 변경이 발생할 때 모듈 내부에서 얼마나 많이 변경해야 하니?
• 결합도 : 한 모듈이 변경되기 위해 다른 모듈을 얼마나 많이 변경해야 하니?

훌륭한 설계?

훌륭한 설계란 합리적인 비용 안에서 변경을 수용할 수 있는 구조를 만드는 것!

😊 책임 중심 설계

객체는 협력하는 공동체의 일원이라는 관점으로, 객체 행동에 초점을 맞춘다.

• 설계는 변경에 유연하게 대응할 수 있는 시스템을 만든다는 목적을 가지고 진행된다.
  • 이 목적 아래서 모든 객체들은 서로에게 덜 영향받도록 최대한 자율적이어야 하며, 따라서 추상화되고 캡슐화된다.

😡 상태 중심 설계

상태 = 데이터. 객체를 독립된 데이터 덩어리로 바라보는 관점

캡슐화를 위반하고, 결합도가 높아지며, 응집도가 낮아져서 문제에요~

• 객체에게 필요한 데이터가 무엇인가? 에 초점이 맞춰진다.
• 구현에 관한 세부사항이 객체 인터페이스에 강하게 결합된다.
  • 따라서 변경에 유연하게 대응할 수 없다.
    • 상태를 변경하면 인터페이스가 변해야하고, 인터페이스에 의존하는 모든 객체들을 바꿔야하니까!

🤔 데이터 중심 설계가 갖는 문제점을 구체적으로 확인해보자!

• 1️⃣ 캡슐화 위반
  • 문맥이 아닌, 내부 데이터에 초점을 맞췄기 때문에 언제 상태값이 사용될 지 알 수 없다.
    • 따라서 발생 가능한 상황들을 커버하기 위해 모든 상태에 대해 접근자 메서드와 수정자 메서드를 두어야 한다. (= 추측에 의한 설계 전략)
  • 객체 내부에 접근하기 위해 사용하는 접근자와 수정자가, 오히려 객체 내부에 어떤 값이 있다는 사실을 퍼블릭 인터페이스에 드러내게 된다!
    • 따라서 내부 구현을 퍼블릭 인터페이스에 노출하면서 자연스럽게 캡슐화를 위반하고, 변경에 약해진다.
• 2️⃣ 높은 결합도
  • 전체 시스템을 하나의 거대한 의존성 덩어리로 만드는 지름길!
    • 캡슐화 위반 -> 내부 구현의 노출 -> 클라이언트가 구현에 강결합 -> 뭐 하나 바꾸려면 전부 바꿔야함
    • 여러 데이터 객체를 쓰는 제어 로직이 특정 객체에게 집중 -> 특정 객체에게 전체 로직이 강결합 -> 뭐 하나 바꾸려면 전부 바꿔야함22
• 3️⃣ 낮은 응집도
  • 단일 책임 원칙(SRP)의 위반 : 클래스는 단 하나의 변경 이유만 가져야 한다.
    • 변경의 이유가 다른 코드들을 하나의 모듈에 뭉쳐둠 -> 변경과 아무 상관 없는 코드들이 변경에 영향을 받음
    • 다른 모듈에 위치해야 할 책임의 일부가 엉뚱한 곳에 위치 -> 하나의 요구사항 변경을 위해 여러 모듈 수정 필요

🥺 어떻게 고쳐쓸 순 없을까요?

• 1️⃣ 캡슐화를 지키자!
  • 특정 객체의 변경 주체를 외부에서 내부로 이동시키자!
    • 객체가 스스로를 책임지게 만들기
      • 객체가 어떤 데이터를 포함해야 하는지 & 이 데이터에 대해 수행해야 하는 행동은 무엇인지 고려
      • = 객체 내부 상태를 저장하는 방식 & 저장된 상태에 대해 호출할 수 있는 오퍼레이션의 집합
  • 객체 구현도 내부로 이동시키자!
    • 내부 변경이 외부로 퍼져나가지 않게 만들기
      • 변할 수 있는 것은 어떤 것(속성이든, 뭐든 전부!)이라도 전부 감춰야 한다
• 2️⃣ 결합도를 낮추자!
  • 변경의 여파가 퍼지지 않도록, 위의 캡슐화 원칙을 통해 결합도를 낮추기
• 3️⃣ 응집도를 높이자!
  • 바꿀 때 하나만 바꿔도 되게, 위의 캡슐화 원칙을 통해 응집도를 높이기

😮 그거 완전.. 책임 중심 설계 아니에요?

맞아용!

• 데이터 중심 설계가 유연하지 못한 이유는 캡슐화를 위반했기 때문!
  • 객체의 상태는 결국 구현의 일부
    • 잘 변하는 불안정한 요소에 초점을 맞추고 설계했으니 당연히 변경에 취약해진 것
  • 상태 처리 오퍼레이션을 나중에 추가하느라 내부 지식이 인터페이스에 노출된다
    • 협력 문맥을 놓쳤기에 객체가 고립될 수 밖에 없다
    • 협력이 구현에 종속되게 만들면 당연히 객체들은 변경에 휩쓸리게 된다.
• 객체지향 설계는 항상 객체 외부를 위주로 이루어져야 한다.
  • 객체가 어떻게 다른 객체와 협력하는지가 중요하지, 내부 상태를 관리하는 방법은 전체 설계에서 그닥 중요한 일이 아니다!

오브젝트 : 코드로 이해하는 객체지향 설계 (조영호 저) 를 읽고 정리합니다.

역할, 책임, 협력

객체 = 협력이라는 연극 안에서 역할이라는 배역을 연기하는 배우

• 객체지향의 본질은 협력하는 객체들의 공동체를 창조하는 것!
  • 기능 구현에 필요한 협력을 먼저 설계하고, 이후 클래스와 상속 등의 구현 메커니즘을 이용해 완성할 때 유연한 코드를 짤 수 있다.
• 동일한 객체(배우)라도, 참여하는 협력(연극)에 따라 역할(배역)이 계속 달라진다.
  • 따라서 특정 협력(연극) 안에서, 필요한 객체의 특정 역할(배역) 이외의 부분은 감춰진다.

1️⃣ 협력

객체들이 어플리케이션의 기능을 구현하기 위해 수행하는 상호작용

• 객체지향 시스템은 자율적인 객체들의 공동체! 자기 일은 스스로 해야 한다.
  • 객체는 자율적이기 위해 필요한 정보와 정보에 기반한 행동만으로 구성되어야 한다 (캡슐화)
  • 따라서 객체는 자신이 할 수 없는 일을 다른 객체에게 요청하며, 이를 협력이라고 한다.
    • Ex. A객체는 자신이 할 수 없는 일을 B객체에게 요청(메시지 전송)하고, B객체는 필요한 메서드를 선택하여 실행해 요청에 응답한다.
• 협력은 객체 설계(= 객체에게 할당할 책임을 결정)에 필요한 문맥을 제공한다.
  • 협력은 객체의 행동을 결정하고, 행동은 객체의 상태를 결정한다.
    • 객체는 협력에 필요한 행동을 보유할 때만 어플리케이션에 필요하기 때문!

2️⃣ 책임

객체가 협력에 참여하기 위해 수행하는 로직

• 책임은 객체가 유지해야 하는 정보와 수행할 수 이는 행동에 대해 개략적으로 서술한다.
  • '하는 것' 책임
    • 객체가 '하는' 책임을 수행하기 위해선 '아는' 책임이 필요하다.
    • Ex. 객체를 생성하거나, 계산을 수행하거나, 다른 객체에게 도움을 요청하거나...
  • '아는 것' 책임
    • 객체는 자신이 맡은 책임을 수행하는데 필요한 정보를 알 책임이 있다.
    • 객체는 자신이 할 수 없는 일을 도와줄 객체를 알고 있을 책임이 있다.
    • Ex. 사적인 정보에 대해 알거나, 관련된 객체에 대해 알거나, 내가 할 수 있는 걸 알거나...
• 객체가 할 수 있는 행동들을 종합적으로 서술한다는 점에서 메시지보다 추상적이고 큰 개념!
  • 따라서 객체에게 얼마나 적절한 책임을 할당하는지가 설계에서 굉장히 중요!
• 보통 정보 전문가 패턴을 이용해 책임을 할당한다.
  • 정보 전문가 패턴 : 책임 수행에 필요한 정보를 가장 잘 알고있는 전문가에게 책임을 할당하는 것
    • 보통 일 시킬 때 잘 하는, 잘 아는 사람한테 시킨다. 똑같은 이유~
    • 물론 응집도와 결합도의 관점에서, 다른 방식이 더 적절할 수도 있다. 고냥 보통은 이렇게 한다고~
  • 협력이라는 문맥 안에서 더 작은 책임을 찾고, 그 책임의 적임자를 찾아 할당하는 과정을 반복하며 설계가 이루어진다.
    • 이 과정(책임 주도 설계)을 통해 퍼블릭 인터페이스를 구성할 수도 있다!

📌 책임에 집중하는 책임 주도 설계

• 책임이 협력에 참여할 객체를 결정하도록, 객체의 구현보다는 책임에 집중할 때 유연한 시스템이 된다.
• 단, 책임을 할당할 때는 아래를 고려한다.
  • 메세지가 객체를 결정한다.
    • (1) 식별된 메세지를 기반으로 인터페이스를 구성하기 때문에, 객체가 최소한의 인터페이스를 가질 수 있게 된다.
    • (2) 외부 객체가 요청하는 케이스를 고려할 수 있으므로, 메세지를 먼저 식별하면 무엇을 수행할지에 초점을 맞추는 추상적인 인터페이스를 가질 수 있게 된다.
  • 행동이 상태를 결정한다.
    • 다른 객체로부터 '무엇을 얻어야 하는지' 고민할 때, 즉 협력에 초점을 맞출 때 높은 응집도와 낮은 결합도를 구현할 수 있다.
    • 협력에 적합한지를 판단하는 기준은 행동! 상태를 기준으로 설계할 때 내부 구현과 퍼블릭 인터페이스의 의존도가 높아진다.

3️⃣ 역할

협력 안에서 특정 객체가 수행하는 책임들이 모인 것

• 책임의 할당은 (1) 적절한 역할이 뭔지 찾고 (2) 그 역할을 수행할 객체를 선택하는 과정으로 이루어진다.
  • 동일한 책임을 수행하는 역할을 기반으로 다수의 협력을 하나로 통합할 수 있다.
    • 즉, 역할을 이용해 불필요한 코드의 중복을 방지하고, 유연한 협력을 구현할 수 있다.
• 설계 초반에는 책임과 협력을 탐색하며 큰 그림을 그리는 것에 집중하자.
  • 일단 구체적인 객체들로 시작하고, 이후 유사한 협력들을 합치다보면 역할을 나눌 수 있을 것!
    • 역할의 기준
      • 협력에 적합한 책임을 수행하는 대상이 한 종류 -> 객체
      • 반대로 대상이 여러 종류가 될 수 있다면? -> 역할
  • 역할을 중심으로 역할 모델링을 시도할 때, 설계의 구성 요소를 추상화할 수 있다.
    • 역할은 모양이나 구조가 아닌, 시스템 문맥 안에서 무엇을 하는지에 의해 정의한다.
• 역할을 슬롯이라는 관점으로 이해하자!
  • 동일한 책임을 수행하는 객체는 동일한 역할을 수행하기에 서로 대체할 수 있다.
  • 따라서 역할이라는 추상화를 이용할 때, 새로운 기능을 구현할 때 유연하게 처리할 수 있다.

오브젝트 : 코드로 이해하는 객체지향 설계 (조영호 저) 를 읽고 정리합니다.

객체지향 프로그래밍

객체지향의 핵심은 애플리케이션 기능 구현을 위해, 객체들이 협력하며 상호작용하는 것!

• 프로그래밍 관점에 치우쳐서 객체지향을 바라보지말자.
  • 프로그래밍 관점에서 생각해보면, 우리는 기능을 만들기 위해 클래스를 짜고, 클래스 안에 메소드와 변수들을 채워넣어야한다.
  • 하지만? 우리는 클래스들이 서로 상호작용한다고 생각하는게 아니라, 객체들이 서로 상호작용한다고 생각해야한다.

🤷 그럼 뭘 생각하며 객체지향을 구현해요?

1. 어떤 객체가 필요한가? : 기능 구현을 위해 어떤 클래스가 필요한지를 고민하는게 아니라, 어떤 객체가 필요한지 고민해야 한다.

2. 객체는 기능을 구현하기 위한 협력체의 일원! : 기능 구현을 위해 다른 객체에게 도움을 주거나 의존하고 있는지 생각해야 한다.

🤷‍♀️ 예?

무슨 소린지 모르겠다면, 도메인을 활용해 이해해보자.

• 도메인 (domain) : 문제를 해결하기 위해 사용자가 프로그램을 사용하는 분야

  • 우리가 구현하려는 기능 = 문제를 해결하려는 수단 = 도메인
    • Ex. 문제 : 영화를 보고 싶은데, 보려면 티켓이 필요해!
    • Ex. 수단(도메인) : 티켓 예매

• 요구사항부터 구현까지 전부 객체의 관점으로 바라보자

  • 도메인을 구성하는 개념들을 나열하고, 그 개념들을 객체와 클래스로 재구성하자.
    • Ex. 티켓 예매 도메인을 구현하려면 어떤 상태와 행동이 필요할까? : 영화, 예매, 상영, 영화별 적용되는 할인 정책, 할인 정책1, 정책 2...
    • Ex. 이 상태와 행동들 중 유사한 친구들을 묶어서 하나의 개념으로 만들자. : 할인정책1과 할인정책2는 >할인 정책< 이라는 점에서 공통점을 가지니까, 하나로 묶자.
    • Ex. 이렇게 만든 개념을 클래스로 구현하자. : 할인정책은 할인정책1이라는 객체와 할인정책2라는 객체를 가질 수 있는 클래스로 정리된다.
  • 즉, 클래스의 구조가 도메인의 구조와 유사할 때 프로그램의 구조를 이해하고 예상하기 쉽다.
  
  

오케. 그럼 클래스는 어떻게 구현해야 하나요?

좋은 코드는? 변경하기 쉬운 코드. 변경하기 쉬운 코드는? 이해하기 쉬운 코드!

🧚 우리는 객체가 자율적인 존재라고 약속했어요!

• 객체가 자율적이고, 외부에 덜 의존적이게 되려면 외부 간섭을 최소화해야 한다.

  • 나는 떡볶이 먹고 싶을 때 떡볶이 먹을거고, 만두 먹고 싶으면 만두 먹을건데 이상한 애가 찾아와서 아냐 넌 만두를 먹으려면 단무지가 필요한 애야~~ 하면 성질나니까..!

• 이를 위해 객체는 상태와 행동을 객체 내부로 묶고 (= 캡슐화), 외부에서의 접근은 허가된 친구만 가능하도록 제어한다 (= 접근 제어).

  • 인터페이스와 구현의 분리 원칙
    • 퍼블릭 인터페이스 (public interface) : 외부에서 접근 가능
    • 구현 (implementation) : 외부에서 접근 불가능, 내부에서만 접근 가능
  
  

🤨 객체 접근 제어가 자율성에 어떻게 영향을 미치는지 잘 모르겠어요.

• 중요한건 변경을 관리하는 것!
  • 프로그래머를 두 종류로 구분해보자.
    • 클래스 작성자 : 새로운 데이터 타입을 프로그램에 추가한다
    • 클라이언트 프로그래머 : 클래스 작성자가 만든 데이터 타입을 사용한다
    • 클래스 작성자 A씨는 내가 신나게 짠 코드가 클라이언트 B씨에게 어떤 영향을 줄 지 걱정하고, 클라이언트 B씨는 빠르게 기능을 만들고 싶은데 A씨가 코드를 갑자기 바꿀까봐 걱정한다.
  • 하지만 A씨의 코드 핵심은 안에 숨겨두고, 이 코드에 접근하는 간접적인 방법만 B씨에게 알려준다면?
    • A씨는 내부 로직만 변경하면 되고, B씨는 내부 로직에 무관하게 접근 통로만 신경쓰면 된다!
• 우린 이걸 구현 은닉 (implementation hiding) 이라고 부르기로 했어요
  • 정리 : 객체로의 접근을 제어해 사용자 영향 고려 없이 내부 구현을 변경 가능하게 만들 수 있다.

😯 근데.. 객체는 협력해야 한다고 하지 않으셨나요?

B씨가 A씨의 코드에 접근하는 간접적인 방식 = 객체 상호 작용 = 메시지를 주고 받는 행위

• 객체는 다른 객체와 협력할 때, 협력을 요청하는 메시지를 보낸다.

  • 주의할 점은, 메시지 != 문제의 해결 이라는 점이다.
    • 문제의 해결은 메시지를 받은 객체가 메서드를 통해 스스로 해결한다.
    • 메시지를 보낸 객체는 메시지를 받은 객체가 문제를 어떻게 해결하는지 전혀 알 수 없다.
  
  

근데 우리 아까 비슷한 친구들을 묶어놓지 않았나요?

메시지를 받은 객체가 어떤 친구로 응답해야 하는지 어떻게 알 수 있을까?

🐳 상속은 몬가요..?

• 기존 클래스를 기반으로 새로운 클래스를 만드는 행위
  • 서로 공통점이 있지만, 차이점도 있는 클래스를 쉽게 추가할 수 있다. (= 차이에 의한 프로그래밍)
• 그렇다고 목적이 코드 재사용은 아니에요~
  • 부모의 인터페이스를 자식이 물려받을 수 있게 만드는게 중요!
    • 즉 구현이 아닌 인터페이스 상속이 객체지향적으로 가치있는 상속
  • 외부 객체가 봤을 때, 자식과 부모를 동일한 타입이라고 생각하게 만드는게 주 목적이다.
• 템플릿 메서드 (Template Method) 패턴
  • 부모는 기본적인 알고리즘 흐름을 구현하고, 중간에 필요한 처리는 자식에게 위임하는 패턴
• 코드 (클래스) 의존성과 실행 시점 (객체) 의존성이 다를 때 확장 가능하다.
  • 객체는 내가 어떤 클래스의 인스턴스와 협력하는지가 아니라, 내가 협력하는 친구가 내 메시지를 수신할 수 있는지 아닌지가 중요하다.
  • 따라서 객체가 소통할 수 있는 창구를 부모에게 터두고 처리 자체는 담당 자식에게 맡기자.
    • 상속을 통해 자식에게 부모의 인터페이스가 존재하기에 자식은 부모를 대신(업캐스팅)할 수 있다.
  • 단, 이 경우 기능은 유연해져도 코드 가독성은 떨어질 수 있다 ^.ㅠ

🐳 다형성은요?

• 동일한 메시지를 전송했을 때, 메시지 수신 객체 클래스에 따라 실행되는 메서드가 달라지는 것
  • 이를 위해 협력에 참여하는 객체들은 모두 같은 메시지를 이해할 수 있어야 한다.
  • Ex. 부모가 받을 수 있는 동일한 메시지를 전송했을 때, 각기 다른 자식이 메시지를 처리한 경우
• 메시지에 응답할 (= 실행될) 메서드를 컴파일 시점이 아닌 실행 시점에 정한다.
  • 메시지와 메서드를 실행 시점에 바인딩한다 = 지연 바인딩 = 동적 바인딩
• 자식 클래스들이 순수하게 인터페이스만 공유하는 경우는?
  • 마찬가지로 동일한 인터페이스를 공유하면서, 부모를 대신해 사용될 수 있기에 업캐스팅이 적용되며 다형적!

즉 상속과 다형성에는 추상화가 깔려있다.

추상화

최대한 인터페이스에 초점을 맞추고, 자식 클래스에게 결정권을 일임하는 것

📌 추상화를 통해 요구사항 정책을 높은 수준에서 서술할 수 있다.

세부적인 내용을 무시한 채 상위 정책을 쉽고 간단하게 표현할 수 있다는 의미

• 자식 하나하나를 언급하는게 아니라, 인터페이스 수준에서 설명할 수 있으니까!
  • Ex. 할인 정책 1, 할인 정책 2로 구분하지 않고 전체 할인 정책으로 구분
• 추상화를 통해 애플리케이션의 기본 협력 흐름을 기술할 수 있다 (= 상위 정책 기술)
  • 디자인 패턴, 프레임워크 등 재사용 가능한 설계들은 모두 위와 같은 메커니즘을 활용한다.

📌 추상화를 통해 유연하게 설계할 수 있다.

책임의 위치를 정하기 위해 조건문을 사용하기보다는, 예외 케이스를 최소화하고 일관성을 유지해라.

• 설계는 포괄적으로 하고, 세부 사항은 자식이 처리하게 결정 위임
  • 기존 구조를 수정하지 않으면서 새로운 기능을 쉽게 추가 & 확장할 수 있다.
• 컨텍스트 독립성 (context independency)
  • 설계가 구체적인 상황에 결합되지 않아, 어떤 클래스와도 협력이 가능하다.

📌 트레이드 오프

• 구현과 관련된 모든 것들이 트레이드 오프의 대상이 될 수 있다.
  • Ex. 이상적으로는 인터페이스를 활용해 책임을 명확하게 하는게 좋지만, 또 현실적으로 생각했을 때 아주 작고 단순한 기능 하나만을 위해 인터페이스를 추가하는건 과할 수 있다.
• 따라서 모든 코드를 합당한 이유를 기반으로 설계하고 작성해야 한다.

코드 재사용

코드를 재사용할 땐 상속 말고 합성을 쓰기로 약속해요~

• 합성 : 다른 객체의 인스턴스를 자신의 인스턴스 변수로 포함해서 재사용하는 방법

🔨 상속을 이용한 코드 재사용의 문제점

클래스를 통한 강결합

• 캡슐화 위반
  • 부모 클래스의 구현이 자식 클래스에게 노출됨
  • 즉, 자식이 부모에게 강하게 결합되고, 부모의 변경에 따라야 할 가능성이 생겨 코드 변경하기 어려워진다
• 설계를 유연하지 않게 만듬
  • 부모 클래스와 자식 클래스의 관계를 컴파일 시점에 결정한다
  • 따라서 실행 시점에 객체 종류를 변경할 수 없다

🔨 합성을 이용한 코드 재사용의 장점

인터페이스를 통한 약결합

• 인터페이스에 정의된 메시지를 통해서만 코드를 재사용할 수 있다
  • 메서드를 외부에 제공한다는 것만 알고, 내부 구현에 대해서는 전혀 모르는 상태!
  • 즉, 상속과 달리 인터페이스를 통해 약하게 결합된다.
• 따라서 구현을 효과적으로 캡슐화할 수 있고, 변경시 의존하는 인터페이스만 교체하면 되어 변경이 쉽다.

⚒ 그렇다고 상속을 쓰지 말라는건 아니고..!

• 코드를 재사용할 때는 : 합성
• 다형성을 위해 인터페이스를 재사용할 때는 : 상속과 합성을 함께 조합하기

객체지향의 핵심은 객체들의 협력과 상호작용이 적절하게 이루어져야 한다는 것!

• 적절한 협력을 식별하고, 적절한 객체에게 협력에 필요한 역할을 할당하자
• 프로그래밍 관점에 치우치는게 아니라, 객체를 지향하는 관점에서 설계해야한다.

오브젝트 : 코드로 이해하는 객체지향 설계 (조영호 저) 를 읽고 정리합니다.

객체와 설계

소프트웨어 설계와 유지보수에 중점을 두기 위해서, 이론이 아닌 실무(실제 코드)에 집중해야 한다.

소프트웨어 모듈이 가져야 하는 세 가지 기능

1. 실행 중 제대로 동작할 것
2. 변경을 위해 존재할 것 (변경 용이성)
3. 코드를 읽는 사람과 의사소통할 수 있을 것 (이해 용이)

단순히 동작하는 것에 만족하면 안되는 이유

프로그램은 오늘 기능을 완성하는 동시에, 내일 쉽게 변경되어야 한다.

왜 변경이 쉬워야할까?

• 요구사항이 항상 변경되기 때문
  • 유저의 의견으로, 기획자의 요청으로, 리소스의 한계로... 소프트웨어는 타의적으로든 자의적으로든 언제든지 변경될 수 있다.
• 코드 변경과 버그 변경 가능성은 떼어놓을 수 없다
  • 요구사항의 변경은 코드의 변경을, 코드의 변경은 버그 발생 가능성을 높인다.
  • 변경이 어려울 수록 기구현된 코드를 많이 고쳐야하고, 당연히 그만큼 기존 모듈 또는 신규 모듈에서 버그가 발생할 가능성이 높아진다.

변경이 쉬운 코드란?

• 변경이 쉬운 코드 = 변경에 유연하게 대응할 수 있는 코드 = 이해하기 쉬운 코드
  • 이해하기 쉬워야 보고 고치기 쉬우니까!
  • 이해하기 쉬운 코드 = 우리 예상에서 크게 벗어나지 않는 코드
    • 척보고 무슨 기능인지 딱 연상이 되어야 이해하기 쉽지, 가나다라 하다가 갑자기 efg 나오면 갑자기? 싶어진다. 그런 맥락이다.
• 근데 코드 (객체)들이 하나만 있나?
  • 기능을 구현하기 위해 여러 객체들이 필요하고, 기능을 수정하기 위해 여러 객체들을 관리해야 한다.
• 결국 이 객체 하나만 보고 이 객체의 역할이 뭔지 알 수 있어야 예상을 벗어나지 않는 이해하기 쉬운 코드인거고, 변경이 쉬운 코드인 것!

어? 이거 어디서 많이 들어본 소리 아니냐?

~ ✨ 우린 이걸 응집도가 높다고 표현하기로 했어요 ✨ ~

• 응집도 (cohesion) : 객체 내부 로직이 하나의 목표를 바라보고 있는가?
• 결합도 (coupling) : 객체가 다른 객체와 얼마나 연관성이 있는가?
  • 대학생때.. 교수님이 커플 보면 보기 싫으니까 커플링을 낮춰야 한다고 설명해주신 적이 있다. 너무 충격적인 드립이라 평생 못 잊을 듯

응집도를 높이고 결합도를 낮춰야 하는 이유

• 응집도가 낮고 결합도가 높으면 객체 역할을 알아내기 어렵다.
  • 객체 역할을 알기 위해 여러 객체를 참조해야하니까!
• 또, 객체를 변경하는 것도 어려워진다.
  • 한 객체를 변경하기 위해 관련있는 여러 객체들을 전부 변경해야하니까

~ ✨ 우린 이걸 의존성이 낮다고 표현하기로 했어요 ✨ ~

• 즉, 객체 사이의 의존성을 낮추고, 변경이 용이한 설계를 만드는게 최종 목표!

의존성은 어떻게 낮추죠?

• 객체 의존성이 높아지는 이유
  • 내가 할 일을 쟤가 하고 있으니까, 내가 뭘 할 때마다 쟤의 협조가 필요해지는 것.
• Ex. 밥을 먹는데 반찬을 스스로 집을 수 없고 누군가 떠먹여줘야 하는 상황을 생각해보자.
  • 밥을 국에도 말아먹고 싶고, 반찬 올려서 먹고도 싶고, 이것저것 넣고 볶아도 먹고 싶은데 그때마다 남한테 허락을 받아야 한다면?
  • 오늘은 콩밥말고 쌀밥먹고 싶은데 내게는 선택권이 없다면?

아! 객체가 스스로 처리할 수 있게 자율적인 친구로 만들어주면 되겠구나!

• 뭔가를 수행할 때, 다른 객체와 엮여서 처리하는게 아니라 객체가 스스로 직접 셀프로 움직이게 해주면 된다.
  • 객체 내부의 세부적인 사항을 스스로 수행하게 만들기 위해, 외부에서 접근할 수 없게 강제하자!

~ ✨ 우린 이걸 캡슐화라고 표현하기로 했어요 ✨ ~

• 개념적, 물리적으로 객체 내부의 세부적인 사항을 감추고 객체 내부로의 접근을 제한하는 행위
• 외부 객체는 객체의 인터페이스에만 의존하고, 실제 기능의 구현은 해당 객체만 가능하도록 만들자.
  • 즉, 객체를 인터페이스와 구현으로 나누고 인터페이스만을 공개하는게 중요!
    • 결국 객체는 나와 연관있는 작업만 수행하고, 연관 없는 작업은 다른 객체에게 위임하게 된다.
• 객체를 모두 사람이라고 생각하자. (= 의인화)
  • 객체가 쌀밥이어도, 떡볶이여도, 얘네는 다 살아있고 스스로의 의지로 움직이는 애들이라고 생각하고 책임을 넘기자.

이제 각 객체들이 스스로를 책임지게 되었습니다! 😮

• 어느 한 대장 객체가 다른 객체들을 모두 책임지는게 아니라, 모든 객체들에게 책임이 적절히 분배되었고, 각 객체들은 자율적으로 스스로의 책임을 수행한다.
• 데이터와 데이터를 사용하는 프로세스들이 동일한 객체 안에 위치해서 객체 응집도가 높아진 상태!

그럼 이제 객체들이 완전히 독립적인 건가요?

아니용!

트레이드 오프 (trade-off)

• 어떤 기능을 설계하는 방법은 한 가지 이상일 수 있다.
• 객체 자율성을 지키기 위해 전체 설계 관점에서 타 객체와의 결합도가 높아질 수도 있다.

왜 이런 일이 발생한거죠?

• 한 어플리케이션을 만들기 위해 여러 객체들이 서로 협력해야 하고, 이를 위해 객체 사이에 메시지를 주고받게 된다.
  • 이 메시지를 주고 받기 위해 필요한 최소한의 지식이 의존성을 만들게 된다.
    • 아무리 인터페이스에만 접근하게 설계하게 만들어 의존성을 낮춰도, 결국 타 객체의 인터페이스 < 에는 접근하게 되는 것.
• 좋은 설계의 목적은 의존성을 없애는게 아니라, 의존성을 낮추는 것이다.
  • 최대한 한 번에 하나의 클래스만 변경할 수 있도록, 최대한 데이터와 프로세스가 동일한 모듈 내부에 위치할 수 있도록!

그럼 객체 지향 설계의 최종 목표는 뭔가요?

협력하는 객체 사이의 의존성을 적절하게 관리하는 설계를 구현하자!

• 불필요한 의존 관계 없이, 객체들이 적절하게 상호작용하고 적당한 수준의 변경을 구현 가능하게 할 때 유연하게 설계되었다고 평가할 수 있을 것이다.

• 트랜잭션
  • DB 상태를 변화시키기 위해 수행하는 작업 단위
  • 즉, 유저(서비스)가 정의한 쿼리 묶음
    • Ex. 로그인 : 중복 ID 확인 (select)와 신규 계정 생성 (insert)
• 트랜잭션의 ACID
  • 원자성 (Atomicity) : 트랜잭션은 완전히 성공하거나 완전히 실패하거나 둘 중 하나의 상태를 가져야 한다.
  • 일관성 (Consistency) : 트랜잭션의 작업 처리 결과는 항상 일관적이어야 한다.
    • Ex. 트랜잭션 진행 중 DB가 변경되어도, 처음 참조한 DB로 트랜잭션을 진행해야 한다.
  • 격리성 (Isolation) : 둘 이상의 트랜잭션이 실행될 때, 그 어떤 트랜잭션도 다른 트랜잭션의 연산을 침범할 수 없다.
  • 지속성 (Durability) : 트랜잭션이 성공적으로 완료되었을 때, 해당 트랜잭션의 결과는 DB에 영구적으로 반영되어야 한다.

전파 속성 (Propagation)

spring boot @Transactional에서는 Propagation.REQUIRED가 default로 세팅되어 있다

전파 속성이란?

• SQL단에서 제공하는게 아니라 spring 단에서 제공하는 속성
  • Spring은 @Transactional (선언적 트랜잭션)을 이용해 여러 트랜잭션을 묶어 하나의 큰 트랜잭션 경계를 만들 수 있다.
  • 따라서 기존 트랜잭션 작업 중, 추가 트랜잭션 작업을 진행해야 할 때 해당 작업을 어떻게 진행할지 흐름을 결정해야 한다.
    • Ex. 추가 트랜잭션을 기존 트랜잭션의 일부로 볼 것인지, 아니면 별도로 볼 것인지, 아님 에러를 발생시키던지..!
  • 즉, 이 추가 트랜잭션의 흐름을 결정하는 옵션이 전파 속성!

• 요런 느낌

    @Transactional
    public void parent() {
      deviceRepository.save(new Device());
      child();
    }
  
    @Transactional
    public void child() {
      deviceRepository.save(new Device());
    }

Spring Boot @Transactional 옵션 정리

• 부모 트랜잭션 : 호출한 메소드의 트랜잭션
• 자식 트랜잭션 : 호출당한 메소드의 트랜잭션

• Propagation.REQUIRED
  • 부모 트랜잭션이 존재한다면, 자식 트랜잭션은 부모에게 포함된다.
    • 즉, 자식 트랜잭션이 실패하면 부모도 롤백된다
  • 부모 트랜잭션이 존재하지 않다면, 새로운 트랜잭션을 생성한다 (즉 자식이 부모가 된다)
• Propagation.REQUIRES_NEW
  • 부모 트랜잭션의 존재 유무와 관계없이, 새로운 트랜잭션을 생성한다.
• Propagation.NESTED
  • 부모 트랜잭션이 존재할 경우, 부모 트랜잭션 안에 새로운 트랜잭션을 생성한다.
  • 단, 자식 트랜잭션은 부모 트랜잭션의 영향(커밋, 롤백)을 받지만 부모는 자식의 영향을 받지 않는다.
    • 부모를 롤백하면 자식도 롤백되지만, 자식을 롤백해도 부모는 영향 X
• Propagation.MANDATORY
  • 부모가 존재하면 부모에 포함
  • 부모가 존재하지 않는다면 예외 발생
• Propagation.SUPPORTS
  • 부모가 존재하면 부모에 포함
  • 부모가 존재하지 않는다면 트랜잭션 없이 동작
• Propagation.NOT_SUPPORTED
  • 부모가 존재하면 부모 트랜잭션을 보류하고, 트랜잭션 없이 동작
  • 부모가 존재하지 않는다면 트랜잭션 없이 동작
• Propagation.NEVER
  • 트랜잭션을 사용하지 않도록 강제한다.
  • 부모가 존재할 경우, 예외 발생

고립 레벨 (Isolation)

spring boot @Transactional에서는 Isolation.DEFAULT, 즉 JDBC isolation level가 default로 세팅되어 있다. :: 즉 MySQL InnoDB를 사용한다면 REPEATABLE READ 사용

고립 레벨이란?

• Shared Lock (공유 잠금) : 읽기 잠금
• Exclusive Lock (배타적 잠금) : Insert, Update, Delete (=쓰기) 잠금

• SQL의 Isolation level과 동일하게 동작
• SQL의 고립 레벨 (= 고립 수준 = 격리 레벨 = 격리수준)이란?
  • 트랜잭션끼리 일관성 없는 데이터를 허용하는 수준
• 종류
  • [Level 0] Read Uncommitted : select 수행하는 동안 해당 데이터에 Shared lock이 걸리지 않는다.
  • [Level 1] Read Committed : select 수행하는 동안 해당 데이터에 Shared lock이 걸린다.
  • [Level 2] Repeatable Read : 트랜잭션이 완료될 때까지 해당 데이터 수정이 불가능하다.
  • [Level 3] Serializable : 트랜잭션이 완료될 때까지 해당 데이터 수정, 입력이 불가능하다.

고립 레벨별 나타나는 이슈

• Dirty Read : Uncommitted 또는 더티 버퍼에 있는 데이터를 읽어, 롤백된 데이터를 노출하게 됨
• Non Repeatable Read : 동일한 쿼리를 2번(A와 B라고 가정) 실행 할 때, A와 B 사이에 수정 또는 삭제가 일어나 A와 B의 결과가 달라짐 (=행 값의 변화)
• Phantom Read : 동일한 쿼리를 2번(A와 B라고 가정) 실행할 때, A와 B 사이에 삽입이 일어나 A와 B의 결과가 달라짐 (=행 수의 변화)

DB별 default isolation

• MySQL InnoDB : REPEATABLE READ
• Oracle : READ COMMITTED

Spring Boot @Transactional 옵션 정리

SQL의 고립레벨과 동일!!!

Ex. 홍길동씨와 강동원씨가 공유 통장에 대해 아래 작업을 요청할 때

1. 통장 잔고 확인 (=select)
2. 통장 잔고 수정 (=update)

• Isolation.READ_UNCOMMITTED (level 0)
  • 홍길동씨가 잔고 수정 작업을 끝마치기 전, 강동원씨는 통장 잔고를 확인할 수 있다.
• Isolation.READ_COMMITTED (level 1)
  • 홍길동씨가 잔고 수정을 끝마치기 전까지, 강동원씨는 통장 잔고를 확인할 수 없다.
• Isolation.REPEATABLE_READ (level 2)
  • 홍길동씨가 잔고 확인, 잔고 수정 작업을 끝마칠 때까지 강동원씨는 아무 작업도 시작할 수 없다.
  • 단, 입금의 경우 (=insert) 처리할 수 있다. 하지만 홍길동씨와 강동원씨의 잔고 확인 결과가 달라질 수 있다.
• Isolation.SERIALIZABLE (level 3)
  • 홍길동씨가 잔고 확인, 잔고 수정 작업을 끝마칠 때까지 강동원씨는 아무 작업도 시작할 수 없다 (입금도 불가능).

완전 탐색을 쌈싸먹기 전, 관련 개념을 알아보자 🧐

비트 마스크

bit 연산을 이용해 부분 집합을 나타내는 방법 집합을 배열의 인덱스로 표현할 수 있기 때문에 상태 다이나믹을 할 때 자주 사용한다. STL의 bitset을 이용해서 더 쉽게 사용할 수 있다!

종류

• and (&) : 둘 다 1일 때 1
• or (|) : 둘 중 하나라도 1이면 1
• not (~) : 0이면 1, 1이면 0
• xor (^) : 같으면 0, 다르면 1

비트 연산

• 두 수 A와 B를 비트 연산 하는 경우, 가장 뒤의 자리부터 하나씩 연산을 수행한다.
• not 연산의 경우
  • 자료형에 따라 결과 달라진다. 비트가 자료형에 따라 달라지니까!
    • 8비트 자료형, 32비트 자료형, unsigned, signed...
• shift left (<<), shift right (>>)
  • A << B : A를 왼쪽으로 B비트만큼 민다. A * 2^B와 동일
    • 1 << 1 : 10이니까 2
  • A >> B : A를 오른쪽으로 B비트만큼 민다. A / 2^B와 동일
    • 10 >> 2 : 10이니까 2
  • (A+B)/2 = (A+B) >> 1

비트 마스크

• *정수로 집합(S)을 나타낼 수 있다. *
  • {1, 3, 4, 5, 9] = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9 = 1000111010
• *어떤 수(i)의 포함 여부를 확인하기 위해 & 연산을 이용한다. *
  • S & (1 << i)
  • 0이 포함되어 있는지 검사
    • 570 & 2^0 = 570 & (1<<0) = 1000111010 & 1 = 0
  • 1이 포함되어 있는지 검사
    • 570 & 2^1 = 570 & (1<<1) = 1000111010 & 10 = 10 = 2
  • 2가 포함되어 있는지 검사
    • 570 & 2^2 = 570 & (1<<2) = 1000111010 & 100 = 000 = 0
• *어떤 수(i)를 새로 추가하기 위해 | 연산을 이용한다. *
  • S | (1 << i)
  • 2 추가하기
    • 570 | 2^2 = 570 | (1<<2) = 1000111010 | 100 = 1000111110 = 574
  • 만약 이미 존재하는 수를 새로 추가한다면? 그대로!
    • 1 추가하기
    • 570 | 2^1 = 570 | (1<<1) = 1000111010 | 10 = 1000111010 = 570
• 어떤 수(i)를 제거하기 위해 ~ 연산을 이용한다.
  • S & ~(1 << i)
  • 1 제거하기
    • 570 & ~2^1 = 570 & ~(1<<1) = 570 & ~(10) = 1000111010 & ~(01) = 1000111010 & 1111111101 = 1000111000 = 568
• 어떤 수(i)를 토글하기 위해 ^ 연산을 이용한다.
  • S ^ (1 << i)
• *전체 집합 : (1<<N) - 1 *
• 공집합 : 0

문제 예제 (1) : 백준 집합

https://www.acmicpc.net/problem/11723

내 풀이

• 고냥 저항없이 위에서 공부한대로 코드를 짰다.
  • 그랬더니 시간 초과~😇
  • 입력은 버퍼로 받았으니 아마 출력하는 부분이 문제겠지 싶어서 StringBuilder를 사용하도록 코드를 수정해줬다.
  • 수정해주니 통과했다. 굿굿 앞으론 스트링빌더를 걍 습관처럼 써줘야지

순열

1~N까지로 이루어진 수열. 크기는 항상 N이며, 겹치는 숫자가 존재하지 않아야 한다.

다음 순열

순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법

다음 순열 찾는 법 (O(n))

예시 순열 : 7 2 3 6 5 4 1

• A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾는다.
  • 가장 큰 i니까 오른쪽에서 부터 체크!
    • 즉 순열의 마지막 수에서 끝나는 가장 긴 감소 수열 찾기.
      • A[i-1] = 3, A[i] = 6. i = 3
      • 감소수열은 6 5 4 1
• j >= i 면서 A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다.
  • 가장 큰 j니까 오른쪽에서 찾아야!
  • A[j] = 4. j = 5
• A[i-1]과 A[j]를 swap한다
  • 7 2 4 6 5 3 1
• A[i]부터 순열을 뒤집는다.
  • 7 2 4 1 3 5 6

다음 순열에서 제일 첫 번째 순열은 오름차순, 제일 마지막 순열은 내림차순이다. 따라서 다음 순열을 구할 때, 특정 인덱스에서 사전 순 다음 값의 조건은

• 현재 값보다 크면서
• 현재 값 다음 인덱스의 수들 중 제일 작은 값이어야 한다

을 충족해야 한다.

문제 예제 (2) : 백준 다음 순열

https://www.acmicpc.net/problem/10972

내 풀이

• 이번에도 저항없이... 위에서 공부한 다음 순열 구하는 방식을 그대로 코드로 구현했다.
• System.out을 이용한 경우
• StringBuilder를 이용한 경우

문제 예제 (3) : 백준 이전 순열

https://www.acmicpc.net/problem/10973

내 풀이

• 다음 순열 구했던거랑 반대로 구하면 된다.
• 맞았당ㅎ.ㅎ

문제 예제 (4) : 백준 모든 순열

https://www.acmicpc.net/problem/10974

내 풀이

• 다음 순열 구했던걸 응용하면 된다.
• 맞았다~

문제 예제 (5) : 백준 순열의 순서

https://www.acmicpc.net/problem/1722

내 풀이

• 두번째 입력의 첫번째 수가 1이면 k번째 순열을, 2면 뒤이어 입력한 순열이 몇 번째 순열인지 찾으면 된다.
• 완전 아무 생각 없이 풀면, 위에서 풀었던 다음 순열을 응용하면 된다.
  • 순서 변수 하나 만들어서, 다음 순열 함수가 호출될 때마다 카운트하는 방식.
  • 근데 이게 좋은 풀이일까? 🤔
• 아아아아아주 오래 전 공부했던 확통 지식을 되살려보면, 순열의 개수는 팩토리얼로 구했다.
  • ex. 1~N으로 이루어진 순열의 크기는 N!
    • 요건 각 자리에 올 수 있는 숫자의 개수로 만든 공식이다.
    • N= 5일 때, 맨 처음에 올 수 있는 수는 1, 2, 3, 4, 5니까 5, 두번째 올 수 있는 수는 앞에 나온 수 제외하고 전부니까 5, ... 하는 식으로.
  • 요걸 잘 응용하면 되지 않을까?
    • 왜냐하면 문제 조건에서 순열의 순서는 사전순 (오름차순)이라고 했으니까!
    • 예를 들어 N=3일 때 { 1 2 3 } 의 순서를 찾아보자.
    • 각 자리수에 올 수 있는 첫번째 숫자들이 배치되어 있으니, 0 x 0 x 0 = 0. 첫번째 순열을 고려해서 +1해주면 k = 1.
    • 이번엔 { 3 2 1 }
      • 첫번째 자리수에 3은 세번째로 올 수 있는 수다. 따라서 2! x 2 = 4
      • 두번째 자리수에 2는 두번째로 올 수 있는 수다. 따라서 1
      • 세번째 자리수에 1은 처음으로 올 수 있는 수다. 따라서 0
    • 4 + 1 + 1(첫번째) = 6
    • 실제로 순열을 전부 나열해보면 아래와 같으므로 6번째 순열이 맞다.
      1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
  • 옹 일단 순서는 구할 수 있겠다! 그럼 이제 순서가 주어졌을 때 순열을 찾는 방법을 고민해보자.
  • 위에서 생각한 순서 찾는 로직을 응용하면 된다. 주어진 숫자가 전체 수 N에서 몇 번째 순서에 위치해있는지를 알면 쏘~이지

그리디 알고리즘을 쌈싸먹어 보자2

문제 예제 (1) : 백준 잃어버린 괄호

https://www.acmicpc.net/problem/1541

내 풀이

• 세준이는 왜 이런 일을 하는 걸까..? 진짜 이상한 애야..
• '+'와 '-' 연산으로만 이루어져 있다는게 포인트인 것 같다.
  • '+'만 있는 경우엔 더하기만, '-'만 있는 경우엔 빼기만 하면 된다. 즉 문제는 더하기랑 빼기가 섞여 있는 경우!
• 상식적으로 생각하면 결과가 작으려면 작은 수에서 큰 수를 빼면 된다.
  • 그럼 빼기 연산자 바로 뒤에 더하기 연산자가 나온다면, 그 위치에 괄호를 넣으면 된다.
  • ex. a-b+c가 있다면 a-(b+c) 요런식으로!
• 습 근디 코드로 어케 구현하지?
  • 근데 문제가 괄호의 위치를 구하는게 아니라, 최소값을 구하는거니까 그냥 + 연산자가 나왔을 때 -계산을 하면 되는거 아닌가..?!
    • 구론데구로나 + 연산자만 있는 경우엔 + 연산만 해야 한다. 그렇다고 전체 반복을 돈 다음 +만 있는지 -만 있는지 둘다 있는지 케이스를 나눠서 수행하면 쓸데없이 코드 라인만 길어지고 반복도 많이 돌게 된다.
  • StringTokenizer로 음수 기준으로 자르고, 자른 문자열에 연산자가 끼어있다면 더해서 빼자
    • 근데 문제가 있다! 맨 초기값을 정해야 하는데, 만약 + 연산자만 있다면 StringTokenizer가 자르지 못하니까 숫자로 형변환를 할 수 없다.
      • result를 이상한 값(MAX_VALUE 등)으로 초기화하고 조건문으로 체크해주는 방법도 있겠지만, 마지막에 result에서 초기값을 다시 연산해주는게 싫어서 && 혹시라도 반복문 중간에 초기값이 또 나올까봐 boolean 플래그를 하나 두었다.

    int result = 0;
    boolean isFirst = true;
    while (st.hasMoreTokens()) {
      String subStr = st.nextToken();
      int subResult = 0;
      StringTokenizer plusSt = new StringTokenizer(subStr, "+");
      while (plusSt.hasMoreTokens()) {
        subResult += Integer.parseInt(plusSt.nextToken());
      }
      if (isFirst) {
        result += subResult;
        isFirst = false;
      }
      else result -= subResult;
    }

• 맞았다ㅎㅎ

해설

• sign와 minus 변수 두개를 활용한다.
• 만약 + 연산자가 나오면 sign에 1을, - 연산자가 나오면 sign에 -1을 넣는다.
• 이후 minus 변수를 이용, sign에서 -1이 한 번이라도 나오면 그 이후로 나오는 모든 수를 전부 뺀다 (+와 -가 섞인 경우니까 전부 빼기로 대체)

근데 이게 왜 그리디 유형인지 아직 잘 모르겠다..! 😇

문제 예제 (2) : 백준 수 묶기

https://www.acmicpc.net/problem/1744

내 풀이

• 아까는 더하기, 빼기를 응용해서 최소값을 구했다면 지금은 곱하기를 응용해서 최대값을 구하기!
• 조건 : 동일 숫자를 묶어서 곱하면 안됨, 모든 수는 단 한번만 묶거나 혹은 묶지 않아야 함, 정답은 항상 2^31보다 작음
• 당연히 곱해서 큰 수끼리 묶어야겠지?
  • 일단 수를 입력받는데, 음수랑 양수를 묶으면 안되니까 따로 입력받자.
  • 입력받은 수들을 내림차순 정렬하자. 이때 음수는 오름차순 정렬해야한다.
    • 왜냐하면 음수 * 음수는 양수니까, 작은 순서대로 정렬해야 결과적으로 수가 커지기 때문!
  • 0은 음수 배열에 들어가야한다.
    • 만약 입력받은 음수가 총 짝수개라면, 음수와 곱해서 0으로 만들어 더하는게 좋고, 홀수개라면 오름차순 정렬해서 마지막 남은 1개 (묶이지 않은)로 더해주는게 좋으니까.
• 이후 각각 배열에서 수를 묶어서 결과값에 더한다.
  • 배열 사이즈가 홀수라면 제일 마지막 인덱스는 제외하고 묶고, 짝수라면 고냥 다 묶는 방식
• 근데 대차게 틀렸다ㅋㅋㅋㅋ
  • 왜지? 하고 테케를 다시 흝어봤는데, 하나하나 다 돌려보니 [2, 1, 1]에서 틀렸다!
  • (테케 다 돌려보지도 않고 제출한 내가 돌멩이긴 함ㅠㅠ)
  • 위처럼 1이 짝수개 연속해서 나온다면, 걍 각자 더하는게 더 결과가 커지기 때문! 진짜...멍청하다 나 자신....

  public static int tieNum(List<Integer> numList) {
    int result = 0;
    int size = numList.size();
    int j = 0;
    while (j < size) {
      // DESCRIBE: 전체 크기가 짝수일 때 마지막 수가 아니라면, 그리고 현재랑 다음이 1이 아니라면 곱해서 더하기
      if (j+1 < size && numList.get(j) != 1 && numList.get(j+1) != 1) {
        result += numList.get(j++) * numList.get(j++);
      }

      // DESCRIBE: 아니라면 각각 더하기
      else {
        result += numList.get(j++);
      }
    }
    return result;
  }

• 맞았다~~

해설

• 양수는 큰 수끼리
  • 하지만 1끼리는 묶지 말기!
• 음수는 작은 수끼리
• 0은 묶지 않는 것이 최대
  • 하지만 묶이지 않은 음수가 있다면 0을 이용하자
• 처음 숫자 입력 받을 때부터 1의 개수와 0의 개수를 세고, 양수 배열과 음수 배열을 짝수 사이즈로 만들어서 푸는 방법도 있다.

문제 예제 (3) : 백준 대회 or 인턴

https://www.acmicpc.net/problem/2875

내 풀이

• n과 m을 줄이면서 팀 수를 카운트하면 된다.
• 근데 이제 남은 사람으로 인턴십도 보내고~ 팀도 만들 수 있을 때까지!

    int result = 0;
    while (n+m >= k+3 && n >= 2 && m >= 1) {
      n -= 2;
      m -= 1;
      result+=1;
    }

• 맞았돵

해설

• 아래 경우가 한 팀 (동일 접근)
  • n+3 >= k+3
  • m >= 1
  • n >= 2

문제 예제 (4) : 백준 30 (10:53, 8분 종료)

https://www.acmicpc.net/problem/10610

내 풀이

• 미르코씨...재밌게 사시는 분이시군요
• 30의 배수 = 3 * 10의 배수
• 즉 아래 조건을 충족해야 한다
  • 하나 이상의 0 포함 (10의 배수가 되려면 마지막 자리가 0이여야 함)
  • 각 자리의 숫자들을 더했을 때 3의 배수여야 함 (3의 배수 조건)
  • 일단 위 조건 충족 못 하면 바로 -1 리턴하게 하자.
• 충족한다면 이제 최대값을 찾아야함~
  • 위에서 3의 배수 조건을 이미 충족했으니 제일 마지막 자리가 0이기만 하면 된다.
  • 입력값이 무조건 양수임을 이용, 입력 문자열을 정수 배열로 만들어서 내림차순 정렬하면 된다.

코드를 입력하세요

• 맞았지렁

해설

• 동일 접근

그리디 알고리즘을 쌈싸먹어 보자!

그리디 알고리즘

특징

• 결정해야 할 때 그 순간 제일 좋다고 생각되는 걸 선택하면서 답을 찾는 알고리즘
  • 졸리면 자고~ 배고프면 밥 먹고~
• 즉 그 순간엔 최적이라도, 최종적으로는 답이 최적이 아닐 수 있다

  유형

• 거스름돈 문제
  • 동전도 지페도 아주 많을 때, N원을 최소 개수의 지폐, 동전을 이용해서 거슬러주려면 어떻게 해야 하는가?
    • 가장 큰 액면가를 가진 지폐 / 동전부터 거슬러주자!
• 즉, 지금 순간에 제일 최적인 걸 골라야 할 때 사용하는 알고리즘...! 🤔

문제 예제 (1) : 백준 동전 0

https://www.acmicpc.net/problem/11047

내 풀이

• 가치의 합은 최대인데, 사용해야 하는 동전 개수는 최소
  • 즉 K원을 만들기 위해 숫자를 쪼갰을 때 가장 적게 쪼갤 수 있는 기준(배수)를 찾아야 한다.
• 주어진 동전의 가치가 오름차순이니까, 뒤에서부터 내려와야 한다.
  • 뒤에서 내려오면서 만약 현재 동전 가치가 K보다 크다면 넘기고, 작다면 쪼개는 과정을 반복하면 될 듯?

    // DESCRIBE: 동전 개수 찾기
    for (int i = N-1; i >= 0; i--) {
      if (array[i] <= K) {
        answer += (K/array[i]);
        K %= array[i];
      }
    }

• 옹ㅎㅎ 맞았다

해설

• (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
  • 요 조건 덕분에 그리디 알고리즘이 성립하게 된다
  • 돈을 1원짜리로 전부 바꾼 다음, 그 다음 동전의 가치가 항상 이전 동전의 배수를 만드는지 확인해서 항상 성립하는지 확인하자.

문제 예제 (2) : 백준 회의실 배정

https://www.acmicpc.net/problem/1931

내 풀이

• 이 문제가 그리디 유형인걸 어떻게 알 수 있을까?
  • N개 중 어떤 것을 선택하느냐에 따라 결과가 달라지는 문제다.
  • 즉 일종의 거스름돈 문제인거지..!
    • 거스름돈은 최대 액면가를 가진 동전/지폐부터 골랐다면, 이 문제에서는 어떤 회의를 우선적으로 골라야 할까?
      • 평범하게 생각해보면 회의 시간이 짧거나, 일찍 시작하는 회의를 고르면 될거다. 하지만 시작 시간을 기준으로 잡으면 안된다. 다음 회의랑 겹칠 수 있으니까!
        • (1 4, 3 5, 0 6이 있을 때 시작 시간 기준으로 잡으면 1 4, 0 6이지만 종료 시간을 고려하면 겹치는 회의다)
        • 따라서 종료 시간을 기준으로 잡고, 시작 시간이 앞에서 잡은 종료 시간보다 같거나 큰 경우를 우선적으로 고르면 될거다
      • 위의 흐름에서, 회의를 선택하는 기준은 (1) 회의 종료 시간이 빠르면서 (2) 전체 회의 시간이 짧은 친구를 우선적으로 골라내야 한다.
• 그럼 어케 풀까?
  • 일단 회의 종료 시간을 기준으로 입력 회의들을 오름차순 정렬한다.
  • 첫번째 인덱스부터 시작해서, 만약 다음 인덱스의 시작 시간이 이전 인덱스의 종료 시간보다 같거나 큰 경우만 카운트한다.
    • 이렇게 하면, 만약 시작 시간이 동일하더라도 종료 시간이 더 빠른 친구가 먼저 선택되니까 굳이 회의 전체 시간을 따로 계산해 줄 필요가 없다!
      • 테케에서 (5,7) (5,9)가 해당. 시작 시간이 동일하다고 가정했을 때, 종료 시간을 기준으로 오름차순 정렬했으니 자연스럽게 전체 회의 시간이 짧은 (5, 7)이 카운트된다.

    // DESCRIBE: 종료 시간 기준으로 오름차순 정렬. 만약 동일하다면 시작 시간 오름차순으로 
    Arrays.sort(array, (o1, o2) -> {
      if(o1[1] == o2[1]) {
        return o1[0] - o2[0];
      }else {
        return o1[1] - o2[1];
      }
    });

    // DESCRIBE: 현재 인덱스의 시작 시간이 이전 인덱스의 종료 시간보다 크거나 같다면 카운트
    int prevEndTime = array[0][1];
    for (int i = 1; i < N; i++) {
      if (array[i][0] >= prevEndTime) {
        result += 1;
        prevEndTime = array[i][1];
      }
    }

• 맞았다! (2차원 배열 정렬 연습 좀 해야할듯^^^^)

해설

• 오 회의 시간이 짧은 경우는 아예 기준이 될 수 없구나..!
  • 기준 세우고 반례 고민하는 연습을 해야 할 것 같다.
    • 나는 풀 때 어? 정렬해두고 보니 회의 시간 짧은건 따로 계산 안해도 되네? 하고 풀었는데, 사실은 아예 고려하면 안되는 대상이었던 것..! 🤔
    • 이건 맞은게 아니라 틀렸다고 봐야 할 것 같다. 걍 얻어 걸린거니까... 😇

문제 예제 (3) : 백준 ATM

https://www.acmicpc.net/problem/11399

내 풀이

• 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값 = 누적합이 최소
  • 즉 돈을 뽑는데 걸리는 시간이 작은 사람 순으로 고르면 된다.
    • ex. 3 1 4 3 2 -> 3 + (3+1) + (3+1+4) + (3+1+4+3) + (3+1+4+3+2) = 39
    • ex. 1 2 3 3 4 -> 1 + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4) = 32
• 입력값을 오름차순으로 정렬하고, 이후 누적합을 구하자.

    // DESCRIBE: 오름차순 정렬
    Arrays.sort(array);

    // DESCRIBE: 누적합 구하기
    int waitTime = 0;
    int totalWaitTime = 0;
    for (int i = 0; i<N; i++) {
      waitTime += array[i];
      totalWaitTime += waitTime;
    }

• 맞았다 ^~^

해설

• 오름차순 = 비내림차순으로 정렬! 동일한 접근
  • (증명) 오름차순으로 정렬하고 결과값(S)을 구했을 때, 인덱스를 바꿔서 다시 계산(S')해보면 값이 같거나 커지게 된다.
  • (증명) S-S' = (i-j)(pj-pi)
  • (i-j)가 <= 0 이므로 항상 음수가 된다. 즉 S'는 언제나 S보다 같거나 크다.
    • 따라서 오름차순으로 정렬하는게 최적해가 된다.
• 우억 이렇게 증명할 생각은 안하고 그냥 냅다 응 당연히 오름차순이지~ 하고 풀었는데.. 이렇게 풀면 이제 실전에서 테케에 갈려나가는거겠지?! 🔨
  • 구상한 풀이를 먼저 증명한 후 구현하는 연습이 필요하다! 그냥 이럴 것 같아~ 하고 풀지 말자!

스택을 쌈싸먹어 보자!

스택

특징

• 한 쪽으로만 자료를 넣고 뺄 수 있다
• 위 특징 때문에 제일 먼저 들어간 자료가 제일 나중에 나오는 구조 = 선입후출 (LIFO)

스택의 구현

• 배열을 이용, 자료를 넣을 땐 size가 늘어나고 뺄 땐 size가 줄어드는 원리

문제 예제 1 (백준 9012 괄호)

https://www.acmicpc.net/problem/9012

내 풀이

• '('와 ')'의 쌍이 안 맞는 경우가 있다면 NO를 출력하면 된다.

  • '('가 ')'보다 먼저 나와야 함
    • 즉 현재 위치에서 ')'의 수는 항상 '('의 수보다 작거나 같아야 함
    • 동시에 문자열 끝까지 갔을 때, '('의 수와 ')'의 수는 같아야 함

• 문자열을 입력받은 후, 첫 글자부터 마지막 글자까지 넘어가면서 괄호 수를 센다.

  • 만약 반복문 도는 도중에 '('의 수가 ')'의 수보다 적어진다면 바로 리턴

    • (불필요한 반복을 줄이기 위함)

  • 끝까지 돌았을 때 '('의 수와 ')'의 수 비교

    public static void count(String str) {
    int left = 0;
    int right = 0;
    
    for (int i = 0; i < str.length(); i++) {
      if (str.charAt(i) == '(') left++;
      else right++;
    
      if (right > left) {
        System.out.println("NO");
        return;
      }
    }
    
    if (right != left) System.out.println("NO");
    else System.out.println("YES");
    }

• 맞았당

해설

• 닫는 괄호가 나왔을 때, 아직 짝이 없는 여는 괄호와 매칭한다면?
  • 모든 문자에 대해 검사를 수행해야 하므로 시간 복잡도는 O(N)
• (풀이) 스택에 아직 짝이 없는 여는 괄호를 집어 넣고, 닫는 괄호가 나올 때마다 하나씩 스택에서 빼주는 방식으로 구현한다.
  • 이 경우 최종적으로 스택이 비었는지 아닌지 체크만 하면 되니까 시간 복잡도는 O(1)
  • 근데 이제 이걸 스택에 직접 넣고 빼지 말고, cnt 값을 이용하면 좀 더 쉬워진다!
    • cnt가 음수인지 아닌지로 판별하는 방식

훔 풀이를 어떻게 하느냐보다, 이 문제를 보고 스택이 생각났냐 안났냐로 접근하면 좋을 것 같다..! 사실 풀이를 듣고도 왜 굳이 스택을 응용해야 하는지 모르겠다 (어차피 문자열의 처음부터 끝까지 반복을 돌아야 하는건 똑같으니까)

문제 예제 2 (백준 9012 쇠막대기)

https://www.acmicpc.net/problem/10799

내 풀이

• 이 친구도 결국 방금 풀었던 괄호 쌍 만드는 문제!
• 스택을 응용해서 풀어보자.
  • 여는 괄호가 나오면 스택에 넣는다.
  • 닫는 괄호가 나오면 스택에서 뺀다. 이때 result += 1
• 이렇게 입력 문자열 끝까지 돈 다음, result 수를 출력하면 될 것 같다.
  • 근데 이제 쇠막대기가 겹쳐있을 수 있다는 점을 고려해야 하는..!
  • 여는 괄호가 연속해서 나온다면 -> 즉, 닫는 괄호가 나와서 스택을 pop했을 때 스택이 비지 않았다면 스택 사이즈만큼 더해주면 된다.
• 라고 생각했는데 테케에서 틀렸다ㅋㅎ
  • )(의 경우와 ())(()의 경우, 즉 가운데가 빈 경우와 아닌 경우를 고려해야 하기 때문!

• 즉 인접한 쇠 막대기가 있냐 없냐로 result를 증가시켜야 한다.

  • 그럼 인접한 쇠 막대기가 있다는걸 코드로 어떻게 알 수 있을까?
    • 위 사진에서 제일 작은 쇠막대기가 +1이 될 때, 그 밑에 있는 친구들은 카운트되면 안된다. 아직 안 잘렸으니까! 이 차이에서 어떻게 알 수 있는지 잡아보자.
      • 밑까지 전부 잘리는 경우, 즉 인접한 쇠막대가 없는 경우는 여는 괄호와 닫는 괄호가 바로 이어서 나오는 경우다.
      • 밑은 안 잘리는 경우, 즉 인접한 쇠막대가 있는 경우는 여는 괄호와 닫는 괄호의 사이가 떨어져 있는 경우다.
  • 하지만 여는 괄호와 닫는 괄호가 연달아 나오는지 알기 위해선 인덱스가 필요하다.
    • 어차피 스택에 괄호를 넣어봤자 쓸모가 없으니 (닫는 괄호 나올 때 pop하는 용도로 썼으니 안에 뭐가 들어가도 상관없음) 인덱스를 넣어서 풀어보자.

      for (int i=0; i<str.length(); i++) {
      if (str.charAt(i) == '(') stack.push(i);
      else {
        if (i-1 == stack.pop()) result += stack.size();
        else result += 1;
      }
      }

• 맞았당22

해설

• 옹 같은 방식으로 인덱스로 접근했다! ^____^ 햅비~

문제 예제 3 (백준 1406 에디터)

https://www.acmicpc.net/problem/9012

내 풀이

• 요건 예전에 풀었던 문제라 생략!
• 스택을 이용해 풀었고, 커서 왼쪽과 오른쪽을 구분해서 명령어마다 push, pop 작업을 수행하도록 구현했었다.

해설

• 문제 N 제한이 제일 중요하다!

  • 조건에 따라, 문자열의 길이는 최대 60만이 될 수 있다.
  • 단순 문자열로 풀면 L은 O(1), D는 O(1), B는 O(N), P는 O(N)으로 O(N^2)가 나와 시간 초과가 뜰 것

• 따라서 좀 더 효율적인 방식으로 -> 커서를 기준으로 왼쪽과 오른쪽으로 나눠서 풀자!

  • 왼쪽 오른쪽 번갈아 push, pop을 먹이면 모든 명령이 O(1)이 된다.
  • 즉 O(n)이 되므로 문제 제한 시간에 딱 맞출 수 있게 된다.
  
  

옹 접근 자체는 맞았는데, 이렇게 시간 복잡도를 하나하나 따지진 않았던 것 같다. 솔직히 문제 분류에서 스택인거 보고 힌트 얻었던 것 같군 😇 조건과 시간 복잡도 따지는 연습을 해야겠다.

스키마 & 타입

객체 타입과 필드

스키마의 대부분은 객체 타입이다! 서비스에서 가져올 수 있는 객체의 종류와 그 객체의 필드를 표현한다.

• GraphQL 스키마 언어 예시
  • Character : GraphQL 객체 타입
  • name, apperasIn : Character의 필드
  • String : 내장 스칼라 타입 -> 스칼라 객체로 해석
  • ! : 해당 필드가 non-null임을 표현
  • [Episode] : Episode 객체의 배열(array)임을 표현
  • length(unit: LengthUnit = METER) : 인자
    • 필수 혹은 옵셔널
    • 옵셔널일 경우, 디폴트 값 정의 가능

쿼리 타입 & 뮤테이션 타입

스키마에 대한 진입점 (Entry point) 정의 위 특이점 제외, 나머지는 객체 타입과 정확히 동일한 방식으로 작동!

// 쿼리 
query {
  hero {
    name
  }
  droid(id: "2000") {
    name
  }
}

// GraphQL 서비스
type Query {
  hero(episode: Episode): Character
  droid(id: ID!): Droid
}

스칼라 타입

하위 필드가 없는 쿼리의 끝

• 위 쿼리에서 name, appearIn은 스칼라 타입이다.
  • Int : 부호가 있는 32비트 정수
  • Float : 부호가 있는 부동소수점 값
  • String: UTF-8 문자열
  • Boolean : true 혹은 false
  • ID : 고유 식별자

열거형 타입 (Enums)

특정 값들로 제한되는 특별한 종류의 스칼라

• 이런 작업을 할 수 있어요!

  • 타입의 인자가 허용된 값 중 하나임을 검증
  • 필드가 항상 값의 열거형 집합 중 하나가 될 것임을 타입 시스템을 이용해 소통

• 이렇게 생겼어요

리스트와 Non-Null

스키마의 다른 타입, 또는 쿼리 변수 선언에서 타입을 활용하면 값의 유효성 검사를 할 수 있는 타입 수정자 (type modifiers)를 적용할 수 있다.

• !를 이용해 Non-Null로 표시 :: null값이 발생하면 GraphQL 실행 오류 발생 -> 유효성 검사 오류 반환
• [] 를 이용해 리스트로 표시 :: 해당 타입의 배열을 반환. 배열이 필요한 인자에 대해 유효성 검사 작동

👾 요따구로 섞어 쓸 수도 있답니다~~

• myField: [String!]
• 리스트 자체는 null일 수 있지만, element는 null일 수 없다.
  • myField: null // valid
  • myField: [] // valid
  • myField: ['a', 'b'] // valid
  • myField: ['a', null, 'b'] // error

인터페이스

뭔가를 구현하기 위해 타입이 포함해야 하는 특정 필드들을 포함하는 추상 타입

// 인터페이스 
interface Character {
  id: ID!
  name: String!
  friends: [Character]
  appearsIn: [Episode]!
}

// 인터페이스를 구현한 타입
type Human implements Character {
  id: ID!
  name: String!
  friends: [Character]
  appearsIn: [Episode]!
  starships: [Starship]
  totalCredits: Int
}

type Droid implements Character {
  id: ID!
  name: String!
  friends: [Character]
  appearsIn: [Episode]!
  primaryFunction: String
}

유니온 타입

인터페이스와 유사하지만, 타입 간 공통 필드를 특정하지 않는다.

• 유니온 타입의 멤버는 구체적인 객체여야 한다.
• 인터페이스 혹은 유니온 타입에서 다른 유니온 타입을 사용할 수 없다.

• 위 예시에서 SearchResult를 반환할 때마다 Human, Droid, Startship 를 얻을 수 있다.
• SearchResult를 반환하는 필드를 쿼리하려면, 어떤 필드라도 쿼리할 수 있도록 조건부 프래그먼트를 활용해야 한다.

  {
    search(text: "an") {
      ... on Human {
        name
        height
      }
      ... on Droid {
        name
        primaryFunction
      }
      ... on Starship {
        name
        length
      }
    }
  }

입력 타입

뮤테이션에서 생성될 전체 객체를 전달할 때 사용! 일반 객체 타입과 동일하지만, type 대신 input을 사용한다.

• 입력 객체 타입의 입력란은 입력 객체 타입을 참조할 수 있다.
• 입력 및 출력 타입을 스키마에 혼합할 수는 없다.
• 필드에 인자를 가질 수 없다.

/// input 객체
input ReviewInput {
  stars: Int!
  commentary: String
}

// 뮤테이션
mutation CreateReviewForEpisode($ep: Episode!, $review: ReviewInput!) {
  createReview(episode: $ep, review: $review) {
    stars
    commentary
  }
}

// variables
{
  "ep": "JEDI",
  "review": {
    "stars": 5,
    "commentary": "This is a great movie!"
  }
}

// 결과 
{
  "data": {
    "createReview": {
      "stars": 5,
      "commentary": "This is a great movie!"
    }
  }
}

레퍼런스

• 공식문서

구조

Query

• 데이터 조회(fetch) 역할
• read 수행

// 쿼리 
{
  hero {
    name
    friends {
      name
    }
  }
}

// 결과 
{
  "data": {
    "hero": {
      "name": "R2-D2",
      "friends": [
        {
          "name": "Luke Skywalker"
        },
        {
          "name": "Han Solo"
        },
      ]
    }
  }
}

🔨 프래그먼트

• 복잡한 데이터 요구사항을 작은 단위로 분할하기 위해 사용하는 재사용 가능한 단위
• 프래그먼트를 이용, 필드셋을 구성해 쿼리에 포함시킬 수 있다.
• 청크가 다른 여러 UI 구성 요소를 하나의 데이터 fetch로 통합할 때 많이 사용!

🛠 지시어

• 쿼리 구조와 형태를 동적으로 변경하기 위해 사용한다.
• 필드나 프래그먼트 안에 삽입될 수 있다.
• 종류
  • @include(if: Boolean) : 인자가 true인 경우에만 결과에 필드 포함
  • @skip(if: Boolean) : 인자가 true인 경우에만 이 필드 건너뜀

Mutation

• 데이터 변조 역할
• create, update, delete 수행
• 쿼리도 데이터를 수정할 수 있지만, 변조 작업은 뮤테이션을 통해 전송되어야 한다는 규칙을 지키는게 좋다!

🎃 다중 필드

• 쿼리 필드는 병렬로 실행되지만, 뮤테이션 필드는 하나씩 차례로 실행된다.

mutation CreateReviewForEpisode($ep: Episode!, $review: ReviewInput!) {
  createReview(episode: $ep, review: $review) {
    stars
    commentary
  }
}

// variables
{
  "ep": "JEDI",
  "review": {
    "stars": 5,
    "commentary": "This is a great movie!"
  }
}

// 결과 
{
  "data": {
    "createReview": {
      "stars": 5,
      "commentary": "This is a great movie!"
    }
  }
}

GraphQL

웹 클라이언트가 서버로부터 데이터를 효율적으로 가져오는 것을 목적으로 설계된 쿼리 언어.

• 데이터베이스나 플랫폼에 종속적이지 않음
• 네트워크 통신 방식에 종속적이지 않음
  • HTTP POST 메소드와 웹 소켓 프로토콜을 활용

REST API와 비교

장점

• OverFetching
  • 필요한 정보들만 들고 올 수 있음
  • 따라서 통신 리소스 감소
• UnderFetching
  • 필요한 여러 계층의 정보들을 한 번에 가져올 수 있음
  • 요청 횟수 감소
  • 필요 데이터가 쪼꼼 달라졌다고 새로운 REST API 만들지 않아도 됨..!
• 하나의 POST End-point에서 모든 요청 처리 가능
  • 힘들게 API 문서를 관리하지 않아도 됨!
• 프론트엔드 개발자와 백엔드 개발자의 결합도가 떨어짐
  • 백엔드가 모델 만들어서 GraphQL로 노출하면, 프론트엔드 개발자가 니즈에 따라 바로 활용 가능

단점

• 맵 / 테이블 / 딕셔너리 지원 X
• API 버전 관리에 대한 명확한 방법이 없음
• 디도스 공격을 방어하기 위해 직접 코드를 짜야 함
  • 리턴되는 데이터 양에 레이트 리밋 걸기, 페이지네이션 직접 구현 등

레퍼런스

• 공식문서
• 얄팍한 GraphQL & Apollo 강좌
• GraphQL은 쫌 짜증나요