[Next.js] Trie를 사용해서 네트워크 요청 없이 자동완성 구현하기 (Typescript, Zustand)

 

[Next.js]
Trie를 사용해서 네트워크 요청 없이 자동완성 구현하기
(Typescript, Zustand)

 

썸네일

 

 

 

서비스를 운영하면서 드는 고민 중 하나는 서버 비용이 아닐까 싶어요. 크루위키 서비스를 운영하면서 매달 지출되는 비용이 생각보다 많이 나오더라구요. 클라이언트 측에서 네트워크 요청 횟수를 크게 줄일 수 있는 방법은 없을지 고민하다가, 검색 input을 활용해 보면 좋겠다는 생각이 들었습니다.

 

 

 

 

동료들과 했던 자료구조 스터디에서 Trie 자료구조를 학습했던 적이 있는데요, Trie 자료구조는 O(N) (N : 문자열의 길이)의 시간 복잡도를 가지고 있어 자동 완성이나 사전 검색 등 문자열을 사용하는 곳에서 자주 활용된다고 합니다.

 

[Typescript] Trie (트라이) 자료구조 직접 구현하기

 

 

크루위키는 컴파일 시 모든 게시글의 정보를 서버에서 가져와 클라이언트 서버에 캐싱해 두고 요청 시마다 활용하고 있습니다. 이 정보들을 활용해 클라이언트 측에 Trie 자료구조로 저장한 뒤, 자동완성 기능에 사용하는 접근으로 설계했습니다.

 

Trie 자료구조를 클라이언트에 저장할 경우 메모리 사용량이 증가할 수도 있으나, 네트워크 요청을 절감한다는 트레이드 오프가 있었습니다. 그렇지만 저희 서비스의 게시글 수는 약 300개 수준으로 메모리 부담은 사실상 무시할 수 있다고 판단했습니다. 따라서 네트워크 요청 절감과 사용자 경험 개선 측면에서 Trie를 도입하기로 결정했습니다.

 

 

 

Trie 클래스 생성하기

 

먼저 Trie 클래스를 생성합니다. 각 노드는 Map 자료구조로 구성되어 있고, 저장할 값인 uuid와 title, 그리고 마지막인지 여부를 확인할 수 있는 isEnd 프로퍼티를 저장합니다. Trie 클래스에서는 인스턴스 생성 시 캐싱되어 있는 title과 uuid를 받아 add 메서드를 통해 Trie 인스턴스에 저장합니다.

class Node {
  child: Map<string, Node> = new Map();
  uuid?: string;
  title?: string;
  isEnd: boolean = false;
}

export class Trie {
  private root: Node;

  constructor(data: TitleAndUUID[] = []) {
    this.root = new Node();
    data.forEach(({title, uuid}) => this.add(title, uuid));
  }
  // ...
}

 

 

 

Add

Trie 클래스의 메서드 중 Trie에 문자열을 저장하는 add를 살펴보겠습니다.

사용자는 문서의 제목을 검색 input에 입력하기 때문에 title의 각 문자를 받아 자식 노드를 확인할 수 있어야 합니다. 따라서 add 메서드에서는 for문으로 title의 각 문자를 순회하면서 currentNode의 자식에 해당 노드가 존재하는지 확인합니다. 만약 자식 노드에 존재하지 않는 경우 새로운 노드로 추가합니다.

export class Trie {
// ...
  add(title: string, uuid: string): void {
    let currentNode = this.root;

    for (const char of title) {
      if (!currentNode.child.has(char)) {
        currentNode.child.set(char, new Node());
      }
      currentNode = currentNode.child.get(char)!;
    }
    currentNode.uuid = uuid;
    currentNode.title = title;
    currentNode.isEnd = true;
  }
}

 

 

Search

이제 저장된 노드들을 검색할 때 search 메서드를 활용합니다. 앞서 title을 활용한다고 언급했었는데요, search에서는 사용자가 입력한 input을 받아 노드를 돌며 검색된 결과를 출력하는 역할을 합니다.

 

prefix를 순회하면서 다음 노드를 확인하는데요, 만약 다음 노드가 없는 경우 (= 해당 input으로 저장된 문서가 없는 경우) 빈 배열을 반환하고, 다음 노드가 존재하는 경우 searchFunc 메서드를 실행합니다.

 

export class Trie {
// ...
  search(prefix: string): TitleAndUUID[] {
    let currentNode = this.root;

    for (const char of prefix) {
      const nextNode = currentNode.child.get(char);
      if (!nextNode) return [];
      currentNode = nextNode;
    }

    const results: TitleAndUUID[] = [];
    this.searchFunc(currentNode, prefix, results);
    return results;
  }

  private searchFunc(node: Node, prefix: string, results: TitleAndUUID[]) {
    if (node.isEnd && node.uuid && node.title) {
      results.push({title: node.title, uuid: node.uuid});
    }
    for (const [char, child] of node.child) this.searchFunc(child, prefix + char, results);
  }
}

 

