{"id":5286,"date":"2024-09-13T12:44:51","date_gmt":"2024-09-13T12:44:51","guid":{"rendered":"https:\/\/dalelane.co.uk\/blog\/?p=5286"},"modified":"2024-09-13T12:44:51","modified_gmt":"2024-09-13T12:44:51","slug":"flink-can-recognize-when-youre-cheating","status":"publish","type":"post","link":"https:\/\/dalelane.co.uk\/blog\/?p=5286","title":{"rendered":"Flink can recognize when you&#8217;re cheating"},"content":{"rendered":"<h3>aka An unnecessarily complex and silly demo of <code>MATCH_RECOGNIZE<\/code><\/h3>\n<p>I play a lot of video games. That includes <a href=\"https:\/\/www.exophase.com\/user\/dalelane\/\">a lot of modern games<\/a>, but I also still love <a href=\"https:\/\/retroachievements.org\/user\/dalelane\">going back to the retro games of my childhood<\/a>. There are a lot of fun things from that era of video games that I love.<\/p>\n<p>For example, cheat codes. You\u2019d press a specific sequence of buttons on the game controller at a specific time to unlock some \u201csecret\u201d bit of content &#8211; like special abilities, special resources, or levels.<\/p>\n<p>Some of these are so ingrained in me now that my fingers just know how to enter them without thinking. The level select cheat for Sonic the Hedgehog is the best example of this: press UP, DOWN, LEFT, RIGHT, START + A during the title screen to access a level select mode that would let you jump immediately to any part of the game.<\/p>\n<p><iframe loading=\"lazy\" width=\"450\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/mvBR6jbiBW0?si=xgFGW52iOCZ3BEP_\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><br \/>\n<small><a href=\"https:\/\/youtu.be\/mvBR6jbiBW0\">level select cheat code for Sonic the Hedgehog<\/a><\/small><\/p>\n<p>With this in the back of my head, it\u2019s perhaps no surprise that when I needed to <strong>explain <a href=\"https:\/\/nightlies.apache.org\/flink\/flink-docs-master\/docs\/dev\/table\/sql\/queries\/match_recognize\/\">pattern recognition in Apache Flink<\/a><\/strong>, the metaphor I thought of first was how games of yesteryear could recognize certain button press sequences.<\/p>\n<p>If you think of each button press on the game controller as an event, then recognizing a cheat code is just a pattern of events to recognize.<\/p>\n<p>And once I thought of the metaphor &#8211; I had to build it. \ud83d\ude42 <\/p>\n<h3>Version 1 (virtual controllers)<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/github.com\/dalelane\/flink-gaming-cheat-codes\/blob\/master\/diagrams\/diagram.png?raw=true\" style=\"width: 100%; max-width: 1200px;\" alt=\"architecture diagram for the demo\"\/><\/p>\n<p>There is more detail on <a href=\"https:\/\/github.com\/dalelane\/flink-gaming-cheat-codes\/blob\/master\/README.md\">how I built this<\/a> in the git repository, but this is the overall idea for what I\u2019ve made.<\/p>\n<p><!--more-->(1) &#8211; Virtual on-screen controllers emit events to a Kafka topic every time a button is pressed.<\/p>\n<p>(2) &#8211; A Flink job consumes the events from the BUTTONPRESSES topic and looks for a sequence of button presses from any user that matches one of predefined patterns. When it recognizes a pattern, it emits an event to the CHEATS topic.<\/p>\n<p>(3) &#8211; Each user subscribes to receive a notification when their cheat was recognized.<\/p>\n<p>If you don\u2019t recognise the \u201cKonami\u201d references in the topic names, then\u2026 well, you probably stopped reading several paragraphs ago, but just in case any non-gamers have stuck with me, it\u2019s a reference to the iconic \u201c<a href=\"https:\/\/en.wikipedia.org\/wiki\/Konami_Code\">Konami Code<\/a>\u201d.<\/p>\n<p>This is what it looks like in action:<\/p>\n<p><iframe loading=\"lazy\" width=\"450\" height=\"230\" src=\"https:\/\/www.youtube.com\/embed\/pIA4lVWQqoY?si=qGi9_lzBZK_9s9Ls\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><br \/>\n<small><a href=\"https:\/\/youtu.be\/pIA4lVWQqoY\">screen recording of the demo<\/a><\/small><\/p>\n<h3>How can Flink do this?<\/h3>\n<p>I&#8217;m using Flink SQL as it\u2019s a simple way to do pattern recognition that is easy to write (and perhaps more importantly, easy to read!).<\/p>\n<h4>Getting the button presses<\/h4>\n<p>The input for the Flink job is a Kafka topic with very simple JSON messages. Each button press, from any user, is a separate message, all going onto the same topic.<\/p>\n<p>The user is identified both in the record key, and a property in the payload.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/github.com\/dalelane\/flink-gaming-cheat-codes\/blob\/master\/screenshots\/screenshot-input-topic.png?raw=true\" style=\"border: thin black solid; width: 100%; max-width: 900px;\" alt=\"screenshot of the input topic\"\/><\/p>\n<p>The message payloads look like:<\/p>\n<pre style=\"border: thin #AA0000 solid; color: #770000; background-color: #ffffc0; padding: 1em; overflow-y: scroll; overflow-x: scroll; font-size: 0.8em; white-space: pre;\">{\n    \"user\": \"dale\",\n    \"buttons\": \"B\"\n}<\/pre>\n<p>If someone presses multiple buttons at once, the message looks like:<\/p>\n<pre style=\"border: thin #AA0000 solid; color: #770000; background-color: #ffffc0; padding: 1em; overflow-y: scroll; overflow-x: scroll; font-size: 0.8em; white-space: pre;\">{\n    \"user\": \"nic\",\n    \"buttons\": \"START+A\"\n}<\/pre>\n<p>These are consumed into Flink like this:<\/p>\n<pre style=\"border: thin #AA0000 solid; color: #770000; background-color: #ffffc0; padding: 1em; overflow-y: scroll; overflow-x: scroll; font-size: 0.8em; white-space: pre;\">CREATE TABLE `buttonpresses`\n(\n    `user`        STRING,\n    `buttons`     STRING,\n    `event_time`  TIMESTAMP(3) METADATA FROM 'timestamp',\n    WATERMARK FOR `event_time` AS `event_time`\n)\nWITH (\n    'connector' = 'kafka',\n    'format' = 'json',\n    'topic' = 'KONAMI.BUTTONPRESSES',\n    ...\n);<\/pre>\n<p>There are <a href=\"https:\/\/github.com\/dalelane\/flink-gaming-cheat-codes\/blob\/master\/cheatcodes.sql#L16-L25\">more properties<\/a> relating to the connection config for the Kafka cluster, but that was the interesting bit.<\/p>\n<p>Next, I defined the patterns that the Flink job should recognize &#8211; one for each cheat code.<\/p>\n<h4>Sonic the Hedgehog<\/h4>\n<p><img decoding=\"async\" src=\"https:\/\/github.com\/dalelane\/flink-gaming-cheat-codes\/blob\/master\/screenshots\/sonicthehedgehog.png?raw=true\" style=\"width: 100%; max-width: 600px;\"\/><\/p>\n<p>First, the <strong>Sonic the Hedgehog level select<\/strong> cheat that inspired this ridiculous demo.<\/p>\n<p>I defined the different button codes to watch out for, and then define the pattern as UP, DOWN, LEFT, RIGHT, START+A<\/p>\n<pre style=\"border: thin #AA0000 solid; color: #770000; background-color: #ffffc0; padding: 1em; overflow-y: scroll; overflow-x: scroll; font-size: 0.8em; white-space: pre;\">CREATE\n    TEMPORARY VIEW `sonic` AS\nSELECT\n    `cheat_time`,\n    `user`,\n    CAST('sonic-level-select' AS STRING) AS `cheat`,\n    CONCAT('\/konami\/cheats\/', `user`) AS `target`\nFROM buttonpresses\n    MATCH_RECOGNIZE (\n        PARTITION BY `user`\n        ORDER BY event_time\n        MEASURES\n            PRESS_STARTANDA.event_time AS cheat_time\n        ONE ROW PER MATCH\n        AFTER MATCH SKIP PAST LAST ROW\n        PATTERN (\n            PRESS_UP PRESS_DOWN PRESS_LEFT PRESS_RIGHT\n            PRESS_STARTANDA\n        )\n        DEFINE\n            PRESS_UP AS buttons = 'UP',\n            PRESS_DOWN AS buttons = 'DOWN',\n            PRESS_LEFT AS buttons = 'LEFT',\n            PRESS_RIGHT AS buttons = 'RIGHT',\n            PRESS_STARTANDA AS buttons = 'START+A'\n    );<\/pre>\n<h4>Mortal Kombat<\/h4>\n<p><img decoding=\"async\" src=\"https:\/\/github.com\/dalelane\/flink-gaming-cheat-codes\/blob\/master\/screenshots\/mortalkombat.png?raw=true\" style=\"width: 100%; max-width: 600px;\"\/><\/p>\n<p>Next, the cheat code that inspired so much media hysteria when I was a kid &#8211; the <strong>Mortal Kombat blood code<\/strong>.<\/p>\n<p>I defined the different button codes to watch out for, and then define the pattern as A, B, A, C, A, B, B<\/p>\n<p>Notice that I can\u2019t use a defined event more than once in the pattern, so I worked around this by defining B press events as \u201cPRESS_B1\u201d, \u201cPRESS_B2\u201d, and \u201cPRESS_B3\u201d.<\/p>\n<pre style=\"border: thin #AA0000 solid; color: #770000; background-color: #ffffc0; padding: 1em; overflow-y: scroll; overflow-x: scroll; font-size: 0.8em; white-space: pre;\">CREATE\n    TEMPORARY VIEW `mortalkombat` AS\nSELECT\n    `cheat_time`,\n    `user`,\n    CAST('mortalkombat-blood-code' AS STRING) AS `cheat`,\n    CONCAT('\/konami\/cheats\/', `user`) AS `target`\nFROM buttonpresses\n    MATCH_RECOGNIZE (\n        PARTITION BY `user`\n        ORDER BY event_time\n        MEASURES\n            PRESS_B3.event_time AS cheat_time\n        ONE ROW PER MATCH\n        AFTER MATCH SKIP PAST LAST ROW\n        PATTERN (\n            PRESS_A1 PRESS_B1 PRESS_A2 PRESS_C PRESS_A3 PRESS_B2 PRESS_B3\n        )\n        DEFINE\n            PRESS_A1 AS buttons = 'A',\n            PRESS_A2 AS buttons = 'A',\n            PRESS_A3 AS buttons = 'A',\n            PRESS_B1 AS buttons = 'B',\n            PRESS_B2 AS buttons = 'B',\n            PRESS_B3 AS buttons = 'B',\n            PRESS_C  AS buttons = 'C'\n    );<\/pre>\n<h4>Contra<\/h4>\n<p><img decoding=\"async\" src=\"https:\/\/github.com\/dalelane\/flink-gaming-cheat-codes\/blob\/master\/screenshots\/contra.png?raw=true\" style=\"width: 100%; max-width: 600px;\"\/><\/p>\n<p>Finally, the iconic Konami code used to get an <strong>extra 30 lives in Contra<\/strong>.<\/p>\n<p>Notice that I can recognize repeated events, such as &uarr; &uarr;, by using a quantifier <code style=\"color: #770000; font-weight: bold;\">PRESS_UP{2}<\/code>.<\/p>\n<p>Notice the way that all of these include <code style=\"color: #770000; font-weight: bold;\">PARTITION BY `user`<\/code> so that with button press events coming from multiple controllers (&#8220;users&#8221;) at the same time, Flink will recognize a cheat code entered by a particular controller &#8211; where different users are entering different codes concurrently.<\/p>\n<pre style=\"border: thin #AA0000 solid; color: #770000; background-color: #ffffc0; padding: 1em; overflow-y: scroll; overflow-x: scroll; font-size: 0.8em; white-space: pre;\">CREATE\n    TEMPORARY VIEW `contra` AS\nSELECT\n    `cheat_time`,\n    `user`,\n    CAST('contra-30-lives' AS STRING) AS `cheat`,\n    CONCAT('\/konami\/cheats\/', `user`) AS `target`\nFROM buttonpresses\n    MATCH_RECOGNIZE (\n        PARTITION BY `user`\n        ORDER BY event_time\n        MEASURES\n            PRESS_A.event_time AS cheat_time\n        ONE ROW PER MATCH\n        AFTER MATCH SKIP PAST LAST ROW\n        PATTERN (\n            PRESS_UP{2}\n            PRESS_DOWN{2}\n            PRESS_LEFT1 PRESS_RIGHT1\n            PRESS_LEFT2 PRESS_RIGHT2\n            PRESS_B PRESS_A\n        )\n        DEFINE\n            PRESS_UP AS buttons = 'UP',\n            PRESS_DOWN AS buttons = 'DOWN',\n            PRESS_LEFT1 AS buttons = 'LEFT',\n            PRESS_LEFT2 AS buttons = 'LEFT',\n            PRESS_RIGHT1 AS buttons = 'RIGHT',\n            PRESS_RIGHT2 AS buttons = 'RIGHT',\n            PRESS_A AS buttons = 'A',\n            PRESS_B AS buttons = 'B'\n    );<\/pre>\n<h4>Emitting the results<\/h4>\n<p>Finally, the last thing to do is to get Flink to output events from any of the MATCH_RECOGNIZE expressions to the destination topic.<\/p>\n<pre style=\"border: thin #AA0000 solid; color: #770000; background-color: #ffffc0; padding: 1em; overflow-y: scroll; overflow-x: scroll; font-size: 0.8em; white-space: pre;\">CREATE TABLE `output`\n(\n    `cheat_time`  TIMESTAMP(3) METADATA FROM 'timestamp',\n    `user`        STRING,\n    `cheat`       STRING,\n    `target`      STRING\n)\nWITH (\n    'connector' = 'kafka',\n    'key.format' = 'raw',\n    'key.fields' = 'target',\n    'value.format' = 'json',\n    'value.fields-include' = 'EXCEPT_KEY',\n    'topic' = 'KONAMI.CHEATS',\n    ...\n);\n\nINSERT INTO `output`\n    SELECT * FROM `sonic`\n        UNION ALL\n    SELECT * FROM `mortalkombat`\n        UNION ALL\n    SELECT * FROM `contra`;<\/pre>\n<p>This gets the recognized cheat codes to the output Kafka topic.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/github.com\/dalelane\/flink-gaming-cheat-codes\/blob\/master\/screenshots\/screenshot-output-topic.png?raw=true\" style=\"border: thin black solid; width: 100%; max-width: 900px;\" alt=\"screenshot of the output topic\"\/><\/p>\n<p>The output messages are simple JSON payloads that look like this:<\/p>\n<pre style=\"border: thin #AA0000 solid; color: #770000; background-color: #ffffc0; padding: 1em; overflow-y: scroll; overflow-x: scroll; font-size: 0.8em; white-space: pre;\">{\n    \"user\": \"dale\",\n    \"cheat\": \"contra-30-lives\"\n}<\/pre>\n<h3>The serious(ish) point<\/h3>\n<p>One of the key values that Flink brings is that it allows us to process events without needing to look at each individual event in isolation, but rather to look at events in the context of other events that happen before and after it.<\/p>\n<p>Naturally, I&#8217;m not proposing sending button press events to a remote Kafka topic for analysis in Flink. I&#8217;m not saying this is a sensible way to recognize cheat codes. But it is a fun and simple way to illustrate and explain <code style=\"color: #770000; font-weight: bold;\">MATCH_RECOGNIZE<\/code>.<\/p>\n<p>In this demo, I&#8217;m looking for a certain sequence of button presses, but the general principle of wanting to recognize when a pattern of events happens has a variety of real world uses, such as recognizing customer behaviours in retail, problematic sensor readings in manufacturing, or fraudulent financial transaction events in banking.<\/p>\n<h3>Version 2 (real controllers)<\/h3>\n<p>Obviously, the next step is to do this using real game controllers \ud83d\ude09<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I used cheat-codes from retro video games as a way of explaining pattern recognition in Apache Flink<\/p>\n","protected":false},"author":1,"featured_media":5287,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[593,610,584],"class_list":["post-5286","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-code","tag-apachekafka","tag-flink","tag-kafka"],"_links":{"self":[{"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5286","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5286"}],"version-history":[{"count":0,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5286\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/media\/5287"}],"wp:attachment":[{"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5286"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5286"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5286"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}