한빛출판네트워크

제공 : 한빛 네트워크
저자 : Baron Schwartz
역자 : 노재현
원문 : How to Optimize Rank Data in MySQL

컴퓨터 게임을 하는 사용자의 랭킹을 관리하는 사이트가 있다고 하자. 이 사이트의 랭킹 게시판에는 최상위의 점수를 가진 유저부터 시작해서 차례대로 유저들의 정보가 게시가 되고 있다. 웹 사이트는 PHP로 개발되었고, MySQL 5 데이터베이스를 이용하고 있다. 또 정보가 자주 변경되는 사이트 이기 때문에 MySQL의 InnoDB를 사용하고 있다.

위와 같은 가정은 주로 인기도라던가 점수와 같은 기준을 가지고 랭킹 데이터를 페이징해서 출력해야 하는 애플리케이션에서 많이 사용하게 되는 전형적인 시나리오라고 볼 수 있다.

보통 게임 사이트의 유저수는 수 백만에 달하고, 이 많은 유저들을 한 화면에 표시할 수 없기 때문에 페이징을 사용하게 된다. 이 말인즉 랭킹 데이터를 잘 정렬한 후에 일정 수의 데이터만 표시하기 위해서 제한 수치를 설정해야 함을 의미한다. 말이야 정말 쉽다. 하지만 실제로 위의 데이터를 추출해 내는 과정은 생각만큼 만만치 않은 과정이다. 아마도 간단하게 생각해 낼 수 있는 SQL 쿼리문으로는 데이터베이스가 견뎌내지 못할 것이고, 유저 데이터가 더욱 많이 늘어날 수록 상황은 더욱 더 악화될 것이다.

이 글에서는 세 가지 해결책을 제시하고자 한다. 일반적인 방법으로 디자인하게 될 경우 아주 안 좋은 성능을 낼 수 있지만, 분명히 해결책은 존재한다.

여기서 소개하는 디자인은 아마 중간급 규모의 사이트에서 유용하게 사용할 수 있을 것이다. 중간급이라고 해서 절대 작은 규모라고 생각하지 말길 바란다. 중간급이지만 최적화되지 않은 한 대의 MySQL 가지고는 택도 없을 수준의 규모라고 생각하면 된다. 그렇다고 여러대의 클러스터를 구성해야 할 만큼 거대하지도 않으니 겁먹진 말기 바란다. 단지 여러분의 사이트에서 어떻게 효율적인 랭킹 데이터 애플리케이션을 만들어 낼 수 있는지를 제시해보고자 함이니 말이다.

사이트 요약

더 나가기 전에 우리가 구성하고자 하는 사이트에 대해서 더 자세히 알아보도록 하자. 우선 10,000명의 유저의 점수를 관리할 것이고, 유저는 다섯 국가에 있는 10가지의 게임을 하게 된다. 여기서는 모든 유저들이 모든 게임을 한다고 가정하겠다. 그러므로 총 100,000개의 점수 기록을 관리하게 되게 된다. 이 글에서는 일부러 유저의 수와 게임의 수를 작게 나타내었다. 너무 크면 여러분의 컴퓨터에서 테스트해보기가 힘들 수도 있기 때문이다.

이 사이트에서 가장 중요한 페이지는 바로 유저들의 랭킹 게시판이다. 이 게시판은 유저의 랭킹을 나라, 게임, 전체와 같은 기준으로 내림차순으로 표시하게 된다. 예를 들어, 1010이라는 유저가 2번 나라에 살고 있고, 1번 게임을 한다고 할 수 있다. 그리고 그 유저는 자신의 나라에서 1번 게임을 기준으로 51위에 랭크되어 있고, 세계에서는 290위에, 세계에 있는 전체게임을 기준으로 할때에는 1867위에 랭크되어 있다.

각각의 랭킹 게시판에서는 한 번에 20명의 유저들을 볼 수 있게 되어 있다. 예를 들어, 1010이라는 유저의 프로필에서 1010 유저의 랭킹 게시판으로 이동하는 링크가 있다고 할때, 이 링크를 클릭하게 되면 1010 유저가 1번 게임에서 51위에 랭크되어 있기 때문에, 랭킹 게시판의 3번째 페이지가 나타나게 될 것이다.

데이터베이스 디자인

아래는 이 글에서 사용하게될 데이터베이스 스크립트이다. 이 스크립트를 실행하게 되면 우리가 필요한 테이블과 이 테이블에 rand() 함수를 이용해서 무작위로 데이터를 생성하게 된다. rand() 함수를 호출할 때 seed 값으로 0을 주었기 때문에 필자가 테스트할 때 사용한 데이터와 동일한 데이터를 가지고 테스트 해 볼 수 있을 것이다.