searchFunc 메서드에서는 자동 완성 결과값으로 출력될 results에 title과 uuid를 넣어주는 역할을 해요. 해당 노드가 마지막이고, title과 uuid가 존재하는 경우 results.push를 합니다. 그렇지만 현재 노드는 사용자가 입력한 접두어까지의 깊이를 갖고 있습니다. 즉, "티스토리"문서를 검색하기 위해 "티스"를 입력했지만 현재 노드는 "티스"까지만 도달하여 "티스" 문서는 검색되지만 "티스토리" 문서는 검색되지 않는 상황인 것이죠. 이를 해결하기 위해서는 searchFunc 재귀를 반복하여 각 노드의 마지막 단어까지 도달해야 합니다.

 

따라서 searchFunc에서 받은 노드의 자식들을 순회하며 노드의 끝까지 도달할 때까지 재귀문을 실행합니다.

for (const [char, child] of node.child) this.searchFunc(child, prefix + char, results);

 

 

Delete

문서를 생성할 수 있으면 삭제도 가능해야 하죠. 삭제는 Trie의 delete 메서드를 통해 진행됩니다. delete 되는 조건은 1. 해당 노드가 마지막 노드여야 하고 2. uuid가 동일해야 성립됩니다. 즉, 삭제하고자 하는 문서의 제목을 끝까지 따라갔을 때 각 문서가 갖는 고유한 uuid가 일치해야 Trie에서 삭제가 됩니다.

 

deleteFunc을 재귀로 반복하며 shouldDeleteChild가 true가 될 때 해당 문서는 최종적으로 삭제됩니다.

export class Trie {
// ...
  delete(word: string, uuid: string): void {
    this.deleteFunc(this.root, word, uuid, 0);
  }

  private deleteFunc(node: Node, word: string, uuid: string, depth: number): boolean {
    if (depth === word.length) {
      if (!node.isEnd || node.uuid !== uuid) return false;
      node.isEnd = false;
      node.uuid = undefined;
      node.title = undefined;
      return node.child.size === 0;
    }

    const char = word[depth];
    const nextNode = node.child.get(char);
    if (!nextNode) return false;

    const shouldDeleteChild = this.deleteFunc(nextNode, word, uuid, depth + 1);
    if (shouldDeleteChild) node.child.delete(char);
    return node.child.size === 0 && !node.isEnd;
  }
}

 

 

Update

문서의 제목을 변경하는 경우는 기존 메서드들을 활용하면 되는데요, 기존 title과 변경될 새로운 title, 그리고 uuid를 받아 delete와 add 메서드를 실행하면 됩니다. 단순히 Trie에서 기존 title을 갖는 노드를 삭제하고 -> 새로운 title을 갖는 노드를 추가하는 것이죠.

export class Trie {
// ...
  update(oldTitle: string, newTitle: string, uuid: string): void {
    this.delete(oldTitle, uuid);
    this.add(newTitle, uuid);
  }
}

 

 

 

Trie 활용하기

 

이제 이 Trie 인스턴스를 생성해 클라이언트에 저장해야 하는데요, 프로젝트에서 상태 관리 라이브러리인 Zustand를 활용하려 합니다. 

개발하면서 느낀 건데, 확실히 Zustand가 깔끔하게 사용하기 좋은 것 같아요. Zustand는 단순하고 보일러플레이트 코드가 적어서 검색 캐싱과 같은 상태 관리에 적합하다고 느꼈습니다.

 

 

useTrie를 통해 먼저 Trie 인스턴스를 선언하고 각 메서드에서 getter로 Trie를 가져다 사용합니다. 

 

import {TitleAndUUID} from '@apis/client/document';
import {Trie} from '@utils/trie';
import {create} from 'zustand';

type State = {
  trie: Trie;
  titles: TitleAndUUID[];
};

type Action = {
  setInit: (titles: TitleAndUUID[]) => void;
  addTitle: (title: string, uuid: string) => void;
  updateTitle: (oldTitle: string, newTitle: string, uuid: string) => void;
  deleteTitle: (title: string, uuid: string) => void;
  searchTitle: (title: string) => TitleAndUUID[];
};

export const useTrie = create<State & Action>((set, get) => ({
  trie: new Trie(),
  titles: [],

  setInit: titles => {
    const trie = new Trie(titles);
    set({trie, titles});
  },

  addTitle: (title, uuid) => {
    const {trie, titles} = get();
    trie.add(title, uuid);
    set({titles: [...titles, {title, uuid}]});
  },

  updateTitle: (oldTitle, newTitle, uuid) => {
    const {trie, titles} = get();
    trie.update(oldTitle, newTitle, uuid);
    set({titles: titles.map(t => (t.uuid === uuid ? {title: newTitle, uuid} : t))});
  },

  deleteTitle: (title, uuid) => {
    const {trie, titles} = get();
    trie.delete(title, uuid);
    set({titles: titles.filter(t => t.title !== title)});
  },

  searchTitle: title => {
    const {trie} = get();
    const results = trie.search(title);
    return results;
  },
}));

 

 

