본 논문은 쿠버네티스의 전신인 Borg System 논문이다.

오늘의 요약

• 즉 구글은 수 십만 개의 잡을 돌리는 클러스터 매니저인 Borg를 개발했다.
• 해당 잡 들은 수 천개의 서로 다른 애플리케이션에서 발생하는데
  • 이들이 어떻게 관리되는지 시스템 유저(서비스 개발자)는 알 필요 없이 Borg System을 만들었다.
    • 자원 관리에 대한 세부 사항 (CPU, Memory, Disk, Network 할당 등)
    • 어느 컴퓨터에서 개발된 서비스가 동작할지
    • 실패되어도 다시 살아난다. (Self Healing)
    • 실패 처리를 유저가 직접하지 않아도 된다.
• 구글은 이러한 시스템을 만들기 위해 구글이 실행하는 서비스를 두 가지로 분류했다.
  • Long Running Services
    • End User에게 제공되는 Production
      • GMail, Google Search, Google Docs, 그리고 구글 내부의 BigTable 등
    • 즉 절대 죽어서는 안되는, 수 µs ~ 몇백 ms 라는 짧은 latency를 가져 사용자에게 불편함을 주면 안되는 서비스
    • 매우 많은 리소스를 사용한다.
    • 쉽게 말해 Production Level
  • Batch Jobs
    • 짧게는 수 초, 길게는 수 일 동안 작업되는 서비스
    • 단기적 성능 변동에 훨씬 덜 민감하다.
    • 쉽게 말해 Non-Production Level
• 해당 작업을 수행하는 머신들은 Cell이라 불리는 곳에 저장된다.
  • 셀 안에 많은 머신이 포함되며, 해당 머신들은 고성능 데이터 센터 규모로 정의된 단일 클러스터에 포함된다.
    • 단일 클러스터에 속하는 머신들은
      • High Performance, Datacenter Scale Network 구조로 정의
      • 해당 클러스터는 단일 데이터센터 빌딩에 존재하고, 이러한 빌딩들의 집합이 site를 만든다.
      • 클러스터는 일반적으로 하나의 거대한 셀의 주인이고(hosts)
        • 몇 개의
          • 작은 스케일의 테스트를 갖거나
          • 특수 목적 셀을 가진다.
      • Single Point of Failure를 피한다.
    • 중간 사이즈의 셀들은
      • 테스트 셀을 제외하고 대략 1만대 이상의 머신을 가지는데, 몇 몇은 더 큰 규모를 가진다.
      • 해당 머신들은 서로 이질적인 많은 디멘션을 가지는데,
        • CPU, RAM, Network, Disk 등
        • Processor Type, Performance, 외부 IP 주소 등
  • 놀랍게도 Borg System은 이러한 차이점 및 특징을 시스템 사용자(개발자 등)에게 철저히 숨겨 개발자들이 본연의 업무(개발)에만 집중할 수 있도록 한다.

Abstract

• 구글의 Borg 시스템은 수 십만 개의 잡을 돌리는 클러스터 매니저다.
  • 해당 잡 들은 수 천 개의 서로 다른 애플리케이션으로 부터 발생하는데
  • 해당 애플리케이션은 수 만 개의 머신에서 동작한다.
• Borg 시스템은 High Utilization을 달성하는데
  • 제어 허용(admission control), 효율적인 작업 패킹, 과다 할당(over commitment to machine), 그리고 프로세스 레벨의 성능 격리를 통한 머신 공유(자원 공유)
  • 를 조합하여 사용함으로써
• Bog 시스템은 고가용성 runtime 애플리케이션을 지원한다.
  • Fault Recovery 시간을 최소화하고
  • 관련있는 실패할 가능성을 줄이는 스케줄링 정책을 수립함으로써
• Borg 시스템은 사용자의 삶을 단순화한다.
  • Declarative Job Specification Language, Name Service 통합, 실시간 작업 모니터링 및 시스템 동작을 분석하고 시뮬레이션하는 도구를 제공하여
