search

paust-team / paust-db

GNU General Public License v3.0
6 stars 5 forks source link

Fix rowkey duplication problem due to salt generation #144

Open dragon0170 opened 5 years ago

dragon0170 commented 5 years ago

Reference

131

현재 rowkey에 구성에 사용되는 salt는 client에서 uint16값을 random하게 생성되고 있습니다. 하지만 이는 동일한 timestamp 값에 대해 매우 작은 확률로 rowkey가 겹칠 수 있습니다. 두 데이터의 rowkey가 겹치는 경우 하나의 데이터가 다른 데이터에 덮어씌어지므로 두 데이터가 정상적으로 저장되지 않습니다. 따라서 salt가 같을 때 rowkey가 중복되는 문제를 해결할 필요가 있습니다.

이 문제를 해결하기 위해서는 salt의 생성방식을 바꾸거나 rowkey의 구조를 변경하는 방법이 있어보입니다.

1dennispark commented 5 years ago

으음... 이 경우에 적절할지는 모르겠지만 rocksdb의 merge 기능도 고려해볼만합니다.

그 이전에 multi value를 유지해야하는가 overwrite가 되는것이 오히려 바람직한가 고민해볼 필요가 있습니다.

2019년 3월 18일 (월) 오후 4:23, Kevin Choi notifications@github.com님이 작성:

Reference

131 https://github.com/paust-team/paust-db/issues/131

현재 rowkey에 구성에 사용되는 salt는 client에서 uint16값을 random하게 생성되고 있습니다. 하지만 이는 동일한 timestamp 값에 대해 매우 작은 확률로 rowkey가 겹칠 수 있습니다. 두 데이터의 rowkey가 겹치는 경우 하나의 데이터가 다른 데이터에 덮어씌어지므로 두 데이터가 정상적으로 저장되지 않습니다. 따라서 salt가 같을 때 rowkey가 중복되는 문제를 해결할 필요가 있습니다.

이 문제를 해결하기 위해서는 salt의 생성방식을 바꾸거나 rowkey의 구조를 변경하는 방법이 있어보입니다.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/paust-team/paust-db/issues/144, or mute the thread https://github.com/notifications/unsubscribe-auth/AqM4Skh-Ef7gikmBmVnFObpBrM-0F-ZLks5vXz7WgaJpZM4b5G8n .

dragon0170 commented 5 years ago

그 이전에 multi value를 유지해야하는가 overwrite가 되는것이 오히려 바람직한가 고민해볼 필요가 있습니다.

해당 문제에 대해 andrew, elon과 디스커션한 내용입니다.

현재 구조에서는 동일한 timestamp에 대해서 multi value write가 가능하지만 1/2^16 확률로 rowkey의 salt가 겹칠 수 있습니다. timestamp와 salt가 동일한 경우 해당 rowkey의 데이터는 overwrite되기 때문의 기존의 put한 데이터의 loss가 생깁니다.

우리는 수많은 유저가 데이터를 저장할 때 timestamp가 겹치는 경우가 분명이 있을 것이라 생각하고 이 경우 multi value write가 가능한 것은 유지하는 것이 좋다고 생각합니다. 하지만 overwrite로 인한 데이터 loss는 최대한 줄여야 한다고 생각합니다. 그리고 "어떤 상황에서 데이터 loss가 발생할 수 있고 데이터 loss가 발생할 확률은 얼마다"라는 것을 알려주어야 한다고 생각합니다.

우리는 rowkey에 metadata에 대한 정보를 추가해서 rowkey의 duplication을 줄이는 방법을 생각해보았습니다. 한가지 예시로 rowkey를 timestamp, salt, metadata의 hash값으로 구성하는 것이 있겠네요. 이 경우에는 timestamp, metadata가 모두 동일한 경우에만 1/2^16 확률로 rowkey가 겹치게 되므로 데이터 loss가 생길 확률이 더 줄어듭니다. 이와 같이 duplication을 줄이는 방향으로 rowkey를 변경할 필요가 있습니다.

