멱등성

음량을 20으로 맞추는 버튼을 여러 번 눌러도 음량은 20에 머무른다. 음량을 1 올리는 버튼은 누를 때마다 값을 바꾼다. 같은 연산을 거듭 적용해도 한 번 적용한 결과가 유지되는 성질을 멱등성(idempotence 또는 API 문맥의 idempotency)이라고 한다.

서버 개발자는 중복 결제를 막거나 요청 키를 저장할 때 이 말을 자주 쓰지만 수학자는 훨씬 전부터 반복 연산의 성질을 구분하는 데 썼다. 함수를 합성할 때나 HTTP 요청을 다시 보낼 때, 여러 복제본의 상태를 합칠 때도 같은 용어를 쓰는데 각 분야에서 무엇을 반복하고 어떤 결과를 비교하는지 짚어 보면 차이가 드러난다.

거듭제곱에서 가져온 이름

Benjamin Peirce는 《Linear Associative Algebra》 §25에서 idempotent라는 용어를 도입하며 별도 언급이 없으면 A² = A인 경우를 가리킨다고 정했다. 함께 정의한 nilpotent는 거듭제곱하면 0이 되는 대상을 뜻한다. 같은 원소를 거듭 곱했을 때 자기 자신이 남는지 0이 되는지에 따라 이름을 붙인 셈이다. 여기서의 Peirce는 철학자 Charles Sanders Peirce의 아버지 Benjamin Peirce다.

(원문 출처)

그림은 저작권이 만료된 1882년판 스캔의 본문 8쪽, PDF 20쪽이다. 이 판본의 서문에는 석판 인쇄본을 1870년에 배포했다는 기록이 있다. 원문은 더 높은 거듭제곱도 언급한 뒤 제곱의 경우를 기본으로 삼으므로 1870년의 배포 이력과 여기서 인용한 1882년판을 함께 밝혀둔다. 판본 정보, 서문.

한 번 구한 결과를 다시 입력한다

곱셈 자리에 함수 합성을 놓아보자. 같은 집합에서 같은 집합으로 가는 함수 f가 모든 입력 x에 대해 f(f(x)) = f(x)를 만족하면 멱등이다. 한 번 구한 함수값을 다시 입력해도 그 값이 유지되는 것이다.

정수의 절댓값은 첫 계산에서 이미 음수가 사라졌으니 다시 계산해도 같다. 반면 제곱은 2를 4로 바꾸고 그 결과를 다시 16으로 바꾼다.

def square(x):
    return x * x

assert abs(abs(-3)) == abs(-3)
assert square(square(2)) != square(2)
print(abs(-3), square(2), square(square(2)))  # 3 4 16

Python 3에서 실행할 수 있다. square(2)를 거듭 호출하면 매번 4가 나오는데 이는 같은 입력에 같은 결과를 내는 결정성(determinism)이다. 멱등성을 확인할 때는 그 4를 다음 계산에 넣는다. 같은 입력을 여러 번 주는 것과 앞선 결과에 같은 연산을 다시 적용하는 것을 나눠서 봐야 한다.

여기서 고정점도 연결된다. f(y) = y인 y를 고정점이라 부르며 멱등 함수가 내놓은 값 y = f(x)는 곧바로 고정점이다. f(y) = f(f(x)) = f(x) = y이기 때문이다. 멱등 함수는 한 번 적용한 결과를 이후에도 그대로 둔다.

반복하다가 나중에 멈추는 계산은 구별해야 한다. 음이 아닌 정수에 h(n) = n // 2를 반복하면 8은 8 → 4 → 2 → 1 → 0 → 0으로 바뀐다. 마지막에는 고정점에 도달하지만 한 번 적용한 4와 두 번 적용한 2는 다르다. 특정 입력에서 안정되거나 어떤 입력 하나가 고정점이라는 사실만으로 함수 전체의 멱등성을 얻지는 못한다.

이항 연산에서는 두 피연산자를 같게 놓고 비교한다. 집합의 합집합은 A ∪ A = A를 만족한다. 함수 합성에서 앞선 결과를 다시 넣는 경우와 식의 모양은 달라도 같은 대상을 거듭 적용했을 때 결과가 더 바뀌지 않는다는 점에서 둘 다 멱등이라 부른다.

프로그램에서는 어떤 상태를 비교하는가

음량 설정 명령은 상태 s를 다음 상태로 바꾼다. 같은 명령을 T라고 쓰면 T(T(s)) = T(s)인지 확인할 수 있다.

