-
Notifications
You must be signed in to change notification settings - Fork 1
CRDT 방식
CRDT할때,
RGA Tree와 같은 Sequence(list) CRDT를 사용해야 하는지?
- Sequence CRDT
- RGA → Array
- → Linked List → 일반적이다?
- → Tree → 복잡하다? 큰 규모의 프로젝트
- RGA → Array
RGA Tree Linked List ⇒ text에서는
Tree 까지는 필요없어 보임.
⇒ 탐색 및 삽입 삭제가 O(logN) 미만으로 가능하다는 장점
가장 큰 차이?
-
LWWR → 순서, 삽입, 삭제 보장 x, 한글 자료, 보다 구현하기 쉬움
-
RGA → 순서, 삽입, 삭제 보장 o?, 영문 자료, 보다 어려움
-
1 2 3 4 5
-
3 1 2 4 5
⇒ 3 1 2 4 5 (왜냐하면 어차피 영상 컨텐츠 갯수는 삽입 / 삭제 X)
⇒ 순서 편집
-
시간 편집! ← 근데 얘는 블록시키려고했던거 아니에요?
⇒ 애는 순서가 중요한게 아니지 않나요?!
Figma가 Grow-only set + LWWR?
https://cdn.sanity.io/files/599r6htc/regionalized/74aa5f68d0393aec0399e321101a9412c0828ea0.mp4
https://cdn.sanity.io/files/599r6htc/regionalized/e8b3d7dd4745e9fec062586d91f3eba62c2052be.mp4
[How Figma’s multiplayer technology works | Figma Blog]
상태 기반 메커니즘(CvRDT)은 모든 필수 정보가 상태에 의해 캡처되므로 추론하기 쉽습니다. 약한 채널 가정이 필요하므로 알려지지 않은 수의 복제본을 허용합니다. 그러나 상태를 전송하는 것은 대형 객체에 비효율적일 수 있습니다. 이는 델타를 전송하여 해결할 수 있지만, 여기에는 op 기반 접근 방식과 유사한 메커니즘이 필요합니다. 역사적으로 상태 기반 접근 방식은 NFS, AFS, Coda와 같은 파일 시스템과 Dynamo 및 Riak과 같은 키 값 저장소에서 사용됩니다.
작업 기반 객체(CmRDT)를 지정하는 것은 이력에 대한 추론이 필요하기 때문에 더 복잡할 수 있지만, 반대로 더 큰 표현력을 가지고 있습니다. 일부 상태가 효과적으로 채널로 오프로드되므로 페이로드가 더 간단할 수 있습니다. Op 기반 복제는 일반적으로 추적 그룹 멤버십이 필요한 안정적인 브로드캐스트가 필요하기 때문에 채널에 더 많은 요구가 있습니다. 역사적으로 Op 기반 접근 방식은 Bayou, Rover, IceCube, Telex와 같은 협력 시스템에서 사용되었습니다.
[GitHub - pfrazee/crdt_notes at 68c5fe81ade109446a9f4c24e03290ec5493031f]
최종 작성자 승리 등록부(LWW-Register)
Last-Writer-Wins Register(LWW-Register)는 각 업데이트에 타임스탬프를 연결하여 할당의 전체 순서를 만듭니다. 타임스탬프는 고유하고, 완전히 정렬되어 있으며, 인과 순서와 일치한다고 가정합니다. 즉, 할당 1이 할당 2보다 먼저 발생한 경우, 전자의 타임스탬프는 후자의 타임스탬프보다 작습니다. 이는 MAC 주소와 같은 고유한 복제본 식별자와 연결된 복제본별 카운터로 구현될 수 있습니다.
참고: 완전히 정렬된 타임스탬프는 구현하기 쉽지 않습니다. 예를 들어 벡터 클록은 다른 값이 동등할 수 있으므로 부분적인 순서만 제공합니다. (예를 들어 두 노드에서 동시 이벤트를 나타내는 <1,2>vs를 생각해 보세요 <2,1>.) 약하지만 간단한 해결책은 순서에서 노드의 주소를 사용하는 것입니다("A"의 노드가 "B"의 노드보다 앞선다). 이는 결정론적 답변과 전체 순서를 제공하지만 애플리케이션에 의미적으로 의미가 없습니다.
상태 기반 LWW-Register . 값의 유형은 모든 (로컬) 데이터 유형 X가 될 수 있습니다. 값 연산은 현재 값을 반환합니다. 할당 연산은 새 할당된 값으로 페이로드를 업데이트하고 새 타임스탬프를 생성합니다. 단조 반격자는 연관된 타임스탬프에 따라 두 값을 정렬합니다. 병합 절차는 최대 타임스탬프가 있는 값을 선택합니다. 분명히 이 데이터 유형은 CvRDT입니다.
Ops 기반 LWW-Register . 작업 할당은 소스에서 새 타임스탬프를 생성합니다. 다운스트림에서 업데이트는 새 타임스탬프가 현재 타임스탬프보다 큰 경우에만 적용됩니다. 타임스탬프가 생성되는 방식 때문에 순차적 의미론이 보존되고, 동시 할당은 실행 순서에 관계없이 타임스탬프가 가장 높은 할당만 적용되므로 전환됩니다. LWW-Register는 분산 시스템에서 널리 사용됩니다. 예를 들어, NFS와 같은 복제 파일 시스템에서 유형 X는 파일(또는 파일의 블록)입니다.
제안하고자 하는 내용을 정의하고, 결정의 이유에 대해 설명합니다.
우선, 데이터의 삽입 삭제 연산이 없기 때문에 Self-balancing을 사용하는 RGA Tree방식은 필요가 없어 보인다.
또한, Sequence CRDT의 RGA방식조차 자료가 많이 없다. 구현하기 위해서는 논문을 읽어봐야 한다.
하지만, LWW Register의 경우, 국내 자료도 많고 하기에 개발관련 공수는 크게 들꺼 같지는 않다.
또한 LWW Register로도 충분히 가능해 보이기에 난이도 측면에서 LWW Register를 제안한다.
처음에 기대했던 CRDT 동작 방식은 RGA Tree를 활용하는 방식에 가깝긴 한데, 각각 장단점이 있고 공수가 필요 이상으로 큰 것도 사실이라서 두 방법 다 상관없습니다
맞아요~
발표때는 저희가 CRDT에 대해서 어디까지 알아봤고, 제한된 기간 고려해서 이런 방식으로 결정햇다 하면 되지않을까요 저는 좋습니다~~~~~~~~~~
- 시간 제한에 적합한건 무엇인가? → LWWR
- 현재 최소한의 기능을 커버할 수 있는가? → RGA, LWWR
- 추후 개선 및 확장 가능한가? → RGA, LWWR(figma case)
⇒ LWWR, 구현하고 완성하는 과정에서 다양한 문제점이 또 발생할텐데 지금은 일단 부담이 적은 LWWR이 더 낫지 않을까.
⇒ 추후? LWWR + Logical Clock + (Tree?) = BS’ Multiplayer Technology
CYHJLWWR………??
LWWR → State Based? 네넵 약간 짬뽕느낌
그럼 이제 Task?
상관없어요~~~~~~~~~
ㅇ ㅏ 전 상관 없긴 합니다 일단 화장실 좀.. .. …ㅁㅁㅁㅁㅋㅋㅋ
저도요 둘다 상관없긴 합니다
낼아침?가나요?ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
위치 이동 지혜님 아닌가요? 길이 조절이 석영님?
그러게유 넵
팬재스처를 쓰는데 만약에 순서가 바뀌어있으면 어카냐는 말ㅇ ㅏ닌가요?
A가 이동
B가 이동
→ 우선순위가 A면, B의 로컬에서는 B의 결과를 보여주고 A의 결과물로 바꿔버리면…
저는 그건 diffable 이용할것같고
제가 걱정된건 셀 드래그해서 다른곳으로 이동할때 다른 유저도 똑같이 셀을 이동중이라면 결과는 우선순위 유저 결과에 맞춰서 디퍼블 애니메이션 그냥 때려박나요?????????
A유저가 셀을 드래그해서 옮기는 와중에 다른 유저가 동영상상태를 바꿔서 디퍼블 소스의 형태가 바뀌었다고 하면 애니메이션 도중에는 어떻게 되나요?
12345 였는데
제가 1을 들면 2345가 되잖아요
근데 다른 유저가 31245로 바꾼거에요
근데 저는 1을 들고있어요
이상황에서는 그냥 데이터소스 업데이트 반영 안하고 제기준으로 적용하나요?
(31245가 반영 안되고 12345에서 1을 옮기는 동작 그대로 가져간다)
그럼 일단 이렇게 생각할게요~~!
유저가 1을 들고있는거가 말이안되지않아요?? 31245를 반영하려면
근데 업데이트된 31245 인덱스에 맞춰야하지않아요?? 어쨋든 제가 셀을 들고있는데 31245로 바뀐걸 반영해야하잖아요
그럼 일단 수정중인 사람에게는 다른 변경사항이 반영 안되고 그상태 그대로보내는걸로 할게요
그럼 그렇게 가는걸로 생각하게쓰빈다~~~~~!!
가정
→ A가 수정 중에는 다른 이벤트 결과를 받지 않도록 블락
→ B 수정 후 이벤트 보냄
→ A가 수정을 완료하면 우선 내 이벤트를 보낸 뒤, 블락을 풀고 이벤트를 받아서 처리
→ B가 A 이벤트 받아서 적용
→ A도 다시 이벤트 받아서 A 적용?
= 결과로 A가 가장 나중에 수정했기에 A 적용
1 2 3 4 5
3
1 2 4 5
3 1 2 4 5
발표 → 건우
학습공유 AVFoundation → 지혜
새로운 PR에 할건데 ㅠㅠ 좀 걸리겟네용
테스크 → 내일 스크럼
오오오오오오ㅗ