하지만 데이터 loss가 발생하는 확률을 줄이더라도 또 하나의 문제가 있습니다. A라는 유저와 B라는 유저가 동일한 metadata(현재는 ownerId, qualifier)를 갖고 paust-db에 put을 하게되는 경우 query시 해당 데이터를 누가 저장했는지 알 수 없습니다. 관련된 예시로는 예전에 말했던 chatting app의 log를 paust-db에 저장할 때 누군가 악의적으로 채팅 log를 조작할 수 있는 것이 있습니다.

이 문제를 해결할 수 있는 방법으로는 data를 put할 때 유저에 대한 인증 과정을 거치는 것이 있습니다만 이를 적용하는 것에 대해서는 논의가 필요해 보입니다.

1dennispark commented 5 years ago

salt key를 UUID로 저장하기 떄문에 발생하는 것일 수 있습니다. 정말로 rowkey가 중복되는 것을 피하려면 Counter를 적용할 수 있습니다.

rocksdb는 counter를 생성하기에 적절한 솔루션이 존재합니다. https://github.com/facebook/rocksdb/wiki/Merge-Operator#user-content-client-code-change 를 보시면 rocksdb는 최소한의 성능 감소로 counter를 구현할 수 있는 방법을 제시해주고 있습니다.

elon0823 commented 5 years ago

salt key를 UUID로 저장하기 떄문에 발생하는 것일 수 있습니다. 정말로 rowkey가 중복되는 것을 피하려면 Counter를 적용할 수 있습니다.

rocksdb는 counter를 생성하기에 적절한 솔루션이 존재합니다. https://github.com/facebook/rocksdb/wiki/Merge-Operator#user-content-client-code-change 를 보시면 rocksdb는 최소한의 성능 감소로 counter를 구현할 수 있는 방법을 제시해주고 있습니다.

counter 는 rocksdb 에 저장할때 중복저장을 피하기 위함으로 생각되는데, 그전에 중복을 허용할 것인지 아니면 overwrite 를 할 것인지에 대한 정책 또한 정할 필요가 있지않을까합니다. counter 를 통해서 같은 rowkey 에 대해 중복을 피한다고 해도 meta 가 같다고 가정했을때 query를 날리면 데이터가 2개 날라오는 문제는 그대로이지 않나요?

elon0823 commented 5 years ago

rocksdb 상에서 merge 쪽 implementation 에서 중복된 키라면 못쓰게하면 클라이언트엔 fail 로 날라올태니 그 때 다시 클라이언트상에서 put 요청을 해서 쓰도록 하는 방법도 있겠네요. 서비스관점에서 데이터 put 실패했을때 클라이언트가 다시 쓰도록 유도하는 것이 좋은 로직인가는 좀 더 생각해봐야겠지만요

dragon0170 commented 5 years ago

rocksdb 상에서 merge 쪽 implementation 에서 중복된 키라면 못쓰게하면 클라이언트엔 fail 로 날라올태니 그 때 다시 클라이언트상에서 put 요청을 해서 쓰도록 하는 방법도 있겠네요. 서비스관점에서 데이터 put 실패했을때 클라이언트가 다시 쓰도록 유도하는 것이 좋은 로직인가는 좀 더 생각해봐야겠지만요

associative merge operator의 Merge 함수 interface는 아래를 참고해보면 existing_value에 따라 분기가 나뉘겠네요.

virtual bool Merge(const Slice& key,
                         const Slice* existing_value,
                         const Slice& value,
                         std::string* new_value,
                         Logger* logger) const = 0;

timestamp를 현재는 client에서 생성해서 보내주고 있는데 이를 paust-db client interface 내에서 생성하거나 paust-db master application 내에서 생성하는 방식으로 바뀔 수 있다는 걸 염두해두면 좋겠네요.

동일한 timestamp, metadata에 대해서 중복된 데이터를 put할 때의 처리는 크게 아래와 같을 것 같네요.