두 줄은 같은 초기 음량 5에서 출발하며 각 줄에서 동일한 명령을 두 번 적용한다. 두 명령의 결과 상태를 나란히 비교한 도해다.

def set_volume(state):
    return {**state, "volume": 20}

def increase_volume(state):
    return {**state, "volume": state["volume"] + 1}

initial = {"volume": 5}
assert set_volume(set_volume(initial)) == set_volume(initial)
assert increase_volume(increase_volume(initial)) != increase_volume(initial)
print(set_volume(initial), increase_volume(increase_volume(initial)))

두 함수는 실제 음량 장치를 조작하는 대신 새 딕셔너리를 반환한다. 둘 다 입력에서 새 값을 계산하지만 set_volume만 멱등이다. 실제 장치에 값을 쓰는 명령이라면 부수 효과를 일으키면서도 음량에 대해서는 같은 성질을 가질 수 있다.

불리언을 한 번 반전한 값과 두 번 반전한 값은 다르다. 또 제곱 함수는 0과 1을 유지하지만 2에서는 멱등 법칙을 만족하지 않는다. 이런 구분은 한 번의 출력만 보고 성질을 붙이거나 몇 개의 입력에서 맞았다는 이유로 전체 입력 범위에 같은 보장을 붙이는 일을 막아준다.

실제 프로그램에서는 관찰하는 상태의 범위도 정한다. 음량과 별도로 버튼을 누른 횟수까지 기록한다면 음량은 그대로여도 전체 기록은 매번 달라진다. HTTP가 나중에 '요청이 의도한 효과'를 기준으로 삼은 것도 이런 구분과 관련이 있다.

다른 명령과 섞어 실행할 때

멱등성은 같은 연산의 재적용을 설명한다. 서로 다른 연산의 순서는 교환법칙으로 따진다. 음량을 20으로 설정하는 명령과 50으로 설정하는 명령은 각각 멱등이지만 어느 쪽을 마지막에 실행하느냐에 따라 최종 음량이 달라진다.

여러 멱등 연산을 합쳐도 합성 결과가 항상 멱등인 것은 아니다. 정수 쌍에서 F(x, y) = (x, x), G(x, y) = (y + 1, y)라고 해보자. F와 G는 각각 두 번 적용해도 한 번 적용한 값과 같지만 F 다음 G를 실행하는 한 묶음을 반복하면 다음처럼 바뀐다.

위 표의 정수 쌍을 Python 3 코드로 옮기면 다음과 같다. F와 G를 각각 반복하는 경우와 두 함수를 묶어 반복하는 경우를 나란히 실행한다.

def F(point):
    x, _ = point
    return x, x

def G(point):
    _, y = point
    return y + 1, y

start = (0, 0)
once = G(F(start))
twice = G(F(once))
assert F(F(start)) == F(start)
assert G(G(start)) == G(start)
print(once, twice)  # (1, 0) (2, 1)

두 멱등 연산이 서로 교환하기까지 한다면 합성도 멱등이 된다. 합성을 두 번 펼쳤을 때 순서를 바꿔 같은 연산끼리 모은 뒤 각 연산의 멱등 법칙을 적용할 수 있기 때문이다. 여러 명령을 포함한 업무 전체를 재시도하려면 그 묶음의 효과도 살펴야 한다.

동시에 다른 사람이 상태를 바꾸는 경우도 마찬가지다. 클라이언트가 음량을 20으로 설정한 뒤 다른 사용자가 50으로 바꾼 상태에서 앞선 클라이언트가 예전 요청을 다시 보내면 음량은 다시 20이 된다. 같은 설정 명령이 멱등이라는 사실과 다른 사용자의 변경을 보존하는 일은 별개다. 뒤의 문제는 버전 조건이나 동시성 제어로 다룬다.

응답이 오지 않을 때의 재시도

클라이언트가 서버에 주문 요청을 보냈는데 응답이 오지 않는다. 서버가 요청을 받기 전에 연결이 끊겼을 수도 있고, 주문을 저장한 뒤 돌아오는 응답만 사라졌을 수도 있다. 클라이언트가 같은 요청을 다시 보낼 때 앞의 경우에는 주문을 만들 수 있지만 뒤의 경우에도 서버가 새 주문을 만들면 주문이 두 개가 된다.