• 우리는 Borg System의 아키텍처와 Features, 중요한 디자인 결정, Borg System의 몇몇 정책 결정에 대한 질적인 분석, 10년간의 운영 경험에서 얻은 교훈에 대한 질적 교훈을 제시한다.

1. Introduction

• Borg System이라 부르는 클러스터 관리 시스템은
  • 관리하고, 스케줄하고, 시작하고, 재시작하고, 그리고 모니터링한다.
  • 구글이 실행하는 모든 애플리케이션의 Full Range로부터
• 해당 본문은 이것이 어떻게 되는지 설명한다.
• Borg는 세 가지 주요 장점을 제공한다.
  • 자원 관리에 대한 세부 사항과 실패 처리와 관련된 세부 사항을 숨김으로써, 유저는 애플리케이션 개발에 집중할 수 있다.
  • 매우 높은 신뢰성과 가용성을 바탕으로 동작하며, Borg에서 관리되는 애플리케이션 또한 이를 제공받는다.
  • 수만 대의 시스템에서 워크로드를 효율적으로 실행할 수 있도록 한다.
• Borg는 이러한 이슈를 제기한 첫 번째 시스템이 아니다.
  • 하지만 Borg와 같이 큰 스케일, 탄력성과 완전성,에서 실행되는 것은 몇 없다.
• 해당 논문은 이러한 주제를 중심으로 구성되어 있으며
• 10년 이상 프로덕션 환경에서 Borg를 운영하면서 얻은 일련의 정성적 관찰로 결론을 내린다.

2. The User Perspective

• Borg 시스템의 유저는 구글의 개발자와 시스템 관리자(Site Reliability Engineers)다.
  • 구글의 애플리케이션과 서비스들을 실행하는
• 사용자들은 그들의 일을 Borg의 jobs 폼에 맞춰 제출한다.
  • jobs: 하나 이상의 tasks로 구성
  • tasks: 모두 동일한 바이너리 프로그램을 실행
• 각각의 job은 Borg Cell에서 실행되는데
  • Borg Cell은 하나의 유닛처럼 관리되는 머신의 집합이다.
• 본 단락에서 중요한 것은 Borg가 유저에게 어떻게 노출되느냐다.
  • 유저 관점에서 Borg를 어떻게 사용하는지

2.1 The Workload

• Borg Cells는 두 개의 이질적인 주요 파트에서 실행된다.
• 첫 번 째는, “절대로” 죽어서는 안되고, 수 µs ~ 몇백 ms 라는 짧은 latency를 가지는, Long Running Services다.
  • Gmail, Google Docs, Web Search와 같이 End User에게 제공되는 Product들, 그리고 구글 내부의 인프라 서비스(Big Table) 등이 그 예다.
• 두 번 째는, 수 초 ~ 수 일 안에 완료되는 batch jobs다.
  • 이러한 작업은 단기적인 성능 변동에 훨씬 덜 민감하다.
• 워크로드 혼합은 Borg Cell 마다 다르며
  • Borg Cell은 다양한 애플리케이션의 혼합을 실행하는데
    • 애플리케이션은 작업에 따라 다르다. (주요 테넌트에 따라 다양한 애플리케이션 혼합을 실행)
      • 예: 일부 셀은 배치 집약적임
    • 또한 실행 시간에 따라 다르다.
    • 예를 들어
      • 배치 작업은 빠른 시간 안에 실행 되었다가 종료되고
      • End User Facing(Proudcts)는 주간 사용 패턴을 보인다. (오래 사용)
• Borg 시스템은 이들 케이스 모두를 동일하게 잘 처리할 필요가 있다.
• 대표적인 Borg workload는 2011년 5월부터 월 단위 추적이 가능한데, 이는 매우 잘 광범위하게 분석되었다.
• 많은 애플리케이션 프레임워크는 Borg의 Top에서 만들어졌다.
  • Internal Map Reducing System, Flume Java, Millwhell, Pregel 등