dragon0170 commented 5 years ago

논의 결과 최종적으로는 paust-db의 초기 구성을 할 때 중복 저장이 되게 할지, overwrite가 되도록 할지 설정할 수 있도록 하는 것이 좋습니다.

우선 ab test 관점에서 보았을 때 현재는 rowkey가 중복될 가능성이 있고 해당 경우 overwrite가 되는 방식이므로 다음으로 개발할 feature는 rowkey가 중복되지 않고 write 되는 방식입니다. 이는 위에서 말한 것처럼 rocksdb의 merge기능을 이용해 counter 방식으로 rowkey를 생성하는 것을 생각해볼 예정입니다.

dragon0170 commented 5 years ago

우선 가장 간단하게 생각나는 counter로 구현한 중복방지 rowkey 설계입니다. 원래는 merge를 활용해보려 했는데 merge function의 결과로 성공/실패만 알고 existing value나 update된 새로운 value의 값을 알 수 없는 것 같아 고민입니다...ㅜㅜ 더 좋은 counter나 rowkey 구성이 필요해보입니다.

rowkey구조는 다음과 같습니다. rowkey = timestamp + count value put되는 데이터의 timestamp마다 counter가 존재하고 count value는 해당 counter에서 가져오게 됩니다. 예를 들면 A인 timestamp를 가진 data1이 put되었을 경우 서버에서는 A를 rowkey로 해서 rocksdb의 value를 get 합니다. 만약 value가 없을 경우 A라는 timestamp를 가진 데이터가 처음으로 put되었다는 것을 의미합니다. 이 때는 A rowkey의 value값을 1로 put하고 data1을 저장할 rowkey는 A + 0이 됩니다. 이후 또 A인 timestamp를 가진 data2가 put이 되었다고 해봅시다. 이 경우 마찬가지 과정으로 A를 rowkey로 해서 rocksdb의 value를 get 합니다. value값은 1이므로 data2를 저장할 rowkey는 A + 1이 되고 A rowkey의 value값을 기존의 1에서 1을 더한 2로 put 합니다.

위와 같은 방식으로 저장을 하면 중복은 방지가 되겠지만 performance 적인 문제가 발생할 거 같네요. 위 방법은 결국 데이터를 put을 할 때 마다 매번 counter의 value에 대한 get, put이 1번씩 일어나는 구조라서 매우 비효율적입니다. 지금 당장은 해결책이 떠오르지 않습니다만 rocksdb의 merge를 활용하고 counter에 대한 get, put을 최대한 줄일 수 있는 구조를 생각해보려고 합니다.

dragon0170 commented 5 years ago

andrew, elon과 논의해본 결과, rocksdb 내에 timestamp마다 counter를 두는 것은 저장공간도 차지하고 데이터 put 시 효율적이지도 않은 것 같습니다. 중복 방지를 위해서라면 굳이 억지로 counter를 rocksdb에 도입하는 것이 아니라 ABCI server 상에서 데이터를 저장할 때 count value를 추가해서 rowkey를 구성하는 것이 더 좋아보입니다.

그래서 매 블록마다 메모리 상의 counter를 ABCI server에서 범용적으로 사용하는 방식을 테스트해볼 예정입니다. 즉, 특정 block에 대한 ABCI cycle을 돌 때 시작 시 counter value를 0으로 초기화하고 deliverTx 실행 시마다 counter value를 1씩 증가시키면서 rowkey = timestamp + counter value 구조로 데이터를 저장하는 것을 의미합니다.

elon0823 commented 5 years ago

중복에 대한 case 는 counter 를 이용하여 해결 가능하다는 것을 실험을 통해 알게 되었으니, 추후에 engineering 단계에서 실험한 내용을 적용시켜 네트워크를 구성할때 동일한 데이터에 1.중복을 허용할지 2.overwrite 할 지를 처리해주면 될 것 같습니다.