MySQL RAND 함수의 난수 생성 원리

MySQL 서버의 RAND 함수는 시드(Seed)값이 주어지지 않은 경우 0이상 1.0 미만의 부동소수값을 반환하는 함수이다. 어떠한 경우에도 랜덤 값은 1.0 이상으로 생성되지 않는다.

MySQL 서버에는 내부적으로 난수를 생성하는 과정에 난수 생성 최대값 제한(1073741823)이 존재하는데, 이 최대값으로 시드값에 모듈러 연산을 수행하고 시드값이 32비트를 넘을 경우에는 2^32 모듈러 연산을 수행한다. 시드값이 크게 주어진다해도 결국 RAND 함수는 난수 생성 최대값 제한에 영향을 받는다.
시드값이 존재하는 경우와 그렇지 않은 경우를 나누어 좀 더 자세한 계산 과정을 살펴보겠다.

Seed 값이 존재하는 경우

RAND 함수내에 인자로 주어진 시드값은 난수 구조체(rand structure)에 의해 계산되고 관리된다.
 

SELECT RAND(123.11);

 
위와 같이 시드값으로 123.11이 전달되면 RAND 함수에 의한 랜덤값은 다음과 같은 과정을 거쳐 계산된다.
 

1) item_func.cc:Item_func_rand::seed_random
 

void Item_func_rand::seed_random(Item *arg) {
  /*
    TODO: do not do reinit 'rand' for every execute of PS/SP if
    args[0] is a constant.
  */
  const uint32 tmp = (uint32)arg->val_int();
  randominit(m_rand, (uint32)(tmp * 0x10001L + 55555555L),
             (uint32)(tmp * 0x10000001L));
}

 
Line 6

- tmp: 123
(부호없는 양의 정수로 변환하여 tmp 변수에 할당)

Line 7
- m_rand: rand_struct 타입의 포인터
(Item_func.cc:Item_func_rand::fix_fields에서 메모리 할당됨. 구조체 정의는 item_func.h 참조)
- (uint32)(tmp * 0x10001L + 55555555L): 63616606
(seed 123에 0x10001을 곱하고 55555555를 더하는 것은 난수 생성 알고리즘의 일부로 보임)
- (uint32)(tmp * 0x10000001L): 2952790139
- randominit: 난수 생성 초기화

→ 시드값 123.11을 32비트의 부호없는 양의 정수로 변환한 뒤, 계산식을 다르게 적용한 2개의 시드값을 난수 생성 초기화 함수로 전달한다. 64비트 정수로 표현할 수 있는 값을 초과하여 시드값을 입력하는 경우 해당 값은 64비트 최대 값(slient overflow)으로 래핑된다.
 

2) password.cc:randominit
 

void randominit(struct rand_struct *rand_st, ulong seed1,
                ulong seed2) { /* For mysql 3.21.# */
  rand_st->max_value = 0x3FFFFFFFL;
  rand_st->max_value_dbl = (double)rand_st->max_value;
  rand_st->seed1 = seed1 % rand_st->max_value;
  rand_st->seed2 = seed2 % rand_st->max_value;
}

 
Line 1

- rand_st: rand_st를 통해 m_rand가 가리키는 난수 구조체를 초기화

Line 3
- rand_st->max_value: 1073741823 (2^30-1)
(난수 구조체의 최대값 제한 설정)

Line 4
- rand_st->max_value_dbl: 1073741823
(난수 최대값을 double형으로 변환하여 저장)

Line 5, 6
- rand_st->seed1: 63616606 % 1073741823 = 63616606
- rand_st->seed2: 2952790139 % 1073741823 = 805306493

→ random 구조체의 시드값과 난수 생성 최대 값을 초기화한다. 초기화된 값은 실제 난수 생성 시에 사용된다.
 

3) item_func.cc:Item_func_rand::var_real
 