• 이들 대부분은 컨트롤러를 가지고 있는데
  • master job 과 하나 이상의 워커 잡을 제출한다.
  • 이들은 YARN의 어플리케이션 매니저와 비슷하다.
    • https://blog.cloudera.com/apache-hadoop-yarn-concepts-and-applications/
    • https://sungsoo.github.io/2014/02/28/yarn-concepts-and-applications.html
• 구글의 분산 저장소 시스템, GFS, CFS, Bigtable, Megastore 모두 Borg에서 동작한다.
• 본 문단에서 명시하는 것은
  • workload를 두 가지로 분류 가능한데
  • production 레벨
    • Long Running Services
  • non-production 레벨
    • Batch Jobs
• 대표적인 셀에
  • production 레벨의 잡은 70% 정도의 CPU, 55%의 메모리를 할당받았으며
    • 이 중 60%, 85% 를 사용중이다.
  • 나머지를 non-production이 할당 및 사용
  • 이 실제 할당량과 사용량의 불일치는 5.5단락에서 자세하게 설명된다.

2.2 Clusters and Cells

셀의 머신은 이를 연결하는 고성능 데이터 센터 규모의 네트워크 패브릭으로 정의된 단일 클러스터에 속한다.

• 단일 클러스터에 속하는 셀의 머신들은
  • High Performance, Datacenter Scale Network 구조로 정의되는데
  • 해당 클러스터는 단일 데이터센터 빌딩에 존재하고, 이러한 빌딩들의 집합이 site를 만든다.
  • 클러스터는 일반적으로 하나의 거대한 셀의 주인이고(hosts)
    • 몇 개의
      • 작은 스케일의 테스트를 갖거나
      • 특수 목적 셀을 가진다.
  • 우리는 몇 개의 단일 실패 지점을 피한다.
• 우리의 중간 셀의 사이즈는 테스트 셀을 제외하여 대략 1만대의 머신의 크기인데
  • 몇 몇은 훨씬 더 크다.
  • 해당 머신들은 이질적인, 많은 디멘션에 속하는데
    • CPU, RAM, Disk, Network의 크기가 다르거나
    • processor type이 다르거나
    • performance가 다르거나
    • Flash Storage 혹은 외부 IP 주소 등 능력이 다르거나
• Borg 시스템은 이러한 차이점 대부분으로부터 사용자를 격리한다.(사용자는 신경쓸 필요 없다.)
  • 셀에서 작업을 실행할 위치를 결정하고
  • 리소스를 할당하고
  • 프로그램 및 기타 종속성을 설치하고
  • 상태를 모니터링하고
  • 실패할 경우 다시 시작하는 등

Problem

• 연속 펄스 부분 수열의 합

darklight

sublimevimemacs

Java

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• 100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

입출력 예

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

Description

• 솔직히 이게 3레벨이라 믿기지 않는 문제. 1레벨이면 충분할 것 같다.
• 설명에서 주어진 바와 같이 배열의 각 인덱스에 1과 -1을 번갈아가며 곱해준 것과 -1과 1을 번갈아가며 곱해준 것 중 연속 합이 큰 것을 고르면 된다.
• DP를 이용해 쉽게 풀 수 있는데, 현재 값을 더 했을 때의 최대 값과 더하지 않았을 때의 최대 값을 비교하면 된다.
• 최대 값을 저장하기 위한 1차원 DP 배열을 선언한다.
  • long[] sum = new long[length]
