Skip List

Skip List Skip List는 정렬된 연결 리스트를 기반으로 하여 빠른 검색, 삽입, 삭제 연산을 지원하는 확률적 데이터 구조이다. Skip List는 여러 레벨의 연결 리스트로 구성된 데이터 구조로, 각 레벨은 그 아래 레벨의 일부 요소를 포함하며, 최하위 레벨은 모든 요소를 포함한다. https://en.wikipedia.org/wiki/Skip_list#/media/File:Skip_list.svg 특징 다중 레벨 구조: 여러 층의 연결 리스트로 구성된다. 확률적 균형: 랜덤화를 통해 구조의 균형을 유지한다. 정렬 상태 유지: 요소들은 정렬된 순서로 유지된다. 장점 빠른 검색: 평균 O(log n) 시간 복잡도로 검색이 가능하다. 효율적인 삽입/삭제: 평균 O(log n) 시간에 삽입과 삭제가 가능하다. 구현의 단순성: 균형 이진 탐색 트리에 비해 구현이 간단하다. 단점 추가 메모리 사용: 여러 레벨의 포인터로 인해 추가 메모리가 필요하다. 확률적 성능: 최악의 경우 O(n) 시간 복잡도가 발생할 수 있다. 응용 데이터베이스 인덱싱: RocksDB와 같은 키-값 저장소에서 사용된다. 메모리 관리: 비휘발성 메모리 최적화에 활용된다. 캐시 구현: 효율적인 캐시 시스템 구축에 사용된다. 동작 원리 검색: 최상위 레벨에서 시작하여 목표 값보다 작은 노드를 따라 이동하고, 큰 값을 만나면 아래 레벨로 내려간다. 삽입: 랜덤하게 레벨을 결정하고, 해당 레벨까지 노드를 생성하여 연결한다. 삭제: 노드를 찾아 모든 레벨에서 제거한다. 구성 요소 노드: 키, 값, 여러 레벨의 다음 노드 포인터를 포함한다. 헤드 노드: 모든 레벨의 시작점 역할을 한다. 레벨: 여러 층의 연결 리스트 구조를 형성한다. 구현 방식 JavaScript를 사용한 Skip List 구현 예시: ...

October 8, 2024 · 4 min · Me