사용처에서는 단 한 줄로 store의 메서드들을 사용할 수 있습니다.

 

'use client';

export const usePostDocument = () => {
  const addTitle = useTrie(state => state.addTitle);

  const {mutate, isPending} = useMutation<PostDocumentContent, WikiDocument>({
    mutationFn: postDocumentClient,
    onSuccess: document => {
      addTitle(document.title, document.documentUUID);
    },
  });
  // ...
};

 

 

SSR + CSR 하이브리드 환경에서의 주의사항

 

단, 주의할 점이 있는데요. Next.js에서 Zustand는 클라이언트 사이드에서만 동작합니다. SSR 단계에서는 동작하지 않고, Hydration 이후 클라이언트에서 상태를 갖습니다. 따라서 Zustand store를 초기화할 때는 클라이언트 컴포넌트에서 진행해야 합니다.

 

크루위키는 layout.tsx 서버 컴포넌트에서 모든 초기화가 일어나도록 설계되어 있는데요, 이곳에 InitTrie라는 클라이언트 컴포넌트를 추가합니다. 컴파일 이후 Next.js 서버에서 기본 뼈대가 완성된 뒤, 클라이언트 사이드에서 InitTrie가 실행되어 Zustand store가 초기화됩니다.

const Layout = ({children}: React.PropsWithChildren) => {
  return (
    <div className="App relative">
      <InitTrie />
      <div className="flex h-fit items-center justify-center">
        <main className="flex h-fit w-full max-w-[1440px] items-start justify-center gap-6 px-4 py-6 max-[768px]:px-0 max-[768px]:py-2">
          {children}
        </main>
      </div>
    </div>
  );
};

'use client';

const InitTrie = () => {
  const {data} = useGetDocumentTitleList();
  const setInit = useTrie(state => state.setInit);

  useEffect(() => {
    if (data) {
      setInit(data);
    }
  }, [data, setInit]);

  return null;
};

export default InitTrie;

 

 

 

 

PR (전체 코드 확인)

검색 자동완성 기능 구현 by chosim-dvlpr · Pull Request #120 · Crew-Wiki/crew-wiki-next

 

 

 

 

 

Trie 전체 코드

import {TitleAndUUID} from '@apis/client/document';

class Node {
  child: Map<string, Node> = new Map();
  uuid?: string;
  title?: string;
  isEnd: boolean = false;
}

export class Trie {
  private root: Node;

  constructor(data: TitleAndUUID[] = []) {
    this.root = new Node();
    data.forEach(({title, uuid}) => this.add(title, uuid));
  }

  add(title: string, uuid: string): void {
    let currentNode = this.root;

    for (const char of title) {
      if (!currentNode.child.has(char)) {
        currentNode.child.set(char, new Node());
      }
      currentNode = currentNode.child.get(char)!;
    }
    currentNode.uuid = uuid;
    currentNode.title = title;
    currentNode.isEnd = true;
  }

  search(prefix: string): TitleAndUUID[] {
    let currentNode = this.root;

    for (const char of prefix) {
      const nextNode = currentNode.child.get(char);
      if (!nextNode) return [];
      currentNode = nextNode;
    }

    const results: TitleAndUUID[] = [];
    this.searchFunc(currentNode, prefix, results);
    return results;
  }

  private searchFunc(node: Node, prefix: string, results: TitleAndUUID[]) {
    if (node.isEnd && node.uuid && node.title) {
      results.push({title: node.title, uuid: node.uuid});
    }
    for (const [char, child] of node.child) this.searchFunc(child, prefix + char, results);
  }

  delete(word: string, uuid: string): void {
    this.deleteFunc(this.root, word, uuid, 0);
  }

  private deleteFunc(node: Node, word: string, uuid: string, depth: number): boolean {
    if (depth === word.length) {
      if (!node.isEnd || node.uuid !== uuid) return false;
      node.isEnd = false;
      node.uuid = undefined;
      node.title = undefined;
      return node.child.size === 0;
    }

    const char = word[depth];
    const nextNode = node.child.get(char);
    if (!nextNode) return false;

    const shouldDeleteChild = this.deleteFunc(nextNode, word, uuid, depth + 1);
    if (shouldDeleteChild) node.child.delete(char);
    return node.child.size === 0 && !node.isEnd;
  }

  update(oldTitle: string, newTitle: string, uuid: string): void {
    this.delete(oldTitle, uuid);
    this.add(newTitle, uuid);
  }
}