double Item_func_rand::val_real() {
  assert(fixed);
  rand_struct *rand;
  if (arg_count > 0) {
    if (!args[0]->const_for_execution())
      seed_random(args[0]);
    else if (first_eval) {
      /*
        Constantness of args[0] may be set during JOIN::optimize(), if arg[0]
        is a field item of "constant" table. Thus, we have to evaluate
        seed_random() for constant arg there but not at the fix_fields method.
      */
      first_eval = false;
      seed_random(args[0]);
    }
    rand = m_rand;
  } else {
    /*
      Save the seed only the first time RAND() is used in the query
      Once events are forwarded rather than recreated,
      the following can be skipped if inside the slave thread
    */
    THD *const thd = current_thd;
    if (!thd->rand_used) {
      thd->rand_used = true;
      thd->rand_saved_seed1 = thd->rand.seed1;
      thd->rand_saved_seed2 = thd->rand.seed2;
    }
    rand = &thd->rand;
  }
  return my_rnd(rand);
}

 
Line 16

- rand: m_rand가 가리키는 구조체를 3번째 줄에서 정의한 rand 구조체 포인터로 전달

Line 31
- my_rnd(rand): my_rnd 함수에 rand 포인터를 인자로 전달

→ my_rnd 함수를 호출하여 난수를 생성한다.
 

4) my_rnd.cc:my_rnd
 

double my_rnd(struct rand_struct *rand_st) {
  rand_st->seed1 = (rand_st->seed1 * 3 + rand_st->seed2) % rand_st->max_value;
  rand_st->seed2 = (rand_st->seed1 + rand_st->seed2 + 33) % rand_st->max_value;
  return (((double)rand_st->seed1) / rand_st->max_value_dbl);
}

 
Line 2, 3

- rand_st->seed1: (63616606 * 3 + 805306493) % 1073741823 = 996156311
- rand_st->seed2: (996156311 + 805306493 + 33) % 1073741823 = 727721014

Line 4
- return: 996156311 / 1073741823 = 0.92774286114400517 ≒ 0.9277428611440052
 

SELECT RAND(123.11);
+--------------------+
| RAND(123)          |
+--------------------+
| 0.9277428611440052 |
+--------------------+

 
→ 첫 번째 시드값과 두 번째 시드값을 사용하여 최종적인 난수 값 1개를 생성한다. mod로 계산된 결과값은 오른쪽 피연산자보다 큰 수가 될 수 없기 때문에 난수 생성에 사용되는 seed1과 seed2 값은 난수 최대값보다 작을 수밖에 없다. 또한 이 시드값을 난수 최대값으로(즉, 작은 값을 큰 값으로) 나누기 때문에 1 이상의 값은 절대 나올 수 없다.

그러므로, 난수 값은 0 <= a < 1 범위의 값으로만 생성된다.

Seed 값이 존재하지 않는 경우

시드값을 전달하지 않는 경우에도 동작 방식은 비슷하지만 약간의 차이가 있다.
 

SELECT RAND();

 
<최초 수행 시>

1) sql_class.cc:randominit

auto_inc_intervals_forced.clear();
   {
     ulong tmp;
     tmp = sql_rnd_with_mutex();
     randominit(&rand,
                tmp + static_cast<ulong>(reinterpret_cast<uintptr_t>(&rand)),
                tmp + (ulong)::atomic_global_query_id);
   }

 
Line 1

- auto_inc_intervals_forced.clear(): 쿼리를 수행할 때 THD 객체를 초기화(THD::init)하게 되는데, 이 때 객체 내부의 rand 구조체 멤버 변수를 초기화한다.

Line 4
- tmp: 47641308128
(sql_rnd_with_mutex(mysqld.cc) 함수에서 난수를 생성 후, tmp 변수에 할당)
 

