1주차 과제 진행상황 - seonghoo1217/Todo-List-Study GitHub Wiki

1주차

과제 요구사항

  • JPA를 사용하지않고, 데이터 모델을 생성해야한다.
  • 그렇다면, In-Memory를 사용할 구조체부터 파악해보자
  • 기본적으로 MAP을 사용한다면 DB와 유사한 구조를 낼 수 있지않을까?
    • 하지만 HashTable도 있는데, 이를 지표로 분석해볼까

HashTable vs ConcurrentHashMap

🤔 우선 왜 HashMap은 안씀?

image

  • HashMap의 경우 비동기화되어 synchronized를 보장받지 못해 멀티스레드 환경에서 안전성을 보장받지 못한다.
  • 여러 스레드가 동시에 HashMap 객체를 수정하거나 삽입할 수 있어 무결성에 문제가 생김
    • 물론 투두 리스트가 그만한 동시성이슈가 발생할까? 라는 고민은 있지만 스터디가 목적이기에 고려사항으로 두어야함
  • 또한 가장 중요한 부분은 null을 Key값으로 허용하며, value로서도 허용함
  • 싱글 쓰레드 환경에서 사용하는 게 좋다. 한편, 동기화 처리를 하지 않기 때문에 데이터를 탐색하는 속도가 빠르다
  • 멀티 스레드 환경에서 사용하기 위해선, 위 그림과 같이 전체에 Lock을 걸어야함
  • 결론적으로 HashTable과 ConcurrentHashMap보다 데이터를 찾는 속도는 빠르지만, 신뢰성과 안정성이 떨어진다.

HashMap의 내부구조

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

...

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) &amp; hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node&lt;K,V&gt; e; K k;
        if (p.hash == hash &amp;&amp;
            ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount &gt;= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &amp;&amp;
                    ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size &gt; threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

...



}
  • Map의 put을 이용하여 값을 삽입하는순간 putavl이라는 메서드의 리턴 값을 전달한다.
  • 로직을 보면 동기화처리가 별도로 존재하지 않기에 삽입 / 조회 연산이 빠르다.

HashTable

  • In-Memory로 과제를 진행하기 위해서 맨처음 로컬 스토리지로 생각했던 대안이 HashTable이다.
  • HashTable의 경우 ThreadSafe할 뿐만 아니라 메소드를 호출하기 전에 쓰레드간 동기화 락을 걸기에 멀티 쓰레드 환경에서 무결성이 보장된다.
  • 하지만, 동기화 락은 매우 느린 동작이라는 단점이 존재한다.

ConcurrentHashMap

image

  • ConcurrentHashMap 또한 thread-safe하기 때문에, 멀티 쓰레드 환경에서 사용할 수 있다.
  • 각각의 Bucket 별로 동기화를 진행하기에 다른 Bucket에 속해있을 경우엔 별도의 lock없이 운용한다.
  • 이 구현체는 HashMap의 동기화 문제를 보완하기 위해 나타났다
  • 동기화 처리를 할 때, 어떤 Entry를 조작하는 경우에 해당 Entry에 대해서만 락을 건다. 그래서 HashTable보다 데이터를 다루는 속도가 빠르다.
    • 즉, Entry 아이템별로 락을 걸어 멀티 쓰레드 환경에서의 성능을 향상시킨다

지표로 분석해보자

public class MapConcurrencyTest {
    static final int ITERATION_COUNT = 10000000;
    static CountDownLatch latch;
    static Map<Integer, Integer> map;
    static List<Long> times;

private void init(Map&lt;Integer, Integer&gt; m) {
    latch = new CountDownLatch(20);
    map = m;
    for (int i = 1; i &lt;= 1000; i++) {
        map.put(i, i);
    }
}

@Test
public void test() throws InterruptedException {
    for (Map m : new Map[]{
            new HashMap&lt;Integer, Integer&gt;(),
            new ConcurrentHashMap&lt;Integer, Integer&gt;(),
            new Hashtable&lt;Integer, Integer&gt;()
    }) {
        times = new ArrayList&lt;&gt;();

        for (int t = 0; t &lt; 10; t++) {
            init(m);

            long start = System.currentTimeMillis();

            // 쓰기 작업 쓰레드 10개
            for (int counter = 0; counter &lt; 10; counter++) {
                new Thread(() -&gt; {
                    for (int i = 1; i &lt;= ITERATION_COUNT; i++) {
                        int key = i % 1000 + 1;
                        map.put(key, key);
                    }
                    latch.countDown();
                }).start();
            }

            // 읽기 작업 쓰레드 10개
            for (int counter = 0; counter &lt; 10; counter++) {
                new Thread(() -&gt; {
                    for (int i = 1; i &lt;= ITERATION_COUNT; i++) {
                        int key = i % 1000 + 1;
                        map.get(key);
                    }
                    latch.countDown();
                }).start();
            }

            // 모든 쓰레드 작업 대기
            latch.await();

            long time = System.currentTimeMillis() - start;
            times.add(time);
        }

        System.out.println(&quot;Map: &quot; + m.getClass().getSimpleName());
        System.out.println(&quot;Execution Times: &quot; + Arrays.toString(times.toArray()));
        System.out.println(&quot;Average execution Time: &quot; + times.stream().mapToLong(Long::longValue).average().getAsDouble() + &quot;ms&quot;);
        System.out.println();
    }
}



}

image

이렇게 차이가 나는 이유는 Hashtable은 조회와 삽입 작업에 모두 synchronized를 통해 테이블 전체를 lock걸어 반면, ConcurrentHashMap은 조회 작업에는 lock을 걸지 않고, 삽입 작업에서만 사용되는 키 값에 따라 세분화된 lock을 제공하여 여러 스레드가 동시에 다른 부분을 수정할 수 있다

정리

  HASHMAP HASHTABLE CONCURRENTHASHMAP
key와 value에 null 허용 O X X
동기화 보장(Thread-safe) X O O
추천 환경 싱글 쓰레드 멀티 쓰레드 멀티 쓰레드

도메인 분석 사항

  • PK인 ID를 노출시키지 않고, 최대한 기존 프로덕션된 서비스와 유사한 환경을 구성하고자 했음
  • 그렇기에 UUID를 도입하여 보조키로 사용하며, 필요한 필드 값들을 묶어 ToDoEssential이라는 별도 클래스로 분리
  • 회원이 필요할 것 같아 현재 더미 데이터로서의 역할을 수행만 할 수 있도록 제작
    • 추후 세션 인증 처리
⚠️ **GitHub.com Fallback** ⚠️