Replication is often used to allow high performance interactive operations to the users of distributed virtual environments. This is important especially when users are geographically distributed over large networks like the Internet. On the other hand, multiple concurrent updates due to replication may lead to inconsistent views among users. This results in the need of concurrency control.
Concurrency control schemes used in the existing systems are broadly categorized into pessimistic, optimistic and prediction schemes. The pessimistic scheme interferes with users in natural interaction due to communication delay while the optimistic scheme confuses users due to repairs. The prediction scheme provides acceptable interactive performance and consistency. However, the existing prediction scheme does not scale as the number of users increases.
This paper proposes a prediction based concurrency control scheme that satisfies the needs for large scale distributed virtual environments in terms of interactive performance as the number of users increases. The proposed scheme allows real time interactions for users as the optimistic concurrency control scheme and eliminates the need for repairs as the pessimistic concurrency control scheme. We exploit the entity-centric multicast: only the users surrounding a target entity do multicast the ownership requests for ownership prediction by joining the multicast group address assigned to the entity. We have implemented the proposed scheme as a library and evaluated its performance using a test-bed application, CVRAT. Also we have performed to a set of experiments to demonstrate the efficiency and scalability of the proposed scheme. The first set of experiments was run to find an optimal geometry size of an entity-centric multicast group. We have learned from the results that the size must be at least as large as the twofold of latency. The second set of experiments was designed to demonstrate the scalability of the proposed scheme as the number of users increases. Our scheme maintains the number of messages for a single owner constant, regardless of the number of users, while an existing prediction scheme increases in proportion to the number of users. This results in a higher degree of accurate prediction probability and interactive performance. The experimental results show that the proposed concurrency control scheme provides an efficient, scalable serialization of concurrent ownership requests in large-scale distributed virtual environments.
인터넷으로 연결된 다수의 참여자를 위한 대규모 가상 공유 환경에서, 복제는 사용자로 하여금 로컬에서 데이터에 접근할 수 있게 함으로써 시스템의 상호작용 성능을 높인다. 그러나, 동시에 다수의 참여자의 데이터 접근을 허용하기 때문에 사용자 간의 인지(view)의 일관성을 보장할 수 없다. 따라서 사용자 간 일관성을 유지하기 위해 같은 객체가 동시에 변경될 수 없도록 하는 동시성 제어가 필요하다.
기존의 대부분의 시스템은 동시성 제어 방식으로 비관적 방식 또는 낙관적 방식을 사용한다. 그러나 이 방식들은 상호작용 성능이나 참여자 수에 제한이 있어 대규모 가상 환경에 확장성을 지원하지 못한다.
본 논문에서는 대규모 가상 환경을 위하여 객체 중심 예측 기반 동시성 제어 기법을 제안한다.
예측 방식은 객체를 조작할 사용자를 예측하여 그 사용자가 데이터를 조작하기 전에 미리 소유권을 주는 방식이다. 예측 방식은 소유권을 가진 사용자에게만 데이터 수정을 허용하므로 비관적 방식처럼 완벽한 일관성을 제공할 수 있고, 사용자가 데이터를 수정하기 정에 소유권을 받으므로 소유권 응답에 소요되는 지연 없이 바로 수정을 할 수가 있으므로 낙관적 방식처럼 빠른 반응 시간을 제공한다. 예측 방법의 핵심은 정확한 소유자 예측, 시간 내에 소유권 전달, 그리고 잘 못 예측 했을 경우의 빠른 복구 이다. 또한 예측에 필요한 메시지 숫자도 크지 않아야 한다.
이를 위하여 본 논문에서는 객체 중심 다중 전송 그룹을 이용한다. 관심 있는 객체 주변에 있는 참여자들은 그 객체에 할당된 다중 전송 주소로 암시적 소유권 요청을 의미하는 Join 메시지를 현재 소유자에게 보내고, 소유자 후보가 된다. 소유자는 영역 내의 모든 사용자 대신 객체 다중 전송 그룹에 참여하고 있는 사용자로부터 만 메시지를 받으므로 소유권 요청 메시지 수가 작고, 따라서 현재 소유자의 요청 처리 시간이 줄어든다. 소유자는 적은 수의 요청을 가지고 다음 소유자를 결정하므로 보다 정확한 예측을 할 수 있고, 제 시간에 소유자 후보에게 소유권을 보낼 수 있다.
현재 소유자는 소유자 후보 중 소유자 후보의 현재 거리와 객체를 향한 소유자 후보의 방향에 기초하여 다음 소유자를 예측한다. 다음 소유자는 객체를 보고 있는 소유자 후보 중 가장 가까운 거리에 있는 사용자가 된다. 너무 일찍 소유권을 양도하는 것은 소유자예측이 잘못 될 확률을 높인다. 이를 위해서 현재 소유자는 예측된 소유자의 상호 작용 성능을 감소시키지 않는 범위 내, 즉 객체 조작 바로 직전에 소유권이 도착하도록, 소유권 전송 시간을 계산하여 그 시간에 보낸다.
만일 잘못 예측했을 경우를 위해 예측 오류 발견과 복구 알고리즘이 제공된다. 복구는 두 가지 경우를 고려한다. 첫째, 예측된 소유자가 객체를 조작하지 않고 방향을 바꿔 객체로부터 멀어지기 시작하면 즉시 다음 소유자를 예측한다. 둘째, 현재 소유자가 객체를 조작하기 전에, 다른 소유자 후보로부터 충돌 감지(collision detection) 메시지를 받으면, 즉시 소유권을 전달한다.
본 논문에서 제안한 동시성 제어 방식은 ATLAS의 일부분으로써, 라이브러리로 구현되었고, 기존의 가상 환경 시스템인 CVRAT에 적용되어 검증을 마쳤다. 제안된 방식의 확장성을 증명하기 위해 수행된 실험의 결과로부터 제안된 방식이 기존의 예측 방식보다 확장성이 높음을 알 수 있었다.
