{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/28033500","id":28033500,"diff_hunk":"@@ -529,6 +522,322 @@ def sorted(self, iterator, key=None, reverse=False):\n         return heapq.merge(chunks, key=key, reverse=reverse)\n \n \n+class ExternalList(object):\n+    \"\"\"\n+    ExternalList can have many items which cannot be hold in memory in\n+    the same time.\n+\n+    >>> l = ExternalList(range(100))\n+    >>> len(l)\n+    100\n+    >>> l.append(10)\n+    >>> len(l)\n+    101\n+    >>> for i in range(10240):\n+    ...     l.append(i)\n+    >>> len(l)\n+    10341\n+    >>> import pickle\n+    >>> l2 = pickle.loads(pickle.dumps(l))\n+    >>> len(l2)\n+    10341\n+    >>> list(l2)[100]\n+    10\n+    \"\"\"\n+    LIMIT = 10240\n+\n+    def __init__(self, values):\n+        self.values = values\n+        self.count = len(values)\n+        self._file = None\n+        self._ser = None\n+\n+    def __getstate__(self):\n+        if self._file is not None:\n+            self._file.flush()\n+            f = os.fdopen(os.dup(self._file.fileno()))\n+            f.seek(0)\n+            serialized = f.read()\n+        else:\n+            serialized = ''\n+        return self.values, self.count, serialized\n+\n+    def __setstate__(self, item):\n+        self.values, self.count, serialized = item\n+        if serialized:\n+            self._open_file()\n+            self._file.write(serialized)\n+        else:\n+            self._file = None\n+            self._ser = None\n+\n+    def __iter__(self):\n+        if self._file is not None:\n+            self._file.flush()\n+            # read all items from disks first\n+            with os.fdopen(os.dup(self._file.fileno()), 'r') as f:\n+                f.seek(0)\n+                for values in self._ser.load_stream(f):\n+                    for v in values:\n+                        yield v\n+\n+        for v in self.values:\n+            yield v\n+\n+    def __len__(self):\n+        return self.count\n+\n+    def append(self, value):\n+        self.values.append(value)\n+        self.count += 1\n+        # dump them into disk if the key is huge\n+        if len(self.values) >= self.LIMIT:\n+            self._spill()\n+\n+    def _open_file(self):\n+        dirs = _get_local_dirs(\"objects\")\n+        d = dirs[id(self) % len(dirs)]\n+        if not os.path.exists(d):\n+            os.makedirs(d)\n+        p = os.path.join(d, str(id))\n+        self._file = open(p, \"w+\", 65536)\n+        self._ser = CompressedSerializer(PickleSerializer())\n+        os.unlink(p)\n+\n+    def _spill(self):\n+        \"\"\" dump the values into disk \"\"\"\n+        global MemoryBytesSpilled, DiskBytesSpilled\n+        if self._file is None:\n+            self._open_file()\n+\n+        used_memory = get_used_memory()\n+        pos = self._file.tell()\n+        self._ser.dump_stream([self.values], self._file)\n+        self.values = []\n+        gc.collect()\n+        DiskBytesSpilled += self._file.tell() - pos\n+        MemoryBytesSpilled += (used_memory - get_used_memory()) << 20\n+\n+\n+class ExternalListOfList(ExternalList):\n+    \"\"\"\n+    An external list for list.\n+    \"\"\"\n+    def __init__(self, values):\n+        ExternalList.__init__(self, values)\n+        self.count = sum(len(i) for i in values)\n+\n+    def append(self, value):\n+        ExternalList.append(self, value)","path":"python/pyspark/shuffle.py","position":528,"original_position":519,"commit_id":"e78c15c41ff0c1cf393bb6e65eb513ebd8357c75","original_commit_id":"0b0fde8b568141b03d7ba8b7d74e5b885dcb4557","user":{"login":"davies","id":40902,"avatar_url":"https://avatars.githubusercontent.com/u/40902?v=3","gravatar_id":"","url":"https://api.github.com/users/davies","html_url":"https://github.com/davies","followers_url":"https://api.github.com/users/davies/followers","following_url":"https://api.github.com/users/davies/following{/other_user}","gists_url":"https://api.github.com/users/davies/gists{/gist_id}","starred_url":"https://api.github.com/users/davies/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davies/subscriptions","organizations_url":"https://api.github.com/users/davies/orgs","repos_url":"https://api.github.com/users/davies/repos","events_url":"https://api.github.com/users/davies/events{/privacy}","received_events_url":"https://api.github.com/users/davies/received_events","type":"User","site_admin":false},"body":"done","created_at":"2015-04-09T03:44:51Z","updated_at":"2015-04-09T03:44:51Z","html_url":"https://github.com/apache/spark/pull/1977#discussion_r28033500","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/1977","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/28033500"},"html":{"href":"https://github.com/apache/spark/pull/1977#discussion_r28033500"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/1977"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/1977","id":19874520,"html_url":"https://github.com/apache/spark/pull/1977","diff_url":"https://github.com/apache/spark/pull/1977.diff","patch_url":"https://github.com/apache/spark/pull/1977.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/1977","number":1977,"state":"open","locked":false,"title":"[SPARK-3074] [PySpark] support groupByKey() with single huge key","user":{"login":"davies","id":40902,"avatar_url":"https://avatars.githubusercontent.com/u/40902?v=3","gravatar_id":"","url":"https://api.github.com/users/davies","html_url":"https://github.com/davies","followers_url":"https://api.github.com/users/davies/followers","following_url":"https://api.github.com/users/davies/following{/other_user}","gists_url":"https://api.github.com/users/davies/gists{/gist_id}","starred_url":"https://api.github.com/users/davies/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davies/subscriptions","organizations_url":"https://api.github.com/users/davies/orgs","repos_url":"https://api.github.com/users/davies/repos","events_url":"https://api.github.com/users/davies/events{/privacy}","received_events_url":"https://api.github.com/users/davies/received_events","type":"User","site_admin":false},"body":"This patch change groupByKey() to use external sort based approach, so it can support single huge key.\r\n\r\nFor example, it can group by a dataset including one hot key with 40 millions values (strings), using 500M memory for Python worker, finished in about 2 minutes. (it will need 6G memory in hash based approach).\r\n\r\nDuring groupByKey(), it will do in-memory groupBy first. If the dataset can not fit in memory, then data will be partitioned by hash. If one partition still can not fit in memory, it will switch to sort based groupBy(). ","created_at":"2014-08-16T00:32:33Z","updated_at":"2015-04-09T03:44:51Z","closed_at":null,"merged_at":null,"merge_commit_sha":"025a71f89ccea5c66b0cd2b3b5e17fd4ab091a8f","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/1977/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/1977/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/1977/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/e78c15c41ff0c1cf393bb6e65eb513ebd8357c75","head":{"label":"davies:groupby","ref":"groupby","sha":"e78c15c41ff0c1cf393bb6e65eb513ebd8357c75","user":{"login":"davies","id":40902,"avatar_url":"https://avatars.githubusercontent.com/u/40902?v=3","gravatar_id":"","url":"https://api.github.com/users/davies","html_url":"https://github.com/davies","followers_url":"https://api.github.com/users/davies/followers","following_url":"https://api.github.com/users/davies/following{/other_user}","gists_url":"https://api.github.com/users/davies/gists{/gist_id}","starred_url":"https://api.github.com/users/davies/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davies/subscriptions","organizations_url":"https://api.github.com/users/davies/orgs","repos_url":"https://api.github.com/users/davies/repos","events_url":"https://api.github.com/users/davies/events{/privacy}","received_events_url":"https://api.github.com/users/davies/received_events","type":"User","site_admin":false},"repo":{"id":21724875,"name":"spark","full_name":"davies/spark","owner":{"login":"davies","id":40902,"avatar_url":"https://avatars.githubusercontent.com/u/40902?v=3","gravatar_id":"","url":"https://api.github.com/users/davies","html_url":"https://github.com/davies","followers_url":"https://api.github.com/users/davies/followers","following_url":"https://api.github.com/users/davies/following{/other_user}","gists_url":"https://api.github.com/users/davies/gists{/gist_id}","starred_url":"https://api.github.com/users/davies/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davies/subscriptions","organizations_url":"https://api.github.com/users/davies/orgs","repos_url":"https://api.github.com/users/davies/repos","events_url":"https://api.github.com/users/davies/events{/privacy}","received_events_url":"https://api.github.com/users/davies/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/davies/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/davies/spark","forks_url":"https://api.github.com/repos/davies/spark/forks","keys_url":"https://api.github.com/repos/davies/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/davies/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/davies/spark/teams","hooks_url":"https://api.github.com/repos/davies/spark/hooks","issue_events_url":"https://api.github.com/repos/davies/spark/issues/events{/number}","events_url":"https://api.github.com/repos/davies/spark/events","assignees_url":"https://api.github.com/repos/davies/spark/assignees{/user}","branches_url":"https://api.github.com/repos/davies/spark/branches{/branch}","tags_url":"https://api.github.com/repos/davies/spark/tags","blobs_url":"https://api.github.com/repos/davies/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/davies/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/davies/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/davies/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/davies/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/davies/spark/languages","stargazers_url":"https://api.github.com/repos/davies/spark/stargazers","contributors_url":"https://api.github.com/repos/davies/spark/contributors","subscribers_url":"https://api.github.com/repos/davies/spark/subscribers","subscription_url":"https://api.github.com/repos/davies/spark/subscription","commits_url":"https://api.github.com/repos/davies/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/davies/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/davies/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/davies/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/davies/spark/contents/{+path}","compare_url":"https://api.github.com/repos/davies/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/davies/spark/merges","archive_url":"https://api.github.com/repos/davies/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/davies/spark/downloads","issues_url":"https://api.github.com/repos/davies/spark/issues{/number}","pulls_url":"https://api.github.com/repos/davies/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/davies/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/davies/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/davies/spark/labels{/name}","releases_url":"https://api.github.com/repos/davies/spark/releases{/id}","created_at":"2014-07-11T06:39:41Z","updated_at":"2015-04-08T19:45:01Z","pushed_at":"2015-04-09T03:44:10Z","git_url":"git://github.com/davies/spark.git","ssh_url":"git@github.com:davies/spark.git","clone_url":"https://github.com/davies/spark.git","svn_url":"https://github.com/davies/spark","homepage":null,"size":104542,"stargazers_count":1,"watchers_count":1,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":1,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"e40ea8742a8771ecd46b182f45b5fcd8bd6dd725","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-04-09T03:35:47Z","pushed_at":"2015-04-09T03:44:12Z","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":1487084,"stargazers_count":3534,"watchers_count":3534,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":3054,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":327,"forks":3054,"open_issues":327,"watchers":3534,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/1977"},"html":{"href":"https://github.com/apache/spark/pull/1977"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/1977"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/1977/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/1977/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/1977/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/e78c15c41ff0c1cf393bb6e65eb513ebd8357c75"}}}}