Chapter 5 작은 것으로 큰 성과 이루기, 캐시

[chapakook]

Chapter Ownership @simbokyung98

[simbokyung98]

캐시, 어디에나 존재하는 것

폰노이만 구조는 cpu가 실행하는 기계 명령어와 명령어가 처리하는 데이터가 모두 메모리에 저장되어 있어야 한다는 사실을 알려줍니다. 하지만 레지스터 용량은 극히 제한되어 있어 cpu는 반드시 빈번하게 메모리에 집근하여 명령어와 데이터를 가져와야 합니다. 또 명령여의 실행 결과도 메모리에 다시 기록해야합니다.
=> cpu와 메모리 속도가 서로 잘 맞는지 확인하는 것 핵심

cpu는 메모리를 기다려요

• 속도가 미친듯이 빠른 cpu는 명령어를 실행할 때 어쩔 수 없이 느린 메모리를 기다리고 있을 수 밖에 없음.
• 메모리 속도는 cpu의 100분의 1

cpu와 메모리 사이의 속도 불일치를 해결하고싶어지다

• 최신 cpu는 메모리 사이에 캐시 계층을 추가하여 속도 불일치를 해결한다.

• 캐시 안에는 최근에 메모리에서 얻은 데이터가 저장되며, cpu는 메모리에서 명령어와 데이터를 꺼내야 할 때도 무조건 먼저 캐시에서 해당 내용을 찾음.

• 캐시가 적중하면 메모리에 접근할 필요 없이 cpu가 명령어를 실행하는 속도를 크게 끌어올리는 목적을 달성!

• 3단계 캐시

  • L1캐시 : 레지스터 접근 속도에 비해 약간 느리지만 거의 대동소이. 대략 4클럭
  • L2캐시 : 접근속도는 10클럭 주기
  • L3캐시 : 접근속도는 50클럭 주기 소요
  • 캐시 단계에 따라 접근 속도는 낮아지지만 용량은 증가함
  • 3단계 캐시와 cpu 코어는 레지스터 칩 내에 묶여 패키징 되어 있음.
  • cpu는 메모리에 접근할 필요가 있을때 L1 -> L2 -> L3 -> 메모리 순서로 접근

캐시 친화적인 프로그램 작성

• 캐시 친화적이다 = 캐시 적중률이 좋다

프로그램 지역성의 원칙(locality of reference or principle of locality)

• 프로그램이 매우 규칙적으로 메모리에 접근
  • 시간의 지역성
    • 프로그램이 메모리 조각에 접근하고 나서 이 조각을 여러 번 참조하는 경우
    • 데이터가 캐시에 있는 한 메모리에 접군하지 않아도 반복적으로 캐시 적중이 가능하여 캐시 친화적
  • 공간의 지역성
    • 프로그램이 메모리 조각을 참조할 때 인접한 메모리도 참조하는 경우
    • 일반적으로 인접 데이터도 함께 캐시에 저장됨.

메모리 풀 이용

• 프로그램이 메모리에 조각을 n개 할당 받아야 할 경우 malloc을 사용하여 할당받으면 메모리 조각 n개가 힙 영역의 이곳저곳 흩어져 있을 가능성 발생

  • 해결 -> 메모리 풀

    • 커다란 메모리 조각을 미리 할당받으며, 이후에는 메모리를 요청하거나 해제할 때 malloc을 거치치 않는 것

    궁금증 : 메모리 풀이 뭐지?

    • 왜 필요할까?

• 작은 메모리를 계속 할당하고 해제하면 힙 메모리에 빈 공간이 여기저기 생겨 단편화가 발생할 수 있음
• 그러면 전체 빈 메모리 양은 충분해도, 큰 객체 하나를 담을 연속 공간이 부족해질 수 있음
• 어떻게 해결할까?

• 메모리 풀은 큰 메모리 공간을 먼저 확보해 두고, 그 안을 잘라서 재사용하는 방식
• 사용이 끝난 메모리는 운영체제에 바로 돌려주기보다 풀에 반납했다가 다시 사용함
• 메모리 풀 을 초기화 할때 일반적으로 연속된 메모리 공간을 할당 받음
• 장점은?
  • 메모리 단편화를 완화하는 데 도움이 됨
  • malloc/free를 자주 반복할 때 드는 비용을 줄일 수 있음

