{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/44096254","id":44096254,"diff_hunk":"@@ -0,0 +1,304 @@\n+/*\n+ * Licensed to the Apache Software Foundation (ASF) under one or more\n+ * contributor license agreements.  See the NOTICE file distributed with\n+ * this work for additional information regarding copyright ownership.\n+ * The ASF licenses this file to You under the Apache License, Version 2.0\n+ * (the \"License\"); you may not use this file except in compliance with\n+ * the License.  You may obtain a copy of the License at\n+ *\n+ *    http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing, software\n+ * distributed under the License is distributed on an \"AS IS\" BASIS,\n+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ * See the License for the specific language governing permissions and\n+ * limitations under the License.\n+ */\n+\n+package org.apache.spark.streaming.util\n+\n+import java.io.{ObjectInputStream, ObjectOutputStream}\n+\n+import scala.reflect.ClassTag\n+\n+import org.apache.spark.SparkConf\n+import org.apache.spark.streaming.util.OpenHashMapBasedStateMap._\n+import org.apache.spark.util.collection.OpenHashMap\n+\n+/** Internal interface for defining the map that keeps track of sessions. */\n+private[streaming] abstract class StateMap[K: ClassTag, S: ClassTag] extends Serializable {\n+\n+  /** Get the state for a key if it exists */\n+  def get(key: K): Option[S]\n+\n+  /** Get all the keys and states whose updated time is older than the given threshold time */\n+  def getByTime(threshUpdatedTime: Long): Iterator[(K, S, Long)]\n+\n+  /** Get all the keys and states in this map. */\n+  def getAll(): Iterator[(K, S, Long)]\n+\n+  /** Add or update state */\n+  def put(key: K, state: S, updatedTime: Long): Unit\n+\n+  /** Remove a key */\n+  def remove(key: K): Unit\n+\n+  /**\n+   * Shallow copy `this` map to create a new state map.\n+   * Updates to the new map should not mutate `this` map.\n+   */\n+  def copy(): StateMap[K, S]\n+\n+  def toDebugString(): String = toString()\n+}\n+\n+/** Companion object for [[StateMap]], with utility methods */\n+private[streaming] object StateMap {\n+  def empty[K: ClassTag, S: ClassTag]: StateMap[K, S] = new EmptyStateMap[K, S]\n+\n+  def create[K: ClassTag, S: ClassTag](conf: SparkConf): StateMap[K, S] = {\n+    val deltaChainThreshold = conf.getInt(\"spark.streaming.sessionByKey.deltaChainThreshold\",\n+      DELTA_CHAIN_LENGTH_THRESHOLD)\n+    new OpenHashMapBasedStateMap[K, S](64, deltaChainThreshold)\n+  }\n+}\n+\n+/** Specific implementation of SessionStore interface representing an empty map */\n+private[streaming] class EmptyStateMap[K: ClassTag, S: ClassTag] extends StateMap[K, S] {\n+  override def put(key: K, session: S, updateTime: Long): Unit = {\n+    throw new NotImplementedError(\"put() should not be called on an EmptyStateMap\")\n+  }\n+  override def get(key: K): Option[S] = None\n+  override def getByTime(threshUpdatedTime: Long): Iterator[(K, S, Long)] = Iterator.empty\n+  override def getAll(): Iterator[(K, S, Long)] = Iterator.empty\n+  override def copy(): StateMap[K, S] = new EmptyStateMap[K, S]\n+  override def remove(key: K): Unit = { }\n+  override def toDebugString(): String = \"\"\n+}\n+\n+\n+\n+/** Implementation of StateMap based on Spark's OpenHashMap */\n+private[streaming] class OpenHashMapBasedStateMap[K: ClassTag, S: ClassTag](\n+    @transient @volatile var parentStateMap: StateMap[K, S],\n+    initialCapacity: Int = 64,\n+    deltaChainThreshold: Int = DELTA_CHAIN_LENGTH_THRESHOLD\n+  ) extends StateMap[K, S] { self =>\n+\n+  def this(initialCapacity: Int, deltaChainThreshold: Int) = this(\n+    new EmptyStateMap[K, S],\n+    initialCapacity = initialCapacity,\n+    deltaChainThreshold = deltaChainThreshold)\n+\n+  def this(deltaChainThreshold: Int) = this(\n+    initialCapacity = 64, deltaChainThreshold = deltaChainThreshold)\n+\n+  def this() = this(DELTA_CHAIN_LENGTH_THRESHOLD)\n+\n+  @transient @volatile private var deltaMap =\n+    new OpenHashMap[K, StateInfo[S]](initialCapacity)\n+\n+  /** Get the session data if it exists */\n+  override def get(key: K): Option[S] = {\n+    val stateInfo = deltaMap(key)\n+    if (stateInfo != null) {\n+      if (!stateInfo.deleted) {\n+        Some(stateInfo.data)\n+      } else {\n+        None\n+      }\n+    } else {\n+      parentStateMap.get(key)\n+    }\n+  }\n+\n+  /** Get all the keys and states whose updated time is older than the give threshold time */\n+  override def getByTime(threshUpdatedTime: Long): Iterator[(K, S, Long)] = {\n+    val oldStates = parentStateMap.getByTime(threshUpdatedTime).filter { case (key, value, _) =>\n+      !deltaMap.contains(key)\n+    }\n+\n+    val updatedStates = deltaMap.iterator.flatMap { case (key, stateInfo) =>","path":"streaming/src/main/scala/org/apache/spark/streaming/util/StateMap.scala","position":121,"original_position":121,"commit_id":"0f1b1bc9d71921b8a526bbf88994b6585861f0ec","original_commit_id":"0f1b1bc9d71921b8a526bbf88994b6585861f0ec","user":{"login":"zsxwing","id":1000778,"avatar_url":"https://avatars.githubusercontent.com/u/1000778?v=3","gravatar_id":"","url":"https://api.github.com/users/zsxwing","html_url":"https://github.com/zsxwing","followers_url":"https://api.github.com/users/zsxwing/followers","following_url":"https://api.github.com/users/zsxwing/following{/other_user}","gists_url":"https://api.github.com/users/zsxwing/gists{/gist_id}","starred_url":"https://api.github.com/users/zsxwing/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/zsxwing/subscriptions","organizations_url":"https://api.github.com/users/zsxwing/orgs","repos_url":"https://api.github.com/users/zsxwing/repos","events_url":"https://api.github.com/users/zsxwing/events{/privacy}","received_events_url":"https://api.github.com/users/zsxwing/received_events","type":"User","site_admin":false},"body":"How about replace `flatMap` with `filter + map`?","created_at":"2015-11-06T02:02:01Z","updated_at":"2015-11-06T02:02:01Z","html_url":"https://github.com/apache/spark/pull/9256#discussion_r44096254","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/9256","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/44096254"},"html":{"href":"https://github.com/apache/spark/pull/9256#discussion_r44096254"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/9256"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/9256","id":48637322,"html_url":"https://github.com/apache/spark/pull/9256","diff_url":"https://github.com/apache/spark/pull/9256.diff","patch_url":"https://github.com/apache/spark/pull/9256.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/9256","number":9256,"state":"open","locked":false,"title":"[SPARK-2629][STREAMING] Basic implementation of trackStateByKey [WIP]","user":{"login":"tdas","id":663212,"avatar_url":"https://avatars.githubusercontent.com/u/663212?v=3","gravatar_id":"","url":"https://api.github.com/users/tdas","html_url":"https://github.com/tdas","followers_url":"https://api.github.com/users/tdas/followers","following_url":"https://api.github.com/users/tdas/following{/other_user}","gists_url":"https://api.github.com/users/tdas/gists{/gist_id}","starred_url":"https://api.github.com/users/tdas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tdas/subscriptions","organizations_url":"https://api.github.com/users/tdas/orgs","repos_url":"https://api.github.com/users/tdas/repos","events_url":"https://api.github.com/users/tdas/events{/privacy}","received_events_url":"https://api.github.com/users/tdas/received_events","type":"User","site_admin":false},"body":"Current updateStateByKey provides stateful processing in Spark Streaming. It allows the user to maintain per-key state and manage that state using an updateFunction. The updateFunction is called for each key, and it uses new data and existing state of the key, to generate an updated state. However, based on community feedback, we have learnt the following lessons.\r\n* Need for more optimized state management that does not scan every key\r\n* Need to make it easier to implement common use cases - (a) timeout of idle data, (b) returning items other than state\r\n\r\nThe high level idea that of this PR\r\n* Introduce a new API trackStateByKey that, allows the user to update per-key state, and emit arbitrary records. The new API is necessary as this will have significantly different semantics than the existing updateStateByKey API. This API will have direct support for timeouts.\r\n* Internally, the system will keep the state data as a map/list within the partitions of the state RDDs. The new data RDDs will be partitioned appropriately, and for all the key-value data, it will lookup the map/list in the state RDD partition and create a new list/map of updated state data. The new state RDD partition will be created based on the update data and if necessary, with old data.\r\nHere is the detailed design doc. Please take a look and provide feedback as comments.\r\nhttps://docs.google.com/document/d/1NoALLyd83zGs1hNGMm0Pc5YOVgiPpMHugGMk6COqxxE/edit#heading=h.ph3w0clkd4em\r\n\r\nThis is still WIP. Major things left to be done. \r\n- [x] Implement basic functionality of state tracking, with initial RDD and timeouts\r\n- [x] Unit tests for state tracking\r\n- [x] Unit tests for initial RDD and timeout\r\n- [ ] Unit tests for TrackStateRDD\r\n       - [x] state creating, updating, removing\r\n       - [ ] emitting\r\n       - [ ] checkpointing\r\n- [ ] Misc unit tests for State, TrackStateSpec, etc.\r\n- [ ] Update docs and experimental tags","created_at":"2015-10-23T22:30:04Z","updated_at":"2015-11-06T02:02:02Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0a72577e33caa05b8fbedf2b5ec4a5b3f8d28775","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/9256/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/9256/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/9256/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/0f1b1bc9d71921b8a526bbf88994b6585861f0ec","head":{"label":"tdas:trackStateByKey","ref":"trackStateByKey","sha":"0f1b1bc9d71921b8a526bbf88994b6585861f0ec","user":{"login":"tdas","id":663212,"avatar_url":"https://avatars.githubusercontent.com/u/663212?v=3","gravatar_id":"","url":"https://api.github.com/users/tdas","html_url":"https://github.com/tdas","followers_url":"https://api.github.com/users/tdas/followers","following_url":"https://api.github.com/users/tdas/following{/other_user}","gists_url":"https://api.github.com/users/tdas/gists{/gist_id}","starred_url":"https://api.github.com/users/tdas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tdas/subscriptions","organizations_url":"https://api.github.com/users/tdas/orgs","repos_url":"https://api.github.com/users/tdas/repos","events_url":"https://api.github.com/users/tdas/events{/privacy}","received_events_url":"https://api.github.com/users/tdas/received_events","type":"User","site_admin":false},"repo":{"id":17603343,"name":"spark","full_name":"tdas/spark","owner":{"login":"tdas","id":663212,"avatar_url":"https://avatars.githubusercontent.com/u/663212?v=3","gravatar_id":"","url":"https://api.github.com/users/tdas","html_url":"https://github.com/tdas","followers_url":"https://api.github.com/users/tdas/followers","following_url":"https://api.github.com/users/tdas/following{/other_user}","gists_url":"https://api.github.com/users/tdas/gists{/gist_id}","starred_url":"https://api.github.com/users/tdas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tdas/subscriptions","organizations_url":"https://api.github.com/users/tdas/orgs","repos_url":"https://api.github.com/users/tdas/repos","events_url":"https://api.github.com/users/tdas/events{/privacy}","received_events_url":"https://api.github.com/users/tdas/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/tdas/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/tdas/spark","forks_url":"https://api.github.com/repos/tdas/spark/forks","keys_url":"https://api.github.com/repos/tdas/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/tdas/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/tdas/spark/teams","hooks_url":"https://api.github.com/repos/tdas/spark/hooks","issue_events_url":"https://api.github.com/repos/tdas/spark/issues/events{/number}","events_url":"https://api.github.com/repos/tdas/spark/events","assignees_url":"https://api.github.com/repos/tdas/spark/assignees{/user}","branches_url":"https://api.github.com/repos/tdas/spark/branches{/branch}","tags_url":"https://api.github.com/repos/tdas/spark/tags","blobs_url":"https://api.github.com/repos/tdas/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/tdas/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/tdas/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/tdas/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/tdas/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/tdas/spark/languages","stargazers_url":"https://api.github.com/repos/tdas/spark/stargazers","contributors_url":"https://api.github.com/repos/tdas/spark/contributors","subscribers_url":"https://api.github.com/repos/tdas/spark/subscribers","subscription_url":"https://api.github.com/repos/tdas/spark/subscription","commits_url":"https://api.github.com/repos/tdas/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/tdas/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/tdas/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/tdas/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/tdas/spark/contents/{+path}","compare_url":"https://api.github.com/repos/tdas/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/tdas/spark/merges","archive_url":"https://api.github.com/repos/tdas/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/tdas/spark/downloads","issues_url":"https://api.github.com/repos/tdas/spark/issues{/number}","pulls_url":"https://api.github.com/repos/tdas/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/tdas/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/tdas/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/tdas/spark/labels{/name}","releases_url":"https://api.github.com/repos/tdas/spark/releases{/id}","created_at":"2014-03-10T18:19:48Z","updated_at":"2015-04-24T21:16:02Z","pushed_at":"2015-11-03T10:40:00Z","git_url":"git://github.com/tdas/spark.git","ssh_url":"git@github.com:tdas/spark.git","clone_url":"https://github.com/tdas/spark.git","svn_url":"https://github.com/tdas/spark","homepage":null,"size":126884,"stargazers_count":1,"watchers_count":1,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":2,"mirror_url":null,"open_issues_count":3,"forks":2,"open_issues":3,"watchers":1,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"e1a897b657eb62e837026f7b3efafb9a6424ec4f","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","created_at":"2014-02-25T08:00:08Z","updated_at":"2015-11-06T01:35:54Z","pushed_at":"2015-11-06T01:59:36Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":1649934,"stargazers_count":6036,"watchers_count":6036,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":5617,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":370,"forks":5617,"open_issues":370,"watchers":6036,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/9256"},"html":{"href":"https://github.com/apache/spark/pull/9256"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/9256"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/9256/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/9256/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/9256/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/0f1b1bc9d71921b8a526bbf88994b6585861f0ec"}}}}