데커 알고리즘 (Dekker's Algorithm)

데커 알고리즘 (Dekker’s Algorithm) 데커 알고리즘(Dekker’s Algorithm)은 두 프로세스 간 **상호 배제(Mutual Exclusion)**를 보장하기 위해 1965년 네덜란드의 수학자 Theodorus Dekker가 개발한 최초의 소프트웨어 상호 배제(mutual exclusion) 알고리즘이다. 이 알고리즘은 두 개의 프로세스가 공유 자원에 동시에 접근하는 것을 방지하여 경쟁 상태(race condition)를 해결하는 방법을 제시한다. 공유 자원에 대한 안전한 접근을 위해 **플래그(flag)**와 턴(turn) 변수를 활용하며, 하드웨어적 명령어 없이 소프트웨어만으로 구현 가능하다. 데커 알고리즘은 상호 배제 문제 해결의 역사적 중요성을 가지지만, 현대 시스템에서는 **세마포어(Semaphore)**나 **뮤텍스(Mutex)**와 같은 더 효율적인 동기화 기법이 주로 사용된다. ...

October 3, 2024 · 3 min · Me

램포트의 빵집 알고리즘 (Lamport's Bakery Algorithm)

램포트의 빵집 알고리즘 (Lamport’s Bakery Algorithm) 램포트의 빵집 알고리즘(Lamport’s Bakery Algorithm)은 N개 프로세스의 상호 배제(Mutual Exclusion) 문제를 해결하기 위한 소프트웨어 기반 알고리즘이다. 1974년 레슬리 램포트(Leslie Lamport)가 제안했으며, 빵집에서 번호표를 받아 순서대로 서비스받는 방식에서 아이디어를 얻었다. 램포트의 빵집 알고리즘은 병행 프로그래밍의 이론적 토대를 제공했지만, 현대 시스템에서는 주로 하드웨어 지원 동기화 기법이 사용된다. 단, 분산 시스템이나 임베디드 환경에서는 여전히 연구 및 적용 사례가 존재한다. 핵심 원리 번호표 시스템 각 프로세스는 임계 영역 진입 전 고유한 번호표를 받는다. 번호표는 단조 증가(monotonically increasing) 방식으로 발급되며, 동시 접근 시 프로세스 ID로 우선순위 결정한다. 단조 증가(monotonically increasing)란 함수나 수열이 항상 증가하거나 일정한 값을 유지하는 성질을 의미한다. 즉, 감소하는 구간 없이 유지되거나 증가하는 경우를 말한다. ...

October 3, 2024 · 3 min · Me

피터슨 알고리즘 (Peterson's Algorithm)

피터슨 알고리즘 (Peterson’s Algorithm) 피터슨 알고리즘(Peterson’s Algorithm)은 두 프로세스의 **상호 배제(Mutual Exclusion)**를 보장하기 위한 소프트웨어 기반 동기화 알고리즘이다. 1981년 개리 피터슨(Gary L. Peterson)이 제안한 이 알고리즘은 간결성과 이론적 엄밀성으로 운영체제 및 병행 프로그래밍 분야에서 널리 연구된다. 피터슨 알고리즘은 이론적 완결성을 인정받지만, 현대 시스템에서는 주로 하드웨어 기반 동기화 기법(예: TAS, CAS)이 사용됩니다. 그러나 병행 프로그래밍의 근본 원리를 이해하는 데 여전히 핵심적인 역할을 한다. 핵심 구성 요소 플래그 배열(flag) 각 프로세스의 임계 영역 진입 의사 표시 (flag, flag 초기값 False) 턴 변수(turn) 임계 영역 진입 순서 결정 (0 또는 1 값을 가짐) 동작 원리 진입 의사 표시: 프로세스 i가 임계 영역 진입 전 flag[i] = True 설정. ...

October 3, 2024 · 3 min · Me

CI/CD Principles

CI/CD Principles CI/CD 원칙은 지속적 통합 (CI) 과 지속적 배포 (CD) 를 기반으로 코드 변경 사항을 빠르게 통합, 테스트, 배포하는 자동화된 프로세스를 강조한다. CI/CD 는 DevOps 문화의 중심에 있으며, 개발팀이 더 자주, 더 안정적으로 코드를 통합하고 배포할 수 있게 해준다. 핵심 개념 CI/CD 는 두 가지 연관된 개념의 조합이다: 지속적 통합 (Continuous Integration, CI): 개발자들이 코드 변경사항을 중앙 리포지토리에 자주 통합하는 개발 방식으로, 보통 하루에 여러 번 이루어진다. 각 통합은 자동화된 빌드와 테스트로 검증되어 통합 문제를 빠르게 식별한다. ...

October 2, 2024 · 31 min · Me

Gitlab CI

Gitlab CI .gitlab-ci.yml 구조 Stage/Job 구성 및 GitLab Pages 활용 Multi-Project 파이프라인 Auto DevOps 설정 Kubernetes 배포 자동화 GitLab에 내장된 지속적 통합/배포 도구로, .gitlab-ci.yml 파일을 통해 파이프라인을 정의하고 관리 특징 통합성: GitLab 저장소와 긴밀하게 통합되어 있어 별도의 도구 없이 CI/CD 파이프라인을 구축할 수 있습니다. 유연성: YAML 파일을 통해 파이프라인을 구성할 수 있어 다양한 프로젝트 요구사항에 맞춤 설정이 가능합니다. 확장성: 다양한 Runner 유형을 지원하여 다양한 환경에서 작업을 실행할 수 있습니다. 가시성: 파이프라인 실행 상태와 결과를 GitLab 인터페이스에서 쉽게 확인할 수 있습니다. 기능 자동 빌드 및 테스트: 코드 변경 시 자동으로 빌드 및 테스트를 실행합니다. 환경 배포: 다양한 환경(개발, 스테이징, 프로덕션 등)에 자동으로 배포할 수 있습니다. 아티팩트 관리: 빌드 결과물을 저장하고 관리할 수 있습니다. 병렬 실행: 여러 작업을 동시에 실행하여 파이프라인 속도를 향상시킵니다. 환경 변수 관리: 민감한 정보를 안전하게 저장하고 사용할 수 있습니다. 구성요소 .gitlab-ci.yml: 파이프라인 구성 파일 Runners: 작업을 실행하는 에이전트 Jobs: 실행할 개별 작업 Stages: 작업의 실행 순서를 정의하는 단계 Pipeline: 전체 CI/CD 프로세스 장점 GitLab과의 긴밀한 통합 쉬운 설정과 사용 확장성과 유연성 무료로 사용 가능한 기능이 많음 단점 GitLab에 종속적 복잡한 워크플로우의 경우 설정이 복잡해질 수 있음 일부 고급 기능은 유료 버전에서만 사용 가능 설정 방법 프로젝트 루트에.gitlab-ci.yml 파일 생성 YAML 형식으로 파이프라인 구성 작성 변경사항을 커밋하고 푸시 GitLab에서 파이프라인 실행 확인 .gitlab-ci.yml 파일의 기본 구조 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 stages: - build - test - deploy job1: stage: build script: - echo "Building the project..." job2: stage: test script: - echo "Running tests..." job3: stage: deploy script: - echo "Deploying to production..." 주요 구성 요소 stages: 파이프라인의 실행 단계를 정의합니다. 각 단계는 순차적으로 실행됩니다. jobs: 각 작업을 정의합니다. 작업은 특정 단계에 속하며, 실행할 스크립트를 포함합니다. script: 작업에서 실행할 명령어들을 정의합니다. image: 작업을 실행할 Docker 이미지를 지정합니다. artifacts: 작업 결과물을 저장하고 다른 작업에서 사용할 수 있게 합니다. cache: 작업 간에 공유할 파일이나 디렉토리를 지정합니다. 고급 구성 옵션 only/except: 특정 브랜치나 태그에서만 작업을 실행하거나 제외할 수 있습니다. variables: 파이프라인 전체 또는 특정 작업에서 사용할 변수를 정의합니다. before_script/after_script: 작업 실행 전후에 실행할 스크립트를 정의합니다. environment: 배포 환경을 지정합니다. 예시 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 # 파이프라인 단계 정의 stages: - build - test - deploy # 캐시 설정: node_modules 폴더를 캐시하여 빌드 속도 향상 cache: paths: - node_modules/ # 빌드 작업 정의 build: stage: build image: node:14 # Node.js 14 버전 이미지 사용 script: - npm install # 의존성 설치 - npm run build # 프로젝트 빌드 artifacts: paths: - dist/ # 빌드 결과물 저장 # 테스트 작업 정의 test: stage: test image: node:14 script: - npm install # 의존성 설치 - npm test # 테스트 실행 # 배포 작업 정의 deploy: stage: deploy image: alpine:latest script: - apk add --no-cache rsync openssh # 배포에 필요한 도구 설치 - mkdir -p ~/.ssh - echo "$SSH_PRIVATE_KEY" | tr -d '\r' > ~/.ssh/id_rsa - chmod 600 ~/.ssh/id_rsa - ssh-keyscan -H $DEPLOY_SERVER_IP >> ~/.ssh/known_hosts - rsync -avz --delete dist/ $DEPLOY_USER@$DEPLOY_SERVER_IP:/path/to/deployment/ only: - master # master 브랜치에 푸시될 때만 실행 stages: 파이프라인의 단계를 정의합니다. 여기서는 build, test, deploy 세 단계로 구성됩니다. cache: node_modules 폴더를 캐시하여 빌드 속도를 향상시킵니다. build 작업: stage: build로 빌드 단계에 할당합니다. Node.js 14 버전 이미지를 사용합니다. npm install로 의존성을 설치하고, npm run build로 프로젝트를 빌드합니다. artifacts를 사용하여 빌드 결과물을 저장합니다. test 작업: stage: test로 테스트 단계에 할당합니다. npm test 명령으로 테스트를 실행합니다. deploy 작업: stage: deploy로 배포 단계에 할당합니다. Alpine Linux 이미지를 사용하여 가벼운 환경을 구성합니다. SSH 키를 설정하고 rsync를 사용하여 빌드 결과물을 서버에 배포합니다. only: - master로 master 브랜치에 푸시될 때만 실행되도록 설정합니다. 기본 설정 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 # GitLab CI의 기본 설정 예시 image: node:16 # 기본 Docker 이미지 지정 # 파이프라인 스테이지 정의 stages: - build - test - deploy # 캐시 설정 - node_modules 디렉토리를 캐시 cache: paths: - node_modules/ # 빌드 작업 정의 build: stage: build # 속한 스테이지 지정 script: - npm install # 의존성 설치 - npm run build # 빌드 실행 artifacts: # 빌드 결과물 저장 paths: - dist/ # 테스트 작업 정의 test: stage: test script: - npm run test # 테스트 실행 dependencies: # build 작업의 결과물 사용 - build # 배포 작업 정의 deploy: stage: deploy script: - echo "Deploying application…" - npm run deploy only: # main 브랜치에서만 실행 - main 고급 설정 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 # 환경변수와 조건부 실행이 포함된 고급 설정 예시 variables: DOCKER_IMAGE: $CI_REGISTRY_IMAGE:$CI_COMMIT_REF_SLUG # Docker 이미지 태그 정의 # 커스텀 도커 이미지 빌드 build_image: image: docker:20.10.16 services: - docker:20.10.16-dind # Docker-in-Docker 서비스 stage: build script: # Docker 레지스트리 로그인 - docker login -u $CI_REGISTRY_USER -p $CI_REGISTRY_PASSWORD $CI_REGISTRY # Docker 이미지 빌드 및 푸시 - docker build -t $DOCKER_IMAGE . - docker push $DOCKER_IMAGE rules: - if: $CI_COMMIT_BRANCH == "main" # main 브랜치에서만 실행 when: always - when: never # 그 외의 경우 실행하지 않음 # 보안 스캔 작업 security_scan: image: security-scanner stage: test script: - scan-dependencies # 의존성 취약점 검사 - scan-code # 코드 보안 검사 allow_failure: true # 실패해도 파이프라인 계속 진행 # 스테이징 환경 배포 deploy_staging: stage: deploy environment: name: staging script: - deploy-to-kubernetes.sh --env staging rules: - if: $CI_COMMIT_BRANCH == "develop" 환경별 배포 설정 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 # 환경별 배포 구성 예시 .deploy_template: &deploy_template # 재사용 가능한 배포 템플릿 정의 script: - echo "Deploying to $CI_ENVIRONMENT_NAME" - kubectl apply -f k8s/$CI_ENVIRONMENT_NAME/ deploy_dev: <<: *deploy_template # 템플릿 상속 environment: name: development rules: - if: $CI_COMMIT_BRANCH == "develop" deploy_prod: <<: *deploy_template environment: name: production rules: - if: $CI_COMMIT_BRANCH == "main" when: manual # 수동 승인 후 배포 병렬 작업 실행 1 2 3 4 5 6 7 8 9 10 11 12 13 14 # 병렬 테스트 실행 예시 test: parallel: 3 # 3개의 병렬 작업 생성 script: - npm run test -- --split=$CI_NODE_INDEX/$CI_NODE_TOTAL # 매트릭스 작업 정의 test_matrix: parallel: matrix: - NODE_VERSION: ["14", "16", "18"] DB_TYPE: ["mysql", "postgres"] script: - docker-compose run --rm -e NODE_VERSION=$NODE_VERSION -e DB_TYPE=$DB_TYPE test 캐시와 아티팩트 관리 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 # 캐시와 아티팩트 관리 예시 build: cache: key: ${CI_COMMIT_REF_SLUG} # 브랜치별 캐시 키 paths: - node_modules/ - .npm/ policy: pull-push # 캐시 정책 설정 artifacts: paths: - dist/ # 빌드 결과물 - coverage/ # 테스트 커버리지 리포트 reports: junit: test-results.xml # 테스트 결과 리포트 coverage: coverage/lcov.info # 커버리지 리포트 expire_in: 1 week # 아티팩트 유효 기간 이러한 설정들은 프로젝트의 요구사항과 규모에 따라 적절히 조정하여 사용할 수 있습니다. ...

October 2, 2024 · 6 min · Me

CI vs. CD vs. CD

CI(지속적 통합) Vs. CD(지속적 전달) vs. CD(지속적 배포) CI/CD 는 현대 소프트웨어 개발 방법론의 핵심으로, 개발 과정을 자동화하고 신속하게 가치를 전달하는 데 중점을 둔다. 지속적 통합 (CI) 은 개발자가 코드 변경 사항을 자주 통합하고 검증하는 과정을 말하며, 지속적 전달 (CD) 은 검증된 코드를 자동으로 프로덕션 환경에 배포 가능한 상태로 준비하는 과정을, 지속적 배포 (CD) 는 검증된 코드를 자동으로 프로덕션 환경에 배포하는 과정을, 각각 자동화하는 방법론이다. 이 세 가지 접근 방식의 주요 차이점은 코드 변경 사항이 프로덕션 환경에 도달하는 자동화 수준과 사람의 개입 정도에 있다. CI/CD 파이프라인은 코드 품질 향상, 출시 주기 단축, 팀 협업 강화 등 다양한 이점을 제공하며, 최신 트렌드로는 GitOps, AIOps, 보안 통합 (DevSecOps) 등이 있다. ...

October 2, 2024 · 10 min · Me

Context Switching

Context Switching 1단계: 기본 분석 및 검증 대표 태그 프로세스관리 (Process Management) 멀티태스킹 (Multitasking) CPU스케줄링 (CPU Scheduling) 시스템성능 (System Performance) 분류 체계 검증 현재 분류 구조 중 “Computer Science Fundamentals > Operating Systems > Process Management >Processes"는 적절합니다. “Context Switching(컨텍스트 스위칭)“은 운영체제의 멀티태스킹을 가능하게 하며, 프로세스 관리의 핵심에 해당합니다. 다만, 실무적 관점에서는 “Performance Optimization(성능 최적화)”, “Concurrency(동시성)“에도 연계되며, 실질적으로 “시스템 성능”·“프로세스 스케줄링”·“CPU 관리” 분류에 투입하는 것도 추천합니다. 핵심 요약 컨텍스트 스위칭(문맥 교환, Context Switching)은 CPU가 실행 중인 프로세스 상태를 저장하고, 새로운 프로세스 상태를 복원해 여러 작업이 병렬처럼 실행될 수 있도록 하는 운영체제 핵심 기능입니다.[1][2][3] ...

October 2, 2024 · 56 min · Me

History and Evolution of CI/CD

History and Evolution of CI/CD CI/CD(지속적 통합/지속적 배포) 의 역사와 발전은 소프트웨어 개발 방법론의 진화를 보여주는 중요한 여정입니다. 1990 년대 후반 익스트림 프로그래밍 (XP) 에서 처음 등장한 지속적 통합 개념이 시작점이었으며, 이후 애자일 방법론의 부상과 함께 발전했다. 워터폴 모델의 한계를 극복하기 위해 등장한 CI/CD 는 개발자들이 코드 변경사항을 빈번하게 통합하고 자동화된 테스트를 수행하는 방식으로 진화했다. 2000 년대 중반 젠킨스 (이전의 허드슨) 의 등장은 CI/CD 도구의 대중화를 이끌었고, 이후 클라우드와 컨테이너 기술의 발전과 함께 GitLab CI, CircleCI, GitHub Actions 등 다양한 도구들이 등장했다. 현재 CI/CD 는 GitOps, AIOps, 보안 통합 (DevSecOps) 등의 최신 트렌드를 포함하며 계속 발전하고 있다. 이 발전 과정은 수동적이고 경직된 개발 프로세스에서 자동화되고 유연한 방식으로의 전환을 보여주며, 소프트웨어 산업의 혁신과 속도를 가속화하는 데 중요한 역할을 하고 있다. ...

October 2, 2024 · 5 min · Me

페이징 (Paging)

페이징 (Paging) 먼저 페이징이 필요한 배경을 이해해보자. 초기 컴퓨터 시스템에서는 프로그램 전체가 물리 메모리에 연속적으로 적재되어야 했다. 이는 두 가지 큰 문제를 발생시켰다: 큰 프로그램은 메모리에 적재하기 어려웠다. 메모리 단편화(fragmentation)가 심각했다. 이러한 문제를 해결하기 위해 페이징이 도입되었다. 페이징의 기본 개념은 프로그램의 논리적 주소 공간과 물리적 메모리를 동일한 크기의 작은 단위로 나누어 관리하는 것이다. 이때 논리적 주소 공간의 단위를 ‘페이지(page)‘라 하고, 물리적 메모리의 단위를 ‘프레임(frame)‘이라고 한다. Source: https://www.geeksforgeeks.org/paging-in-operating-system/ 페이징 시스템의 주요 구성 요소 페이지 테이블(Page Table): ...

October 1, 2024 · 4 min · Me