Cassandra for Data Analytics Backends

Transcript

1. @ifesdjeen
2. Cassandra Monitoring
4. Precision
5. is not same as
6. Semantics
7. is not same as
8. Anomaly detection
9. Do you see the elephant being swallowed by the snake?
10. Agenda
11. Ad-hoc queries
12. Aggregations Fast
13. Machine Learning
14. parallel queries Step 1
15. +---------------+---------------+ | timestamp | sequenceId | +---------------+---------------+
16. Used to avoid timestamp resolution collisions To ensure sub-resolution order Snapshot the data on overflow or timeout Ensures idempotence Sequence ID
17. Fighting Dispersion
18. ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts8 ts9 ts10 ts11 ts12 ts13 Range Tables
19. Full Table Scan ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts8 ts9 ts10 ts11 ts12 ts13 Start End
20. ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts8 ts9 ts10 ts11 ts12 ts13
21. Open Range Start End ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts8 ts9 ts10 ts11 ts12 ts13
22. ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts8 ts9 ts10 ts11 ts12 ts13
23. “Between” Range ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts8 ts9 ts10 ts11 ts12 ts13 Start End
24. ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts8 ts9 ts10 ts11 ts12 ts13
25. (rich query API) Step 2 add some algebra
27. Stream Fusion for rich ad-hoc queries
28. What is even Stream Fusion
29. map filter reduce
30. single step mapFilterReduce
31. data Step data cursor = Yield data !cursor | Skip !cursor | Done data Stream data = ∃s. Stream (cursor → Step data cursor) cursor
32. Stream Beginning: reading from the DB
33. map Yield data cursor → Yield (f cursor) cursor Skip cursor → Skip cursor Done → Done maps :: (a → b) → Stream a → Stream b
34. filter Yield data cursor | p data → Yield data cursor | otherwise → Skip cursor Skip cursor → Skip cursor Done → Done filters :: (a → Bool) → Stream a → Stream a
35. reduce/fold Yield x cursor → loop (f data x) cursor Skip cursor → loop data cursor Done → z foldls :: (Monoid acc) => (acc → a → acc) → acc → Stream a → acc
36. Append class Monoid a where mempty :: a mappend :: a -> a -> a -- ^ Identity of 'mappend' -- ^ An associative operation
37. class (Monoid intermediate) => Aggregate intermediate end where combine :: intermediate -> end Combine
38. data Count = Count Int instance Monoid Count where mempty = Count 0 mappend (Count a) (Count b) = Count $ a + b instance Aggregate Count Int where combine (Count a) = a Count Example
39. add some ML Step 3
40. Storing Models
41. Support Vector Machines
42. Hyperplane α·x - φ = 1
43. [ α1 α1 α1 ...αn ] ρ
44. Option 1: list<double>
45. CREATE TABLE support_vectors( path varchar, alpha list<double>, phi int, PRIMARY KEY(path))
46. Problems High deserialisation overhead Need to add PK specifiers for multiple SVs
47. Alternative: blob & byte buffers
48. Vector Representation
49. 0 8 16 24 32 40 n*8 +----+----+----+----+----+----+----+----+ | α | α | α | α | α | ... | α | +----+----+----+----+----+----+----+----+ byte address points 1 2 3 4 0 n
50. Matrix Representation
51. 0 8 16 24 32 40 n*8 +----+----+----+----+----+---------+----+ | α | α | α | α | α | ... | α | +----+----+----+----+----+---------+----+ 01 02 03 04 00 1n n*8+ 0 8 16 24 32 40 n*8 +----+----+----+----+----+---------+----+ | α | α | α | α | α | ... | α | +----+----+----+----+----+---------+----+ 01 02 03 04 00 1n m*n*8+ 0 8 16 24 32 40 n*8 +----+----+----+----+----+---------+----+ | α | α | α | α | α | ... | α | +----+----+----+----+----+---------+----+ m1 m2 m3 m4 m0 mn
52. Advantages No serialisation overhead Fast relative access Easy to go multi-dimensional Easy to implement atomic in-memory operations
53. Bayesian Classifiers
54. P(X | blue)= Number of Blue near X Total number of blue P(X | red)= Number of Red near X Total number of Red
55. [[Mean(x1), Var(x1)] [Mean(x2), Var(x3)] ... [Mean(xn), Var(xn)]]
56. 0 8 16 +---------+---------+ | Mean(x )| Var(x ) | +---------+---------+ 0 0 16 24 32 +---------+---------+ | Mean(x )| Var(x ) | +---------+---------+ 1 1 2n*8 (2n+1)*8 +---------+---------+ | Mean(x )| Var(x ) | +---------+---------+ n n byte address payloads
57. make it rocket-fast Step 4
58. Approximate Data Structures
59. Bloom Filters are basically long arrays / vectors
60. BitSet
61. 0 8 +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | +---+---+---+---+---+---+---+---+ 8 16 +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | +---+---+---+---+---+---+---+---+ 16 24 +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | +---+---+---+---+---+---+---+---+ 24 32 +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | +---+---+---+---+---+---+---+---+ bit address
62. Advantages 64 bits per 8-byte Long Easy to represent by the long-array using offsets, bit shifts and masks Easy to implement atomic in-memory operations
63. Count-min sketches are basically int matrices
64. Histograms are basically long vectors
65. Conclusions Ad-hoc queries Parallelism Lightweight DSs representation Optimisations and good API fits
66. @ifesdjeen