-
Demand-based FTL
Introduction 안녕하세요? 저번 글에서는 flash에서 사용되는 FTL에 대하여 알아보았습니다. Flash의 특수한 특성 때문에 성능 향상을 꾀하기 위해서는 FTL이라는 기법을 사용해야 하며, page 단위로 mapping table을 저장하는 page-level FTL과 block 단위로 mapping table을 저장하는 block-level FTL이 있으며 전자는 많은 메모리가 필요하다는 점, 후자는 속도가 느리다는 점이 단점이었습니다. 또, 둘을 적절히 섞은 Hybrid Mapping이라는 방법을 사용할 수 있으며, 이 경우 merge operation을 진행해주어야 한다는 점이 주요 특징이었습니다. 이번 글에서는 hybrid mapping을 조금 더 발전시킨 Demand-based FTL(DFTL)이라는 기법에...
-
DDD Aggregate Pattern
오늘은 제가 가장 좋아하는 소프트웨어 설계 기법인 Aggregate Pattern 에 대해서 소개해드리겠습니다! » 이 글을 좀 더 좋은 가독성으로 읽기 « Aggregate Pattern 이란? Aggregate Pattern 은 Eric Evans 의 Domain-Driven Design 에서 소개된 설계 패턴으로써 아주 강력하고 scalable 한 설계 지침을 제공합니다. Aggregate 를 제대로 설명하기 위해서는 Entity 등과 같은 DDD 의 다른 개념들도 같이 설명이 필요한데요. 이 글의 목적이 DDD 가 아니고 DDD 및 Aggregate 에 대한 개념적인 설명들은 인터넷에 많이 있으므로 이...
-
Minimum Arborescence
안녕하세요. 이번 글에서는 weighted directed graph에서 minimum arborescence를 찾는 알고리즘을 소개해드리려고 합니다. minimum arborescence는 minimum spanning tree의 directed 버전이라고 할 수 있습니다. 문제 가중치 있는 방향 그래프 $G=(V,E)$ 와 루트 정점 $r\in V$이 주어집니다. 가중치는 $e\in E$에 대해 $w(e)$로 정의됩니다. 이때 모든 정점 $u$ 에 대하여 $r\rightarrow u$의 경로가 유일하게 존재하며, 가중치의 합이 최소가 되도록 $|V|-1$개의 간선들을 적절히 선택하는 것이 목표입니다. 편의상 loop와 multi edge는 존재하지 않고, 모든 정점이 $r$ 에서 도달 가능하다고 가정하겠습니다. 해당...
-
How to build WebAssembly app with Rust
서론 작년에 마작에서 현재 들고 있는 패의 점수 기대치를 계산하는 웹 사이트를 제작을 하려고 하고 있었는데, 다음과 같은 문제에 부딪혔습니다. 가능하면 클라이언트 사이드에서 패의 정보를 입력하고, 해당 패의 점수 기대치를 클라이언트에서 계산하게 하고 싶다. 하지만 웹에서 클라이언트 사이드에서 계산하는 선택지는 거의 JavaScript 뿐이다. JavaScript를 사용할 줄은 알지만, 굳이 개발하면서 JS를 쓰고 싶지는 않다. 대안으로 TypeScript가 있지만, 그리고 JS보다 훨씬 낫지만, 역시 마음에 들지는 않는다. 그래서 더 생각해본 결과, 클라이언트 사이드에서 계산하는 것을 포기하고 Python +...
-
De Bruijn 수열
De Bruijn 수열 당신은, 친구에게 $1$에서 $K$까지의 수들을 나열한 원형 수열(끝 글자와 첫 글자가 이어지는 수열)을 선물로 받았다. 그런데 이 수열은 신기한 성질을 가지고 있다. 이 수열에서 길이 $N$인 연속한 부분수열들을 모두 나열한다. 물론 원형 수열이기 때문에 그런 수열의 개수는 수열의 길이와 같다. 이 때, 이렇게 모은 부분수열의 모음이 그러면 $1$에서 $K$까지의 수들로 만든 모든 길이 $N$의 수열의 모음과 같았다! 그런 수열을 de Bruijn(‘jin’이 아니라 ‘ijn’임에 유의하자. 드 브루인이라고 읽는다.) 수열이라 한다. 예를 들어 $K...