Algorithm - Hashing Collision

---

ShortId 해싱 및 충돌

필자는 최대한 짧은 alphabetic 문자열을 만들기 위해 해싱함수로 문자열 길이를 고정하지 않도록 생각하였다.
최대한 짧게 만들고, 해당 shortId 이 있으면 길이가 1 더 긴 shortId 을 생성한다.

필자는 해싱함수로 UUID를 사용하기로 결정했고, UUID 앞 3~13글자를 사용한다.
UUID 는 기본적으로 Java 단에서 구현이 되어있기 때문에, 해싱 함수로 구현할 때보다 고민하지 않아도 된다.

위 그림은 UUID의 구조이다.

• 구체적으로 'time_low' 필드는 타임스탬프의 하위 32비트를 나타내고 'time_mid' 필드는 타임스탬프의 다음 16비트를 나타낸다.
• 이 두 필드는 함께 총 48비트의 타임스탬프 정보를 제공한다.
• UUID에 대한 타임스탬프를 생성하려면 먼저 현재 시간을 가져와 UTC 에포크 이후 경과된 100나노초 간격의 수로 변환한다.

앞 3~13 글자를 사용한다고 하면, Write 요청이 115.74/s 발생한다고 예상했을 때, 나노초 단위로 나누었을 때, 같은 나노초에 요청이 들어와서 충돌할 확률은 0.00001%(1/10,000,000)이다.

• shortId를 소진하는 데 약 1.6 x 10^19 년이 발생한다.
• 충돌이 발생하면 새로 생성한 UUID를 활용하여 새로운 shortId를 사용한다.
• 추가로 사용할 수 있는 해싱함수 (SHA256, Base64, MD-5)
  • Base64를 제외하고는 고정 길이 해싱값을 반환한다.

코드

자바 코드로 간단하게 구현을 진행했다.
해싱 함수를 바꿀 때는 UUID.randomUUID().toString().substring(0, i) 이 부분을 수정한다.

package me.dragonappear.domain.link;

import lombok.RequiredArgsConstructor;
import me.dragonappear.domain.main.exception.Custom4xxException;
import me.dragonappear.domain.main.exception.Custom5xxException;
import org.springframework.cache.annotation.Cacheable;
import org.springframework.stereotype.Service;
import org.springframework.transaction.annotation.Transactional;

import java.util.UUID;

import static me.dragonappear.domain.main.exception.CustomExceptionError.EXHAUSTED_SHORT_LINK;
import static me.dragonappear.domain.main.exception.CustomExceptionError.NOT_EXIST_SHORT_ID;


/**
 * This is responsible for the service layer, and transaction takes place in here.
 * <p>
 * <p>
 * - createShortUrl: query counts O(N)
 * <p>
 * - createRandomShortId: query counts O(N)
 */

@Service
@Transactional
@RequiredArgsConstructor
public class ShortLinkService {

    private final ShortLinkRepository shortLinkRepository;

    public ShortLinkEntity createShortLink(String url, String clientIp, String userAgent) {
        String randomShortId = createRandomShortId();
        ShortLinkEntity newShortLinkEntity = ShortLinkEntity.createShortUrlEntity(url, randomShortId, clientIp, userAgent);
        return shortLinkRepository.save(newShortLinkEntity);
    }

    @Cacheable(value = "ShortLinkEntity", key = "#shortId", cacheManager = "cacheManager")
    public ShortLinkEntity getShortLink(String shortId) {
        return shortLinkRepository.findByShortId(shortId).orElseThrow(() -> new Custom4xxException(NOT_EXIST_SHORT_ID));
    }

    public String createRandomShortId() {

        for (int i = 3; i < 14; i++) {
            String shortId = UUID.randomUUID().toString().substring(0, i);

            if (shortId.contains("-")) {
                shortId.replace("-", "");
            }

            if (!shortLinkRepository.existsByShortId(shortId)) {
                return shortId;
            }
        }

        throw new Custom5xxException(EXHAUSTED_SHORT_LINK);
    }
}

문제점

위 코드에서는 두가지 문제점이 있다.

1. ShortId에 대한 동시성 처리

• return shortLinkRepository.save(newShortLinkEntity);
  • 동시에 같은 ShortId를 생성하고, DB에 Write 할 때 500 에러가 발생한다.
  • 이 경우에 대한 예외 처리가 되어있지 않다.
• 해결 방안은 시리즈의 DB - Unique Key Concurrency에서 제공한다.

2. UK인 ShortId 에 대한 조회

• shortLinkRepository.existsByShortId(shortId)
  • UK로 인덱싱 처리가 되어있다고 하더라도, 인덱스를 찾아봐야 하므로 매우 비효율적이다.
  • ShortId가 고갈되었을 때 500 에러가 발생하는데, ExceptionHandler단에서 예외 처리가 되어있지 않다.
• 해결 방안은 시리즈의 DB - Unique Key preprocessing에서 제공한다.