struct 구조체 재배치(왜 갑자기?)

• 공간의 지역성 원리로 구조체의 형태를 최적화 하는 방법
  (하나의 캐시 친화적 코드 예시이므로 생략)

캐시가 만드는 문제

캐시 갱신

• 불일치 문제

  • 캐시의 데이터는 갱신되었지만 메모리의 데이터는 아직 예전 것이 남아 있는 문제.

• 문제 해결 방법

  • 연속기입(write-through)
    • 캐시를 갱신할 때 메모리도 함께 갱신하는것
    • cpu는 메모리가 갱신될 때 까지 대기하고 있어야함 -> 동기실 설계 방법(2.6절)
  • 후기입(write-back)
    • 캐시 용량이 한계일 때 자주 사용되지 않는 데이터를 제거하는데, 이때 캐시에서 제거된 데이터가 수정된 적이 있다면 메모리에 갱신.
    • 연속기입 보다 복잡하지만 성능 향상 -> 비동기적 설계 방법

다중 코어 캐시의 일관성

• 다중코어시대 시작

  • cpu 성능 향상을 위해 숫자를 늘리기 시작하여 다중 코어 시대 진입
  • 다중 코어를 최대한 활용하는 다중 스레드 또는 다중 프로세스가 없다면 다중 코어의 위력을 충분히 활용할 수 없음

• 다중코어로 인한 문제 발생

  • 캐시 한개에서 갱신된 변수가 다른 cpu 코어 캐시에도 존재한다면 이 캐시도 함께 갱신되어야함.
  • MESI규칙
    • cpu의 고전적인 다중코어 캐시 일관성 유지 규칙
    • Modified(수정), exclusive(배타), shared(공유), invalid(무효)

궁금증 : MESI 규칙이 뭐지?

• 왜 필요할까?
  • 여러 코어가 같은 데이터를 각자 캐시에 저장할 수 있기 때문
  • 이때 한 코어가 값을 바꾸면 다른 코어 캐시의 값은 오래된 값이 될 수 있음
• 어떤 상태일까?
  • Modified : 수정된 상태, 메모리보다 캐시 값이 최신인 상태
  • Exclusive : 한 코어만 가지고 있지만 수정되지는 않은 상태
  • Shared : 여러 코어가 함께 가지고 있는 상태
  • Invalid : 더 이상 유효하지 않은 상태
• 어떻게 쓰일까?
  • 코어가 데이터를 읽고 쓸 때, 캐시는 각 데이터의 상태를 바꾸며 일관성을 유지함
  • 한 코어가 데이터를 수정하면 다른 코어 캐시에 있는 같은 데이터는 무효화될 수 있음
  • 이후 다른 코어가 그 데이터를 다시 읽으려면 최신 값을 다시 가져와야 함
• 예시
  • 코어1과 코어2가 모두 x를 읽는다
    -> 둘 다 Shared
  • 코어1이 x를 수정한다
    -> Shared 상태에서는 바로 수정할 수 없으므로, 먼저 코어2의 x를 Invalid로 바꿔 공유 상태를 깸
    -> 코어2의 x는 Invalid
    -> 코어1의 x는 Modified
  • 코어2가 x를 다시 읽는다
    -> 자기 캐시 값을 그대로 못 쓰고 최신 값을 다시 가져와야 함
    -> 이때 하드웨어는 각 캐시가 같은 데이터에 대해 어떤 상태를 가지고 있는지 확인함
    -> 코어1의 x가 Modified 상태이므로, 코어1 캐시의 값이 메모리보다 최신이라고 판단함
    -> 그래서 코어2는 자기 캐시에 남아 있는 오래된 값을 쓰지 않고, 코어1 쪽의 최신 값을 다시 받아와야 함

다중 스레드 성능 방해자

캐시 라인

• 프로그램이 어떤 데이터에 접근하면 다음에는 인접한 데이터에 접근할 가능성이 높으므로 접근해야할 데이터가 있는 곳의 묶음 데이터를 캐시에 저장함
• 이 묶음 데이터가 "캐시라인"
• 일반적으로 64바이트

캐시 튕김

