해뜨기전에자자

log structured merge tree. Cassandra, Elasticsearch 등 최신 DB들에서 많이 사용되며 Data를 immutable하게 관리할 수 있다. Disk의 Sequantial Read/Write 속도는 Memory 의 Random access에 비해서도 10배 가까이 빠른 성능을 내므로, LSM tree 는 B+ tree에 비해 더 높은 write workloads를 처리할 수 있다. Random write가 발생하는 b tree와 다르게, SSTable의 write는 항상 sequantial하기 때문이다. 그러나 매우 높은 write 을 처리해야하는 부하 상황에서 Lag이 생길 수 있으며 merge&compaction작업이 느려지면 그만큼 Read가 늘어나 퍼포먼스가 불..

fzf에서 문자열 서치 알고리즘으로 뭘 사용하는지 찾아보다가 정리해둔다. 차이점 위주로 Needleman-Wunch두 문자열의 전체 유사도 https://en.wikipedia.org/wiki/Needleman–Wunsch_algorithm padding 전략: 맨 왼쪽 위 값을 0으로 주고 indel 이 발생했다고 가정한다. gap으로 채워지게 됨.점화식:H[i][j] = max(H[i-1][j-1] + match or mismatch, H[i-1][j] + gap, H[i][j-1] + gap)trace back 시작점: H[str1.length][str2.length] 그러니까 .. 테이블 오른쪽 맨 아래 셀 Smith-Waterman두 문자열의 지역 유사도 https://en.wikipedia.o..

https://aphyr.com/posts/294-jepsen-cassandra 카산드라의 write loss 에 대해서 다루고 있는 글.CRDT, Vector clocks, Isolation Levels 등의 개념에 대해 접할 수 있었고,CRDT를 만족하는 CQL을 쓰면 write loss를 없앨 수 있음.CRDT: semi-lattice의 조건을 만족할때 충돌 없이 Replicated 시킬 수 있는 개념. * semi-lattice는 결합법칙 & 교환법칙 & 멱등성---- 일찍이 카산드라에서는 vector clocks를 구현하지 않기로 결정했는데, 이유는 속도 저하 때문이었음. last-write-win을 모든 케이스에 적용하고, causality graph 를 무시하면서 write를 위한 round..

java library인 guava document를 보다가 bloom filter라는 게 있어서 찾아봤다.https://github.com/google/guava/wiki/HashingExplained#bloomfilter 모든 데이터에 대해서 바로 데이터가 있는지 체크하려고 하면 데이터가 클 수록 비용이 많이 들게 든다. 그래서 bloom filter 에서 데이터가 있는지 한번 체크하고, 데이터에 실제로 접근하도록 하는 모델을 많이 쓴다. bloom filter는 완벽한 searching table을 제공하는게 아니라 서치 비용(space and time)을 줄이기 위함이다. cassandra, base, bigtable, hbase, ip filtering, router, 웹 검색 등 아주 많은 곳..