This post is a start of a new topic on NoSQL\/Big Data<\/p>\n
Today I will give some tricks I found out with Apache Cassandra<\/strong> during my work on Tatami<\/a> and point out some gotchas to avoid.<\/p>\n Those who are not familiar with the Cassandra data model, you can have a look there:<\/p>\n <\/p>\n First we start with good things, the tricks that will help you be more efficient with Cassandra<\/strong> The first disappointment when people discover Cassandra is the lack of support for searching. We are so used to the SQL “like %xxx%<\/strong>” syntax that we take it for granted.<\/p>\n With Cassandra<\/strong>, they is no such syntax for text search. So are we done ?<\/p>\n Of course not. There is a small trick that rely on the clever use of the column sort provided natively by Cassandra.<\/p>\n Since we know that all columns are sorted by their type (string, number, date, UUID …) we can take avantage of this sorting for text search.<\/p>\n Let’s suppose we have a list of user logins and we put them in a wide row<\/strong> as string-ordered column name:<\/p>\n Naturally, Cassandra<\/strong> will use lexicographic ordering for these column names.<\/p>\n Now we want to search for all logins starting with “jdubois”<\/strong>. With a quick SliceQuery<\/strong>, setting start<\/strong> = “jdubois<\/strong>“, end<\/strong> = “”<\/strong>, we will get:<\/p>\n That’s not exactly what we want. Indeed Cassandra<\/strong> filters out the first login (“jduboi<\/strong>“) because it is sorted lexicograpically before the start limit “jdubois<\/strong>“.Since the end limit was set to empty string, Cassandra<\/strong> will take all entries following the first exact match (if there is a match). If there is no exact match, Cassandra still takes all logins that follow lexicograpically the start limit<\/strong>.<\/p>\n If we have set start<\/strong> = “jduboisa<\/strong>“, end<\/strong> = “”<\/strong>, we would have got:<\/p>\n Now if we want to implement the “start with jdubois<\/strong>” search semantic, we need find the way to make Cassandra<\/strong> stop scanning if there is no partial match. The trick is to set the end limit as the start limit, with the last letter being advanced one notch<\/strong>.<\/p>\n For start<\/strong> = “jdubois<\/strong>“, end<\/strong> = “jduboit”<\/strong>, we will get:<\/p>\n This time, the “contains” sematic is respected. Of course we need to get rid of the last entry “jduboit<\/strong>” because it does not match our input. Cassandra<\/strong> selected it because all the SliceQuery range limits are included in the search by default (it’s not possible to exclude the limit bounds currently).<\/p>\n This technique only address the requirement for “startWith<\/strong>” search semantic. For “endWith<\/strong>” semantic, you can reverse all logins and proceed similarly.<\/p>\n For “contains<\/strong>” search semantic I did not find so far any solution apart from in-memory filtering… But honestly if you have complex search requirements it’d be better to look at dedicated solutions like ElasticSearch<\/a>.<\/p>\n <\/p>\n Cassandra provides, among all the primitive types, support for UUID values of type 1 (time and server based) and type 4 (random).<\/p>\n The primary use of UUID<\/strong> (U<\/strong>nique U<\/strong>niversal ID<\/strong>entifier) is to obtain a really unique identifier in a potentially distributed environment.<\/p>\n One naive idea when working with unique identifier is to rely on System<\/strong>.currentTimeMillis()<\/em>. It should work fine for most “basic” applications but for the use case of Big Data where we need to deal with thousands or millions of objects per second, it is clearly not sufficient. In one millisecond your server may create more than one message. System<\/strong>.currentTimeMillis()<\/em> is not fine-grain enough to guarantee unicity.<\/p>\n The JDK also provides System<\/strong>.nanoTime()<\/em> but the Javadocs clearly state that it should be used only to compute duration, not as a time reference.<\/p>\n So we end up with the good old UUID.<\/p>\n Cassandra<\/strong> does support version 1 UUID. It gives you an unique identifier by combining the computer\u2019s MAC address and the number of 100-nanosecond intervals since the beginning of the Gregorian calendar.<\/p>\n As you can see the precision is only 100 nanoseconds, but fortunately it is mixed with a clock sequence<\/strong> to add randomness. Furthermore the MAC address is also used to compute the UUID so it’s very unlikely that you face collision on one cluster of machine, unless you need to process a really really huge volume of data (don’t forget, not everyone is Twitter or Facebook).<\/p>\n One of the most relevant use case for UUID, and espcecially TimeUUID, is to use it as column key<\/strong>. Since Cassandra column keys are sorted, we can take advantage of this feature to have a natural ordering<\/strong> for our column families.<\/p>\n The problem with the default com.eaio.uuid.UUID<\/strong> provided by the Hector client is that it’s not easy to work with. As an ID you may need to bring this value from the server up to the view layer, and that’s the gotcha.<\/p>\n Basically, com.eaio.uuid.UUID<\/strong> overrides the toString()<\/em> to gives a String representation of the UUID. However this String formatting cannot be sorted lexicographically…<\/p>\n Below are some TimeUUID generated consecutively:<\/p>\n “2b6e3160-c482-11e1-addf-20cf309ff6dc”.compareTo(“8e4cab00-c481-11e1-983b-20cf309ff6dc”) gives -6<\/strong> meaning that “2b6e3160-c482-11e1-addf-20cf309ff6dc<\/strong>” is less\/before “8e4cab00-c481-11e1-983b-20cf309ff6dc<\/strong>” which is incorrect.<\/p>\n The current textual display of TimeUUID is split as follow:<\/p>\n time_low – time_mid – time_high_and_version – variant_and_sequence – node<\/strong><\/p>\n If we re-order it starting with time_high_and_version, we can then sort it lexicographically:<\/p>\n time_high_and_version – time_mid – time_low – variant_and_sequence – node<\/strong><\/p>\n The utility class is given below:<\/p>\n The TimeUUIDs become:<\/p>\n Now we get “11e1-c481-8e4cab00-983b-20cf309ff6dc<\/strong>“.compareTo(“11e1-c482-2b6e3160-addf-20cf309ff6dc<\/strong>“) = -1<\/p>\n <\/p>\n If you are using Cassandra, it means that your application is dealing with a huge volume of data. If it’s not then there is something wrong with your data model and you probably should look at conventional SQL databases instead of NoSQL.<\/p>\n With high volume comes the need to page data. For this purpose, the SliceQuery<\/strong> comes to the rescue again!<\/p>\n Let’s say that your mail application manages a list of messages in the inbox. The messages are reverse-ordered with respect to their reception time. <\/p>\n The inbox will only display the latest N messages. Upon user click on “Next” it will fetch the following N messages and so on.<\/p>\n To build a paging system, first we should create an index for the message ID. It is merely a column family with column name of type TimeUUID <\/strong>(see above) for time ordering and column value pointing to a message ID.<\/p>\n To fetch the first N messages, just use SliceQuery<\/strong> with:<\/p>\n for descending sort order. Latest messages first.<\/p>\n Once to get the list of first N messages, it should be pretty easy to get the message ID of the last element in the list. To fetch the next N messages:<\/p>\n And that’s all !<\/p>\n <\/p>\n And now the traps that you should absolutely avoid if you don’t want to suffer endless hours of debugging \ud83d\ude42<\/p>\n <\/p>\n In the latest version of Cassandra<\/strong> composite column key<\/strong> has been added. What is it ?<\/p>\n Basically instead of having a simple column key (column name) of one type, you can aggregate several values (also called components<\/strong>) of several types to form one unique column key.<\/p>\n Examples: login:location<\/strong>, surname:firstname:age<\/strong> …<\/p>\n In the earlier days, people used to concatenate their fields a string value with a arbitrary chosen separator to form a kind of composite key. But this approach is rather limited because the sort order is lexicographical (string). It works well when all the component are of string type because concatenating them does not modify the sort order. If the component are of different types, you’re screwed.<\/p>\n Now with the composite type, it is possible to mix components of different types!<\/p>\n Cool right ? <\/p>\n Not really indeed …<\/p>\n Let’s look at a simple example. We have a list of users and want to find them by their login, age or city. Usually we would have to create 3 indexes, one to index the login, one for the age and one for the city. Now the naive developer will create a composite column key as login : age : city<\/strong>.<\/p>\n Let’s consider the following data set:<\/p>\n Now let’s perform a SliceQuery with composite type. If we want to retrieve all people whose login is exactly “bob”:<\/p>\n The result is:<\/p>\n Please notice the line 5<\/strong> in the above code. Intuitively we would set Composite.ComponentEquality.EQUAL<\/strong> for the end value but paradoxically Cassandra will return no result if set to EQUAL<\/strong>. So I set it to GREATER_THAN_EQUAL<\/strong>.<\/p>\n Now what if we want to get all users whose login start with “bob” <\/strong>?<\/p>\n The result is:<\/p>\n Please notice the trick at line 5<\/strong>. We shift the last letter of “bob<\/strong>” up one notch and we use LESS_THAN_EQUAL<\/strong>. This time the result includes “boby<\/strong>”<\/p>\n Now we want to get users whose login = “bob” and having 32 years old.<\/p>\n The result is:<\/p>\n Please notice that now for the first component (login) we can both use EQUAL for start and end limit (line 5). For the second component (age) again EQUAL for start limit and GREATER_THAN_EQUAL for end limit if we want an exact match.<\/p>\n What if we want users whose login = “bob” and age between 32 and 35 years old inclusive ?<\/p>\n The result is:<\/p>\n Again, we need to set 36<\/strong> and LESS_THAN_EQUAL to the end limit to retrieve bob:35:Seattle<\/strong> because the LESS_THAN_EQUAL operator is a strict <<\/strong><\/p>\n Now, we want to get all users with age = 27<\/p>\n The result:<\/p>\n It is mandatory to provide a value for the first component. Since we do not want to filter by login, I set “” for start limit and Character.MAX_VALUE (line 6<\/strong>) for end limit.<\/p>\n We expect Cassandra<\/strong> to return back only alice:27:New York<\/strong> and jack:27:Los Angeles<\/strong> but it returns all the users! Why ?<\/p>\n Simply because of the way how Cassandra orders composite columns. The composite columns are ordered first by its first component, then by its second component etc… To get all users of 27 years old, Cassandra<\/strong> need to scan all possible values for the first composite component (login) before it can access the second one (age). In the end it needs to retrieve all the columns because there is no other way to process.<\/p>\n Most developers naively think that composite columns provides them multi-dimensional axes for data filtering but it’s just an illusion. The way Cassandra<\/strong> sort columns is the real limitation.<\/p>\n The only way to use composite columns effectively is to filter<\/p>\n <\/p>\n With Cassandra you can filter data either using the row key as search key (exact match or range match with RangeQuery<\/strong>) or using the column key as described previously.<\/p>\n This leads to main 2 designs: wide row<\/strong> and skinny row<\/strong>.<\/p>\n A wide row<\/strong> pattern consists of a column family structure with very few rows and, for each rows, many many columns.<\/p>\n A skinny row<\/strong> pattern consists of a column family structure with many rows and for each row, very few columns.<\/p>\n Each of those design matches different technical needs. However for indexing data, the skinny row<\/strong> pattern should be avoided.<\/p>\n Basically you build indexes to accelerate data access and retrieval. Instead of scanning and reading values from various column families we only need to read data from one column family, the index.<\/p>\n Now what if the index data is spread over many Cassandra nodes ? Well the cluster need to fetch them all from different node and merge them. It has a cost.<\/p>\n Why does it occur ? Because when you index data using the row name as search key, with a RandomPartioner (default configuration) a hash is computed from the row key and the data is sent to a node depending on this hashed value.<\/strong><\/p>\n Of course you can choose a OrderPreservingPartioner<\/strong> but it has many drawbacks, unbalanced cluster structure to cite the few (complete details here<\/a>). Officially the use of OrderPreservingPartioner<\/strong> is strongly not recommended unless you do not have any choice.<\/p>\n So it let us with the wide row<\/strong> pattern as indexing solution and this is the right choice. All columns of a row are stored on the same node, in the same data block and sorted on disk so accessing and scanning these columns is extremely fast. And that’s what you want for your index !<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" This post is a start of a new topic on NoSQL\/Big Data Today I will give some tricks I found out with Apache Cassandra during my work on Tatami and point out some gotchas to avoid. Those who are not…\n
I Tricks<\/h1>\n
\n <\/p>\nA Simple text-based searching<\/h3>\n
\n
\n
\n
\n
B Lexicographic TimeUUID ordering<\/h3>\n
\n
\npublic static String reorderTimeUUId(String originalTimeUUID)\n\t{\n\t\tStringTokenizer tokens = new StringTokenizer(originalTimeUUID, "-");\n\t\tif (tokens.countTokens() == 5)\n\t\t{\n\t\t\tString time_low = tokens.nextToken();\n\t\t\tString time_mid = tokens.nextToken();\n\t\t\tString time_high_and_version = tokens.nextToken();\n\t\t\tString variant_and_sequence = tokens.nextToken();\n\t\t\tString node = tokens.nextToken();\n\n\t\t\treturn time_high_and_version + '-' + time_mid + '-' + time_low + '-' + variant_and_sequence + '-' + node;\n\n\t\t}\n\n\t\treturn originalTimeUUID;\n\t}\n<\/pre>\n\n
C Paging data with sorted column name<\/h3>\n
\n
\n
II Traps<\/h1>\n
A The real semantic of composite column key<\/h3>\n
\n
\nComposite start = new Composite();\nstart.addComponent(0, "bob", Composite.ComponentEquality.EQUAL);\n\nComposite end = new Composite();\nend.addComponent(0, "bob", Composite.ComponentEquality.GREATER_THAN_EQUAL);\n\nList<HColumn<Composite, Object>> columns = HFactory.createSliceQuery(keyspace, se, ce, oe)\n\t.setColumnFamily("composite").setKey("test")\n\t.setRange(start, end, false, 100).execute().get().getColumns();\n<\/pre>\n
\n
\nComposite start = new Composite();\nstart.addComponent(0, "bob", Composite.ComponentEquality.EQUAL);\n\nComposite end = new Composite();\nend.addComponent(0, "boc", Composite.ComponentEquality.LESS_THAN_EQUAL);\n\nList<HColumn<Composite, Object>> columns = HFactory.createSliceQuery(keyspace, se, ce, oe)\n\t.setColumnFamily("composite").setKey("test")\n\t.setRange(start, end, false, 100).execute().get().getColumns();\n<\/pre>\n
\n
\nComposite start = new Composite();\nstart.addComponent(0, "bob", Composite.ComponentEquality.EQUAL);\nstart.addComponent(1, 32, Composite.ComponentEquality.EQUAL);\n\nComposite end = new Composite();\nend.addComponent(0, "bob", Composite.ComponentEquality.EQUAL);\nend.addComponent(1, 32, Composite.ComponentEquality.GREATER_THAN_EQUAL);\n\nList<HColumn<Composite, Object>> columns = HFactory.createSliceQuery(keyspace, se, ce, oe)\n\t.setColumnFamily("composite").setKey("test")\n\t.setRange(start, end, false, 100).execute().get().getColumns();\n<\/pre>\n
\n
\nComposite start = new Composite();\nstart.addComponent(0, "bob", Composite.ComponentEquality.EQUAL);\nstart.addComponent(1, 32, Composite.ComponentEquality.EQUAL);\n\nComposite end = new Composite();\nend.addComponent(0, "bob", Composite.ComponentEquality.EQUAL);\nend.addComponent(1, 36, Composite.ComponentEquality.LESS_THAN_EQUAL);\n\nList<HColumn<Composite, Object>> columns = HFactory.createSliceQuery(keyspace, se, ce, oe)\n\t.setColumnFamily("composite").setKey("test")\n\t.setRange(start, end, false, 100).execute().get().getColumns();\n<\/pre>\n
\n
\nComposite start = new Composite();\nstart.addComponent(0, "", Composite.ComponentEquality.EQUAL);\nstart.addComponent(1, 27, Composite.ComponentEquality.EQUAL);\n\nComposite end = new Composite();\nend.addComponent(0, Character.MAX_VALUE + "", Composite.ComponentEquality.EQUAL);\nend.addComponent(1, 27, Composite.ComponentEquality.GREATER_THAN_EQUAL);\n\nList<HColumn<Composite, Object>> columns = HFactory.createSliceQuery(keyspace, se, ce, oe)\n\t.setColumnFamily("composite").setKey("test")\n\t.setRange(start, end, false, 100).execute().get().getColumns();\n<\/pre>\n
\n
\n<\/strong><\/p>\n\n
B Row or colum indexing ? The (not so) difficult choice<\/h3>\n
Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"_links":{"self":[{"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1227"}],"collection":[{"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1227"}],"version-history":[{"count":0,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1227\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1227"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}