Percolator는 BigTable상에서 트랜잭션을 제공하기 위한 프로젝트이다. 이 시스템은 구글에서 2010년 6월에 논문으로 발표하였다. 하지만 실제로는 2010년 이전부터 오랜 기간 동안 구글의 검색 결과 인덱싱 시스템에서 사용되고 있었으며, 결과가 대만족이었고, 결국에는 논문으로 발표 한 것이다. 이 시스템의 동기는, 원래는 검색엔진 인덱싱을 MapReduce 작업으로 Batch 업데이트를 하고 있었는데, 업데이트를 바로 바로 적용하고 싶었다는 것이다.

특징

Transaction과 Observer기능이 구현되어 있으며, 이 시스템의 특징을 간단히 살펴보면 다음과 같다.

  • BigTable은 건드리지 않고, Client Library만 사용하여 구현되었다.
  • 트렌젝션을 위한 새로운 Table은 만들지 않고, 데이터를 저장하는 UserTable의 Percolator를 위한 Column들을 추가하여 구현되었다.
  • HBaseSI, HAcid와는 달리, 트렌젝션에 대한 정보를 여러 Row에 걸쳐서 저장한다.
  • Timestamp발급은 트렌젝션의 시작 및 종료 시 발급되며, 각각 Start Timestamp와 Write Timestamp가 발급된다. Timestamp Oracle이라는 별도의 모듈을 이용한다. Timestamp Oracle은 timestamp를 strictly increasing order로 발급하며, 한 머신이 초당 200만개의 timestamp를 발급해 준다.

동작 방법

BigTable 이나 Percolator 모두 이론적으로 설명한 논문만 나와 있을 뿐, 동작하는 소스코드는 존재하지 않는다. 실제 동작 방식에 대해서는 논문에서 확인 할 수 있다.

기본적으로 UserTable외에 다른 테이블은 필요 없으며, UserTable에는 다음과 같은 Column들이 있어야 한다. 편의상 Transaction 외에 Observer를 위한 Column은 표시하지 않는다.

  • c:data: 실제 User 의 데이터가 저장된다. Transaction에 의해 쓰여진 data는 특정 Start Timestamp에 데이터가 적히게 된다.
  • c:lock: 데이터를 in-memory로 저장하는 칼럼으로, 해당 Row에 Loc 이 걸려있는지 여부를 저장한다. Lock을 Primary lock과 Secondary lock으로 구분되는데, secondary lock 의 경우에는 primary lock에 대한 참조도 저장한다. Lock은 Start Timestamp로 적힌다.
  • c:write: 현재 유효한 데이터가 어떤 timestamp로 적혔는지 확인이 하기 위한 정보를 저장한다. Primary Lock 이 걸린 Row 의 Write 를 확인해보면 된다. 정보는 Write Stamp 에 적힌다.

위의 테이블을 이용해 아래와 같은 시퀀스로 동작한다:

  1. Execution Phase: Transaction 객체를 만들 때 Oracle 에서 Start Timestamp를 발급한다. 읽고 쓰기를 수행한다. 읽을 때는 Start Timestamp를 가지고 c:data 에서 가장 최근의 데이터를 읽어오고 write는 메모리에 리스트 형태로 저장한다.
  2. Precommit Phase: 메모리에 저장하고 있던 데이터들과 Lock을 Row 에 적는다. 이 때, RowLock 을 이용하므로 이 Operation은 Atomic하다. 이 때 가장 첫 Write의 lock이 Primary lock이 되며, 나머지들은 Secondary lock이 된다. Transaction에 관여한 모든 Row에 데이터와 Lock을 적히게 되며, Commit Phase 가 끝나거나 Lock 이 timeout 될 때 까지는 읽거나 새로운 Prewrite가 시작될 수 없다. Prewirte를 걸면서 c:write에 Start Timestamp 이후에 적힌 write가 있는지 검사하며, 이 때 conflict 발생시 Transaction은 바로 abort된다.
  3. Commit Phase: 모든 Write 에 대한 PreWrite이 성공적으로 끝나면, 해당 트렌젝션은 성공상태가 되며 다른 동시에 실행되는 WritSet이 겹치는 트렌젝션들은 무조건 Conflict이 나게 된다. 따라서, 차례대로 Lock을 지우면서 write에 값을 적게 된다. 이는 RowLock이 걸린 상태에서 진행되므로 Atmoic하다. 이 때, Primary Lock을 가장 먼저 지우게 되는데, Primary Lock이 지워지면 BigTable 성질에 의해 해당 Transaction 은 영원히 Commit 상태로 보존된다. (Durable) 만약, Secondary Lock을 지우다가 시스템이 죽어도 Primary Lock을 보고 Recovery Phase 상태로 빠지기 때문에, 데이터의 무결성이 보장된다.