ulong sql_rnd_with_mutex() {
  mysql_mutex_lock(&LOCK_sql_rand);
  ulong tmp =
      (ulong)(my_rnd(&sql_rand) * 0xffffffff); /* make all bits random */
  mysql_mutex_unlock(&LOCK_sql_rand);
  return tmp;
}

 
Line 5, 6, 7

- tmp + static_cast<ulong>(reinterpret_cast<uintptr_t>(&rand)): 663490581
(rand 구조체 포인터의 주소값을 정수값으로 변환하여 tmp 변수와 더하고 난수 생성에 사용될 첫 번째 시드값을 생성한다.)
- tmp + (ulong)::atomic_global_query_id: 266834210
(글로벌하게 유니크한 쿼리 id 값을 tmp 변수와 더하여 난수 생성에 사용될 두 번째 시드값을 생성한다.)

 

(lldb) p rand
(rand_struct) $346 = (seed1 = 663490581, seed2 = 266834210, max_value = 1073741823, max_value_dbl = 1073741823)

 

2) mysql_rnd.cc:my_rnd

double my_rnd(struct rand_struct *rand_st) {
   rand_st->seed1 = (rand_st->seed1 * 3 + rand_st->seed2) % rand_st->max_value;
   rand_st->seed2 = (rand_st->seed1 + rand_st->seed2 + 33) % rand_st->max_value;
   return (((double)rand_st->seed1) / rand_st->max_value_dbl);
 }

 
Line 1, 2

- rand_st->seed1: (663490581 * 3 + 266834210) % 1073741823
= 109822307
- rand_st->seed2: (109822307 + 266834210 + 33) % 1073741823 = 376656550

Line 3
- return: (109822307 / 1073741823) = 0.10227999380070715

 

SELECT RAND();
+---------------------+
| rand()              |
+---------------------+
| 0.10227999380070715 |
+---------------------+

(lldb) p thd->rand
(rand_struct) $368 = (seed1 = 109822307, seed2 = 376656550, max_value = 1073741823, max_value_dbl = 1073741823)

 
→ Seed 값이 존재하지 않는 경우 sql_class.cc 파일의 randominit 함수는 최초 한 번만 호출되고, 난수 계산에 사용된 시드값 2개는 스레드의 rand 멤버 변수에 저장하여 다음 RAND 함수의 초기 시드값으로 사용한다. 시드값을 저장하는 작업은 서버에 재접속하지 않는한 매 RAND 함수 호출 시 반복된다.

 

<두 번째 수행 시>

1) item_func.cc:Item_func_rand::fix_fields
 

bool Item_func_rand::fix_fields(THD *thd, Item **ref) {
  if (Item_real_func::fix_fields(thd, ref)) return true;

  if (arg_count > 0) {  // Only use argument once in query
    /*
      Allocate rand structure once: we must use thd->stmt_arena
      to create rand in proper mem_root if it's a prepared statement or
      stored procedure.
      No need to send a Rand log event if seed was given eg: RAND(seed),
      as it will be replicated in the query as such.
    */
    assert(m_rand == nullptr);
    m_rand = pointer_cast<rand_struct *>(thd->alloc(sizeof(*m_rand)));
    if (m_rand == nullptr) return true;
  } else {
    /*
      Save the seed only the first time RAND() is used in the query
      Once events are forwarded rather than recreated,
      the following can be skipped if inside the slave thread
    */
    if (!thd->rand_used) {
      thd->rand_used = true;
      thd->rand_saved_seed1 = thd->rand.seed1;
      thd->rand_saved_seed2 = thd->rand.seed2;
    }
  }
  return false;
}

 
Line 23, 24

- thd 포인터가 가리키고 있는 객체를 역참조하여 보면, rand 멤버 변수에 seed1, seed2 값이 저장되어 있는 것을 확인할 수 있다.
 

(lldb) frame variable thd->rand
(rand_struct) thd->rand = (seed1 = 109822307, seed2 = 376656550, max_value = 1073741823, max_value_dbl = 1073741823)

 