• 첫번째 코드

  atomic<int> a;
  
  void threadf(){
    for (int i=0; i < 500000000; i++){
      ++a;
    }
  }
  
  void run(){
    thread t1 = thread(threadf);
    thread t2 = thread(threadf);
  
    t1.join();
    t2.join();
  }
  

• 두번째 코드

  atomic<int> a;
  
  void run(){
  
    for (int i=0; i < 500000000; i++){
      ++a;
    }
  }
  

  • 두가지 코드를 실행해보면 병렬로 처리한 첫번째 보다 단일 스레드로 처리한 두번째가 더빠름
    • 캐시의 일관성을 보장하기 위하여 두 코어 는 끊임 없이 서로 상대의 캐시를 무효화 시키기 때문

거짓 공유

• 첫번째 코드

  struch data{
    int a;
    int b;
  }
  
  struct data global_data;
  
  void add_a(){
    for (int i=0; i < 500000000; i++){
      ++global_data.a;
    }
  }
  
    void add_b(){
    for (int i=0; i < 500000000; i++){
      ++global_data.b;
    }
  }
  
  void run(){
    thread t1 = thread(add_a);
    thread t2 = thread(add_b);
  
    t1.join();
    t2.join();
  }
  

• 두번째 코드

  struch data{
    int a;
    int b;
  }
  
  struct data global_data;
  
  void run(){
    for (int i=0; i < 500000000; i++){
      ++global_data.a;
    }
  
    for (int i=0; i < 500000000; i++){
      ++global_data.b;
    }
  }
  

  • 스레드 두개가 어떤 데이터도 공유하지 않는것처럼 보이더라도 캐시 동작 방식에 따라 캐시 라인을 공유 하는 경우
  • 해결방법
    • 두 변수 사이에 사용되지 않는 데이터 채우기(캐시 라인 크기 만큼)

메모리 장벽

• 원래 cpu는 반드시 엄격하게 프로그래머가 코드를 작성한 순서대로 기계 명령어를 실행하지 않음.

  • 이유 -> 성능 향상을 위해 비순차적으로 아래 명령어를 실행함
    • 기계 명령어를 생성하는 단계 : 컴파일 중에 명령어를 재정렬
    • cpu가 명령ㅇ어를 실행하는 단계 : 실행 중 명령어가 비순차적으로 실행됨

• 컴파일러의 수작

  • 컴파일러가 코드를 cpu가 실행할 수 있는 기계 명령어로 변환하면서 수작을 부릴 수 있음

    int a;
    int b;
  
    void main(){
      a = b+100;
      b= 200;
    }
  

  • 해당 코드를 기계명령어 변환시 컴파일러 코드 최적화를 하게 되면 명령어를 재정렬시킬 수 있음.

      mov  Ox200b54(%rip) , %eax # $eax = b
      add  $0x64, %eax.          # %eax = %eax + 100
      mov  %eax, 0x200b4f(%rip)  #
      movl $0xc8, 0x200b4f(%rip) # b = 200
    

      mov  Ox200b54(%rip) , %eax # $eax = b
      movl $0xc8, 0x200b4f(%rip) # b = 200
      add  $0x64, %eax.          # %eax = %eax + 100
      mov  %eax, 0x200b4f(%rip)  #
    

    • 수작에도 오류가 발생하지 않는 이유는 eax레지스터가 b변수의 초기값인 100을 저장하기 때문

  • 컴파일러는 명령어를 실행할 때도 수작을 부림

    • 비 순차적 명령어 처리(Out of Order Excution, OoOE)
      • cpu 와 메모리 사이의 속도 차이가 있어 cpu가 기계 명령어를 엄격한 순서대로 실행하면 명령어가 의존하는 피연산자를 기다리는 동안 파이프라인 내부에 빈 공간인 슬롯이 생김
      • 이때 이미 준비 완료된 다른 명령어로 이 빈공간을 메꿔 명령어 실행속도를 향상시킴
      • 실행 결과는 명령어가 순서대로 실행된 것과 같은 결과를 얻을 수 있음

• 단일 스레드는 근본적으로 비순차적 실행을 신경 쓸 필요 없음

캐시 개념의 확장

디스크도 캐시가 필요하다

