해당 챕터는 사용자 수에 따른 규모 확장성을 이루기위한 방법을 소개한다.들어가며어느 날 갑자기 서비스의 사용자가 100배로 늘어난다면?대규모 시스템 설계는 단순히 "성능 좋은 서버를 구축"하는 문제가 아니다. 사용자가 늘어남에 따라 발생하는 병목 지점을 파악하고, 비용과 복잡도 사이의 균형을 맞추며 시스템을 발전시켜 나가는 과정이다.본 포스팅에서는 "가상 면접 사례로 배우는 대규모 시스템 설계 기초" 1장의 내용을 바탕으로, 단일 서버에서 시작해 수백만 사용자를 감당할 수 있는 전역적 서비스로 나아가기 위한 핵심 아키텍처 원리들을 정리한다.웹 계층의 무상태(Stateless)화서버 확장의 첫걸음은 웹 계층을 무상태로 만드는 것이다.서버를 한 대에서 두 대, 세 대... 이렇게 수평적으로 확장(Scale-..

들어가며플로이드-워셜은 "모든 정점 쌍 사이의 최단 경로"를 구하는 대표적인 알고리즘이다. 이 포스팅에서는 백준 11403번 문제를 통해 플로이드-워셜의 본질을 파악하고, 최단 거리가 아닌 "경로 존재 여부" 변형을 다룬다. 단순히 "삼중 for문으로 푼다"는 개념을 넘어서, 왜 k를 가장 바깥 루프에 두는지, 인접 행렬과 그래프 탐색의 차이는 무엇인지, BFS/DFS 대신 플로이드-워셜을 선택하는 기준은 무엇인지 등 구현하며 고민했던 지점들을 공유한다.플로이드-워셜 이란?모든 정점 쌍의 경로다음과 같은 그래프가 있다고 하자.1 -> 22 -> 3Q1. 1에서 3으로 갈 수 있나?직접 확인: graph[1][3] = 0 (간선 없음)간접 확인: 1 -> 2 -> 3 (경로 존재)플로이드-워셜은 이처럼 "..

들어가며투포인터는 연속된 구간을 효율적으로 탐색하는 알고리즘이다. 이 포스팅에서 탕후루 문제를 통해 투포인터를 알아보고 깊이 살펴본다.단순히 "left 와 right 포인터를 움직인다."는 개념을 넘어서, 실제 구현 시 마주치는 선택 지점들을 다룬다. 왜 그리디가 아닌 투포인터인지, HashMap 과 배열 중 무엇을 선택할지, 포인터 이동 시점은 언제인지 등 구현하며 고민했던 지점들을 공유한다.투포인터란?연속된 구간 탐색의 효율적 접근다음과 같은 배열에서 합이 5인 연속 구간을 찾는다고 하자.[1, 2, 3, 4, 5]완전탐색으로 찾기:[1] = 1[1,2] = 3[1,2,3] = 6[2] = 2[2,3] = 5 (찾음)모든 구간을 확인 -> O(N^2)투포인터로 찾기:left=0, right=0 → [..

들어가며가상 면접 사례로 배우는 대규모 시스템 설계 기초 의 2장 "모든 프로그래머가 알아야 할 응답 지연 시간 표" 를 보고 막연히 "디스크가 메모리보다 느리다" 는 건 알았지만, 실제로 얼마나 차이 나는지 궁금해졌다.그래서 직접 자바로 측정해보았다.측정 환경JMH (Java Microbenchmark Harness) 1.37Java 17OS: MacOSCPU: Apple M1Disk: SSD측정 항목책에 나온 연산 중 자바 애플리케이션 레벨에서 측정 가능한 것들로만 골랐다.뮤텍스 락/언락메모리 1MB 순차 read디스크 1MB 순차 read1KB GZIP 압축네트워크 왕복 지연 (localhost)측정 불가능한 것들: L1/L2 캐시 접근, 분기 예측 오류, 주 메모리 참조등은 CPU 내부 하드웨어 ..

들어가며BFS와 DFS는 그래프 탐색의 가장 기본적인 알고리즘이다. 이 포스팅에서 대표문제를 통해 BFS와 DFS를 알아보고 깊이 살펴본다.단순히 "DFS는 깊이 우선, BFS는 너비 우선"이라는 개념을 넘어서, 실제 구현 시 마주치는 선택 지점들을 다룬다. 인접 리스트와 인접 행렬 중 무엇을 선택할지, 방문 체크는 언제 해야 하는지, DFS를 Stack으로 구현하면 재귀와 어떻게 다른지 등 구현하며 고민했던 지점들을 공유한다.BFS/DFS 란?그래프 탐색의 두 가지 접근다음과 같은 그래프가 있다고 하자. 1 /|\ 2 3 4DFS로 탐색: 1 → 2 → (돌아옴) → 3 → (돌아옴) → 4 (한 방향으로 깊게 들어갔다가 돌아옴)BFS로 탐색: 1 → 2 → 3 → 4 (레벨별로 넓게)탐색 ..

첫 접근: 완전 탐색백준 1654번 랜선 자르기 문제를 처음 봤을 때 떠오른 생각은 단순했다."가능한 최대 길이부터 시작해서 1씩 줄여가며 확인하면 되지 않을까?"// 이렇게 하면 되지 않을까?long maxPossible = Arrays.stream(cables).max().getAsInt();for (long length = maxPossible; length >= 1; length--) { if (canMake(cables, length, N)) { return length; // 처음으로 가능한 길이 = 최댓값! }}직관적이고 확실한 방법이다. 하지만 제약 조건을 보는 순간 뭔가 이상했다.K(랜선 개수): 1 ~ 10,000N(필요한 개수): 1 ~ 1,000,000 각..