• 주어진 예제를 이용해 설명해 보면
  • 먼저 1, -1, 1, -1, … 을 곱한 배열은 다음과 같다.
  • [2, -3, -6, -1, 3, 1, 2, -4]
  • 여기에 대해 0번 인덱스 부터 하나씩 옮겨가며 다음과 같이 비교한다.
    • if 문의 비교연산은 다음 의미를 갖는다.
      • 이전까지의 합과 현재 합을 더했을 때, 0보다 큰가? 즉, 음수가 되지 않았는가에 대한 비교이다.
      • 만약 0 이하라면, sum[i] → 0으로 설정하여 현재 인덱스 까지의 연산을 초기화한다.
  • if(sum[i-1] + sequence[i] > 0) sum[i] = sum[i-1] + sequence[i]; else sum[i] = 0;
  • 그런 다음, answer와 현재까지의 합에 대하여 크기 비교를 수행한다.
    • if 문의 비교 연산은 다음 의미를 갖는다.
      • 이전 index까지 배열의 합이 answer보다 크다는 것은, 이전의 최대 합 보다 현재의 최대 합이 더 크다는 뜻이다. 따라서 answer을 갱신한다.
      • 그렇지 않을 경우, 이전에 찾은 answer가 최대 값이기 때문에 answer를 유지한다.
  • if(sum[i] > answer) answer = sum[i];

Result

import java.util.*;
class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        int length = sequence.length;
        long[] sum = new long[length];
        int m = 0, n = 1;

        if(length == 1){
            return Math.max(sequence[0], sequence[0] * -1);
        }

        //* [1, -1, 1, -1] ... 을 곱했을 때
        for(int i = 0; i < length; i++){
            if(i % 2 == 1){
                sequence[i] *= -1;
            }

            //* Business Logic
            if(i == 0){
                sum[i] = Math.max(sequence[i], 0);
                continue;
            }
            sum[i] = Math.max(0, sum[i-1] + sequence[i]);
            answer = Math.max(answer, sum[i]);
        }

        //* [-1, 1, -1, 1] ... 을 곱했을 때
        for(int i = 0; i < length; i++){
            sequence[i] *= -1;

            //* Business Logic
            if(i == 0){
                sum[i] = Math.max(sequence[i], 0);
                continue;
            }
            sum[i] = Math.max(0, sum[i-1] + sequence[i]);
            answer = Math.max(answer, sum[i]);
        }

        return answer;
    }
}

TDD(Test Driven Development)는 QA를 떠나 서비스를 개발할 때 필수적으로 거쳐야 한다.

NodeJS에서 TDD를 수행하기 위해 mocha와 chai를 이용할 수 있다. 이 외에도 좋은 라이브러리가 많으니, 각자 취향에 맞는 라이브러리를 사용하면 된다.

TDD를 공부하기 위해 간단한 To Do List를 함께 제작할 것이다.

Install Dependencies

npm install mocha chai chai-as-promise **--save-dev**|--global

Mocha

Mocha는 Javascript를 Test할 수 있는 하나의 프레임워크다. Mocha를 사용하여 우리가 수행할 단위 테스트 환경을 쉽고 간결하게 작성할 수 있으며 작성한 함수 등에 대하여 스펙에 맞게 테스트를 수행할 수 있다.

또한 Mocha가 제공하는 describe와 it을 이용하여 테스트에 대한 설명을 작성하고 구분지음으로써 어떤것에 대한 내용인지 확인할 수 있다.

Chai

Chai는 assertion 라이브러리로 Mocha와 함께 쓰이는 라이브러리다. Chai는 Mocha를 통해 수행한 테스트의 결과가 내가 기대한 값인지 테스트할 수 있도록 assertion을 제공한다.

특히 Chai는 사람이 이해할 수 있는 구조로 syntax가 작성되어 있기 때문에 사용하기 편하다.

우리는 chai와 chai-as-promise를 함께 사용하여 NodeJS에서 발생하는 Asynchronous Function에 대한 테스트도 수행할 것이다.

Setting Environment

이제 Mocha와 Chai를 이용한 테스트 환경을 구축하려 한다.

NodeJS상에서 ES6를 이용하여 프로젝트를 만들것이다.

NodeJS: 16.16.0
ECMAScript6
Language: Javascript ( not typescript )

mkdir todolist
cd todolist
npm install mocha chai chai-as-promised --save-dev
npm install express http fs
mkdir test route public middleware model