set @num_gamers    := 10000,
    @num_countries := 5,
    @num_games     := 10;

drop table if exists gamer;
drop table if exists game;
drop table if exists country;
drop table if exists score;
drop table if exists semaphore;

create table semaphore(i int not null primary key);
insert into semaphore(i) values (0);

create table gamer(
   gamer int not null,
   country int not null,
   name varchar(20) not null,
   primary key(gamer)
) engine=InnoDB;

create table game(
   game int not null,
   name varchar(20) not null,
   primary key(game)
) engine=InnoDB;

create table score(
   gamer int not null,
   game int not null, 
   score int not null, 
   primary key(gamer, game),
   index(game, score),
   index(score)
) engine=InnoDB;

create table country(
   country int not null,
   name varchar(20) not null,
   primary key(country)
) engine=InnoDB;

-- 샘플 데이터를 생성하기 위해서 integers 테이블을 사용
drop table if exists integers;
create table integers(i int not null primary key);
insert into integers(i) values(0),(1),(2),(3),(4),(5),(6),(7),(8),(9);

insert into country(country, name)
   select t.i * 10 + u.i, concat("country", t.i * 10 + u.i)
   from integers as u
      cross join integers as t
   where t.i * 10 + u.i < @num_countries;

insert into game(game, name)
   select t.i * 10 + u.i, concat("game", t.i * 10 + u.i)
   from integers as u
      cross join integers as t
   where t.i * 10 + u.i < @num_games;

insert into gamer(gamer, name, country)
   select th.i * 1000 + h.i * 100 + t.i * 10 + u.i,
      concat("gamer", th.i * 1000 + h.i * 100 + t.i * 10 + u.i),
      floor(rand(0) * @num_countries)
   from integers as u
      cross join integers as t
      cross join integers as h
      cross join integers as th;

insert into score(gamer, game, score)
   select gamer.gamer, game.game, floor(rand(0) * @num_gamers * 10)
   from gamer
      cross join game;

랭킹 게시판의 페이징 처리를 위한 전형적인 쿼리

1010본 유저의 랭킹을 보여주는 페이지를 시작으로 SQL을 만들어보자. 유저 1010이 위치하는 페이지를 찾기 위한 가장 간단한 방법으로부터 시작을 하면, 우선 랭킹 게시판에서 몇 번째 페이지에 존재하는지를 찾는다. 그 다음으로 그 페이지에 해당되는 20명의 유저를 1번 게임의 점수를 기준으로 내림차순으로 찾는다. 바로 이 방법이 첫 번째 방법이다. SQL로 표현하면,

-- 게임 1번의 1010번 유저를 찾는다. 결과 : 97101
select score from score where gamer = 1010 and game = 1;

-- 1010번 게이머가 몇 번째에 위치하고 있는가? 결과 : 309.
-- 동점인 경우는 게이머의 ID를 이용해서 구분한다.
select count(*) from score
where score.game = 1 and score.score >= 97101;

-- 1010번 게이머가 위치하게 될 랭킹 게시판 페이지의 데이터를 찾는다.
select gamer.gamer, gamer.name, score.score
from gamer
   inner join score on gamer.gamer = score.gamer
where score.game = 1
order by score.score desc
limit 300, 20;

-- 찾은 페이지의 제일 처음에 나오는 결과값의 랭킹을 찾는다. 결과값 : 284.
select count(distinct score.score)
from score
where score.game = 1 and score.score >= 97101;

마지막 Query는 랭킹 게시판에 표시할 랭킹을 알아내기 위해서 사용한다. 그 위의 Query에서는 표시할 row 들을 가져올 수는 있지만, 몇 번째 랭킹인지까지는 가져올 수가 없다. 그래서 위의 Query를 이용해서 페이지의 첫 번째 랭킹정보를 받아온 후에 차례차례로 다음row를 출력하면서 바로 이전의 유저정보의 게임 점수와 점수가 다른 row가 나오게 되면 랭킹을 1씩 증가시켜 주어야 한다.

더 나은 두가지 디자인

이전의 Query는 단지 20개의 row를 가져오기 위해서 너무 많은 검색을 하고 사용하지 않는 row를 버리고 있다. 이렇게 낭비적인 검색말고 더 좋은 방법은 없을까?

우선 사용하게 될 Query는 랭킹과 그 랭킹이 위치하고 있는 Offset 값을 알아야만 한다. 그런데 안타깝게도 우리가 사용하고 있는 InnoDB는 COUNT() 명령에서는 그다지 빠른 성능을 내지를 못한다.

