본문 바로가기

IT105

Topological Sorting 위상 정렬이라고 불리는 Topological Sorting 에 대해 알아보려고 한다. Topological Sorting은 Directed Acyclic Graph (DAG)를 사용하여 Vertices를 순서 있게 나열하는 것이다. (즉, DAG 형태가 아니라면 해당 정렬은 사용할 수 없다.) 그림 1. DAG 그런데 기본 구조인 그래프의 특성상 정렬 방법은 여러개가 될 수 있다.그림 1을 보면 (5, 4, 2, 3, 1, 0), (4, 5, 2, 3, 1, 0) 이렇게 2개가 될 수 있다. 이는 시작점은 항상 들어오는 부분이 없는 (in-degree가 0) 정점이 되어야 한다. 이를 바탕으로 그림 1을 보면 In-degree가 0인 부분은 2개(5, 4) 이다. Topological Sorting의 구.. 2019. 6. 10.
[Kubernetes] StatefulSet 이번 포스팅에서는 StatefulSet에 대해 알아보려고 한다. ReplicaSet 그림 1. ReplicaSet 다시금 ReplicaSet을 살펴보면 그림 1 처럼 미리 정의해 놓은 Pod의 설정을 Replicas 개수에 따라 만든다. 그림 2. PVC & PV 더군다나 Pod를 설정 할 때 PVC와 같은 Volume을 포함하게 되면 그림 2와 같이 Replicas로 만들어진 모든 Pod는 동일한 PVC를 참조하게 된다. (ReplicaSet으로 만들어지는 모든 Pod는 동일한 매니페스트 파일을 사용하기 때문에) 만일, 위와 같이 사용하고 싶다면 큰 문제는 없지만 그렇지 않다면 문제가 될 수 있다. 이미 매니페스트 파일을 만들 때 PVC를 정의했기 때문에 각 Pod는 다른 PVC를 접근할 수 없다. 이.. 2019. 6. 7.
[Kubernetes] Headless Service 그림 1. Service 일반적으로 Service는 Client에 의해 요청이 들어올 경우 Service가 관리하고 있는 여러 Pod들 중 임의로 하나를 선택해서 연결을 한다. 그런데 만일 Client가 Service가 제공하는 모든 Pod와 연결이 필요하다면 어떻게 해야 할 것인가? 어찌보면 당연하게도 모든 Pod의 주소를 알면된다.이를 위해 k8s에서는 Client가 DNS lookup을 통해 Pod의 IP를 찾는 것을 허용한다. 그런데 매니페스트 파일을 구성할 때 속성에 따라 DNS lookup 에서 나오는 결과가 다르다.spec: clusterIP: None 위와 같이 Service의 ClusterIP를 None으로 설정하면 DNS는 Service의 ClusterIP 대신에 모든 Pod의 IP 목.. 2019. 6. 7.
Segment Tree Segment Tree는 Tree의 일종으로 각 노드에 특정 범위에 대한 정보가 담겨있다. (범위를 Interval, Segment 등으로 표현한다.) Tree의 응용은 당연스럽게 기존의 방식으로는 시간 복잡도가 높기 때문이다. 한 가지 예를 든다면, [1,2,3,4,5]의 트리에서 (배열로 구성된 트리) 2~4 사이의 합을 알고 싶다면 어떻게 해야 할까?누구나 접근할 수 있는 쉬운 방법은 전체를 다 훑어보는 것이다. 그렇다면 O(n) 정도의 시간 복잡도가 나온다. 그런데 만약 부분합과 같이 각 노드에 미리 합쳐진 값이 존재한다면 O(1)과 같이 상수의 시간 복잡도로 범위 값을 찾을 수 있다. 이렇듯 Segment Tree는 범위에 대한 정보를 미리 저장함으로써 다음 계산시에 사용할 수 있도록 한다. 때.. 2019. 6. 7.

티스토리툴바