Mocha Chai 설치가 끝났다면, package.json 파일에 다음과 같이 굵은 내용을 추가해 준다.

{
  "name": "tdd-todolist",
  "version": "0.0.1",
  "description": "Study Test Driven Develop in NodeJS - To Do List",
  "main": "starter.js",
  **"scripts": {
    "test": "mocha test/**/**.spec.js",
        "start": "starter.js"
  },**
  "author": "eugene",
  "devDependencies": {
    "chai": "^4.3.7",
        "chai-as-promised": "^7.1.1",
    "mocha": "^10.2.0"
  },
  "dependencies": {
    "express": "^4.18.2",
    "fs": "^0.0.1-security",
    "http": "^0.0.1-security"
  },
  **"type": "module"**
}

이 때, “scripts”아래의 “test”는 test 디렉토리 아래의 모든 *.spec.js를 mocha를 통해 테스트한다. 는 뜻이다.

이를 통해 생성된 프로젝트 구조는 다음과 같다.

Simple Test

이제 간단한 테스트를 통해 환경이 잘 구축되었는지 보려한다. model/user.js, test/user.spec.js를 통해 user가 잘 동작하는지 확인해 볼 것이다.

model/user.js

user.js는 간단하게 전달받은 사용자의 이름과 비밀번호를 바탕으로 객체를 생성하고 다음과 같은 함수를 가진다.

• toObject(): User 정보를 Object 형태로 출력한다.

• promise(shouldResolve, shouldError): promise 함수를 테스트한다.

  • shouldResolve: Boolean
    • caller에게 resolve(true|false)를 반환할 것인지 설정한다.
  • shouldError: Boolean
    • caller에게 error를 반환할 것인지 설정한다.

  toObject() Method를 통해 user의 정보를 출력하는 클래스다. 여기에 추가로, Javascript의 특징인 Asynchronous Function의 테스트를 수행하는 promise(resolve, shouldError)함수가 존재한다.

export default class User {
    constructor(name, password){
        this.name = name;
        this.password = password;
    }

    toObject(){
        return {
            name: this.name,
            password: this.password
        }
    }

        promise(shouldResolve, shouldError){
        return new Promise((resolve, reject) => {
            if(shouldError){
                return reject();
            }

            if(shouldResolve){
                return resolve(true);
            }
            return resolve(false);
        })
    }
}

test/user.spec.js

user.spec.js는 위에서 생성한 model/user.js가 정상적으로 동작하는지 확인하는 Unit Test를 제공한다.

따라서 우리는 User클래스에 존재하는 toObject()함수와 promise(shouldResolve, shouldError)함수를 모두 테스트 할 것이다.

chai와 chaiAsPromised를 사용할 것이기 때문에, 다음과 같은 구문을 최상단에 작성하고, 우리가 테스트할 클래스를 가져온다.

import chai from 'chai';
import chaiAsPromised from 'chai-as-promised';
chai.use(chaiAsPromised);

const expect = chai.expect;
const assert = chai.assert;

import User from '../model/user.js';

그 다음 줄 부터 test를 수행할 내용을 작성하면 되는데, 그 모양은 다음과 같다.

• describe를 통한 Unit Test 단위 정의 예시

    describe('테스트를 수행에 대한 최상위 이름', () => {
        describe('그 다음 이름', () => {
            describe...
        });
    });

• it을 통한 테스트 수행 예시

    describe('최상위 이름', () => {
        it('함수 확인', () => {
            expect(확인할 대상).to.be.a('function')
        });
    });

이를 바탕으로 우리가 수행할 테스트 내용을 작성하면 다음과 같다.

먼저 User class를 정상적으로 사용할 수 있는지 expect().to.be.a('function')과 expect().to.be.a.instanceOf(Parent)를 통해 확인한다.

describe('"Up"', () => {
    it('should be exist', () => {
        expect(User).to.be.a('function');
    });

    it('should be a class', () => {
        const user = new User();
        expect(user).to.be.a.instanceOf(User);
    });
});