또 다른 문제는 Offset 값을 포함한 LIMIT 명령이 있는 Query를 어떻게 최적화 시킬것인지 이다. “LIMIT 20”와 같이 사용하는 경우에는 아무 문제가 없다. 하지만 LIMIT 2000, 20과 같이 사용하게 될 경우 검색하는 동안 받아온 row들의 99%를 버리고 20개의 row만을 취하게 되기 때문에 낭비가 굉장히 커지게 된다. 그래서 여기서는 LIMIT명령에 있는 offset 값을 버리고 대신에 "ORDER BY" 명령이 인덱스를 타도록 하게 하고 싶다.

이렇게 하기 위해서 필자는 테이블이 비록 비정규화 되더라도 새로운 column을 하나 추가하도록 하려고 한다. 바로 인덱스된 랭킹 column을 추가하는 것이다. 이렇게 해서 추가되는 관리비용은 잠시 뒤로 물리도록 하자. 바로 다음이 두 번째 해결책이다.

-- 위에서 설명된 바와 같이 게임 점수와 랭킹을 찾는다.
select score, rank_in_game from score_ranked where gamer = 1010 and game = 1;

-- 랭킹게시판에서의 유저의 위치를 찾는다.  결과 값 : 309
select count(*) from score_ranked
where game = 1 and score >= 97101;

select gamer.gamer, gamer.name, u.score, u.rank_in_game
from gamer
   inner join (
      ( 
         -- Fetch start (first 9 rows) of leaderboard.
         select gamer, score, rank_in_game
         from score_ranked
         where game = 1 and rank_in_game <= 290 and gamer <= 1010
         order by rank_in_game desc, gamer desc
         limit 9
      )
      union all
      (
         -- Fetch remaining 11 rows.
         select gamer, score, rank_in_game
         from score_ranked
         where game = 1
            and ((gamer > 1010 and rank_in_game = 290) or rank_in_game > 290)
         order by rank_in_game, gamer
         limit 11
      )
      order by rank_in_game, gamer
   ) as u on gamer.gamer = u.gamer;

좀 복잡해 보이기는 하지만, 이전 Query에 비하면 효과가 있다. Query에서 COUNT() 명령을 제거하였고, LIMIT 명령에서 사용하고 있던 Offset 값또한 사용하지 않게 되었다. 이제 위에서 작성된 Query를 수행하게 되면 랭킹을 포함한 게시판에 필요한 row들을 얻을 수가 있다.

그런데 제일 위에 랭킹 페이지를 20으로 정확하게 나누어 떨어지게 하기 위해서 사용하는 COUNT()명령이 하나 더 남아있다. 꼭 20으로 나누어 떨어지도록 출력해야 하는게 아니라면 이 COUNT() 명령 마저도 제거할 수가 있다. 이 방법이 세 번째 시나리오이다.

-- 위에서 설명된 바와 같이 게임 점수와 랭킹을 찾는다.
select score, rank_in_game from score_ranked where gamer = 1010 and game = 1;

-- 1010번 게이머가 속한 랭킹 게시판의 페이지 데이터를 찾는다.
select gamer.gamer, gamer.name, u.score, u.rank_in_game
from gamer
   inner join score_ranked as u on gamer.gamer = u.gamer
where game = 1 and rank_in_game >= 290 and u.gamer >= 1010
order by rank_in_game, gamer
limit 20;

더 많이 좋아졌다. 이 Query를 이용하면 최소한의 row를 읽어서 우리가 원하는 랭킹 정보를 얻어낼 수가 있게 되었다. 다른 종류의 랭킹 게시판(예를 들면, 나라를 기준으로 혹은 전체 랭킹 정보 등)또한 같은 방법으로 최적화가 가능할 것이다.

혹시 20개 단위로 페이징을 꼭 해야만 한다면, Query를 시작하기 전에 20개 단위로 페이징을 해야할 위치 값을 먼저 Query로 받아온 후에 이 값을 재사용할 수 있을때까지 유지하면서 사용하는 것이 좋을 것이다.

---

역자 노재현님은 어렸을 때부터 컴퓨터를 접하게 된 덕에 프로그래밍을 오랫동안 정겹게 하고 있는 프로그래머 입니다. 특히나 게임 및 OS 개발에 관심이 많으며, 심심할 때면 뭔가 새로운 프로그램을 만들어내는 것을 좋아합니다. 다음에서 웹 관련 개발을 한 후에 현재는 www.osguru.net이라는 OS관련 웹사이트를 운영하며 넥슨에서 게임 개발을 하고 있습니다.
* e-mail: wonbear@gmail.com
* homepage: http://www.oguru.net

---