Birrell과 Nelson은 1984년 논문 《Implementing Remote Procedure Calls》 §3.2에서 호출 식별자와 순서 번호를 사용해 중복 도착한 호출 패킷을 구별했다. 호출자는 응답을 받기 위해 패킷을 다시 보내고 수신 측은 같은 호출을 다시 실행할지 판단한다. 초기 RPC 설계에서도 이 두 동작을 구분해서 다뤘다. 논문과 서지, 논문 PDF.

웹에서는 1997년 HTTP/1.1 명세인 RFC 2068 §9.1이 안전한 메서드와 멱등인 메서드를 나눴다. 클라이언트가 단순 조회를 요청하는지 아니면 같은 요청을 다시 보내도 서버의 효과가 누적되지 않는지를 구별하고 연결이 끊겼을 때 자동으로 재시도할 요청을 판단하는 데 썼다. RFC 2068 §8.1.4·§9.1.

2014년 RFC 7231과 2022년 RFC 9110도 이 구분을 이어간다. 아래 표는 메서드가 정한 의미이며 서버 구현자는 그 효과를 반복 요청에서도 유지하도록 코드를 작성한다. RFC 7231 §4.2.

2010년 RFC 5789는 PATCH를 부분 변경용 메서드로 정의하면서 특정 PATCH 요청은 멱등하게 구성할 수 있다고 설명했다. 값을 20으로 지정하는 변경과 현재 값에 1을 더하는 변경은 같은 '부분 수정'이어도 반복 효과가 다르다. 기준 버전에 의존하는 변경에는 강한 ETag와 If-Match 같은 조건을 권고한다. RFC 5789 §2.

첫 DELETE가 204를, 다음 DELETE가 404를 반환해도 서버는 같은 삭제 효과를 유지할 수 있다. RFC 9110은 요청마다 로그나 이력을 남길 수 있고 응답도 달라질 수 있다고 설명한다. 클라이언트가 비교해야 할 것은 요청이 의도한 서버의 효과다. RFC 9110 §9.2.2.

서버에서 같은 자원을 조회하는 동안에도 다른 사용자가 내용을 바꾸면 GET 응답은 달라질 수 있다. 응답을 저장해 재사용해도 되는지는 캐시 가능성과 신선도 규칙으로 따로 정한다. 안전성과 멱등성, 캐시 가능성을 각각 나눠 정의하는 까닭이다. RFC 9110 §9.2.1·§9.2.3.

같은 주문을 구별하는 요청 키

클라이언트가 주문을 추가하라고 보낼 때마다 서버가 무조건 새 주문을 만든다면 재시도할 때도 주문이 늘어난다. 이를 피하려면 클라이언트와 서버가 어떤 요청들을 같은 작업으로 볼지 먼저 정한다.

(원문 출처)

Malcolm Featonby의 《Making retries safe with idempotent APIs》 PDF 4쪽·본문 3쪽 도해다. 호출자는 첫 응답을 받지 못하자 같은 식별자로 다시 요청하고 서비스는 StateStore에서 처리 상태를 조회한다. © Amazon Web Services.

사용자가 같은 상품을 같은 수량으로 두 번 주문할 수도 있으므로 서버가 요청 본문만 해시해 두 주문을 하나로 합치면 원래 의도를 잃는다. 그래서 재시도를 구별할 때는 호출자가 부여한 식별자(요청 키)를 쓴다. 같은 작업을 다시 보낼 때는 같은 키를 쓰고 별개의 주문에는 새 키를 쓴다. 서버는 호출자와 키의 범위를 정하고 같은 키에 다른 내용을 보냈을 때의 처리와 기록 보존 기간도 함께 정한다. AWS 원문.

아래는 한 프로세스의 한 스레드에서 순서대로 호출하는 Python 3 예제다. owner에는 서버가 인증한 호출자의 식별자를, key와 item에는 이미 검증한 문자열을 넣는다. 사전의 항목 하나에 주문 내용과 번호를 함께 보관하고 실행하는 동안 기록을 삭제하지 않는다.

requests = {}

def create_order(owner, key, item):
    identity = (owner, key)
    if identity in requests:
        previous_item, order_id = requests[identity]
        if previous_item != item:
            raise ValueError("KEY_REUSED_WITH_DIFFERENT_REQUEST")
        return order_id

    order_id = len(requests) + 1
    requests[identity] = (item, order_id)
    return order_id

first = create_order("alice", "request-1", "book")
retry = create_order("alice", "request-1", "book")
another = create_order("alice", "request-2", "book")
print(first, retry, another)  # 1 1 2

