Django에서 댓글 기능을 어떻게 구현해야 할까?
물론 하나의 게시물에 여러 개의
댓글 기능을 구현하는 것은 간단하다.
하지만 문제는 최근의 댓글 기능에는 댓글 안에 댓글이
그리고 그 댓글 안에 댓글이 달릴 수 있다는 것 이다.
즉, 하나의 댓글에 깊이(레벨)를 알 수 없는 댓글이
달릴 수 있다는 것 이다.
이에 대한 솔루션으로 여러가지가 제시 될 수 있을 것 이다.
가장 간단한 방법으로는
이런 레벨을 예측해
그 수 만큼 테이블을 만드는 것이 아닐까 생각 한다.
다만 이 경우 레벨 이상의 댓글에 댓글을 달 수 없게 해야하며
테이블 수 만큼 리소스를 차지하기 때문에
썩 훌륭한 솔루션이라고는 할 수 없다.
구글링 해본 결과 여러가지 솔루션들을 찾을 수 있었는데,
대개 두 가지의 솔루션을 말하는 것을 확인할 수 있었다.
Django MPTT라는 자료구조를 이용해 구현하는
방법과
Django 1.6 이후 분리된 솔루션을 사용하는
방법이 존재한다.
다만, 후자의 경우 전자의 Django1.6 부터
따로 분리된 솔루션이라고 한다.
또한 MPTT를 통해 중첩된 댓글 기능의 구현은 가능하지만,
이 MPTT라는 자료구조 상
끔찍한 성능을 야기할 수 밖에 없다고 하는데
이번 글은 이에 대해 확장된 글로서
이런 계층형 데이터에 대한 이야기를 하려고 한다.
정확히는 리스트로 저장되는 DB에
어떻게 계층형 자료구조를 구현해야하는
방법론에 대해 이야기 해보고자한다.
먼저 MPTT라는 알고리즘이 무엇이고
어째서 MPTT라는 자료 구조를 이용하면
끔찍한 성능을 야기 할 수 있는지에 대해 이야기 해보자.
DB에서 계층적 데이터(Hierarchical Data) 저장에 대해
우리가 사용하고 있는 DB는 단순한 데이터의 리스트를
테이블의 형태로 구성되어 있을 뿐, 계층적으로 나눌 수 없다.
따라서 이런 리스트 형태를
마치 계층적인 데이터 처럼 구현하기 위해서
지금까지 흔히 언급되어지는 두 가지의 접근 방식이 있다.
바로, 인접 리스트 모델(Adjacency List Model)과
수정된 선 주문 트리 탐색(Modified Preorder Tree Traversal)이다.
먼저 인접 목록 모델 부터 살펴보자.
인접 리스트 모델(Adjacency List Model)
이 인접 리스트 모델은
재귀 방법(Recursion Method)이라고 부르기도 하는데
그 이유는 자기 자신을 계속 호출하면서 찾아가기 때문이다.
따라서 매우 간단한 모델이라고 할 수 있다.
온라인 컴파일러를 이용해 살펴보자.
데이터는 참고했던 자료의 데이터를 그대로 사용하기로 하겠다.
해당 표는 위와 같으며 이를 트리로 도식화 하면
데이터의 왼쪽은 해당 데이터를 말하고
오른쪽 번호는 해당 노드의 id를 말한다.
즉, Food라는 데이터를 가지고,
1이라는 id를 가지는 최상위 노드와
그 아래의 하위 노드에 각각 데이터와
해당 노드의 id 번호를 가지고 있다고 말할 수 있는데
예컨데, Pear라는 데이터를 가지고 있는 노드는
부모 노드 id인 3번이 부모 노드 id로서 실제 DB에 저장 된다.
CREATE TABLE category (
id int(10) unsigned NOT NULL AUTO_INCREMENT,
title varchar(255) NOT NULL,
parent_id int(10) unsigned DEFAULT NULL,
PRIMARY KEY (id),
FOREIGN KEY (parent_id) REFERENCES category (id)
ON DELETE CASCADE ON UPDATE CASCADE
);먼저 위와 같은 DB를 정의하고 데이터를 입력해보자.
-- Insert Root Node
INSERT INTO category(title,parent_id)
VALUES('Food',NULL);다음으로 최상위 노드인 루트 데이터 삽입을 해보자.
그 다음에는 해당 노드가 상위 부모 노드 id를 가지도록
데이터를 추가하면 된다.
-- Insert the other Nodes
INSERT INTO category(title,parent_id)
VALUES('Fruit',1);
INSERT INTO category(title,parent_id)
VALUES('Green',2);
INSERT INTO category(title,parent_id)
VALUES('Pear',3);
INSERT INTO category(title,parent_id)
VALUES('Red',2);
INSERT INTO category(title,parent_id)
VALUES('Cherry',5);
INSERT INTO category(title,parent_id)
VALUES('Yellow',2);
INSERT INTO category(title,parent_id)
VALUES('Banana',7);
INSERT INTO category(title,parent_id)
VALUES('Meet',1);
INSERT INTO category(title,parent_id)
VALUES('Beef',9);
INSERT INTO category(title,parent_id)
VALUES('Pork',9);
그 다음은 그 외의 노드의 데이터를 입력한 다음
-- select category table
SELECT title, id, parent_id FROM category
ORDER BY id
위와 같이 정상적으로 Select 문에
보기 쉽게 id 순으로 정렬 조건을 추가해
의도대로 DB에 계층형 데이터가 들어갔는지 확인해보자.
위와 같이 의도한대로 인접 리스트 모델로
데이터가 생성된 것을 확인할 수 있다.
이는 현재도 많은 웹 애플리케이션에서 사용하고 있는 솔루션이다.
다만,
전체 트리의 하나의 노드에 대해
하나의 SQL문이 필요하게 되므로
그 만큼 쿼리를 실행하는데에 시간이 걸리기 때문에
트리 자체가 커지면 커질 수록
처리할 때의 속도가 매우 느려질 것이다.
또한 재귀로 작동하기 때문에
대부분의 프로그래밍 언어에서 느리고 비효율적일 수 밖에 없다.
실제 대부분의 프로그래밍 언어에서 재귀를 허용하기는 하지만
사용하는 것이 드문 이유는
일반적으로 재귀가 여러 의미에서 매우 비효율적이기 때문이다.
첫째, 메모리 관리 측면에서
둘째, 코드 가독성
물론 프로그래밍 언어에 따라(컴파일러 때문)
그리고 코드 구성에 따라 달라질 수 있다.
특수한 경우에는 재귀를 사용하는 것이
가독성은 둘째 치더라도 성능면에서
훌륭할 수 있다는 사실에는 의심의 여지가 없다.
하지만 개발자로서
그런 영역까지 들어가야 하는 경우는 매우 흔치 않다.
수정된 선 주문 트리 탐색(Modified Pre-order Tree Traversal, MPTT)
위와 같은 사실로서 인접 리스트 모델은
여러가지 의미에서 효율이 썩 좋다고는 할 수는 없을 것이다.
인접 리스트 모델의 대안으로서 활용할 수 있는 것은
수정된 선 주문 트리 탐색(MPTT)라는 자료 구조 이다.
MPTT는 위와 같이 각 노드당 left 값과 right 값을 가지는 형태를 말한다.
CREATE TABLE category (
id int(10) unsigned NOT NULL AUTO_INCREMENT,
title varchar(255) NOT NULL,
parent_id int(10) unsigned DEFAULT NULL,
lft_id int(10) NOT NULL,
rgt_id int(10) NOT NULL,
PRIMARY KEY (id),
FOREIGN KEY (parent_id) REFERENCES category (id)
ON DELETE CASCADE ON UPDATE CASCADE
);MPTT는 기본적으로 인접 리스트 모델 테이블에
노드의 오른쪽 값과 왼쪽 값의 속성을 추가한 테이블이다.
또한 노드 추가와 삭제에 대해서는
아래와 같은 알고리즘을 통해 구현할 수 있다.
① 노드의 추가
1)노드를 삽입할 위치(id)를 찾는다.
2)위치(id) 이상의 id를 가지는
모든 노드의 Left값과 Right 값에 2를 더한다.
3)위치(id)에 Left값과 Right값에 1을 더하고 노드를 삽입한다.
② 노드 삭제
1)삭제하고자 하는 노드의 Right값을 가져온다
2)가져온 Right값 이후의 해당하는
모든 id값의 Right값과 Left값에 2를 뺀다.
3)노드를 제거 한다.
MPTT는 어떤 문제를 야기할 수 있는가?
DB에 left값과 right 값을 추가함으로써
검색 부분에서는 더 이상 재귀를 사용하지 않아도 된다.
왜냐하면 검색은 left값과 right값에 의해 검색되기 때문이다.
문제는 이외에 문제가 그대로 남아 있다는 것이다.
왜냐하면 틀 자체는 그대로이며,
MPTT는 단지 left값과 right값을 추가 한 것 뿐이기 때문이다.
여기서 사용할 수 있는 솔루션은 두 가지이다.
첫째, 추가, 수정, 삭제는 인접 리스트를 그대로 사용하고
검색만 MPTT를 사용하는 방법과
두 번째, 새 노드의 오른쪽에 있는 노드들의
left값과 right값을 수정하는 방법이다.
다만 그렇다고 하더라도
여전히 문제는 남아있는데
먼저 첫 번째 솔루션의 문제는 위에서 언급했다시피
추가, 수정, 삭제는 여전히 재귀로 사용한다는 것이며,
두 번째 솔루션의 문제는
여전히 삭제, 수정에 대해서는 성능면에서 대해
의심의 여지를 감출 수 없다.
왜냐하면 위에서 언급한
MPTT 자료구조의 추가와
삭제 알고리즘을 보면 알 수 있듯이
추가 삭제 할 경우
left,right의 id를 다시 재정렬(Rebulid) 해야하므로,
트리의 크기가 커지면 커질 수록
재정렬 하기 위한 시간이 비례해서 커져
끔찍한 성능을 낳을 수도 있기 때문이다.
따라서 MPTT를 사용한다고 하더라도
추가, 삭제, 수정에의 성능이 떨어진다는
즉, 퍼포먼스가 좋지 않다는 사실에 대해서는 여전하기 때문이다.
그렇다면 어떤 것을 사용해야 할까?
2013년에 작성되어진 이에 대한 포스팅에서는
각자 판단에 맡긴다고 이야기하고 있다.
그렇다면 2020년인 지금
Django에서는 어떤 방법을 사용하고 있을까?
다음 글은 이에 대한 이야기가 될 것이다.
솔루션에 대해 관심이 있다면 아래의 링크를 참고하길 바란다.
[ Django, Database, Algorithm, Data Structure ]
Django에서 중첩된 댓글 기능 구현의 대한 솔루션에 대해 :
참고 :
2020.09.13 초안 작성 및 개행 완료