- thd->rand_saved_seed1: 109822307
- thd->rand_saved_seed2: 376656550

→ 이전 단계에서 저장해두었던 스레드의 시드 값을 스레드의 저장 시드(rand_saved_seed1)에 할당한다.
 

2) item_func.cc:Item_func_rand::val_real
 

double Item_func_rand::val_real() {
  assert(fixed);
  rand_struct *rand;
  if (arg_count > 0) {
    if (!args[0]->const_for_execution())
      seed_random(args[0]);
    else if (first_eval) {
      /*
        Constantness of args[0] may be set during JOIN::optimize(), if arg[0]
        is a field item of "constant" table. Thus, we have to evaluate
        seed_random() for constant arg there but not at the fix_fields method.
      */
      first_eval = false;
      seed_random(args[0]);
    }
    rand = m_rand;
  } else {
    /*
      Save the seed only the first time RAND() is used in the query
      Once events are forwarded rather than recreated,
      the following can be skipped if inside the slave thread
    */
    THD *const thd = current_thd;
    if (!thd->rand_used) {
      thd->rand_used = true;
      thd->rand_saved_seed1 = thd->rand.seed1;
      thd->rand_saved_seed2 = thd->rand.seed2;
    }
    rand = &thd->rand;
  }
  return my_rnd(rand);
}

 
Line 24

- thd->rand_used: Item_func_rand::fix_fields에서 true로 설정되었기 때문에 if문은 건너뜀

Line 29
- rand: thd 포인터가 가리키는 rand 멤버 변수의 주소 값을 rand 구조체 포인터에 할당
(rand->seed1, 2 값이 변경됨)

Line 31
- my_rnd(rand): rand->seed1: 109822307 rand->seed2: 376656550

(my_rnd 함수에 rand 포인터를 인자로 전달)

→ rand_struct 타입의 구조체 포인터 rand가 thd->rand를 가리키도록 주소 값을 할당하고, my_rnd 함수의 인자로 전달한다.
 

3) my_rnd.cc:my_rnd
 

double my_rnd(struct rand_struct *rand_st) {
  rand_st->seed1 = (rand_st->seed1 * 3 + rand_st->seed2) % rand_st->max_value;
  rand_st->seed2 = (rand_st->seed1 + rand_st->seed2 + 33) % rand_st->max_value;
  return (((double)rand_st->seed1) / rand_st->max_value_dbl);
}

 

Line 2, 3
- rand_st->seed1: (109822307 * 3 + 376656550) % 1073741823 = 706123471
- rand_st->seed2: (706123471 + 376656550 + 33) % 1073741823 = 9038231

Line 4
- return: 706123471 / 1073741823 = 0.6576287296206027
 

SELECT RAND();
+--------------------+
| rand()             |
+--------------------+
| 0.2467580877679941 |
+--------------------+

 
→ 시드값이 주어지지 않은 경우에는 위 과정처럼 최초 수행과, 이후 수행되는 단계로 나누어 난수를 생성한다.

결론

RAND 함수로 시드값을 전달하든 전달하지 않든 내부적으로 계산된 2개의 시드값은 난수 최대값에 의해 모듈러 연산이 적용되고 이는 다시 난수 최대값으로 나누어지기 때문에 결과적으로 1이상의 랜덤값은 절대 발생할 수 없다.
시드값이 존재하는 경우 난수를 생성하는 과정에 시드값 이외에 불규칙적인 요소는 없기 때문에 동일한 시드값에 대해서는 항상 동일한 난수가 생성된다.
시드값이 존재하지 않는 경우 최초 수행 시에는 스레드 유일의 시드값으로 난수를 생성하고, 두 번째 수행 시에는 이전 작업의 시드값(이전 RAND 함수의 난수 계산에 사용되었던)으로 난수를 생성하기 때문에 시드값이 고정적이지 않고 항상 다른 난수가 생성된다.