• 디스크의 탐색 속도는 10ms
• 메모리 접근 속도는 디스크 탐색 속도보다 10만배 가량 빠름
• 최신 운영 체제는 해당 이슈 해결을 위해 메모리를 디스크 캐시에 사용
  • 운영체지는 디스크에서 데이터를 읽어 오는 일을 최소화 함

• 메모리를 캐시로 쓰기 때문에 시스템이 충돌하거나 정전 같은 이슈 발생 시 데이터 유실 방지를 위하여 대부분 입출력 라이브러리가 동기화(sync) 또는 캐시 비우기(flush) 함수를 제공
• 최근 메모리가 점점 저렴해지면서 메모리가 디스크를 대체하는 것이 대세

궁금증 : 리눅스는 페이지 캐시로 디스크 읽기를 어떻게 줄일까?

• 리눅스는 디스크에서 읽어 온 파일 데이터를 바로 버리지 않고 메모리에 잠시 저장해 둠

• 이후 같은 파일이나 같은 부분을 다시 읽으려고 하면, 먼저 메모리에 이미 올라와 있는 데이터를 확인함

• 페이지 캐시에 데이터가 있으면 디스크까지 다시 가지 않고 메모리에서 바로 가져올 수 있음

• 디스크는 메모리보다 훨씬 느리기 때문에, 이런 방식은 반복적인 파일 읽기에서 성능을 크게 높여 줌

• 왜 이름이 페이지 캐시일까?

  • 운영체제는 메모리를 페이지(page) 단위로 관리함
  • 페이지는 운영체제가 메모리를 다룰 때 사용하는 일정한 크기의 블록임
  • 디스크에서 읽은 파일 데이터도 이런 페이지 단위의 메모리 공간에 올라가므로 페이지 캐시라고 부름

가상메모리와 디스크

• 시스템에서 프로세스가 N개 있을 때, 이 프로세스 N개가 실제 물리 메모리를 모두 사용하고 있는 경우, 새로운 프로세스가 생성되어 이 N+1 번째 프로세스가 메모리를 요청하면?
  • 일부 프로세스에서 자주 사용하지 않는 메모리 데이터를 디스크에 기록하고 이 데이터가 차지하던 물리 메모리 공간을 해제
  • 디스크가 메모리 일부 작업을 넘겨받기에 모든 프로세스가 요청하는 메모리 크기는 물리 메모리를 넘어설 수 있음.
  • 그러므로 디스크 입출력을 하지 않고 있더라도, 메모리 사용률이 높을 경우 cpu가 디스크에 접근해야할 수 있음.

대용량 데이터를 저장하기 위한 분산 파일 시스템

• 5-14 그림추가
• 원격 분산 파일 시스템의 데이터를 데이터 흐름 형태로 직접 로컬 컴퓨터 시스템에 메모리로 끌어올 수 있음
• 메세지 미들웨어인 아파지 카프카(apach kafka) 시스템의 경우 대용량 메세지는 원격 분산 파일 시스템에 저장되어 있지만 실시간으로 해당 데이터의 소비자에게 전달됨
  • 메모리를 원격 분산 시스템에 캐시로 볼 수 있음

궁금증 : 카프카에서 대용량 메세지가 실시간으로 전달되는 구조

• 원격 분산 파일 시스템과의 관련

  • 원격 분산 파일 시스템의 데이터를 흐름 형태로 로컬 시스템 메모리로 가져와 처리할 수 있음
  • 그래서 대용량 데이터를 원격에 저장해 두더라도 필요한 만큼 계속 읽어 오며 처리할 수 있음

• 카프카에서 더 중요한 점

  • 카프카는 메세지를 로그 형태로 순차적으로 저장함
  • 컨슈머는 offset 기준으로 필요한 위치부터 순차적으로 읽음
  • 페이지 캐시를 활용해 디스크 접근 비용을 줄일 수 있음
  • 배치 처리로 입출력 비용도 줄일 수 있음

• 정리

  • 원격 데이터를 흐름처럼 가져와 처리할 수 있다는 점과 관련 있음
  • 하지만 카프카는 순차 로그 구조, offset 기반 읽기, 페이지 캐시 활용 때문에 더 빠르게 동작함