Riak in NavCloud

How NavCloud uses Riak

1. Riak in NavCloud Tellus Team
2. NavCloud • A cloud-based storage service to allow users to seamlessly synchronise trip information between devices as well as share and receive navigation information with other people (e.g., friends or companies). • NavCloud aims to be scalable and reactive while ensuring privacy and security
3. Persistence • NavCloud uses Riak to persist user sessions, navigation information and all the meta data that we need to ensure security.
4. Difficulties • Synchronisation causes Conflicts! • Who decides which value is the most current: DataStore, Application, User?
5. Why is it Important? • Ubiquitous computing made resolving the conflicts more important • Devices go offline time to time and upon establishing connection, they will send all the data created while they were offline to the server • These data may be stale
6. How does Riak Solve Conflicts Internally? • Riak aims to be highly available • Riak has been designed as multi-node, master- less system • Any node is capable to receive commands and queries • So what is the most current version of a value?
7. How does Riak Solve Conflicts Internally? • Riak uses Vector Clocks for partial ordering.
8. What should user do? • Riak uses the same mechanism as it uses for inter-node synchronisation for new writes issued by the user • User needs to send the last seen vector clock upon any write (X-Riak-Vclock header).
9. Enough? • Sometimes Riak is not able to do auto-repair out-of-sync data: • Concurrent Data • Stale Vector Clock • Missing Vector Clock
10. What will happen? • Riak keeps all the values as Siblings.
11. Who Decides Which Value is the Current One? • There is no general solution for conflict resolution. • Conflict resolution is application specific. • Application should provide conflict resolution algorithm.
12. When does it Apply • Upon any fetch, application keeps the vector clock associated with value • Upon any write, application returns back the last seen vector clock to Riak • If the vector clock is stale, sibling will be created • Upon the next fetch, application decides which sibling is the most current one. • Application writes back the most current one to the Riak to retrieve the most current vector clock to be used in the next write
13. Conflict Resolution Difficulties • The number of IO operation may increase • Conflict resolutions may chase each other for yet another conflict resolution • Sibling explosion may happen
14. How to Prevent? • Last write wins (bucket allow_mult properties set to false so no sibling will be created)
15. You’r Kidding Me!? • Yes, it is naive!!!
16. So How to Prevent? • Solution #1: Try to be immutable in your entire life. (append only) • Solution #2: It is not always necessary to write back the result of the conflict resolution in Riak • Solution #3: Use conflict free data structures (cannot be covered in this presentation)
17. #1: Be Immutable • Try to spread information in different buckets • Use Riak capabilities (memory bucket, time to live, secondary indexes etc.)
18. #1: Be Immutable • NavCloud case: • There is a bucket to keep user sessions in NavCloud • So first, the user needs to be authenticated and the session is created in this bucket • From now on, for every authenticated request we need to keep some meta information to prevent replay attack • This meta information should be removed after some period to prevent Riak to be exploded
19. #1: Be Immutable • Initial solution: • Upon any authenticated request, we update the session entry and append that meta information to its JSON (updating phase). • Before writing back the session to Riak, we removed all expired meta information (pruning phase).
20. #1: Be Immutable
21. #1: Be Immutable • Problems of the initial solution: • For every authenticated request, a Riak write happens. So, IO operations surprisingly increased (Considering we use eLevelDB as the backend and all of compactions etc.)
22. #1: Be Immutable • Problems of the initial solution: • Updating session value may cause conflicts if user have multiple requests at the almost same time. • Conflict Resolution algorithm: Upon read, merge meta informations • But what about one of the clients poll server every 500ms? Sibling explosion + endless conflict resolutions
23. #1: Be Immutable • Working Solution: • Extracting meta information into another bucket • Key of values of that bucket: “sessionId:metaInformationValue”
24. #1: Be Immutable • How to check whether the request is repeated? • By a quick read meta information bucket. Notice that we have the key that we need to look for upon any request
25. #1: Be Immutable • How to reduce the number of IO operations? • Using multi-backend and use memory- backend for meta-information bucket. • Number of Disk IO: Zero :)
26. #1: Be Immutable • How to remove the expired meta information? • Setup time-to-live for memory-backend entries.
27. #1: Be Immutable • How to remove the expired meta information?
28. #1: Be Immutable • How to remove the expired meta information?
29. Now, We are Immutable • Sessions are immutable • Meta informations are just appended to the bucket • No need to think about siblings and conflict resolution because they are not gonna happen
30. #2: Writing back the result of resolution is not needed always • NavCloud case • User may send two destination at almost the same time to NavCloud. • Considering the tunnel case, we need to really find out which route is actually the latest.
31. #2: Writing back the result of resolution is not needed always • Initial solution • Together with destination, we send timing information to the server. • So, if sibling is created, upon read, we pick the one with the latest timestamp. • Then, we write it back to Riak and return the resulting vector clock together with the value as response.
33. #2: Writing back the result of resolution is not needed always • Each value in Riak has a vector clock associated with. • So do Siblings • After resolving the conflict, instead of writing back to Riak to retrieve the latest vector clock, application may just return the sibling vector clock which is at this moment the latest. • It will be eventually resolved in Riak
34. #2: Writing back the result of resolution is not needed always
35. Thank you Any Questions? dmitry.Ivanov@tomtom.com nami.nasserazad@tomtom.com vincenzo.Vitale@tomtom.com