다음으로, User class 내에 모든 Method가 정상적으로 동작하는지 확인한다. 이 때, 우리는 async 함수를 따로 갖고 있으므로 synchronous와 asynchronous를 구분해서 수행하겠다.

const user = new User('eugene', 'password');
/* Synchronous 함수 */
describe('"Synchronous"', () => {
/* toObject() 함수를 통해 user의 이름과 비밀번호가 잘 설정되는지 확인한다. */
    it('toObject()', () => {
        const obj = user.toObject();
        expect(obj.name).to.be.equal('eugene');
        expect(obj.password).to.be.equal('password');
    })
});

/* Asynchronous 함수 */
describe('"Asynchronous"', () => {
    const promise = user.promise;
/* promise함수가 정말 promise 함수인가? */
    it('"promise" is promise function', () => {
        const _promise = promise();
        expect(_promise.then).to.be.a('Function');
        expect(_promise.catch).to.be.a('Function');
    })
/* promise함수에서 내가 설정한 인자를 전달하면, 그 결과가 예상대로 반환되는가 */
    it('"promise()" should be resolved', async () => {
        promise( true ).then(
            (data) => expect(data).to.be.a.true,
            (error) => expect(error).to.be.a.false
        );
    })
/* promise함수에서 내가 설정한 인자를 전달하면, 그 결과가 예상대로 반환되는가 */
    it('"promise()" should be a false', async () => {
        promise( false ).then(
            (data) => expect(data).to.be.a.true,
            (error) => expect(error).to.be.a.false
        );
    })
/* promise함수에서 내가 의도한 에러가 잘 발생하는가 */
    it('"promise()" should be a error', () => {
        expect(promise( false, true )).to.be.rejectedWith(Error);
    })
});

이 내용들을 모두 포함하면, test/user.spec.js가 완성된다.

import chai from 'chai';
import chaiAsPromised from 'chai-as-promised';
chai.use(chaiAsPromised);

import User from '../model/user.js';

const expect = chai.expect;
const assert = chai.assert;

describe('User module', () => {
    describe('"Up"', () => {
        it('should be exist', () => {
            expect(User).to.be.a('function');
        });

        it('should be a class', () => {
            const user = new User();
            expect(user).to.be.a.instanceOf(User);
        });
    });

    describe('"Method Check"', () => {
        const user = new User('eugene', 'password');
        describe('"Synchronous"', () => {
            it('toObject()', () => {
                const obj = user.toObject();
                expect(obj.name).to.be.equal('eugene');
                expect(obj.password).to.be.equal('password');
            })
        });

        describe('"Asynchronous"', () => {
            const promise = user.promise;
            it('"promise" is promise function', () => {
                const _promise = promise();
                expect(_promise.then).to.be.a('Function');
                expect(_promise.catch).to.be.a('Function');
            })

            it('"promise()" should be resolved', async () => {
                promise( true ).then(
                    (data) => expect(data).to.be.a.true,
                    (error) => expect(error).to.be.a.false
                );
            })

            it('"promise()" should be a false', async () => {
                promise( false ).then(
                    (data) => expect(data).to.be.a.true,
                    (error) => expect(error).to.be.a.false
                );
            })

            it('"promise()" should be a error', () => {
                expect(promise( false, true )).to.be.rejectedWith(Error);
            })
        });
    });
});

Mocha를 통한 test 수행

이제 작성한 test/user.spec.js가 잘 되는지 확인하면 된다. 명령어는 우리가 package-.json에 작성해 놓은대로, npm test명령어를 통해 수행할 수 있다.

npm test

만약 결과가 내 예상(user.spec.js에 기술한 것)과 다르다면, 다음과 같이 테스트에 실패한 부분에서 에러가 발생한다.

이렇게 오늘 TDD를 위한 기초에 대해 공부해봤다. 다음 장 에서는 todolist 개발을 함께하면서 어떻게 TDD를 해야하는지 배워보겠다.