같은 호출자가 같은 키로 같은 상품을 보내면 앞서 만든 주문 번호를 돌려주고 새 키를 쓰면 같은 상품이라도 별개의 주문으로 만든다. 같은 키로 상품만 바꿔 create_order("alice", "request-1", "pen")을 호출하면 ValueError를 낸다. 다른 호출자의 키는 (owner, key) 쌍으로 구별한다.

이 예제의 저장소는 인메모리 사전이라 프로세스가 끝나면 주문과 재처리 기록도 함께 사라진다. 실제 서버에서는 여러 요청의 동시 실행과 장애 뒤 복구까지 처리해야 하므로 원자적 확정 문제가 뒤따른다.

서버가 처리 여부를 먼저 조회한 뒤 주문과 키를 따로 저장하면 두 요청이 동시에 '기록 없음'을 보고 각각 주문을 만들 수 있다. 주문만 저장한 직후 서버가 멈추는 경우도 있다. 그래서 요청을 식별하는 기록과 주문 효과를 하나의 원자적인 처리로 확정해야 한다. 어떤 요청이 아직 실행 중인지, 실패 뒤 다시 실행할 수 있는지, 성공 결과를 어떻게 다시 돌려줄지는 이 기록의 상태와 API 계약으로 표현한다.

요청 키는 보존하는 동안 같은 작업을 찾는 데 쓰인다. 기록을 지운 뒤 같은 키가 도착하면 서버는 새 요청과 구별할 정보를 잃을 수 있고 호출자가 키를 바꾸면 별개 요청으로 보일 수도 있다. 보존 기간과 호출자의 키 사용 규칙까지 알아야 보장 범위를 정할 수 있다.

로컬 DB 트랜잭션은 그 DB의 주문과 처리 기록을 함께 확정한다. 외부 결제의 재처리는 결제 서비스가 제공하는 식별자와 계약으로 다룬다. 멱등성은 반복 적용한 효과의 성질이고 중복 제거는 같은 작업을 식별하는 기법이므로 '정확히 한 번'이라고 표현할 때도 메시지 전달과 코드 실행, 최종 업무 효과 중 어느 것을 보장하는지 밝혀야 한다.

복제본의 상태를 합칠 때도 같은 법칙을 쓴다

2011년 Shapiro·Preguiça·Baquero·Zawirski의 《Conflict-free Replicated Data Types》는 상태를 보내 합치는 방식과 연산을 보내 적용하는 방식을 구분했다. 상태 기반 모델에서는 병합의 교환·결합·멱등 법칙과 상태 갱신의 단조성을 이용한다. 중복 전송에 대응하는 데 멱등성이 쓰이는 또 다른 계보다. 논문 §2.1–2.4.

(원문 출처)

논문 PDF 3쪽의 그림 1·2다. 왼쪽에서는 복제본이 상태를 전달하고 받은 쪽이 병합한다. 오른쪽에서는 복제본이 연산을 전달하고 받은 쪽이 적용한다. 아래의 집합 예제는 왼쪽 방식에서 쓸 수 있는 병합 연산을 보여준다.

def merge(left, right):
    return left | right

local = {"a"}
remote = {"b"}
combined = merge(local, remote)
assert merge(combined, remote) == combined
assert merge(local, remote) == merge(remote, local)
print(sorted(combined))  # ['a', 'b']

Python 3의 집합 합집합이다. 같은 원격 상태를 다시 합쳐도 결과는 유지된다. 합집합의 교환법칙은 순서를 바꾸는 경우를, 결합법칙은 여러 상태를 묶는 방법을 다룬다. 항목을 추가하며 상태를 키우고 각 복제본이 갱신을 끝내 전달한다는 조건도 함께 있어야 복제본의 수렴을 설명할 수 있다.

같은 논문의 연산 기반 모델은 인과 순서와 정확히 한 번의 전달을 가정한다. 가령 '1 증가'라는 연산 메시지를 두 번 적용하면 값은 두 번 증가한다. 상태 병합의 중복 허용 조건과 연산 메시지의 전달 조건을 구별해서 읽어야 한다. 논문 §2.3–2.4.

문맥마다 무엇을 비교하는가

수학자는 연산의 법칙을, 클라이언트와 서버는 재시도 뒤의 효과를, 복제 시스템의 설계자는 반복 병합 뒤의 상태를 비교한다. 이 범위를 정해두면 요청 키 저장, 상태 지정, 집합 병합이 각각 어떤 방식으로 멱등성을 제공하는지 읽을 수 있다.